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 Bacula® - The Network Backup Solution
17 Copyright (C) 2005-2006 Free Software Foundation Europe e.V.
19 The main author of Bacula is Kern Sibbald, with contributions from
20 many others, a complete list can be found in the file AUTHORS.
21 This program is Free Software; you can redistribute it and/or
22 modify it under the terms of version two of the GNU General Public
23 License as published by the Free Software Foundation plus additions
24 that are listed in the file LICENSE.
26 This program is distributed in the hope that it will be useful, but
27 WITHOUT ANY WARRANTY; without even the implied warranty of
28 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
29 General Public License for more details.
31 You should have received a copy of the GNU General Public License
32 along with this program; if not, write to the Free Software
33 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
36 Bacula® is a registered trademark of John Walker.
37 The licensor of Bacula is the Free Software Foundation Europe
38 (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
39 Switzerland, email:ftf@fsfeurope.org.
45 /* ===================================================================
50 * Insert an item in the tree, but only if it is unique
51 * otherwise, the item is returned non inserted
52 * The big trick is keeping the tree balanced after the
53 * insert. We use a parent pointer to make it simpler and
56 * Returns: item if item inserted
57 * other_item if same value already exists (item not inserted)
59 bnode *btree::insert(bnode *item, int compare(bnode *item1, bnode *item2))
62 bnode *last = NULL; /* last leaf if not found */
70 comp = compare(item, x);
73 } else if (comp > 0) {
80 if (found) { /* found? */
81 return found; /* yes, return item found */
83 /* Handle empty tree */
90 /* Not found, so insert it on appropriate side of tree */
100 /* Now we must walk up the tree balancing it */
102 while (x != head && x->parent->red) {
103 if (x->parent == x->parent->parent->left) {
104 /* Look at the right side of our grandparent */
105 y = x->parent->parent->right;
107 /* our parent must be black */
108 x->parent->red = false;
110 x->parent->parent->red = true;
111 x = x->parent->parent; /* move up to grandpa */
113 if (x == x->parent->right) { /* right side of parent? */
117 /* make parent black too */
118 x->parent->red = false;
119 x->parent->parent->red = true;
120 right_rotate(x->parent->parent);
123 /* Look at left side of our grandparent */
124 y = x->parent->parent->left;
126 x->parent->red = false;
128 x->parent->parent->red = true;
129 x = x->parent->parent; /* move up to grandpa */
131 if (x == x->parent->left) {
135 /* make parent black too */
136 x->parent->red = false;
137 x->parent->parent->red = true;
138 left_rotate(x->parent->parent);
142 /* Make sure the head is always black */
151 bnode *btree::search(bnode *item, int compare(bnode *item1, bnode *item2))
159 comp = compare(item, x);
162 } else if (comp > 0) {
173 * Get first item (i.e. lowest value)
175 bnode *btree::first(void)
193 * This is a non-recursive btree walk routine that returns
194 * the items one at a time in order. I've never seen a
195 * non-recursive tree walk routine published that returns
196 * one item at a time rather than doing a callback.
198 * Return the next item in sorted order. We assume first()
199 * was called once before calling this routine.
200 * We always go down as far as we can to the left, then up, and
201 * down one to the right, and again down as far as we can to the
204 * Returns: pointer to next larger item
205 * NULL when no more items in tree
207 bnode *btree::next(bnode *item)
212 if ((down && !x->left && x->right) || (!down && x->right)) {
213 /* Move down to right one */
216 /* Then all the way down left */
223 /* We have gone down all we can, so now go up */
225 /* If at head, we are done */
229 /* Move up in tree */
231 /* if coming from right, continue up */
232 if (x->parent->right == x) {
236 /* Coming from left, go up one -- ie. return parent */
242 * Similer to next(), but visits all right nodes when
243 * coming up the tree.
245 bnode *btree::any(bnode *item)
250 if ((down && !x->left && x->right) || (!down && x->right)) {
251 /* Move down to right one */
254 /* Then all the way down left */
261 /* We have gone down all we can, so now go up */
263 /* If at head, we are done */
268 /* Go up one and return parent */
274 /* x is item, y is below and to right, then rotated to below left */
275 void btree::left_rotate(bnode *item)
286 y->parent = x->parent;
287 /* if no parent then we have a new head */
290 } else if (x == x->parent->left) {
293 x->parent->right = y;
299 void btree::right_rotate(bnode *item)
307 x->right->parent = y;
309 x->parent = y->parent;
310 /* if no parent then we have a new head */
313 } else if (y == y->parent->left) {
316 y->parent->right = x;
323 void btree::remove(bnode *item)
327 /* Destroy the tree contents. Not totally working */
328 void btree::destroy()
333 // printf("head=%p first=%p left=%p right=%p\n", head, x, x->left, x->right);
335 for ( ; (y=any(x)); ) {
336 /* Prune the last item */
338 if (x == x->parent->left) {
339 x->parent->left = NULL;
340 } else if (x == x->parent->right) {
341 x->parent->right = NULL;
344 if (!x->left && !x->right) {
348 // if (num_items<30) {
349 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
351 free((void *)x); /* free previous node */
354 x = y; /* save last node */
360 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
365 // printf("Free head\n");
368 // printf("free nitems=%d\n", num_items);
382 static int my_compare(bnode *item1, bnode *item2)
386 jcr1 = (MYJCR *)item1;
387 jcr2 = (MYJCR *)item2;
388 comp = strcmp(jcr1->buf, jcr2->buf);
389 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
401 /* Now do a binary insert for the tree */
402 jcr_chain = New(btree());
404 printf("append %d items\n", CNT*CNT*CNT);
407 for (int i=0; i<CNT; i++) {
408 for (int j=0; j<CNT; j++) {
409 for (int k=0; k<CNT; k++) {
411 if ((count & 0x3FF) == 0) {
412 Dmsg1(000, "At %d\n", count);
414 jcr = (MYJCR *)malloc(sizeof(MYJCR));
415 memset(jcr, 0, sizeof(MYJCR));
416 jcr->buf = bstrdup(buf);
417 // printf("buf=%p %s\n", jcr, jcr->buf);
418 jcr1 = (MYJCR *)jcr_chain->insert((bnode *)jcr, my_compare);
420 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
430 printf("%d items appended\n", CNT*CNT*CNT);
431 printf("num_items=%d\n", jcr_chain->size());
433 jcr = (MYJCR *)malloc(sizeof(MYJCR));
434 memset(jcr, 0, sizeof(MYJCR));
436 jcr->buf = bstrdup("a");
437 if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
438 printf("One less failed!!!! Got: %s\n", jcr1->buf);
440 printf("One less: OK\n");
444 jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
445 if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
446 printf("One greater failed!!!! Got:%s\n", jcr1->buf);
448 printf("One greater: OK\n");
452 jcr->buf = bstrdup("AAA");
453 if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
454 printf("Search for AAA got %s\n", jcr1->buf);
456 printf("Search for AAA not found\n");
460 jcr->buf = bstrdup("ZZZ");
461 if ((jcr1 = (MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
462 printf("Search for ZZZ got %s\n", jcr1->buf);
464 printf("Search for ZZZ not found\n");
470 printf("Find each of %d items in tree.\n", count);
471 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
472 // printf("Got: %s\n", jcr->buf);
473 if (!jcr_chain->search((bnode *)jcr, my_compare)) {
474 printf("btree binary_search item not found = %s\n", jcr->buf);
477 printf("Free each of %d items in tree.\n", count);
478 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
479 // printf("Free: %p %s\n", jcr, jcr->buf);
483 printf("num_items=%d\n", jcr_chain->size());