1 |
|
|
/* $OpenBSD: tsearch.c,v 1.10 2015/09/26 16:03:48 guenther 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 |
8 |
|
|
* |
9 |
|
|
* Written by reading the System V Interface Definition, not the code. |
10 |
|
|
* |
11 |
|
|
* Totally public domain. |
12 |
|
|
*/ |
13 |
|
|
|
14 |
|
|
#include <search.h> |
15 |
|
|
#include <stdlib.h> |
16 |
|
|
|
17 |
|
|
typedef struct node_t { |
18 |
|
|
char *key; |
19 |
|
|
struct node_t *left, *right; |
20 |
|
|
} node; |
21 |
|
|
|
22 |
|
|
/* find or insert datum into search tree */ |
23 |
|
|
void * |
24 |
|
|
tsearch(const void *vkey, void **vrootp, |
25 |
|
|
int (*compar)(const void *, const void *)) |
26 |
|
|
{ |
27 |
|
|
node *q; |
28 |
|
|
char *key = (char *)vkey; |
29 |
|
|
node **rootp = (node **)vrootp; |
30 |
|
|
|
31 |
|
|
if (rootp == (struct node_t **)0) |
32 |
|
|
return ((void *)0); |
33 |
|
|
while (*rootp != (struct node_t *)0) { /* Knuth's T1: */ |
34 |
|
|
int r; |
35 |
|
|
|
36 |
|
|
if ((r = (*compar)(key, (*rootp)->key)) == 0) /* T2: */ |
37 |
|
|
return ((void *)*rootp); /* we found it! */ |
38 |
|
|
rootp = (r < 0) ? |
39 |
|
|
&(*rootp)->left : /* T3: follow left branch */ |
40 |
|
|
&(*rootp)->right; /* T4: follow right branch */ |
41 |
|
|
} |
42 |
|
|
q = malloc(sizeof(node)); /* T5: key not found */ |
43 |
|
|
if (q != (struct node_t *)0) { /* make new node */ |
44 |
|
|
*rootp = q; /* link new node to old */ |
45 |
|
|
q->key = key; /* initialize new node */ |
46 |
|
|
q->left = q->right = (struct node_t *)0; |
47 |
|
|
} |
48 |
|
|
return ((void *)q); |
49 |
|
|
} |
50 |
|
|
|
51 |
|
|
/* delete node with given key */ |
52 |
|
|
void * |
53 |
|
|
tdelete(const void *vkey, void **vrootp, |
54 |
|
|
int (*compar)(const void *, const void *)) |
55 |
|
|
{ |
56 |
|
|
node **rootp = (node **)vrootp; |
57 |
|
|
char *key = (char *)vkey; |
58 |
|
|
node *p = (node *)1; |
59 |
|
|
node *q; |
60 |
|
|
node *r; |
61 |
|
|
int cmp; |
62 |
|
|
|
63 |
|
|
if (rootp == (struct node_t **)0 || *rootp == (struct node_t *)0) |
64 |
|
|
return ((struct node_t *)0); |
65 |
|
|
while ((cmp = (*compar)(key, (*rootp)->key)) != 0) { |
66 |
|
|
p = *rootp; |
67 |
|
|
rootp = (cmp < 0) ? |
68 |
|
|
&(*rootp)->left : /* follow left branch */ |
69 |
|
|
&(*rootp)->right; /* follow right branch */ |
70 |
|
|
if (*rootp == (struct node_t *)0) |
71 |
|
|
return ((void *)0); /* key not found */ |
72 |
|
|
} |
73 |
|
|
r = (*rootp)->right; /* D1: */ |
74 |
|
|
if ((q = (*rootp)->left) == (struct node_t *)0) /* Left (struct node_t *)0? */ |
75 |
|
|
q = r; |
76 |
|
|
else if (r != (struct node_t *)0) { /* Right link is null? */ |
77 |
|
|
if (r->left == (struct node_t *)0) { /* D2: Find successor */ |
78 |
|
|
r->left = q; |
79 |
|
|
q = r; |
80 |
|
|
} else { /* D3: Find (struct node_t *)0 link */ |
81 |
|
|
for (q = r->left; q->left != (struct node_t *)0; q = r->left) |
82 |
|
|
r = q; |
83 |
|
|
r->left = q->right; |
84 |
|
|
q->left = (*rootp)->left; |
85 |
|
|
q->right = (*rootp)->right; |
86 |
|
|
} |
87 |
|
|
} |
88 |
|
|
free((struct node_t *) *rootp); /* D4: Free node */ |
89 |
|
|
*rootp = q; /* link parent to new node */ |
90 |
|
|
return(p); |
91 |
|
|
} |
92 |
|
|
|
93 |
|
|
/* Walk the nodes of a tree */ |
94 |
|
|
static void |
95 |
|
|
trecurse(node *root, void (*action)(const void *, VISIT, int), int level) |
96 |
|
|
{ |
97 |
|
|
if (root->left == (struct node_t *)0 && root->right == (struct node_t *)0) |
98 |
|
|
(*action)(root, leaf, level); |
99 |
|
|
else { |
100 |
|
|
(*action)(root, preorder, level); |
101 |
|
|
if (root->left != (struct node_t *)0) |
102 |
|
|
trecurse(root->left, action, level + 1); |
103 |
|
|
(*action)(root, postorder, level); |
104 |
|
|
if (root->right != (struct node_t *)0) |
105 |
|
|
trecurse(root->right, action, level + 1); |
106 |
|
|
(*action)(root, endorder, level); |
107 |
|
|
} |
108 |
|
|
} |
109 |
|
|
|
110 |
|
|
/* Walk the nodes of a tree */ |
111 |
|
|
void |
112 |
|
|
twalk(const void *vroot, void (*action)(const void *, VISIT, int)) |
113 |
|
|
{ |
114 |
|
|
node *root = (node *)vroot; |
115 |
|
|
|
116 |
|
|
if (root != (node *)0 && action != (void (*)(const void *, VISIT, int))0) |
117 |
|
|
trecurse(root, action, 0); |
118 |
|
|
} |