GNU libmicrohttpd 0.9.77
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, *rlink;
27
28
29/* $NetBSD: tsearch.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */
30/* find or insert datum into search tree */
31void *
32tsearch (const void *vkey, void **vrootp,
33 int (*compar)(const void *, const void *))
34{
35 node_t *q;
36 node_t **rootp = (node_t **) vrootp;
37
38 if (rootp == NULL)
39 return NULL;
40
41 while (*rootp != NULL) /* Knuth's T1: */
42 {
43 int r;
44
45 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
46 return *rootp; /* we found it! */
47
48 rootp = (r < 0) ?
49 &(*rootp)->llink : /* T3: follow left branch */
50 &(*rootp)->rlink; /* T4: follow right branch */
51 }
52
53 q = malloc (sizeof(node_t)); /* T5: key not found */
54 if (q != NULL) /* make new node */
55 {
56 *rootp = q; /* link new node to old */
57 q->key = vkey; /* initialize new node */
58 q->llink = q->rlink = NULL;
59 }
60 return q;
61}
62
63
64/* $NetBSD: tfind.c,v 1.7 2012/06/25 22:32:45 abs Exp $ */
65/* find a node by key "vkey" in tree "vrootp", or return 0 */
66void *
67tfind (const void *vkey, void * const *vrootp,
68 int (*compar)(const void *, const void *))
69{
70 node_t * const *rootp = (node_t * const *) vrootp;
71
72 if (rootp == NULL)
73 return NULL;
74
75 while (*rootp != NULL) /* T1: */
76 {
77 int r;
78
79 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
80 return *rootp; /* key found */
81 rootp = (r < 0) ?
82 &(*rootp)->llink : /* T3: follow left branch */
83 &(*rootp)->rlink; /* T4: follow right branch */
84 }
85 return NULL;
86}
87
88
89/* $NetBSD: tdelete.c,v 1.8 2016/01/20 20:47:41 christos Exp $ */
90/* find a node with key "vkey" in tree "vrootp" */
91void *
92tdelete (const void *vkey, void **vrootp,
93 int (*compar)(const void *, const void *))
94{
95 node_t **rootp = (node_t **) vrootp;
96 node_t *p, *q, *r;
97 int cmp;
98
99 if ((rootp == NULL) || ((p = *rootp) == NULL) )
100 return NULL;
101
102 while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
103 {
104 p = *rootp;
105 rootp = (cmp < 0) ?
106 &(*rootp)->llink : /* follow llink branch */
107 &(*rootp)->rlink; /* follow rlink branch */
108 if (*rootp == NULL)
109 return NULL; /* key not found */
110 }
111 r = (*rootp)->rlink; /* D1: */
112 if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
113 q = r;
114 else if (r != NULL) /* Right link is NULL? */
115 {
116 if (r->llink == NULL) /* D2: Find successor */
117 {
118 r->llink = q;
119 q = r;
120 }
121 else /* D3: Find NULL link */
122 {
123 for (q = r->llink; q->llink != NULL; q = r->llink)
124 r = q;
125 r->llink = q->rlink;
126 q->llink = (*rootp)->llink;
127 q->rlink = (*rootp)->rlink;
128 }
129 }
130 free (*rootp); /* D4: Free node */
131 *rootp = q; /* link parent to new node */
132 return p;
133}
134
135
136/* 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