diff options
Diffstat (limited to 'src/lib/tsearch.c')
-rw-r--r-- | src/lib/tsearch.c | 143 |
1 files changed, 143 insertions, 0 deletions
diff --git a/src/lib/tsearch.c b/src/lib/tsearch.c new file mode 100644 index 00000000..fe5fcd5b --- /dev/null +++ b/src/lib/tsearch.c | |||
@@ -0,0 +1,143 @@ | |||
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; | ||
21 | } node_t; | ||
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 | /* end of tsearch.c */ | ||