diff options
author | Christian Grothoff <christian@grothoff.org> | 2013-05-05 18:07:33 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2013-05-05 18:07:33 +0000 |
commit | 9eb27c8dbe1939344ccced9c498895f0e92e8197 (patch) | |
tree | a97d1b7caf1e5dc79c22b08d58be70bc8c205cba /src/microhttpd/tsearch.c | |
parent | 1725bcf3c546fccbf22d7794bf7290fcc28c385d (diff) | |
download | libmicrohttpd-9eb27c8dbe1939344ccced9c498895f0e92e8197.tar.gz libmicrohttpd-9eb27c8dbe1939344ccced9c498895f0e92e8197.zip |
-changing directory name
Diffstat (limited to 'src/microhttpd/tsearch.c')
-rw-r--r-- | src/microhttpd/tsearch.c | 123 |
1 files changed, 123 insertions, 0 deletions
diff --git a/src/microhttpd/tsearch.c b/src/microhttpd/tsearch.c new file mode 100644 index 00000000..2ab9a467 --- /dev/null +++ b/src/microhttpd/tsearch.c | |||
@@ -0,0 +1,123 @@ | |||
1 | /* $NetBSD: tsearch.c,v 1.3 1999/09/16 11:45:37 lukem Exp $ */ | ||
2 | |||
3 | /* | ||
4 | * Tree search generalized from Knuth (6.2.2) Algorithm T just like | ||
5 | * the AT&T man page says. | ||
6 | * | ||
7 | * The node_t structure is for internal use only, lint doesn't grok it. | ||
8 | * | ||
9 | * Written by reading the System V Interface Definition, not the code. | ||
10 | * | ||
11 | * Totally public domain. | ||
12 | */ | ||
13 | |||
14 | #include <sys/cdefs.h> | ||
15 | #define _SEARCH_PRIVATE | ||
16 | #include <tsearch.h> | ||
17 | #include <stdlib.h> | ||
18 | |||
19 | /* find or insert datum into search tree */ | ||
20 | void * | ||
21 | tsearch(vkey, vrootp, compar) | ||
22 | const void *vkey; /* key to be located */ | ||
23 | void **vrootp; /* address of tree root */ | ||
24 | int (*compar)(const void *, const void *); | ||
25 | { | ||
26 | node_t *q; | ||
27 | node_t **rootp = (node_t **)vrootp; | ||
28 | |||
29 | if (rootp == NULL) | ||
30 | return NULL; | ||
31 | |||
32 | while (*rootp != NULL) { /* Knuth's T1: */ | ||
33 | int r; | ||
34 | |||
35 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ | ||
36 | return *rootp; /* we found it! */ | ||
37 | |||
38 | rootp = (r < 0) ? | ||
39 | &(*rootp)->llink : /* T3: follow left branch */ | ||
40 | &(*rootp)->rlink; /* T4: follow right branch */ | ||
41 | } | ||
42 | |||
43 | q = malloc(sizeof(node_t)); /* T5: key not found */ | ||
44 | if (q != 0) { /* make new node */ | ||
45 | *rootp = q; /* link new node to old */ | ||
46 | /* LINTED const castaway ok */ | ||
47 | q->key = (void *)vkey; /* initialize new node */ | ||
48 | q->llink = q->rlink = NULL; | ||
49 | } | ||
50 | return q; | ||
51 | } | ||
52 | |||
53 | /* find a node, or return 0 */ | ||
54 | void * | ||
55 | tfind(vkey, vrootp, compar) | ||
56 | const void *vkey; /* key to be found */ | ||
57 | void * const *vrootp; /* address of the tree root */ | ||
58 | int (*compar)(const void *, const void *); | ||
59 | { | ||
60 | node_t **rootp = (node_t **)vrootp; | ||
61 | |||
62 | if (rootp == NULL) | ||
63 | return NULL; | ||
64 | |||
65 | while (*rootp != NULL) { /* T1: */ | ||
66 | int r; | ||
67 | |||
68 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ | ||
69 | return *rootp; /* key found */ | ||
70 | rootp = (r < 0) ? | ||
71 | &(*rootp)->llink : /* T3: follow left branch */ | ||
72 | &(*rootp)->rlink; /* T4: follow right branch */ | ||
73 | } | ||
74 | return NULL; | ||
75 | } | ||
76 | |||
77 | /* | ||
78 | * delete node with given key | ||
79 | * | ||
80 | * vkey: key to be deleted | ||
81 | * vrootp: address of the root of the tree | ||
82 | * compar: function to carry out node comparisons | ||
83 | */ | ||
84 | void * | ||
85 | tdelete(const void * __restrict vkey, void ** __restrict vrootp, | ||
86 | int (*compar)(const void *, const void *)) | ||
87 | { | ||
88 | node_t **rootp = (node_t **)vrootp; | ||
89 | node_t *p, *q, *r; | ||
90 | int cmp; | ||
91 | |||
92 | if (rootp == NULL || (p = *rootp) == NULL) | ||
93 | return NULL; | ||
94 | |||
95 | while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) { | ||
96 | p = *rootp; | ||
97 | rootp = (cmp < 0) ? | ||
98 | &(*rootp)->llink : /* follow llink branch */ | ||
99 | &(*rootp)->rlink; /* follow rlink branch */ | ||
100 | if (*rootp == NULL) | ||
101 | return NULL; /* key not found */ | ||
102 | } | ||
103 | r = (*rootp)->rlink; /* D1: */ | ||
104 | if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ | ||
105 | q = r; | ||
106 | else if (r != NULL) { /* Right link is NULL? */ | ||
107 | if (r->llink == NULL) { /* D2: Find successor */ | ||
108 | r->llink = q; | ||
109 | q = r; | ||
110 | } else { /* D3: Find NULL link */ | ||
111 | for (q = r->llink; q->llink != NULL; q = r->llink) | ||
112 | r = q; | ||
113 | r->llink = q->rlink; | ||
114 | q->llink = (*rootp)->llink; | ||
115 | q->rlink = (*rootp)->rlink; | ||
116 | } | ||
117 | } | ||
118 | free(*rootp); /* D4: Free node */ | ||
119 | *rootp = q; /* link parent to new node */ | ||
120 | return p; | ||
121 | } | ||
122 | |||
123 | /* end of tsearch.c */ | ||