diff options
-rw-r--r-- | src/microhttpd/tsearch.c | 86 | ||||
-rw-r--r-- | src/microhttpd/tsearch.h | 31 |
2 files changed, 47 insertions, 70 deletions
diff --git a/src/microhttpd/tsearch.c b/src/microhttpd/tsearch.c index ba550b7d..af373fc3 100644 --- a/src/microhttpd/tsearch.c +++ b/src/microhttpd/tsearch.c | |||
@@ -21,119 +21,105 @@ | |||
21 | 21 | ||
22 | typedef struct node | 22 | typedef struct node |
23 | { | 23 | { |
24 | const void *key; | 24 | const void *key; |
25 | struct node *llink; | 25 | struct node *llink, *rlink; |
26 | struct node *rlink; | ||
27 | } node_t; | 26 | } node_t; |
28 | 27 | ||
29 | 28 | ||
30 | /* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */ | 29 | /* $NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */ |
31 | /* find or insert datum into search tree */ | 30 | /* find or insert datum into search tree */ |
32 | void * | 31 | void * |
33 | tsearch (const void *vkey, /* key to be located */ | 32 | tsearch (const void *vkey, void **vrootp, |
34 | void **vrootp, /* address of tree root */ | ||
35 | int (*compar)(const void *, const void *)) | 33 | int (*compar)(const void *, const void *)) |
36 | { | 34 | { |
37 | node_t *q; | 35 | node_t *q; |
38 | node_t **rootp = (node_t **) vrootp; | 36 | node_t **rootp = (node_t **) vrootp; |
39 | 37 | ||
40 | if (NULL == rootp) | 38 | if (rootp == NULL) |
41 | return NULL; | 39 | return NULL; |
42 | 40 | ||
43 | while (*rootp != NULL) | 41 | while (*rootp != NULL) /* Knuth's T1: */ |
44 | { /* Knuth's T1: */ | 42 | { |
45 | int r; | 43 | int r; |
46 | 44 | ||
47 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ | 45 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ |
48 | return *rootp; /* we found it! */ | 46 | return *rootp; /* we found it! */ |
49 | 47 | ||
50 | rootp = (r < 0) ? | 48 | rootp = (r < 0) ? |
51 | &(*rootp)->llink : /* T3: follow left branch */ | 49 | &(*rootp)->llink : /* T3: follow left branch */ |
52 | &(*rootp)->rlink; /* T4: follow right branch */ | 50 | &(*rootp)->rlink; /* T4: follow right branch */ |
53 | } | 51 | } |
54 | 52 | ||
55 | q = malloc (sizeof(node_t)); /* T5: key not found */ | 53 | q = malloc (sizeof(node_t)); /* T5: key not found */ |
56 | if (q) | 54 | if (q != NULL) /* make new node */ |
57 | { /* make new node */ | 55 | { |
58 | *rootp = q; /* link new node to old */ | 56 | *rootp = q; /* link new node to old */ |
59 | q->key = vkey; /* initialize new node */ | 57 | q->key = vkey; /* initialize new node */ |
60 | q->llink = q->rlink = NULL; | 58 | q->llink = q->rlink = NULL; |
61 | } | 59 | } |
62 | return q; | 60 | return q; |
63 | } | 61 | } |
64 | 62 | ||
65 | 63 | ||
66 | /* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */ | 64 | /* $NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */ |
67 | /* find a node, or return NULL */ | 65 | /* find a node by key "vkey" in tree "vrootp", or return 0 */ |
68 | void * | 66 | void * |
69 | tfind (const void *vkey, /* key to be found */ | 67 | tfind (const void *vkey, void * const *vrootp, |
70 | void *const *vrootp, /* address of the tree root */ | ||
71 | int (*compar)(const void *, const void *)) | 68 | int (*compar)(const void *, const void *)) |
72 | { | 69 | { |
73 | node_t *const *rootp = (node_t *const*) vrootp; | 70 | node_t * const *rootp = (node_t * const *) vrootp; |
74 | 71 | ||
75 | if (NULL == rootp) | 72 | if (rootp == NULL) |
76 | return NULL; | 73 | return NULL; |
77 | 74 | ||
78 | while (*rootp != NULL) | 75 | while (*rootp != NULL) /* T1: */ |
79 | { /* T1: */ | 76 | { |
80 | int r; | 77 | int r; |
81 | 78 | ||
82 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ | 79 | if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ |
83 | return *rootp; /* key found */ | 80 | return *rootp; /* key found */ |
84 | rootp = (r < 0) ? | 81 | rootp = (r < 0) ? |
85 | &(*rootp)->llink : /* T3: follow left branch */ | 82 | &(*rootp)->llink : /* T3: follow left branch */ |
86 | &(*rootp)->rlink; /* T4: follow right branch */ | 83 | &(*rootp)->rlink; /* T4: follow right branch */ |
87 | } | 84 | } |
88 | return NULL; | 85 | return NULL; |
89 | } | 86 | } |
90 | 87 | ||
91 | 88 | ||
92 | /* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */ | 89 | /* $NetBSD: tdelete.c,v 1.8 2016/01/20 20:47:41 christos Exp $ */ |
93 | /* | 90 | /* find a node with key "vkey" in tree "vrootp" */ |
94 | * delete node with given key | ||
95 | * | ||
96 | * vkey: key to be deleted | ||
97 | * vrootp: address of the root of the tree | ||
98 | * compar: function to carry out node comparisons | ||
99 | */ | ||
100 | void * | 91 | void * |
101 | tdelete (const void *__restrict vkey, | 92 | tdelete (const void *vkey, void **vrootp, |
102 | void **__restrict vrootp, | ||
103 | int (*compar)(const void *, const void *)) | 93 | int (*compar)(const void *, const void *)) |
104 | { | 94 | { |
105 | node_t **rootp = (node_t **) vrootp; | 95 | node_t **rootp = (node_t **) vrootp; |
106 | node_t *p; | 96 | node_t *p, *q, *r; |
107 | node_t *q; | ||
108 | node_t *r; | ||
109 | int cmp; | 97 | int cmp; |
110 | 98 | ||
111 | if ((rootp == NULL) || ((p = *rootp) == NULL)) | 99 | if ((rootp == NULL) || ((p = *rootp) == NULL) ) |
112 | return NULL; | 100 | return NULL; |
113 | 101 | ||
114 | while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) | 102 | while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0) |
115 | { | 103 | { |
116 | p = *rootp; | 104 | p = *rootp; |
117 | rootp = (cmp < 0) ? | 105 | rootp = (cmp < 0) ? |
118 | &(*rootp)->llink : /* follow llink branch */ | 106 | &(*rootp)->llink : /* follow llink branch */ |
119 | &(*rootp)->rlink; /* follow rlink branch */ | 107 | &(*rootp)->rlink; /* follow rlink branch */ |
120 | if (*rootp == NULL) | 108 | if (*rootp == NULL) |
121 | return NULL; /* key not found */ | 109 | return NULL; /* key not found */ |
122 | } | 110 | } |
123 | r = (*rootp)->rlink; /* D1: */ | 111 | r = (*rootp)->rlink; /* D1: */ |
124 | if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ | 112 | if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ |
125 | { | ||
126 | q = r; | 113 | q = r; |
127 | } | 114 | else if (r != NULL) /* Right link is NULL? */ |
128 | else if (r != NULL) | 115 | { |
129 | { /* Right link is NULL? */ | 116 | if (r->llink == NULL) /* D2: Find successor */ |
130 | if (r->llink == NULL) | 117 | { |
131 | { /* D2: Find successor */ | ||
132 | r->llink = q; | 118 | r->llink = q; |
133 | q = r; | 119 | q = r; |
134 | } | 120 | } |
135 | else | 121 | else /* D3: Find NULL link */ |
136 | { /* D3: Find NULL link */ | 122 | { |
137 | for (q = r->llink; q->llink != NULL; q = r->llink) | 123 | for (q = r->llink; q->llink != NULL; q = r->llink) |
138 | r = q; | 124 | r = q; |
139 | r->llink = q->rlink; | 125 | r->llink = q->rlink; |
@@ -141,8 +127,8 @@ tdelete (const void *__restrict vkey, | |||
141 | q->rlink = (*rootp)->rlink; | 127 | q->rlink = (*rootp)->rlink; |
142 | } | 128 | } |
143 | } | 129 | } |
144 | free (*rootp); /* D4: Free node */ | 130 | free (*rootp); /* D4: Free node */ |
145 | *rootp = q; /* link parent to new node */ | 131 | *rootp = q; /* link parent to new node */ |
146 | return p; | 132 | return p; |
147 | } | 133 | } |
148 | 134 | ||
diff --git a/src/microhttpd/tsearch.h b/src/microhttpd/tsearch.h index 0cfe16a7..c6d873b4 100644 --- a/src/microhttpd/tsearch.h +++ b/src/microhttpd/tsearch.h | |||
@@ -3,36 +3,27 @@ | |||
3 | * Public domain. | 3 | * Public domain. |
4 | * | 4 | * |
5 | * $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ | 5 | * $NetBSD: search.h,v 1.12 1999/02/22 10:34:28 christos Exp $ |
6 | * $FreeBSD: release/9.0.0/include/search.h 105250 2002-10-16 14:29:23Z robert $ | ||
7 | */ | 6 | */ |
8 | 7 | ||
9 | #ifndef _TSEARCH_H_ | 8 | #ifndef _TSEARCH_H_ |
10 | #define _TSEARCH_H_ | 9 | #define _TSEARCH_H_ |
11 | 10 | ||
12 | #if defined(__cplusplus) | 11 | #ifdef __cplusplus |
13 | extern "C" { | 12 | extern "C" |
13 | { | ||
14 | #endif /* __cplusplus */ | 14 | #endif /* __cplusplus */ |
15 | 15 | ||
16 | void *tdelete (const void *, void **, | ||
17 | int (*)(const void *, const void *)); | ||
16 | 18 | ||
17 | void * | 19 | void *tfind (const void *, void * const *, |
18 | tdelete (const void *__restrict, | 20 | int (*)(const void *, const void *)); |
19 | void **__restrict, | ||
20 | int (*)(const void *, const void *)); | ||
21 | 21 | ||
22 | void *tsearch (const void *, void **, | ||
23 | int (*)(const void *, const void *)); | ||
22 | 24 | ||
23 | void * | 25 | #ifdef __cplusplus |
24 | tfind (const void *, | 26 | } |
25 | void *const *, | ||
26 | int (*)(const void *, const void *)); | ||
27 | |||
28 | |||
29 | void * | ||
30 | tsearch (const void *, | ||
31 | void **, | ||
32 | int (*)(const void *, const void *)); | ||
33 | |||
34 | #if defined(__cplusplus) | ||
35 | }; | ||
36 | #endif /* __cplusplus */ | 27 | #endif /* __cplusplus */ |
37 | 28 | ||
38 | #endif /* !_TSEARCH_H_ */ | 29 | #endif /* !_TSEARCH_H_ */ |