1 /* Copyright (c) 2013-2014, David Anderson
2 All rights reserved.
3
4 Redistribution and use in source and binary forms, with
5 or without modification, are permitted provided that the
6 following conditions are met:
7
8 Redistributions of source code must retain the above
9 copyright notice, this list of conditions and the following
10 disclaimer.
11
12 Redistributions in binary form must reproduce the above
13 copyright notice, this list of conditions and the following
14 disclaimer in the documentation and/or other materials
15 provided with the distribution.
16
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
18 CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
19 INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
20 OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
21 ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR
22 CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
24 NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
25 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
26 HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
27 CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
28 OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE,
29 EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30
31 */
32
33 /* The interfaces follow tsearch (See the Single
34 Unix Specification) but the implementation is
35 written without reference to the source of any
36 version of tsearch.
37
38 See http://www.prevanders.net/tsearch.html
39 for information and an example of use.
40
41 Based on Knuth, chapter 6.2.2, algorithm T and
42 Algorithm D.
43
44 Algorithm D here is with Eppinger's left/right reflection
45 in delete (J L Eppinger CACM26 (1983),663-669, 27 (1984),235).
46
47 */
48
49
50
51 #include "config.h"
52 #include "dwarf_incl.h"
53 #include "stdlib.h" /* for free() */
54 #include <stdio.h> /* for printf */
55 #include "dwarf_tsearch.h"
56
57
58 /* INVARIANT: The head node has no user data.
59
60 head->llink is null, head->rlink points to the real user
61 top node (root of the user tree).
62 So the physical top node we call 'head'. No user data.
63 The user top node we call 'root' here. It has a user key.
64
65 Though we intend that head->rlink be non-NULL
66 except briefly when a tdelete removes the last
67 node (in which case we remove the head too before
68 returning) the code is a bit cautious and tests
69 for a non-NULL head->rlink.
70
71 */
72
73 struct ts_entry {
74 /* Keyptr points to a pointer to a record the user saved, the
75 user record contains the user's key itself
76 and perhaps more. */
77 const void *keyptr;
78 struct ts_entry * llink;
79 struct ts_entry * rlink;
80 };
81
82 /* Not needed for this set of functions. */
83 void *
dwarf_initialize_search_hash(void ** treeptr,DW_TSHASHTYPE (* hashfunc)(const void * key),unsigned long size_estimate)84 dwarf_initialize_search_hash( void **treeptr,
85 DW_TSHASHTYPE(*hashfunc)(const void *key),
86 unsigned long size_estimate)
87 {
88 return *treeptr;
89 }
90
91 /* For debugging. Prints the level number and indents 1 space
92 per level. That won't work very well for a deep tree, so perhaps
93 we should clamp at some number of indent spaces? */
printlevel(int level)94 static void printlevel(int level)
95 {
96 int len = 0;
97 int targetlen = 4 + level;
98 int shownlen = 0;
99 char number[10];
100 len = snprintf(number,sizeof(number),"<%d>",level);
101 printf("%s",number);
102 shownlen = len;
103 while(shownlen < targetlen) {
104 putchar(' ');
105 ++shownlen;
106 }
107 }
108
109 /* For debugging */
110 static void
dumptree_inner(const struct ts_entry * t,char * (* keyprint)(const void *),const char * descr,int level)111 dumptree_inner(const struct ts_entry *t,
112 char *(* keyprint)(const void *),
113 const char *descr, int level)
114 {
115 char *v = "";
116 if(!t) {
117 return;
118 }
119 dumptree_inner(t->rlink,keyprint,"left ",level+1);
120 if(t->keyptr) {
121 v = keyprint(t->keyptr);
122 }
123 printlevel(level);
124 printf("0x%08x <keyptr 0x%08x> <%s %s> <l 0x%08x> <r 0x%08x> %s\n",
125 (unsigned)t,
126 (unsigned)t->keyptr,
127 t->keyptr?"key ":"null",
128 v,
129 (unsigned)t->llink,(unsigned)t->rlink,
130 descr);
131 dumptree_inner(t->llink,keyprint,"right",level+1);
132 }
133
134 static struct ts_entry*
getlink(struct ts_entry * t,int a)135 getlink(struct ts_entry*t,int a)
136 {
137 if(a < 0) {
138 return(t->llink);
139 }
140 return(t->rlink);
141 }
142
143
144 /* Dumping the tree to stdout. */
145 void
dwarf_tdump(const void * rootin,char * (* keyprint)(const void *),const char * msg)146 dwarf_tdump(const void*rootin,
147 char *(* keyprint)(const void *),
148 const char *msg)
149 {
150 const struct ts_entry *head = (const struct ts_entry *)rootin;
151 const struct ts_entry *root = 0;
152 if(!head) {
153 printf("dwarf_tdump null tree ptr : %s\n",msg);
154 return;
155 }
156 root = head->rlink;
157 if(!root) {
158 printf("dwarf_tdump empty tree : %s\n",msg);
159 return;
160 }
161 printf("dwarf_tdump tree head : 0x%08lx %s\n",(unsigned long)head,msg);
162 printf("dwarf_tdump tree root : 0x%08lx %s\n",(unsigned long)root,msg);
163 dumptree_inner(root,keyprint,"top",0);
164 }
165
166 static struct ts_entry *
allocate_ts_entry(const void * key)167 allocate_ts_entry(const void *key)
168 {
169 struct ts_entry *e = (struct ts_entry *)
170 malloc(sizeof(struct ts_entry));
171 if(!e) {
172 return NULL;
173 }
174 e->keyptr = key;
175 e->llink = 0;
176 e->rlink = 0;
177 return e;
178 }
179
180 /* Knuth step T5, the insert. */
181 static struct ts_entry *
tsearch_insert_k(const void * key,int kc,struct ts_entry * p)182 tsearch_insert_k(const void *key,int kc,
183 struct ts_entry *p)
184 {
185 struct ts_entry *e = allocate_ts_entry(key);
186 if (!e) {
187 /* out of memory */
188 return NULL;
189 }
190 if( kc < 0) {
191 p->llink = e;
192 } else {
193 p->rlink = e;
194 }
195 /* Non-NULL means inserted. */
196 return e;
197 }
198
199 /* Knuth step T5. */
200 static struct ts_entry *
tsearch_inner_do_insert(const void * key,int kc,int * inserted,struct ts_entry * p)201 tsearch_inner_do_insert(const void *key,
202 int kc,
203 int * inserted,
204 struct ts_entry* p)
205 {
206 struct ts_entry *q = 0;
207 q = tsearch_insert_k(key,kc,p);
208 if(q) {
209 *inserted = 1;
210 }
211 return q;
212 }
213
214 /* Algorithm T of Knuth 6.2.2.2
215 key is pointer to a user data area containing the key
216 and possibly more.
217
218 We iterate like Knuth does, but using for(;;) instead
219 of go-to. */
220 static struct ts_entry *
tsearch_inner(const void * key,struct ts_entry * localrootp,int (* compar)(const void *,const void *),int * inserted)221 tsearch_inner( const void *key, struct ts_entry* localrootp,
222 int (*compar)(const void *, const void *),
223 int*inserted)
224 {
225 struct ts_entry* p = localrootp;
226 for(;;) {
227 struct ts_entry *r = 0;
228 /* T2. */
229 int kc = compar(key,p->keyptr);
230 if(kc < 0) {
231 /* T3. */
232 struct ts_entry *l = p->llink;
233 if (l) {
234 p = l;
235 continue;
236 }
237 /* T5 */
238 r = tsearch_inner_do_insert(key,kc,inserted,p);
239 return r;
240 } else if (kc > 0 ) {
241 /* T4. */
242 struct ts_entry *r2 = p->rlink;
243 if (r2) {
244 p = r2;
245 continue;
246 }
247 /* T5 */
248 r = tsearch_inner_do_insert(key,kc,inserted,p);
249 return r;
250 }
251 /* K = KEY(P) in Knuth. */
252 /* kc == 0, we found the entry we search for. */
253 return p;
254 }
255 return 0;
256 }
257
258 /* Search and, if missing, insert. */
259 void *
dwarf_tsearch(const void * key,void ** headpin,int (* compar)(const void *,const void *))260 dwarf_tsearch(const void *key, void **headpin,
261 int (*compar)(const void *, const void *))
262 {
263 struct ts_entry *head = 0;
264 struct ts_entry *root = 0;
265 struct ts_entry *r = 0;
266 int inserted = 0;
267
268 if(!headpin) {
269 return NULL;
270 }
271 head = (struct ts_entry *)*headpin;
272 if(head) {
273 root = head->rlink;
274 }
275 if(!head || !root) {
276 if(!head) {
277 head = allocate_ts_entry(0);
278 }
279 if(!head) {
280 return NULL;
281 }
282 root = allocate_ts_entry(key);
283 if(!root) {
284 free(root);
285 return NULL;
286 }
287 head->rlink = root;
288 *headpin = head;
289 return (void *)(&(root->keyptr));
290 }
291 root = head->rlink;
292 r = tsearch_inner(key,root,compar,&inserted);
293 if (!r) {
294 return NULL;
295 }
296 /* Was this found or inserted?
297 Value is the same either way, but the pointer to return
298 is not the same! */
299 /* Discards const. Required by the interface definition. */
300 return (void *)&(r->keyptr);
301 }
302
303 /* Search. */
304 void *
dwarf_tfind(const void * key,void * const * headppin,int (* compar)(const void *,const void *))305 dwarf_tfind(const void *key, void *const*headppin,
306 int (*compar)(const void *, const void *))
307 {
308 struct ts_entry *head = (struct ts_entry *)*headppin;
309 struct ts_entry **proot = 0;
310 struct ts_entry *root = 0;
311 struct ts_entry *p = 0;
312
313 if(!headppin) {
314 return NULL;
315 }
316 head = (struct ts_entry *)*headppin;
317 if(!head) {
318 return NULL;
319 }
320 proot = &head->rlink;
321 root = *proot;
322 if(!root) {
323 return NULL;
324 }
325 p = root;
326 while(p) {
327 int kc = compar(key,p->keyptr);
328 if (!kc) {
329 return (void *)&(p->keyptr);
330 }
331 p = getlink(p,kc);
332 }
333 return NULL;
334 }
335
336 void *
dwarf_tdelete(const void * key,void ** headin,int (* compar)(const void *,const void *))337 dwarf_tdelete(const void *key, void **headin,
338 int (*compar)(const void *, const void *))
339 {
340 struct ts_entry *phead = 0;
341 struct ts_entry **rootp = 0;
342 struct ts_entry *root = 0;
343 struct ts_entry * p= 0;
344 /* If a leaf is found, we have to null a parent link
345 or the root */
346 struct ts_entry * parentp = 0;
347 int parentcomparv = 0;
348 int done = 0;
349 /* We don't really care much if multiple tree
350 tables use this simultaneously. This left/right
351 is a practical thing not supported by known theory,
352 according to Knuth.
353
354 We start with eppingerleftr=1 because that happens to
355 show a different tree than standard knuth
356 in one of our standard tsearch regression test sequences.
357 */
358 static unsigned eppingerleft = 1;
359
360
361 if (!headin) {
362 return NULL;
363 }
364 phead = (struct ts_entry *)*headin;
365 if (!phead) {
366 return NULL;
367 }
368
369 rootp = &phead->rlink;
370 root = phead->rlink;
371 if (!root) {
372 return NULL;
373 }
374 p = root;
375 while(p) {
376 int kc = compar(key,p->keyptr);
377 if (!kc) {
378 break;
379 }
380 parentp = p;
381 parentcomparv = kc;
382 p = getlink(p,kc);
383 }
384 if(!p) {
385 return NULL;
386 }
387 {
388 struct ts_entry **q = 0;
389 struct ts_entry *t = 0;
390 struct ts_entry *s = 0;
391 int emptied_a_leaf = 0;
392
393 /* Either we found root (to remove) or we
394 have a parentp and the parent mismatched the key so
395 parentcomparv is != 0 */
396 if (p == root) {
397 q = rootp;
398 } else if (parentcomparv < 0) {
399 q = &parentp->llink;
400 } else /* (parentcomparv > 0) */ {
401 q = &parentp->rlink;
402 }
403 /* D1. *q is what Knuth calls q. */
404 t = *q;
405 if(!eppingerleft) {
406 struct ts_entry *r = 0;
407 eppingerleft = 1;
408 r = t->rlink;
409 if (!r) {
410 *q = t->llink;
411 done = 1;
412 } else {
413 /* D2. */
414 if (!r->llink) {
415 r->llink = t->llink;
416 *q = r;
417 done = 1;
418 }
419 }
420 while (!done) {
421 /* D3. */
422 s = r->llink;
423 if(s->llink) {
424 r = s;
425 continue;
426 }
427 s->llink = t->llink;
428 r->llink = s->rlink;
429 s->rlink = t->rlink;
430 *q = s;
431 done = 1;
432 }
433 } else {
434 struct ts_entry *l = 0;
435 eppingerleft = 0;
436 l = t->llink;
437 if (!l) {
438 *q = t->rlink;
439 done = 1;
440 } else {
441 /* D2. */
442 if (!l->rlink) {
443 l->rlink = t->rlink;
444 *q = l;
445 done = 1;
446 }
447 }
448 while (!done) {
449 /* D3. */
450 s = l->rlink;
451 if(s->rlink) {
452 l = s;
453 continue;
454 }
455 s->rlink = t->rlink;
456 l->rlink = s->llink;
457 s->llink = t->llink;
458 *q = s;
459 done = 1;
460 }
461 }
462 /* Step D4. */
463 if(!t->llink && !t->rlink) {
464 emptied_a_leaf = 1;
465 }
466 free(t);
467
468 if(emptied_a_leaf) {
469 if (p == root) {
470 /* The tree is completely empty now.
471 Free the special head node.
472 Notify the caller. */
473 free(phead);
474 *headin = 0;
475 return NULL;
476 }
477 }
478 if(!parentp) {
479 /* The item we found was at top of tree,
480 found == root.
481 We have a new root node.
482 We return it, there is no parent. */
483 return (void *)(&(root->keyptr));
484 }
485 return (void *)(&(parentp->keyptr));
486 }
487 return NULL;
488 }
489
490 static void
dwarf_twalk_inner(const struct ts_entry * p,void (* action)(const void * nodep,const DW_VISIT which,const int depth),unsigned level)491 dwarf_twalk_inner(const struct ts_entry *p,
492 void (*action)(const void *nodep, const DW_VISIT which, const int depth),
493 unsigned level)
494 {
495 if (!p->llink && !p->rlink) {
496 action((const void *)(&(p->keyptr)),dwarf_leaf,level);
497 return;
498 }
499 action((const void *)(&(p->keyptr)),dwarf_preorder,level);
500 if(p->llink) {
501 dwarf_twalk_inner(p->llink,action,level+1);
502 }
503 action((const void *)(&(p->keyptr)),dwarf_postorder,level);
504 if(p->rlink) {
505 dwarf_twalk_inner(p->rlink,action,level+1);
506 }
507 action((const void *)(&(p->keyptr)),dwarf_endorder,level);
508 }
509
510
511 void
dwarf_twalk(const void * headin,void (* action)(const void * nodep,const DW_VISIT which,const int depth))512 dwarf_twalk(const void *headin,
513 void (*action)(const void *nodep, const DW_VISIT which, const int depth))
514 {
515 const struct ts_entry *head = (const struct ts_entry *)headin;
516 const struct ts_entry *root = 0;
517 if(!head) {
518 return;
519 }
520 root = head->rlink;
521 if(!root) {
522 return;
523 }
524 dwarf_twalk_inner(root,action,0);
525 }
526
527 static void
dwarf_tdestroy_inner(struct ts_entry * p,void (* free_node)(void * nodep),int depth)528 dwarf_tdestroy_inner(struct ts_entry*p,
529 void (*free_node)(void *nodep),
530 int depth)
531 {
532 if(p->llink) {
533 dwarf_tdestroy_inner(p->llink,free_node,depth+1);
534 p->llink = 0;
535 }
536 if(p->rlink) {
537 dwarf_tdestroy_inner(p->rlink,free_node,depth+1);
538 p->rlink = 0;
539 }
540 /* Discards const. Required by the interface definition. */
541 free_node((void *)p->keyptr);
542 free(p);
543 }
544
545 /* Walk the tree, freeing all space in the tree
546 and calling the user's callback function on each node.
547 The user must zero out the head node, we have no
548 way to do that in the defined interface.
549 */
550 void
dwarf_tdestroy(void * headin,void (* free_node)(void * nodep))551 dwarf_tdestroy(void *headin, void (*free_node)(void *nodep))
552 {
553 struct ts_entry *head = (struct ts_entry *)headin;
554 struct ts_entry *root = 0;
555 if(!head) {
556 return;
557 }
558 root = head->rlink;
559 if(head) {
560 dwarf_tdestroy_inner(root,free_node,0);
561 }
562 free(head);
563 }
564
565
566
567