2 * Bacula red-black binary tree routines.
4 * btree is a binary tree with the links being in the data item.
6 * Developped in part from ideas obtained from several online University
9 * Kern Sibbald, November MMV
15 Copyright (C) 2005 Kern Sibbald
17 This program is free software; you can redistribute it and/or
18 modify it under the terms of the GNU General Public License
19 version 2 as amended with additional clauses defined in the
20 file LICENSE in the main source directory.
22 This program is distributed in the hope that it will be useful,
23 but WITHOUT ANY WARRANTY; without even the implied warranty of
24 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
25 the file LICENSE for additional details.
32 /* ===================================================================
37 * Insert an item in the tree, but only if it is unique
38 * otherwise, the item is returned non inserted
39 * The big trick is keeping the tree balanced after the
40 * insert. We use a parent pointer to make it simpler and
43 * Returns: item if item inserted
44 * other_item if same value already exists (item not inserted)
46 bnode *btree::insert(bnode *item, int compare(bnode *item1, bnode *item2))
49 bnode *last = NULL; /* last leaf if not found */
57 comp = compare(item, x);
60 } else if (comp > 0) {
67 if (found) { /* found? */
68 return found; /* yes, return item found */
70 /* Handle empty tree */
77 /* Not found, so insert it on appropriate side of tree */
87 /* Now we must walk up the tree balancing it */
89 while (x != head && x->parent->red) {
90 if (x->parent == x->parent->parent->left) {
91 /* Look at the right side of our grandparent */
92 y = x->parent->parent->right;
94 /* our parent must be black */
95 x->parent->red = false;
97 x->parent->parent->red = true;
98 x = x->parent->parent; /* move up to grandpa */
100 if (x == x->parent->right) { /* right side of parent? */
104 /* make parent black too */
105 x->parent->red = false;
106 x->parent->parent->red = true;
107 right_rotate(x->parent->parent);
110 /* Look at left side of our grandparent */
111 y = x->parent->parent->left;
113 x->parent->red = false;
115 x->parent->parent->red = true;
116 x = x->parent->parent; /* move up to grandpa */
118 if (x == x->parent->left) {
122 /* make parent black too */
123 x->parent->red = false;
124 x->parent->parent->red = true;
125 left_rotate(x->parent->parent);
129 /* Make sure the head is always black */
138 bnode *btree::search(bnode *item, int compare(bnode *item1, bnode *item2))
146 comp = compare(item, x);
149 } else if (comp > 0) {
160 * Get first item (i.e. lowest value)
162 bnode *btree::first(void)
180 * This is a non-recursive btree walk routine that returns
181 * the items one at a time in order. I've never seen a
182 * non-recursive tree walk routine published that returns
183 * one item at a time rather than doing a callback.
185 * Return the next item in sorted order. We assume first()
186 * was called once before calling this routine.
187 * We always go down as far as we can to the left, then up, and
188 * down one to the right, and again down as far as we can to the
191 * Returns: pointer to next larger item
192 * NULL when no more items in tree
194 bnode *btree::next(bnode *item)
199 if ((down && !x->left && x->right) || (!down && x->right)) {
200 /* Move down to right one */
203 /* Then all the way down left */
210 /* We have gone down all we can, so now go up */
212 /* If at head, we are done */
216 /* Move up in tree */
218 /* if coming from right, continue up */
219 if (x->parent->right == x) {
223 /* Coming from left, go up one -- ie. return parent */
229 * Similer to next(), but visits all right nodes when
230 * coming up the tree.
232 bnode *btree::any(bnode *item)
237 if ((down && !x->left && x->right) || (!down && x->right)) {
238 /* Move down to right one */
241 /* Then all the way down left */
248 /* We have gone down all we can, so now go up */
250 /* If at head, we are done */
255 /* Go up one and return parent */
261 /* x is item, y is below and to right, then rotated to below left */
262 void btree::left_rotate(bnode *item)
273 y->parent = x->parent;
274 /* if no parent then we have a new head */
277 } else if (x == x->parent->left) {
280 x->parent->right = y;
286 void btree::right_rotate(bnode *item)
294 x->right->parent = y;
296 x->parent = y->parent;
297 /* if no parent then we have a new head */
300 } else if (y == y->parent->left) {
303 y->parent->right = x;
310 void btree::remove(bnode *item)
314 /* Destroy the tree contents. Not totally working */
315 void btree::destroy()
320 // printf("head=%p first=%p left=%p right=%p\n", head, x, x->left, x->right);
322 for ( ; (y=any(x)); ) {
323 /* Prune the last item */
325 if (x == x->parent->left) {
326 x->parent->left = NULL;
327 } else if (x == x->parent->right) {
328 x->parent->right = NULL;
331 if (!x->left && !x->right) {
335 // if (num_items<30) {
336 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
338 free((void *)x); /* free previous node */
341 x = y; /* save last node */
347 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
352 // printf("Free head\n");
355 // printf("free nitems=%d\n", num_items);
369 static int my_compare(bnode *item1, bnode *item2)
373 jcr1 = (MYJCR *)item1;
374 jcr2 = (MYJCR *)item2;
375 comp = strcmp(jcr1->buf, jcr2->buf);
376 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
388 /* Now do a binary insert for the tree */
389 jcr_chain = New(btree());
391 printf("append %d items\n", CNT*CNT*CNT);
394 for (int i=0; i<CNT; i++) {
395 for (int j=0; j<CNT; j++) {
396 for (int k=0; k<CNT; k++) {
398 if ((count & 0x3FF) == 0) {
399 Dmsg1(000, "At %d\n", count);
401 jcr = (MYJCR *)malloc(sizeof(MYJCR));
402 memset(jcr, 0, sizeof(MYJCR));
403 jcr->buf = bstrdup(buf);
404 // printf("buf=%p %s\n", jcr, jcr->buf);
405 jcr1 = (MYJCR *)jcr_chain->insert((bnode *)jcr, my_compare);
407 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
417 printf("%d items appended\n", CNT*CNT*CNT);
418 printf("num_items=%d\n", jcr_chain->size());
420 jcr = (MYJCR *)malloc(sizeof(MYJCR));
421 memset(jcr, 0, sizeof(MYJCR));
423 jcr->buf = bstrdup("a");
424 if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
425 printf("One less failed!!!! Got: %s\n", jcr1->buf);
427 printf("One less: OK\n");
431 jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
432 if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
433 printf("One greater failed!!!! Got:%s\n", jcr1->buf);
435 printf("One greater: OK\n");
439 jcr->buf = bstrdup("AAA");
440 if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
441 printf("Search for AAA got %s\n", jcr1->buf);
443 printf("Search for AAA not found\n");
447 jcr->buf = bstrdup("ZZZ");
448 if ((jcr1 = (MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
449 printf("Search for ZZZ got %s\n", jcr1->buf);
451 printf("Search for ZZZ not found\n");
457 printf("Find each of %d items in tree.\n", count);
458 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
459 // printf("Got: %s\n", jcr->buf);
460 if (!jcr_chain->search((bnode *)jcr, my_compare)) {
461 printf("btree binary_search item not found = %s\n", jcr->buf);
464 printf("Free each of %d items in tree.\n", count);
465 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
466 // printf("Free: %p %s\n", jcr, jcr->buf);
470 printf("num_items=%d\n", jcr_chain->size());