1 /* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
2 * Copyright by The HDF Group. *
3 * Copyright by the Board of Trustees of the University of Illinois. *
4 * All rights reserved. *
5 * *
6 * This file is part of HDF. The full HDF copyright notice, including *
7 * terms governing use, modification, and redistribution, is contained in *
8 * the COPYING file, which can be found at the root of the source code *
9 * distribution tree, or in https://support.hdfgroup.org/ftp/HDF/releases/. *
10 * If you do not have access to either file, you may request a copy from *
11 * help@hdfgroup.org. *
12 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * */
13
14 /* $Id$ */
15
16 /* "tbbt.c" -- Routines for using threaded, balanced, binary trees. */
17 /* Extended from (added threads to) Knuth 6.2.3, Algorithm A (AVL trees) */
18 /* Basic tree structure by Adel'son-Vel'skii and Landis */
19
20 #include <stdio.h> /* NULL */
21 #include "hdf.h"
22 #define TBBT_INTERNALS
23 #include "tbbt.h"
24 #define Alloc(cnt,typ) (typ *) HDmalloc( (cnt) * sizeof(typ) )
25 #define Free(x) (HDfree((VOIDP)x))
26
27 # define KEYcmp(k1,k2,a) ((NULL!=compar) ? (*compar)( k1, k2, a) \
28 : HDmemcmp( k1, k2, 0<(a) ? (a) : (intn)HDstrlen(k1) ) )
29
30 VOID tbbt1dump
31 (TBBT_NODE * node, intn method);
32
33 /* Function Prototypes */
34 extern VOID tbbt_printNode(TBBT_NODE * node, VOID(*key_dump)(VOID *,VOID *));
35 extern VOID tbbt_dumpNode(TBBT_NODE *node, VOID (*key_dump)(VOID *,VOID *),
36 intn method);
37 extern VOID tbbt_dump(TBBT_TREE *ptree, VOID (*key_dump)(VOID *,VOID *),
38 intn method);
39
40 static TBBT_NODE *tbbt_get_node(void);
41 static void tbbt_release_node(TBBT_NODE *nod);
42
43 /* #define TESTING */
44
45 /* Returns pointer to end-most (to LEFT or RIGHT) node of tree: */
46 static TBBT_NODE *
tbbt_end(TBBT_NODE * root,intn side)47 tbbt_end(TBBT_NODE * root, intn side)
48 {
49 if (root == NULL)
50 return (NULL);
51 while (HasChild(root, side))
52 {
53 root = root->link[side];
54 }
55 return (root);
56 }
57
58 TBBT_NODE *
tbbtfirst(TBBT_NODE * root)59 tbbtfirst(TBBT_NODE * root)
60 {
61 return (tbbt_end(root, LEFT));
62 }
63
64 TBBT_NODE *
tbbtlast(TBBT_NODE * root)65 tbbtlast(TBBT_NODE * root)
66 {
67 return (tbbt_end(root, RIGHT));
68 }
69
70 /* Return address of parent's pointer to neighboring node (to LEFT or RIGHT) **
71 static TBBT_NODE **tbbt_anbr(TBBT_NODE *ptr, intn side )
72 {
73 TBBT_NODE **aptr;
74
75 if( ! HasChild( ptr, side ) )
76 return( & ptr->link[side] );
77 aptr= & ptr->link[side];
78 while( HasChild( *aptr, Other(side) ) )
79 aptr= & (*aptr)->link[Other(side)];
80 return( aptr );
81 } */
82
83 /* Returns pointer to neighboring node (to LEFT or RIGHT): */
84 static TBBT_NODE *
tbbt_nbr(TBBT_NODE * ptr,intn side)85 tbbt_nbr(TBBT_NODE * ptr, intn side)
86 {
87 /* return( *tbbt_anbr(ptr,side) ); */
88
89 if (!HasChild(ptr, side))
90 return (ptr->link[side]);
91 /* return(NULL); */
92 ptr = ptr->link[side];
93 if(ptr==NULL)
94 return(NULL);
95 while (HasChild(ptr, Other(side)))
96 ptr = ptr->link[Other(side)];
97 return (ptr);
98 }
99
100 /* Returns pointer to node with previous key value: */
101 TBBT_NODE *
tbbtnext(TBBT_NODE * node)102 tbbtnext(TBBT_NODE * node)
103 {
104 return (tbbt_nbr(node, RIGHT));
105 }
106
107 /* Returns pointer to node with next key value: */
108 TBBT_NODE *
tbbtprev(TBBT_NODE * node)109 tbbtprev(TBBT_NODE * node)
110 {
111 return (tbbt_nbr(node, LEFT));
112 }
113
114 /* tbbtfind -- Look up a node in a tree based on a key value */
115 /* tbbtffind is based on this routine - fix bugs in both places! */
116 /* Returns a pointer to the found node (or NULL) */
117 TBBT_NODE *
tbbtfind(TBBT_NODE * root,VOIDP key,intn (* compar)(VOIDP,VOIDP,intn),intn arg,TBBT_NODE ** pp)118 tbbtfind(TBBT_NODE * root, VOIDP key,
119 intn (*compar) (VOIDP, VOIDP, intn), intn arg, TBBT_NODE ** pp)
120 {
121 TBBT_NODE *ptr = root;
122 TBBT_NODE *parent = NULL;
123 intn cmp = 1;
124
125 if (ptr)
126 {
127 intn side;
128
129 while (0 != (cmp = KEYcmp(key, ptr->key, arg)))
130 {
131 parent = ptr;
132 side = (cmp < 0) ? LEFT : RIGHT;
133 if (!HasChild(ptr, side))
134 break;
135 ptr = ptr->link[side];
136 }
137 }
138 if (NULL != pp)
139 *pp = parent;
140 return ((0 == cmp) ? ptr : NULL);
141 }
142
143 /* tbbtffind -- Look up a node in a tree based on a key value */
144 /* This routine is based on tbbtfind (fix bugs in both places!) */
145 /* Returns a pointer to the found node (or NULL) */
146 static TBBT_NODE *
tbbtffind(TBBT_NODE * root,VOIDP key,uintn fast_compare,TBBT_NODE ** pp)147 tbbtffind(TBBT_NODE * root, VOIDP key, uintn fast_compare, TBBT_NODE ** pp)
148 {
149 TBBT_NODE *ptr = root;
150 TBBT_NODE *parent = NULL;
151 intn cmp = 1;
152
153 switch(fast_compare)
154 {
155 case TBBT_FAST_UINT16_COMPARE:
156 if (ptr)
157 {
158 intn side;
159
160 while (0 != (cmp = (*(uint16 *)key - *(uint16 *)ptr->key)))
161 {
162 parent = ptr;
163 side = (cmp < 0) ? LEFT : RIGHT;
164 if (!HasChild(ptr, side))
165 break;
166 ptr = ptr->link[side];
167 }
168 }
169 if (NULL != pp)
170 *pp = parent;
171 return ((0 == cmp) ? ptr : NULL);
172
173 case TBBT_FAST_INT32_COMPARE:
174 if (ptr)
175 {
176 intn side;
177
178 while (0 != (cmp = (*(int32 *)key - *(int32 *)ptr->key)))
179 {
180 parent = ptr;
181 side = (cmp < 0) ? LEFT : RIGHT;
182 if (!HasChild(ptr, side))
183 break;
184 ptr = ptr->link[side];
185 }
186 }
187 if (NULL != pp)
188 *pp = parent;
189 return ((0 == cmp) ? ptr : NULL);
190
191 default:
192 return(NULL);
193 } /* end switch */
194 } /* tbbtffind() */
195
196 /* tbbtdfind -- Look up a node in a "described" tree based on a key value */
197 /* Returns a pointer to the found node (or NULL) */
198 TBBT_NODE *
tbbtdfind(TBBT_TREE * tree,VOIDP key,TBBT_NODE ** pp)199 tbbtdfind(TBBT_TREE * tree, VOIDP key, TBBT_NODE ** pp)
200 {
201 if (tree == NULL)
202 return (NULL);
203 if(tree->fast_compare!=0)
204 return (tbbtffind(tree->root, key, tree->fast_compare, pp));
205 else
206 return (tbbtfind(tree->root, key, tree->compar, tree->cmparg, pp));
207 }
208
209 /* tbbtless -- Find a node in a tree which is less than a key, */
210 /* based on a key value */
211 /* Returns a pointer to the found node (or NULL) */
212 TBBT_NODE *
tbbtless(TBBT_NODE * root,VOIDP key,intn (* compar)(VOIDP,VOIDP,intn),intn arg,TBBT_NODE ** pp)213 tbbtless(TBBT_NODE * root, VOIDP key,
214 intn (*compar) (VOIDP, VOIDP, intn), intn arg, TBBT_NODE ** pp)
215 {
216 TBBT_NODE *ptr = root;
217 TBBT_NODE *parent = NULL;
218 intn cmp = 1;
219
220 if (ptr)
221 {
222 intn side;
223
224 while (0 != (cmp = KEYcmp(key, ptr->key, arg)))
225 {
226 parent = ptr;
227 side = (cmp < 0) ? LEFT : RIGHT;
228 if (!HasChild(ptr, side))
229 break;
230 ptr = ptr->link[side];
231 }
232 }
233 if(cmp!=0)
234 /* didn't find an exact match, search back up the tree until a node */
235 /* is found with a key less than the key searched for */
236 {
237 while((ptr=ptr->Parent)!=NULL)
238 {
239 cmp = KEYcmp(key, ptr->key, arg);
240 if(cmp<0) /* found a node which is less than the search for one */
241 break;
242 } /* end while */
243 if(ptr==NULL) /* didn't find a node in the tree which was less */
244 cmp=1;
245 else /* reset this for cmp test below */
246 cmp=0;
247 } /* end if */
248 if (NULL != pp)
249 *pp = parent;
250 return ((0 == cmp) ? ptr : NULL);
251 }
252
253 /* tbbtdless -- Find a node less than a key in a "described" tree */
254 /* Returns a pointer to the found node (or NULL) */
255 TBBT_NODE *
tbbtdless(TBBT_TREE * tree,VOIDP key,TBBT_NODE ** pp)256 tbbtdless(TBBT_TREE * tree, VOIDP key, TBBT_NODE ** pp)
257 {
258 if (tree == NULL)
259 return (NULL);
260 return (tbbtless(tree->root, key, tree->compar, tree->cmparg, pp));
261 }
262
263 /* tbbtindx -- Look up the Nth node (in key order) */
264 /* Returns a pointer to the `indx'th node (or NULL) */
265 /* Bugs(fixed):
266 Added NULL check for 'ptr' in while loop to
267 prevent endless loop condition.
268 Fixed bug where we subtracted children count from the wrong side of the
269 tree. */
270 TBBT_NODE *
tbbtindx(TBBT_NODE * root,int32 indx)271 tbbtindx(TBBT_NODE * root, int32 indx)
272 {
273 TBBT_NODE *ptr = root;
274
275 /* I believe indx is 1 based */
276 if (NULL == ptr || indx < 1)
277 return (NULL);
278 /* Termination condition is if the index equals the number of children on
279 out left plus the current node */
280 while (ptr != NULL && indx != ((int32) LeftCnt(ptr)) + 1 )
281 {
282 if (indx <= (int32) LeftCnt(ptr))
283 {
284 #if 0
285 indx -= LeftCnt(ptr); /* ??....bug */
286 #endif
287 ptr = ptr->Lchild;
288 }
289 else if (HasChild(ptr, RIGHT))
290 { /* subtract children count from leftchild plus current node when
291 we descend into a right branch */
292 indx -= (int32)(LeftCnt(ptr) + 1);
293 ptr = ptr->Rchild;
294 }
295 else
296 return (NULL); /* Only `indx' or fewer nodes in tree */
297 }
298 return (ptr);
299 }
300
301 /* swapkid -- Often refered to as "rotating" nodes. ptr and ptr's `side'
302 * child, kid, are swapped so ptr becomes kid's `Other(side)' child.
303 * Here is how a single swap (rotate) works:
304 *
305 * | --side--> |
306 * (ptr) (kid)
307 * / \ / \
308 * +-A-+ (kid) (ptr) +-C-+
309 * | | / \ / \ | |
310 * |...| +-B-+ +-C-+ +-A-+ +-B-+ |...|
311 * | | | | | | | |
312 * |...| |...| |...| |...|
313 * `deep' contains the relative depths of the subtrees so, since we set
314 * `deep[1]' (the relative depth of subtree [B]) to 0, `deep[2]' is the depth
315 * of [C] minus the depth of [B] (-1, 0, or 1 since `kid' is never too out of
316 * balance) and `deep[0]' is the depth of [A] minus the depth of [B]. These
317 * values are used to compute the balance levels after the rotation. Note that
318 * [A], [B], or [C] can have depth 0 so `link[]' contains threads rather than
319 * pointers to children.
320 */
321 static TBBT_NODE *
swapkid(TBBT_NODE ** root,TBBT_NODE * ptr,intn side)322 swapkid(TBBT_NODE ** root, TBBT_NODE * ptr, intn side)
323 {
324 TBBT_NODE *kid = ptr->link[side]; /* Sibling to be swapped with parent */
325 intn deep[3]; /* Relative depths of three sub-trees involved. */
326 /* 0:ptr->link[Other(side)], 1:kid->link[Other(side)], 2:kid->link[side] */
327 TBBT_FLAG ptrflg; /* New value for ptr->flags (ptr->flags used after set) */
328 TBBT_LEAF plcnt, prcnt, /* current values of the ptr's and kid's leaf count */
329 klcnt, krcnt;
330
331 deep[2] = (deep[1] = 0) + Delta(kid, side);
332 deep[0] = Max(0, deep[2]) + 1 - Delta(ptr, side);
333 kid->Parent = ptr->Parent;
334 ptrflg = (TBBT_FLAG)SetFlags(ptr, side, deep[0],
335 HasChild(ptr, Other(side)) && HasChild(kid, Other(side)));
336 plcnt = LeftCnt(ptr);
337 prcnt = RightCnt(ptr);
338 klcnt = LeftCnt(kid);
339 krcnt = RightCnt(kid);
340 if (HasChild(kid, Other(side)))
341 {
342 ptr->link[side] = kid->link[Other(side)]; /* Real child */
343 ptr->link[side]->Parent = ptr;
344 }
345 else
346 {
347 ptr->link[side] = kid; /* Thread */
348 }
349 /* Update grand parent's pointer: */
350 if (NULL == ptr->Parent)
351 {
352 *root = kid;
353 }
354 else if (ptr /*->Lchild*/ == ptr->Parent->Lchild)
355 {
356 ptr->Parent->Lchild = kid;
357 }
358 else
359 {
360 ptr->Parent->Rchild = kid;
361 }
362 ptr->Parent = kid;
363 kid->link[Other(side)] = ptr;
364 kid->flags = (TBBT_FLAG)SetFlags(kid, Other(side),
365 deep[2] - 1 - Max(deep[0], 0), HasChild(kid, side));
366
367 /* update leaf counts */
368 if (side == LEFT)
369 { /* kid's left count doesn't change, nor ptr's r-count */
370 kid->rcnt = prcnt + krcnt + 1; /* kid's leafs+former parent's leafs+parent */
371 ptr->lcnt = krcnt;
372 } /* end if */
373 else
374 { /* kid's right count doesn't change, nor ptr's l-count */
375 kid->lcnt = plcnt + klcnt + 1; /* kid's leafs+former parent's leafs+parent */
376 ptr->rcnt = klcnt;
377 } /* end if */
378 ptr->flags = ptrflg;
379 return (kid);
380 }
381
382 /* balance -- Move up tree, incrimenting number of left children when needed
383 * and looking for unbalanced ancestors. Adjust all balance factors and re-
384 * balance through "rotation"s when needed.
385 */
386 static VOID
balance(TBBT_NODE ** root,TBBT_NODE * ptr,intn side,intn added)387 balance(TBBT_NODE ** root, TBBT_NODE * ptr, intn side, intn added)
388 {
389 intn deeper = added; /* 1 if sub-tree got longer; -1 if got shorter */
390 intn odelta;
391 intn obal;
392
393 while (NULL != ptr)
394 {
395 odelta = Delta(ptr, side); /* delta before the node was added */
396 obal = UnBal(ptr);
397 if (LEFT == side) /* One more/fewer left child: */
398 if (0 < added)
399 ptr->lcnt++; /* LeftCnt(ptr)++ */
400 else
401 ptr->lcnt--; /* LeftCnt(ptr)-- */
402 else if (0 < added)
403 ptr->rcnt++; /* RightCnt(ptr)++ */
404 else
405 ptr->rcnt--; /* RightCnt(ptr)-- */
406 if (0 != deeper)
407 { /* One leg got longer or shorter: */
408 if ((deeper < 0 && odelta < 0) || (deeper > 0 && odelta > 0))
409 { /* Became too unbalanced: */
410 TBBT_NODE *kid;
411
412 ptr->flags |= TBBT_DOUBLE; /* Mark node too unbalanced */
413 if (deeper < 0) /* Just removed a node: */
414 side = Other(side); /* Swap with child from other side. */
415 else
416 /* Just inserted a node: */ if (ptr->Parent && UnBal(ptr->Parent))
417 {
418 deeper = 0; /* Fix will re-shorten sub-tree. */
419 }
420 kid = ptr->link[side];
421 if (Heavy(kid, Other(side)))
422 { /* Double rotate needed: */
423 kid = swapkid(root, kid, Other(side));
424 ptr = swapkid(root, ptr, side);
425 }
426 else
427 { /* Just rotate parent and kid: */
428 if (HasChild(kid, side)) /* In this case, sub-tree gets */
429 if (ptr->Parent && UnBal(ptr->Parent))
430 {
431 deeper = 0; /* re-lengthened after a node removed. */
432 }
433 ptr = swapkid(root, ptr, side);
434 }
435 }
436 else if (obal)
437 { /* Just became balanced: */
438 ptr->flags &= ~TBBT_UNBAL;
439 if (0 < deeper)
440 { /* Shorter of legs lengthened */
441 ptr->flags |= TBBT_INTERN; /* Mark as internal node now */
442 deeper = 0; /* so max length unchanged */
443 } /* end if */
444 }
445 else if (deeper < 0)
446 { /* Just became unbalanced: */
447 if (ptr->link[Other(side)] != NULL && ptr->link[Other(side)]->Parent == ptr)
448 {
449 ptr->flags |= (TBBT_FLAG)TBBT_HEAVY(Other(side)); /* Other side longer */
450 if (ptr->Parent)
451 if (ptr->Parent->Rchild == ptr) { /* we're the right child */
452 if (Heavy(ptr->Parent, RIGHT) && LeftCnt(ptr->Parent) == 1)
453 deeper = 0;
454 else
455 /* we're the left child */ if (Heavy(ptr->Parent, LEFT))
456 if (ptr->Parent->Rchild && !UnBal(ptr->Parent->Rchild))
457 deeper = 0;
458 }
459 }
460 }
461 else
462 { /* Just became unbalanced: */
463 ptr->flags |= (TBBT_FLAG)TBBT_HEAVY(side); /* 0<deeper: Our side longer */
464 } /* end else */
465 }
466 if (ptr->Parent)
467 {
468 if (ptr == (ptr->Parent->Rchild))
469 side = RIGHT;
470 else
471 side = LEFT;
472 } /* end if */
473 ptr = ptr->Parent; /* Move up the tree */
474 }
475 /* total tree depth += deeper; */
476 }
477 /* Here is how rotatation rebalances a tree:
478 * Either the deletion of a node shortened the sub-tree [A] (to length `h')
479 * while [B] or [C] or both are length `h+1' or the addition of a node
480 * lengthened [B] or [C] to length `h+1' while the other and [A] are both
481 * length `h'. Each case changes `ptr' from being "right heavy" to being
482 * overly unbalanced.
483 * This | Becomes: |
484 * sub-tree: (ptr) (kid)
485 * / \ --side--> / \
486 * +-A-+ (kid) (ptr) +-C-+
487 * | | / \ / \ | |
488 * | h | +-B-+ +-C-+ +-A-+ +-B-+ | h |
489 * | | | | | | | | | | | |
490 * +---+ | h | | h | | h | | h | +---+
491 * : - : | | | | | | | | : 1 :
492 * `- -' +---+ +---+ +---+ +---+ + - +
493 * : 1 : : 1 : : 1 :
494 * + - + + - + + - +
495 *
496 * However, if [B] is long (h+1) while [C] is short (h), a double rotate is
497 * required to rebalance. In this case, [A] was shortened or [X] or [Y] was
498 * lengthened so [A] is length `h' and one of [X] and [Y] is length `h' while
499 * the other is length `h-1'. Swap `kid' with `babe' then `ptr' with `babe'.
500 * This | Becomes: |
501 * sub-tree: (ptr) (babe)
502 * / \ --side--> / \
503 * +-A-+ (kid) (ptr) (kid)
504 * | | / \ / \ / \
505 * | h | (babe) +-C-+ +-A-+ +-X-+ +-Y-+ +-C-+
506 * | | / \ | | | | |h-1| |h-1| | |
507 * +---+ +-X-+ +-Y-+ | h | | h | +---+ +---+ | h |
508 * : - : |h-1| |h-1| | | | | : 1 : : 1 : | |
509 * `- -' +---+ +---+ +---+ +---+ + - + + - + +---+
510 * : 1 : : 1 :
511 * + - + + - +
512 *
513 * Note that in the node insertion cases total sub-tree length always increases
514 * by one then decreases again so after the rotation(s) no more rebalancing is
515 * required. In the node removal cases, the single rotation reduces total sub-
516 * tree length unless [B] is length `h+1' (`ptr' ends of "right heavy") while
517 * the double rotation ALWAYS reduces total sub-tree length. Thus removing a
518 * single node can require log(N) rotations for rebalancing. On average, only
519 * are usually required.
520 */
521
522 /* Returns pointer to inserted node (or NULL) */
523 TBBT_NODE *
tbbtins(TBBT_NODE ** root,VOIDP item,VOIDP key,intn (* compar)(VOIDP,VOIDP,intn),intn arg)524 tbbtins(TBBT_NODE ** root, VOIDP item, VOIDP key, intn (*compar)
525 (VOIDP /* k1 */, VOIDP /* k2 */, intn /* arg */), intn arg)
526 {
527 intn cmp;
528 TBBT_NODE *ptr, *parent;
529
530 if (NULL != tbbtfind(*root, (key ? key : item), compar, arg, &parent)
531 || NULL == (ptr = tbbt_get_node()))
532 return (NULL);
533 ptr->data = item;
534 ptr->key = key ? key : item;
535 ptr->Parent = parent;
536 ptr->flags = 0L; /* No children on either side */
537 ptr->lcnt = 0;
538 ptr->rcnt = 0;
539 if (NULL == parent)
540 { /* Adding first node to tree: */
541 *root = ptr;
542 ptr->Lchild = ptr->Rchild = NULL;
543 return (ptr);
544 }
545 cmp = KEYcmp(ptr->key, parent->key, arg);
546 if (cmp < 0)
547 {
548 ptr->Lchild = parent->Lchild; /* Parent's thread now new node's */
549 ptr->Rchild = parent; /* New nodes right thread is parent */
550 parent->Lchild = ptr; /* Parent now has a left child */
551 }
552 else
553 {
554 ptr->Rchild = parent->Rchild;
555 ptr->Lchild = parent;
556 parent->Rchild = ptr;
557 }
558 balance(root, parent, (cmp < 0) ? LEFT : RIGHT, 1);
559 return (ptr);
560 }
561
562 /* tbbtdins -- Insert a node into a "described" tree */
563 /* Returns a pointer to the inserted node */
564 TBBT_NODE *
tbbtdins(TBBT_TREE * tree,VOIDP item,VOIDP key)565 tbbtdins(TBBT_TREE * tree, VOIDP item, VOIDP key)
566 {
567 TBBT_NODE *ret_node; /* the node to return */
568
569 if (tree == NULL)
570 return (NULL);
571 ret_node = tbbtins(&(tree->root), item, key, tree->compar, tree->cmparg);
572 if (ret_node != NULL)
573 tree->count++;
574 return (ret_node);
575 }
576
577 /* tbbtrem -- Remove a node from a tree. You pass in the address of the
578 * pointer to the root node of the tree along, a pointer to the node you wish
579 * to remove, and optionally the address of a pointer to hold the address of
580 * the key value of the deleted node. The second argument is usually the
581 * result from a lookup function call (tbbtfind, tbbtdfind, or tbbtindx) so if
582 * it is NULL, tbbtrem returns NULL. Otherwise tbbtrem removes the node from
583 * the tree and returns a pointer to the data item for that node and, if the
584 * third argument is not NULL, the address of the key value for the deleted
585 * node is placed in the buffer that it points to.
586 */
587 /* Data item pointer of deleted node is returned */
588 VOIDP
tbbtrem(TBBT_NODE ** root,TBBT_NODE * node,VOIDP * kp)589 tbbtrem(TBBT_NODE ** root, TBBT_NODE * node, VOIDP *kp)
590 {
591 TBBT_NODE *leaf; /* Node with one or zero children */
592 TBBT_NODE *par; /* Parent of `leaf' */
593 TBBT_NODE *next; /* Next/prev node near `leaf' (`leaf's `side' thread) */
594 intn side; /* `leaf' is `side' child of `par' */
595 VOIDP data; /* Saved pointer to data item of deleted node */
596
597 if (NULL == root || NULL == node)
598 return (NULL); /* Argument couldn't find node to delete */
599 data = node->data; /* Save pointer to data item to be returned at end */
600 if (NULL != kp)
601 *kp = node->key;
602 /* If the node to be removed is "internal" (children on both sides), we
603 * replace it with it's previous (or next) node in the tree and delete that
604 * previous (next) node (which has one or no children) instead. */
605 if (Intern(node))
606 { /* Replace with a non-internal node: */
607 if (Heavy(node, RIGHT))
608 { /* Pick "near-leaf" node from the */
609 side = LEFT; /* heavier of the sub-trees. */
610 }
611 else if (Heavy(node, LEFT))
612 {
613 side = RIGHT;
614 }
615 else
616 { /* If no sub-tree heavier, pick at "random" for "better */
617 side = (0x10 & *(short *) &node) ? LEFT : RIGHT; /* balance" */
618 }
619 leaf = tbbt_nbr(next = node, Other(side));
620 par = leaf->Parent;
621 if (par == next)
622 { /* Case 2x: `node' had exactly 2 descendants */
623 side = Other(side); /* Transform this to Case 2 */
624 next = leaf->link[side];
625 }
626 node->data = leaf->data;
627 node->key = leaf->key;
628 }
629 else
630 { /* Node has one or zero children: */
631 leaf = node; /* Simply remove THIS node */
632 par = leaf->Parent;
633 if (NULL == par)
634 { /* Case 3: Remove root (of 1- or 2-node tree) */
635 side = (intn) UnBal(node); /* Which side root has a child on */
636 if (side)
637 { /* Case 3a: Remove root of 2-node tree: */
638 *root = leaf = node->link[side];
639 leaf->Parent = leaf->link[Other(side)] = NULL;
640 leaf->flags = 0; /* No left children, balanced, not internal */
641 }
642 else
643 { /* Case 3b: Remove last node of tree: */
644 *root = NULL;
645 } /* end else */
646 tbbt_release_node(node);
647 return (data);
648 }
649 side = (par->Rchild == leaf) ? RIGHT : LEFT;
650 next = leaf->link[side];
651 }
652 /* Now the deletion has been reduced to the following cases (and Case 3 has
653 * been handled completely above and Case 2x has been transformed into
654 * Case 2). `leaf' is a node with one or zero children that we are going
655 * to remove. `next' points where the `side' thread of `leaf' points.
656 * `par' is the parent of `leaf'. The only posibilities (not counting
657 * left/right reversals) are shown below:
658 * [Case 1] [Case 2] [Case 2x]
659 * (next) (next) ^ (next & par)
660 * / ^ \ / ^ \ | / ^ \
661 * . . . | . . . | | (leaf) /
662 * / | / | \_/ \_/
663 * (par) | (par) | ^threads^
664 * \ | \ |
665 * (leaf) / (leaf) / [Case 3a] [Case 3b]
666 * / ^ \_/<thread \_/<thread (root)
667 * (n) / \ (root)
668 * \_/<thread --"side"--> (n)
669 * Note that in Cases 1 and 2, `leaf's `side' thread can be NULL making
670 * `next' NULL as well. If you remove a node from a 2-node tree, removing
671 * the root falls into Case 3a while removing the only leaf falls into
672 * Case 2 (with `next' NULL and `par' the root node). */
673 if (!UnBal(leaf))
674 { /* Case 2: `leaf' has no children: */
675 par->link[side] = leaf->link[side];
676 par->flags &= (TBBT_FLAG)(~(TBBT_INTERN | TBBT_HEAVY(side)));
677 }
678 else
679 { /* Case 1: `leaf' has one child: */
680 TBBT_NODE *n;
681
682 if (HasChild(leaf, side))
683 { /* two-in-a-row cases */
684 n = leaf->link[side];
685 par->link[side] = n;
686 n->Parent = par;
687 if (HasChild(n, Other(side)))
688 while (HasChild(n, Other(side)))
689 n = n->link[Other(side)];
690 n->link[Other(side)] = par;
691 } /* end if */
692 else
693 { /* zig-zag cases */
694 n = leaf->link[Other(side)];
695 par->link[side] = n;
696 n->Parent = par;
697 if (HasChild(n, side))
698 while (HasChild(n, side))
699 n = n->link[side];
700 n->link[side] = next;
701 } /* end else */
702 }
703 tbbt_release_node(leaf);
704 balance(root, par, side, -1);
705 ((TBBT_TREE *) root)->count--;
706 return (data);
707 }
708
709 /* tbbtdmake - Allocate a new tree description record for an empty tree */
710 /* Returns a pointer to the description record */
711 TBBT_TREE *
tbbtdmake(intn (* cmp)(VOIDP,VOIDP,intn),intn arg,uintn fast_compare)712 tbbtdmake(intn (*cmp) (VOIDP /* k1 */, VOIDP /* k2 */, intn /* arg */), intn arg, uintn fast_compare)
713 {
714 TBBT_TREE *tree = Alloc(1, TBBT_TREE);
715
716 if (NULL == tree)
717 return (NULL);
718 tree->root = NULL;
719 tree->count = 0;
720 tree->fast_compare=fast_compare;
721 tree->compar = cmp;
722 tree->cmparg = arg;
723 return (tree);
724 }
725
726 #ifdef WASTE_STACK
727 /* You can have a very simple recursive version that wastes lots of stack
728 * space, this next less-simple recursive version that wastes less stack space,
729 * or the last non-recursive version which isn't simple but saves stack space.
730 */
731 static VOID(*FD) (VOIDP item), (*FK) (VOIDP key);
732 static VOID
tbbt1free(TBBT_NODE * node)733 tbbt1free(TBBT_NODE * node)
734 {
735 if (HasChild(node, LEFT))
736 tbbt1free(node->Lchild);
737 if (HasChild(node, RIGHT))
738 tbbt1free(node->Rchild);
739 if (NULL != FD)
740 (*FD) (node->data);
741 if (NULL != FK)
742 (*FK) (node->key);
743 tbbt_release_node(node);
744 }
745
746 VOID
tbbtfree(TBBT_NODE ** root,VOID (* fd)(VOIDP item),VOID (* fk)(VOIDP key))747 tbbtfree(TBBT_NODE ** root, VOID(*fd) (VOIDP item), VOID(*fk) (VOIDP key))
748 {
749 if (NULL == *root)
750 return;
751 FD = fd;
752 FK = fk;
753 tbbt1free(*root);
754 *root = NULL;
755 }
756 #else /* WASTE_STACK */
757
758 /* tbbtfree() - Free an entire tree not allocated with tbbtdmake(). */
759 VOID
tbbtfree(TBBT_NODE ** root,VOID (* fd)(VOIDP),VOID (* fk)(VOIDP))760 tbbtfree(TBBT_NODE ** root, VOID(*fd) (VOIDP /* item */), VOID(*fk) (VOIDP /* key */))
761 {
762 TBBT_NODE *par, *node = *root;
763
764 while (NULL != *root)
765 { /* While nodes left to be free()d */
766 /* First time at this node (just moved down a new leg of tree) */
767 if (!HasChild(node, LEFT))
768 node->Lchild = NULL;
769 if (!HasChild(node, RIGHT))
770 node->Rchild = NULL;
771 do
772 {
773 par = NULL; /* Assume we aren't ready to move up tree yet */
774 if (NULL != node->Lchild)
775 node = node->Lchild; /* Move down this leg next */
776 else if (NULL != node->Rchild)
777 node = node->Rchild; /* Move down this leg next */
778 else
779 { /* No children; free node an move up: */
780 par = node->Parent; /* Move up tree (stay in loop) */
781 if (NULL != fd)
782 (*fd) (node->data);
783 if (NULL != fk)
784 (*fk) (node->key);
785 if (NULL == par) /* Just free()d last node */
786 *root = NULL; /* NULL=par & NULL=*root gets fully out */
787 else if (node == par->Lchild)
788 par->Lchild = NULL; /* Now no longer has this child */
789 else
790 par->Rchild = NULL; /* Ditto */
791
792 tbbt_release_node(node);
793
794 node = par; /* Move up tree; remember which node to do next */
795 }
796 }
797 while (NULL != par); /* While moving back up tree */
798 }
799 }
800 #endif /* WASTE_STACK */
801
802 VOID
tbbtprint(TBBT_NODE * node)803 tbbtprint(TBBT_NODE * node)
804 {
805 if (node == NULL)
806 return;
807 printf("node=%p, key=%p, data=%p, flags=%x\n", node, node->key, node->data, (unsigned) node->flags);
808 printf("Lcnt=%d, Rcnt=%d\n", (int) node->lcnt, (int) node->rcnt);
809 printf("*key=%d\n", (int) *(int32 *) (node->key));
810 printf("Lchild=%p, Rchild=%p, Parent=%p\n", node->Lchild, node->Rchild, node->Parent);
811 } /* end tbbtprint() */
812
813 VOID
tbbt1dump(TBBT_NODE * node,intn method)814 tbbt1dump(TBBT_NODE * node, intn method)
815 {
816 if (node == NULL)
817 return;
818 switch (method)
819 {
820 case -1: /* Pre-Order Traversal */
821 tbbtprint(node);
822 if (HasChild(node, LEFT))
823 tbbt1dump(node->Lchild, method);
824 if (HasChild(node, RIGHT))
825 tbbt1dump(node->Rchild, method);
826 break;
827
828 case 1: /* Post-Order Traversal */
829 if (HasChild(node, LEFT))
830 tbbt1dump(node->Lchild, method);
831 if (HasChild(node, RIGHT))
832 tbbt1dump(node->Rchild, method);
833 tbbtprint(node);
834 break;
835
836 case 0: /* In-Order Traversal */
837 default:
838 if (HasChild(node, LEFT))
839 tbbt1dump(node->Lchild, method);
840 tbbtprint(node);
841 if (HasChild(node, RIGHT))
842 tbbt1dump(node->Rchild, method);
843 break;
844
845 } /* end switch() */
846 } /* end tbbt1dump() */
847
848 VOID
tbbtdump(TBBT_TREE * tree,intn method)849 tbbtdump(TBBT_TREE * tree, intn method)
850 {
851 if (tree != NULL && *(TBBT_NODE **) tree != NULL)
852 {
853 printf("Number of nodes in the tree: %ld\n", tree->count);
854 tbbt1dump(tree->root, method);
855 } /* end if */
856 else
857 printf("Tree is empty\n");
858 } /* end tbbtdump() */
859
860 VOID
tbbt_printNode(TBBT_NODE * node,VOID (* key_dump)(VOID *,VOID *))861 tbbt_printNode(TBBT_NODE * node, VOID(*key_dump)(VOID *,VOID *))
862 {
863
864 if (node == NULL)
865 {
866 printf("ERROR: null node pointer\n");
867 return;
868 }
869 printf("node=%p, flags=%x, Lcnt=%ld, Rcnt=%ld\n", node, (unsigned)node->flags,
870 (long)node->lcnt, (long)node->rcnt);
871 printf("Lchild=%p, Rchild=%p, Parent=%p\n", node->Lchild, node->Rchild, node->Parent);
872 if (key_dump != NULL)
873 {
874 (*key_dump)(node->key,node->data);
875 }
876 fflush(stdout);
877 #if 0
878 printf("Lcnt=%d, Rcnt=%d\n", (int) node->lcnt, (int) node->rcnt);
879 printf("*key=%d\n", (int) *(int32 *) (node->key));
880 printf("Lchild=%p, Rchild=%p, Parent=%p\n", node->Lchild, node->Rchild, node->Parent);
881 #endif
882 } /* end tbbt_printNode() */
883
884 VOID
tbbt_dumpNode(TBBT_NODE * node,VOID (* key_dump)(VOID *,VOID *),intn method)885 tbbt_dumpNode(TBBT_NODE *node, VOID (*key_dump)(VOID *,VOID *),
886 intn method)
887 {
888 if (node == NULL)
889 return;
890 switch (method)
891 {
892 case -1: /* Pre-Order Traversal */
893 tbbt_printNode(node, key_dump);
894 if (HasChild(node, LEFT))
895 tbbt_dumpNode(node->Lchild, key_dump, method);
896 if (HasChild(node, RIGHT))
897 tbbt_dumpNode(node->Rchild, key_dump, method);
898 break;
899
900 case 1: /* Post-Order Traversal */
901 if (HasChild(node, LEFT))
902 tbbt_dumpNode(node->Lchild, key_dump, method);
903 if (HasChild(node, RIGHT))
904 tbbt_dumpNode(node->Rchild, key_dump, method);
905 tbbt_printNode(node, key_dump);
906 break;
907
908 case 0: /* In-Order Traversal */
909 default:
910 if (HasChild(node, LEFT))
911 tbbt_dumpNode(node->Lchild, key_dump, method);
912 tbbt_printNode(node, key_dump);
913 if (HasChild(node, RIGHT))
914 tbbt_dumpNode(node->Rchild, key_dump, method);
915 break;
916
917 } /* end switch() */
918 } /* end tbbt_dumpNode() */
919
920 VOID
tbbt_dump(TBBT_TREE * ptree,VOID (* key_dump)(VOID *,VOID *),intn method)921 tbbt_dump(TBBT_TREE *ptree, VOID (*key_dump)(VOID *,VOID *), intn method)
922 {
923 TBBT_TREE *tree;
924
925 tree = (TBBT_TREE *) ptree;
926 printf("TBBT-tree dump %p:\n\n",ptree);
927 printf("capacity = %ld\n",(long)tree->count);
928 printf("\n");
929 tbbt_dumpNode(tree->root,key_dump, method);
930 return;
931 }
932
933 /* Always returns NULL */
934 TBBT_TREE *
tbbtdfree(TBBT_TREE * tree,VOID (* fd)(VOIDP),VOID (* fk)(VOIDP))935 tbbtdfree(TBBT_TREE * tree, VOID(*fd) (VOIDP /* item */), VOID(*fk) (VOIDP /* key */))
936 {
937 if (tree == NULL)
938 return (NULL);
939
940 tbbtfree(&tree->root, fd, fk);
941 Free(tree);
942 return (NULL);
943 }
944
945 /* returns the number of nodes in the tree */
946 long
tbbtcount(TBBT_TREE * tree)947 tbbtcount(TBBT_TREE * tree)
948 {
949 if (tree == NULL)
950 return (-1);
951 else
952 return ((long)tree->count);
953 }
954
955 /******************************************************************************
956 NAME
957 tbbt_get_node - Gets a tbbt node
958
959 DESCRIPTION
960 Either gets a tbbt node from the free list (if there is one available)
961 or allocates a node.
962
963 RETURNS
964 Returns tbbt ptr if successful and NULL otherwise
965
966 *******************************************************************************/
tbbt_get_node(void)967 static TBBT_NODE *tbbt_get_node(void)
968 {
969 TBBT_NODE *ret_value=NULL;
970
971 if(tbbt_free_list!=NULL)
972 {
973 ret_value=tbbt_free_list;
974 tbbt_free_list=tbbt_free_list->Lchild;
975 } /* end if */
976 else
977 ret_value=(TBBT_NODE *)Alloc(1,TBBT_NODE);
978
979 return ret_value;
980 } /* end tbbt_get_node() */
981
982 /******************************************************************************
983 NAME
984 tbbt_release_node - Releases a tbbt node
985
986 DESCRIPTION
987 Puts a tbbt node into the free list
988
989 RETURNS
990 No return value
991
992 *******************************************************************************/
tbbt_release_node(TBBT_NODE * nod)993 static void tbbt_release_node(TBBT_NODE *nod)
994 {
995 /* Insert the atom at the beginning of the free list */
996 nod->Lchild=tbbt_free_list;
997 tbbt_free_list=nod;
998 } /* end tbbt_release_node() */
999
1000 /*--------------------------------------------------------------------------
1001 NAME
1002 tbbt_shutdown
1003 PURPOSE
1004 Terminate various static buffers.
1005 USAGE
1006 intn tbbt_shutdown()
1007 RETURNS
1008 Returns SUCCEED/FAIL
1009 DESCRIPTION
1010 Free various buffers allocated in the tbbt routines.
1011 GLOBAL VARIABLES
1012 COMMENTS, BUGS, ASSUMPTIONS
1013 Should only ever be called by the "atexit" function HDFend
1014 EXAMPLES
1015 REVISION LOG
1016 --------------------------------------------------------------------------*/
1017 intn
tbbt_shutdown(void)1018 tbbt_shutdown(void)
1019 {
1020 TBBT_NODE *curr;
1021
1022 /* Release the free-list if it exists */
1023 if(tbbt_free_list!=NULL)
1024 {
1025 while(tbbt_free_list!=NULL)
1026 {
1027 curr=tbbt_free_list;
1028 tbbt_free_list=tbbt_free_list->Lchild;
1029 Free(curr);
1030 } /* end while */
1031 } /* end if */
1032 return (SUCCEED);
1033 } /* end tbbt_shutdown() */
1034
1035