diff options
Diffstat (limited to 'src/lib/tsearch.c')
-rw-r--r-- | src/lib/tsearch.c | 28 |
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 */ |
26 | void * | 26 | void * |
27 | tsearch (const void *vkey, /* key to be located */ | 27 | tsearch (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 | } |