GNU libmicrohttpd  0.9.72
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 "tsearch.h"
13 #include <stdlib.h>
14 
15 
16 typedef struct node
17 {
18  const void *key;
19  struct node *llink;
20  struct node *rlink;
22 
23 
24 /* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */
25 /* find or insert datum into search tree */
26 void *
27 tsearch (const void *vkey, /* key to be located */
28  void **vrootp, /* address of tree root */
29  int (*compar)(const void *, const void *))
30 {
31  node_t *q;
32  node_t **rootp = (node_t **) vrootp;
33 
34  if (NULL == rootp)
35  return NULL;
36 
37  while (*rootp != NULL)
38  { /* Knuth's T1: */
39  int r;
40 
41  if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
42  return *rootp; /* we found it! */
43 
44  rootp = (r < 0) ?
45  &(*rootp)->llink : /* T3: follow left branch */
46  &(*rootp)->rlink; /* T4: follow right branch */
47  }
48 
49  q = malloc (sizeof(node_t)); /* T5: key not found */
50  if (q)
51  { /* make new node */
52  *rootp = q; /* link new node to old */
53  q->key = vkey; /* initialize new node */
54  q->llink = q->rlink = NULL;
55  }
56  return q;
57 }
58 
59 
60 /* $NetBSD: tfind.c,v 1.5 2005/03/23 08:16:53 kleink Exp $ */
61 /* find a node, or return NULL */
62 void *
63 tfind (const void *vkey, /* key to be found */
64  void *const *vrootp, /* address of the tree root */
65  int (*compar)(const void *, const void *))
66 {
67  node_t *const *rootp = (node_t *const*) vrootp;
68 
69  if (NULL == rootp)
70  return NULL;
71 
72  while (*rootp != NULL)
73  { /* T1: */
74  int r;
75 
76  if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
77  return *rootp; /* key found */
78  rootp = (r < 0) ?
79  &(*rootp)->llink : /* T3: follow left branch */
80  &(*rootp)->rlink; /* T4: follow right branch */
81  }
82  return NULL;
83 }
84 
85 
86 /* $NetBSD: tdelete.c,v 1.2 1999/09/16 11:45:37 lukem Exp $ */
87 /*
88  * delete node with given key
89  *
90  * vkey: key to be deleted
91  * vrootp: address of the root of the tree
92  * compar: function to carry out node comparisons
93  */
94 void *
95 tdelete (const void *__restrict vkey,
96  void **__restrict vrootp,
97  int (*compar)(const void *, const void *))
98 {
99  node_t **rootp = (node_t **) vrootp;
100  node_t *p;
101  node_t *q;
102  node_t *r;
103  int cmp;
104 
105  if ((rootp == NULL) || ((p = *rootp) == NULL))
106  return NULL;
107 
108  while ((cmp = (*compar)(vkey, (*rootp)->key)) != 0)
109  {
110  p = *rootp;
111  rootp = (cmp < 0) ?
112  &(*rootp)->llink : /* follow llink branch */
113  &(*rootp)->rlink; /* follow rlink branch */
114  if (*rootp == NULL)
115  return NULL; /* key not found */
116  }
117  r = (*rootp)->rlink; /* D1: */
118  if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
119  {
120  q = r;
121  }
122  else if (r != NULL)
123  { /* Right link is NULL? */
124  if (r->llink == NULL)
125  { /* D2: Find successor */
126  r->llink = q;
127  q = r;
128  }
129  else
130  { /* D3: Find NULL link */
131  for (q = r->llink; q->llink != NULL; q = r->llink)
132  r = q;
133  r->llink = q->rlink;
134  q->llink = (*rootp)->llink;
135  q->rlink = (*rootp)->rlink;
136  }
137  }
138  free (*rootp); /* D4: Free node */
139  *rootp = q; /* link parent to new node */
140  return p;
141 }
142 
143 
144 /* end of tsearch.c */
#define NULL
Definition: reason_phrase.c:30
void * tsearch(const void *vkey, void **vrootp, int(*compar)(const void *, const void *))
Definition: tsearch.c:27
struct node node_t
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