aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/microhttpd/tsearch.c86
-rw-r--r--src/microhttpd/tsearch.h31
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
22typedef struct node 22typedef 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 */
32void * 31void *
33tsearch (const void *vkey, /* key to be located */ 32tsearch (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 */
68void * 66void *
69tfind (const void *vkey, /* key to be found */ 67tfind (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 */
100void * 91void *
101tdelete (const void *__restrict vkey, 92tdelete (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
13extern "C" { 12extern "C"
13{
14#endif /* __cplusplus */ 14#endif /* __cplusplus */
15 15
16void *tdelete (const void *, void **,
17 int (*)(const void *, const void *));
16 18
17void * 19void *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
22void *tsearch (const void *, void **,
23 int (*)(const void *, const void *));
22 24
23void * 25#ifdef __cplusplus
24 tfind (const void *, 26}
25 void *const *,
26 int (*)(const void *, const void *));
27
28
29void *
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_ */
generated by cgit v1.2.3 (git 2.39.1) at 2024-04-16 05:15:00 +0000