GNU libmicrohttpd  0.9.29
 All Data Structures Files Functions Variables Typedefs Enumerations Enumerator Macros Groups
tsearch.c
Go to the documentation of this file.
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 */
#define NULL
Definition: reason_phrase.c:31
void * tdelete(const void *__restrict vkey, void **__restrict vrootp, int(*compar)(const void *, const void *))
Definition: tsearch.c:85
void * tfind(void *vkey, void *const *vrootp, int *compar) const
Definition: tsearch.c:55
void * tsearch(void *vkey, void **vrootp, int *compar) const
Definition: tsearch.c:21