This source file includes following definitions.
- check_tree_recurse
- check_tree
- maybe_split_for_insert
- __tsearch
- weak_alias
- weak_alias
- weak_alias
- __twalk
- weak_alias
- __tdestroy
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90 #define _GL_ARG_NONNULL(params)
91
92 #include <config.h>
93
94
95 #include <search.h>
96
97 #include <stdlib.h>
98
99 typedef int (*__compar_fn_t) (const void *, const void *);
100 typedef void (*__action_fn_t) (const void *, VISIT, int);
101
102 #ifndef weak_alias
103 # define __tsearch tsearch
104 # define __tfind tfind
105 # define __tdelete tdelete
106 # define __twalk twalk
107 #endif
108
109 #ifndef internal_function
110
111
112 # define internal_function
113 #endif
114
115 typedef struct node_t
116 {
117
118
119 const void *key;
120 struct node_t *left;
121 struct node_t *right;
122 unsigned int red:1;
123 } *node;
124 typedef const struct node_t *const_node;
125
126 #undef DEBUGGING
127
128 #ifdef DEBUGGING
129
130
131
132 #include <assert.h>
133
134 #define CHECK_TREE(a) check_tree(a)
135
136 static void
137 check_tree_recurse (node p, int d_sofar, int d_total)
138 {
139 if (p == NULL)
140 {
141 assert (d_sofar == d_total);
142 return;
143 }
144
145 check_tree_recurse (p->left, d_sofar + (p->left && !p->left->red), d_total);
146 check_tree_recurse (p->right, d_sofar + (p->right && !p->right->red), d_total);
147 if (p->left)
148 assert (!(p->left->red && p->red));
149 if (p->right)
150 assert (!(p->right->red && p->red));
151 }
152
153 static void
154 check_tree (node root)
155 {
156 int cnt = 0;
157 node p;
158 if (root == NULL)
159 return;
160 root->red = 0;
161 for (p = root->left; p; p = p->left)
162 cnt += !p->red;
163 check_tree_recurse (root, 0, cnt);
164 }
165
166
167 #else
168
169 #define CHECK_TREE(a)
170
171 #endif
172
173 #if GNULIB_defined_tsearch
174
175
176
177
178
179
180
181 static void
182 maybe_split_for_insert (node *rootp, node *parentp, node *gparentp,
183 int p_r, int gp_r, int mode)
184 {
185 node root = *rootp;
186 node *rp, *lp;
187 rp = &(*rootp)->right;
188 lp = &(*rootp)->left;
189
190
191 if (mode == 1
192 || ((*rp) != NULL && (*lp) != NULL && (*rp)->red && (*lp)->red))
193 {
194
195 root->red = 1;
196 if (*rp)
197 (*rp)->red = 0;
198 if (*lp)
199 (*lp)->red = 0;
200
201
202
203 if (parentp != NULL && (*parentp)->red)
204 {
205 node gp = *gparentp;
206 node p = *parentp;
207
208
209
210
211
212 if ((p_r > 0) != (gp_r > 0))
213 {
214
215
216 p->red = 1;
217 gp->red = 1;
218 root->red = 0;
219 if (p_r < 0)
220 {
221
222 p->left = *rp;
223 *rp = p;
224 gp->right = *lp;
225 *lp = gp;
226 }
227 else
228 {
229
230 p->right = *lp;
231 *lp = p;
232 gp->left = *rp;
233 *rp = gp;
234 }
235 *gparentp = root;
236 }
237 else
238 {
239 *gparentp = *parentp;
240
241
242 p->red = 0;
243 gp->red = 1;
244 if (p_r < 0)
245 {
246
247 gp->left = p->right;
248 p->right = gp;
249 }
250 else
251 {
252
253 gp->right = p->left;
254 p->left = gp;
255 }
256 }
257 }
258 }
259 }
260
261
262
263
264 void *
265 __tsearch (const void *key, void **vrootp, __compar_fn_t compar)
266 {
267 node q;
268 node *parentp = NULL, *gparentp = NULL;
269 node *rootp = (node *) vrootp;
270 node *nextp;
271 int r = 0, p_r = 0, gp_r = 0;
272
273 if (rootp == NULL)
274 return NULL;
275
276
277 if (*rootp != NULL)
278 (*rootp)->red = 0;
279
280 CHECK_TREE (*rootp);
281
282 nextp = rootp;
283 while (*nextp != NULL)
284 {
285 node root = *rootp;
286 r = (*compar) (key, root->key);
287 if (r == 0)
288 return root;
289
290 maybe_split_for_insert (rootp, parentp, gparentp, p_r, gp_r, 0);
291
292
293
294
295 nextp = r < 0 ? &root->left : &root->right;
296 if (*nextp == NULL)
297 break;
298
299 gparentp = parentp;
300 parentp = rootp;
301 rootp = nextp;
302
303 gp_r = p_r;
304 p_r = r;
305 }
306
307 q = (struct node_t *) malloc (sizeof (struct node_t));
308 if (q != NULL)
309 {
310 *nextp = q;
311 q->key = key;
312 q->red = 1;
313 q->left = q->right = NULL;
314
315 if (nextp != rootp)
316
317
318 maybe_split_for_insert (nextp, rootp, parentp, r, p_r, 1);
319 }
320
321 return q;
322 }
323 #ifdef weak_alias
324 weak_alias (__tsearch, tsearch)
325 #endif
326
327
328
329
330
331 void *
332 __tfind (const void *key, void *const *vrootp, __compar_fn_t compar)
333 {
334 node *rootp = (node *) vrootp;
335
336 if (rootp == NULL)
337 return NULL;
338
339 CHECK_TREE (*rootp);
340
341 while (*rootp != NULL)
342 {
343 node root = *rootp;
344 int r;
345
346 r = (*compar) (key, root->key);
347 if (r == 0)
348 return root;
349
350 rootp = r < 0 ? &root->left : &root->right;
351 }
352 return NULL;
353 }
354 #ifdef weak_alias
355 weak_alias (__tfind, tfind)
356 #endif
357
358
359
360
361
362 void *
363 __tdelete (const void *key, void **vrootp, __compar_fn_t compar)
364 {
365 node p, q, r, retval;
366 int cmp;
367 node *rootp = (node *) vrootp;
368 node root, unchained;
369
370
371
372 int stacksize = 100;
373 int sp = 0;
374 node *nodestack[100];
375
376 if (rootp == NULL)
377 return NULL;
378 p = *rootp;
379 if (p == NULL)
380 return NULL;
381
382 CHECK_TREE (p);
383
384 while ((cmp = (*compar) (key, (*rootp)->key)) != 0)
385 {
386 if (sp == stacksize)
387 abort ();
388
389 nodestack[sp++] = rootp;
390 p = *rootp;
391 rootp = ((cmp < 0)
392 ? &(*rootp)->left
393 : &(*rootp)->right);
394 if (*rootp == NULL)
395 return NULL;
396 }
397
398
399
400
401 retval = p;
402
403
404
405
406
407 root = *rootp;
408
409 r = root->right;
410 q = root->left;
411
412 if (q == NULL || r == NULL)
413 unchained = root;
414 else
415 {
416 node *parent = rootp, *up = &root->right;
417 for (;;)
418 {
419 if (sp == stacksize)
420 abort ();
421 nodestack[sp++] = parent;
422 parent = up;
423 if ((*up)->left == NULL)
424 break;
425 up = &(*up)->left;
426 }
427 unchained = *up;
428 }
429
430
431
432 r = unchained->left;
433 if (r == NULL)
434 r = unchained->right;
435 if (sp == 0)
436 *rootp = r;
437 else
438 {
439 q = *nodestack[sp-1];
440 if (unchained == q->right)
441 q->right = r;
442 else
443 q->left = r;
444 }
445
446 if (unchained != root)
447 root->key = unchained->key;
448 if (!unchained->red)
449 {
450
451
452
453
454
455
456
457 while (sp > 0 && (r == NULL || !r->red))
458 {
459 node *pp = nodestack[sp - 1];
460 p = *pp;
461
462 if (r == p->left)
463 {
464
465
466 q = p->right;
467 if (q->red)
468 {
469
470
471
472
473
474
475
476 q->red = 0;
477 p->red = 1;
478
479 p->right = q->left;
480 q->left = p;
481 *pp = q;
482
483
484 nodestack[sp++] = pp = &q->left;
485 q = p->right;
486 }
487
488
489 if ((q->left == NULL || !q->left->red)
490 && (q->right == NULL || !q->right->red))
491 {
492
493
494
495
496
497
498
499
500 q->red = 1;
501 r = p;
502 }
503 else
504 {
505
506
507
508 if (q->right == NULL || !q->right->red)
509 {
510
511
512
513
514
515
516
517
518
519
520 node q2 = q->left;
521 q2->red = p->red;
522 p->right = q2->left;
523 q->left = q2->right;
524 q2->right = q;
525 q2->left = p;
526 *pp = q2;
527 p->red = 0;
528 }
529 else
530 {
531
532
533
534
535 q->red = p->red;
536 p->red = 0;
537
538 q->right->red = 0;
539
540
541 p->right = q->left;
542 q->left = p;
543 *pp = q;
544 }
545
546
547 sp = 1;
548 r = NULL;
549 }
550 }
551 else
552 {
553
554 q = p->left;
555 if (q->red)
556 {
557 q->red = 0;
558 p->red = 1;
559 p->left = q->right;
560 q->right = p;
561 *pp = q;
562 nodestack[sp++] = pp = &q->right;
563 q = p->left;
564 }
565 if ((q->right == NULL || !q->right->red)
566 && (q->left == NULL || !q->left->red))
567 {
568 q->red = 1;
569 r = p;
570 }
571 else
572 {
573 if (q->left == NULL || !q->left->red)
574 {
575 node q2 = q->right;
576 q2->red = p->red;
577 p->left = q2->right;
578 q->right = q2->left;
579 q2->left = q;
580 q2->right = p;
581 *pp = q2;
582 p->red = 0;
583 }
584 else
585 {
586 q->red = p->red;
587 p->red = 0;
588 q->left->red = 0;
589 p->left = q->right;
590 q->right = p;
591 *pp = q;
592 }
593 sp = 1;
594 r = NULL;
595 }
596 }
597 --sp;
598 }
599 if (r != NULL)
600 r->red = 0;
601 }
602
603 free (unchained);
604 return retval;
605 }
606 #ifdef weak_alias
607 weak_alias (__tdelete, tdelete)
608 #endif
609
610 #endif
611
612
613 #if GNULIB_defined_twalk
614
615
616
617
618 static void
619 internal_function
620 trecurse (const void *vroot, __action_fn_t action, int level)
621 {
622 const_node root = (const_node) vroot;
623
624 if (root->left == NULL && root->right == NULL)
625 (*action) (root, leaf, level);
626 else
627 {
628 (*action) (root, preorder, level);
629 if (root->left != NULL)
630 trecurse (root->left, action, level + 1);
631 (*action) (root, postorder, level);
632 if (root->right != NULL)
633 trecurse (root->right, action, level + 1);
634 (*action) (root, endorder, level);
635 }
636 }
637
638
639
640
641
642 void
643 __twalk (const void *vroot, __action_fn_t action)
644 {
645 const_node root = (const_node) vroot;
646
647 CHECK_TREE (root);
648
649 if (root != NULL && action != NULL)
650 trecurse (root, action, 0);
651 }
652 #ifdef weak_alias
653 weak_alias (__twalk, twalk)
654 #endif
655
656 #endif
657
658
659 #ifdef _LIBC
660
661
662
663 static void
664 internal_function
665 tdestroy_recurse (node root, __free_fn_t freefct)
666 {
667 if (root->left != NULL)
668 tdestroy_recurse (root->left, freefct);
669 if (root->right != NULL)
670 tdestroy_recurse (root->right, freefct);
671 (*freefct) ((void *) root->key);
672
673 free (root);
674 }
675
676 void
677 __tdestroy (void *vroot, __free_fn_t freefct)
678 {
679 node root = (node) vroot;
680
681 CHECK_TREE (root);
682
683 if (root != NULL)
684 tdestroy_recurse (root, freefct);
685 }
686 weak_alias (__tdestroy, tdestroy)
687
688 #endif