aboutsummaryrefslogtreecommitdiff
path: root/src/lib/tsearch.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/lib/tsearch.c')
-rw-r--r--src/lib/tsearch.c28
1 files changed, 14 insertions, 14 deletions
diff --git a/src/lib/tsearch.c b/src/lib/tsearch.c
index 78f37608..1d74dcce 100644
--- a/src/lib/tsearch.c
+++ b/src/lib/tsearch.c
@@ -24,7 +24,7 @@ typedef struct node
24/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */ 24/* $NetBSD: tsearch.c,v 1.5 2005/11/29 03:12:00 christos Exp $ */
25/* find or insert datum into search tree */ 25/* find or insert datum into search tree */
26void * 26void *
27tsearch (const void *vkey, /* key to be located */ 27tsearch (const void *vkey, /* key to be located */
28 void **vrootp, /* address of tree root */ 28 void **vrootp, /* address of tree root */
29 int (*compar)(const void *, const void *)) 29 int (*compar)(const void *, const void *))
30{ 30{
@@ -38,19 +38,19 @@ tsearch (const void *vkey, /* key to be located */
38 { /* Knuth's T1: */ 38 { /* Knuth's T1: */
39 int r; 39 int r;
40 40
41 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 41 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
42 return *rootp; /* we found it! */ 42 return *rootp; /* we found it! */
43 43
44 rootp = (r < 0) ? 44 rootp = (r < 0) ?
45 &(*rootp)->llink : /* T3: follow left branch */ 45 &(*rootp)->llink : /* T3: follow left branch */
46 &(*rootp)->rlink; /* T4: follow right branch */ 46 &(*rootp)->rlink; /* T4: follow right branch */
47 } 47 }
48 48
49 q = malloc (sizeof(node_t)); /* T5: key not found */ 49 q = malloc (sizeof(node_t)); /* T5: key not found */
50 if (q) 50 if (q)
51 { /* make new node */ 51 { /* make new node */
52 *rootp = q; /* link new node to old */ 52 *rootp = q; /* link new node to old */
53 q->key = vkey; /* initialize new node */ 53 q->key = vkey; /* initialize new node */
54 q->llink = q->rlink = NULL; 54 q->llink = q->rlink = NULL;
55 } 55 }
56 return q; 56 return q;
@@ -73,8 +73,8 @@ tfind (const void *vkey, /* key to be found */
73 { /* T1: */ 73 { /* T1: */
74 int r; 74 int r;
75 75
76 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */ 76 if ((r = (*compar)(vkey, (*rootp)->key)) == 0) /* T2: */
77 return *rootp; /* key found */ 77 return *rootp; /* key found */
78 rootp = (r < 0) ? 78 rootp = (r < 0) ?
79 &(*rootp)->llink : /* T3: follow left branch */ 79 &(*rootp)->llink : /* T3: follow left branch */
80 &(*rootp)->rlink; /* T4: follow right branch */ 80 &(*rootp)->rlink; /* T4: follow right branch */
@@ -112,17 +112,17 @@ tdelete (const void *__restrict vkey,
112 &(*rootp)->llink : /* follow llink branch */ 112 &(*rootp)->llink : /* follow llink branch */
113 &(*rootp)->rlink; /* follow rlink branch */ 113 &(*rootp)->rlink; /* follow rlink branch */
114 if (*rootp == NULL) 114 if (*rootp == NULL)
115 return NULL; /* key not found */ 115 return NULL; /* key not found */
116 } 116 }
117 r = (*rootp)->rlink; /* D1: */ 117 r = (*rootp)->rlink; /* D1: */
118 if ((q = (*rootp)->llink) == NULL) /* Left NULL? */ 118 if ((q = (*rootp)->llink) == NULL) /* Left NULL? */
119 { 119 {
120 q = r; 120 q = r;
121 } 121 }
122 else if (r != NULL) 122 else if (r != NULL)
123 { /* Right link is NULL? */ 123 { /* Right link is NULL? */
124 if (r->llink == NULL) 124 if (r->llink == NULL)
125 { /* D2: Find successor */ 125 { /* D2: Find successor */
126 r->llink = q; 126 r->llink = q;
127 q = r; 127 q = r;
128 } 128 }
@@ -135,7 +135,7 @@ tdelete (const void *__restrict vkey,
135 q->rlink = (*rootp)->rlink; 135 q->rlink = (*rootp)->rlink;
136 } 136 }
137 } 137 }
138 free (*rootp); /* D4: Free node */ 138 free (*rootp); /* D4: Free node */
139 *rootp = q; /* link parent to new node */ 139 *rootp = q; /* link parent to new node */
140 return p; 140 return p;
141} 141}