GNU libmicrohttpd 0.9.75
Loading...
Searching...
No Matches
tsearch.c
Go to the documentation of this file.
1/*
2 * Tree search generalized from Knuth (6.2.2) Algorithm T just like
3 * the AT&T man page says.
4 *
5 * The node_t structure is for internal use only, lint doesn't grok it.
6 *
7 * Written by reading the System V Interface Definition, not the code.
8 *
9 * Totally public domain.
10 */
11
12#include "mhd_options.h"
13#include "tsearch.h"
14#ifdef HAVE_STDDEF_H
15#include <stddef.h>
16#endif /* HAVE_STDDEF_H */
17#ifdef HAVE_STDLIB_H
18#include <stdlib.h>
19#endif /* HAVE_STDLIB_H */
20
21
22typedef struct node
23{
24 const void *key;
25 struct node *llink;
26 struct node *rlink;
28
29
30/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */
31/* find or insert datum into search tree */
32void *
33tsearch (const void *vkey, /* key to be located */
34 void **vrootp, /* address of tree root */
35 int (*compar)(const void *, const void *))
36{
37 node_t *q;
38 node_t **rootp = (node_t **) vrootp;
39
40 if (NULL == rootp)
41 return NULL;
42
43 while (*rootp != NULL)
44 { /* Knuth's T1: */
45 int r;
46
47 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
48 return *rootp; /* we found it! */
49
50 rootp = (r < 0) ?
51 &(*rootp)->llink : /* T3: follow left branch */
52 &(*rootp)->rlink; /* T4: follow right branch */
53 }
54
55 q = malloc (sizeof(node_t)); /* T5: key not found */
56 if (q)
57 { /* make new node */
58 *rootp = q; /* link new node to old */
59 q->key = vkey; /* initialize new node */
60 q->llink = q->rlink = NULL;
61 }
62 return q;
63}
64
65
66/* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
67/* find a node, or return NULL */
68void *
69tfind (const void *vkey, /* key to be found */
70 void *const *vrootp, /* address of the tree root */
71 int (*compar)(const void *, const void *))
72{
73 node_t *const *rootp = (node_t *const*) vrootp;
74
75 if (NULL == rootp)
76 return NULL;
77
78 while (*rootp != NULL)
79 { /* T1: */
80 int r;
81
82 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
83 return *rootp; /* key found */
84 rootp = (r < 0) ?
85 &(*rootp)->llink : /* T3: follow left branch */
86 &(*rootp)->rlink; /* T4: follow right branch */
87 }
88 return NULL;
89}
90
91
92/* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
93/*
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 *
101tdelete (const void *__restrict vkey,
102 void **__restrict vrootp,
103 int (*compar)(const void *, const void *))
104{
105 node_t **rootp = (node_t **) vrootp;
106 node_t *p;
107 node_t *q;
108 node_t *r;
109 int cmp;
110
111 if ((rootp == NULL) || ((p = *rootp) == NULL))
112 return NULL;
113
114 while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
115 {
116 p = *rootp;
117 rootp = (cmp < 0) ?
118 &(*rootp)->llink : /* follow llink branch */
119 &(*rootp)->rlink; /* follow rlink branch */
120 if (*rootp == NULL)
121 return NULL; /* key not found */
122 }
123 r = (*rootp)->rlink; /* D1: */
124 if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
125 {
126 q = r;
127 }
128 else if (r != NULL)
129 { /* Right link is NULL? */
130 if (r->llink == NULL)
131 { /* D2: Find successor */
132 r->llink = q;
133 q = r;
134 }
135 else
136 { /* D3: Find NULL link */
137 for (q = r->llink; q->llink != NULL; q = r->llink)
138 r = q;
139 r->llink = q->rlink;
140 q->llink = (*rootp)->llink;
141 q->rlink = (*rootp)->rlink;
142 }
143 }
144 free (*rootp); /* D4: Free node */
145 *rootp = q; /* link parent to new node */
146 return p;
147}
148
149
150/* end of tsearch.c */
#define NULL
void * tfind(const void *vkey, void *const *vrootp, int(*compar)(const void *, const void *))
Definition tsearch.c:63
void * tdelete(const void *__restrict vkey, void **__restrict vrootp, int(*compar)(const void *, const void *))
Definition tsearch.c:95
struct node node_t
void * tsearch(const void *vkey, void **vrootp, int(*compar)(const void *, const void *))
Definition tsearch.c:27
additional automatic macros for MHD_config.h