2 * Bacula red-black binary tree routines.
4 * rblist 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-2007 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 and included
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.
44 /* ===================================================================
49 * Insert an item in the tree, but only if it is unique
50 * otherwise, the item is returned non inserted
51 * The big trick is keeping the tree balanced after the
52 * insert. We use a parent pointer to make it simpler and
55 * Returns: item if item inserted
56 * other_item if same value already exists (item not inserted)
58 void *rblist::insert(void *item, int compare(void *item1, void *item2))
61 void *last = NULL; /* last leaf if not found */
69 comp = compare(item, x);
72 } else if (comp > 0) {
79 if (found) { /* found? */
80 return found; /* yes, return item found */
83 set_right(item, NULL);
84 set_parent(item, NULL);
86 /* Handle empty tree */
93 /* Not found, so insert it on appropriate side of tree */
97 set_right(last, item);
100 set_parent(item, last);
103 /* Now we must walk up the tree balancing it */
105 while (x != head && red(parent(x))) {
106 if (parent(x) == left(parent(parent(x)))) {
107 /* Look at the right side of our grandparent */
108 y = right(parent(parent(x)));
110 /* our parent must be black */
111 set_red(parent(x), false);
113 set_red(parent(parent(x)), true);
114 x = parent(parent(x)); /* move up to grandpa */
116 if (x == right(parent(x))) { /* right side of parent? */
120 /* make parent black too */
121 set_red(parent(x), false);
122 set_red(parent(parent(x)), true);
123 right_rotate(parent(parent(x)));
126 /* Look at left side of our grandparent */
127 y = left(parent(parent(x)));
129 set_red(parent(x), false);
131 set_red(parent(parent(x)), true);
132 x = parent(parent(x)); /* move up to grandpa */
134 if (x == left(parent(x))) {
138 /* make parent black too */
139 set_red(parent(x), false);
140 set_red(parent(parent(x)), true);
141 left_rotate(parent(parent(x)));
145 /* Make sure the head is always black */
146 set_red(head, false);
153 void *rblist::search(void *item, int compare(void *item1, void *item2))
161 comp = compare(item, x);
164 } else if (comp > 0) {
175 * Get first item (i.e. lowest value)
177 void *rblist::first(void)
195 * This is a non-recursive btree walk routine that returns
196 * the items one at a time in order. I've never seen a
197 * non-recursive tree walk routine published that returns
198 * one item at a time rather than doing a callback.
200 * Return the next item in sorted order. We assume first()
201 * was called once before calling this routine.
202 * We always go down as far as we can to the left, then up, and
203 * down one to the right, and again down as far as we can to the
206 * Returns: pointer to next larger item
207 * NULL when no more items in tree
209 void *rblist::next(void *item)
218 if ((down && !left(x) && right(x)) || (!down && right(x))) {
219 /* Move down to right one */
222 /* Then all the way down left */
229 /* We have gone down all we can, so now go up */
231 /* If at head, we are done */
235 /* Move up in tree */
237 /* if coming from right, continue up */
238 if (right(parent(x)) == x) {
242 /* Coming from left, go up one -- ie. return parent */
248 * Similer to next(), but visits all right nodes when
249 * coming up the tree.
251 void *rblist::any(void *item)
256 if ((down && !left(x) && right(x)) || (!down && right(x))) {
257 /* Move down to right one */
260 /* Then all the way down left */
267 /* We have gone down all we can, so now go up */
269 /* If at head, we are done */
274 /* Go up one and return parent */
280 /* x is item, y is below and to right, then rotated to below left */
281 void rblist::left_rotate(void *item)
288 set_right(x, left(y));
290 set_parent(left(y), x);
292 set_parent(y, parent(x));
293 /* if no parent then we have a new head */
296 } else if (x == left(parent(x))) {
297 set_left(parent(x), y);
299 set_right(parent(x), y);
305 void rblist::right_rotate(void *item)
311 set_left(y, right(x));
313 set_parent(right(x), y);
315 set_parent(x, parent(y));
316 /* if no parent then we have a new head */
319 } else if (y == left(parent(y))) {
320 set_left(parent(y), x);
322 set_right(parent(y), x);
329 void rblist::remove(void *item)
333 /* Destroy the tree contents. Not totally working */
334 void rblist::destroy()
339 // printf("head=%p first=%p left=%p right=%p\n", head, x, left(x), right(x));
341 for ( ; (y=any(x)); ) {
342 /* Prune the last item */
344 if (x == left(parent(x))) {
345 set_left(parent(x), NULL);
346 } else if (x == right(parent(x))) {
347 set_right(parent(x), NULL);
350 if (!left(x) && !right(x)) {
354 // if (num_items<30) {
355 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, left(x), right(x));
357 free((void *)x); /* free previous node */
360 x = y; /* save last node */
366 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, left(x), right(x));
371 // printf("Free head\n");
374 // printf("free nitems=%d\n", num_items);
388 static int my_compare(void *item1, void *item2)
392 jcr1 = (MYJCR *)item1;
393 jcr2 = (MYJCR *)item2;
394 comp = strcmp(jcr1->buf, jcr2->buf);
395 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
407 /* Now do a binary insert for the tree */
408 jcr_chain = New(rblist());
410 printf("append %d items\n", CNT*CNT*CNT);
413 for (int i=0; i<CNT; i++) {
414 for (int j=0; j<CNT; j++) {
415 for (int k=0; k<CNT; k++) {
417 if ((count & 0x3FF) == 0) {
418 Dmsg1(000, "At %d\n", count);
420 jcr = (MYJCR *)malloc(sizeof(MYJCR));
421 memset(jcr, 0, sizeof(MYJCR));
422 jcr->buf = bstrdup(buf);
423 // printf("buf=%p %s\n", jcr, jcr->buf);
424 jcr1 = (MYJCR *)jcr_chain->insert((void *)jcr, my_compare);
426 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
436 printf("%d items appended\n", CNT*CNT*CNT);
437 printf("num_items=%d\n", jcr_chain->size());
439 jcr = (MYJCR *)malloc(sizeof(MYJCR));
440 memset(jcr, 0, sizeof(MYJCR));
442 jcr->buf = bstrdup("a");
443 if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
444 printf("One less failed!!!! Got: %s\n", jcr1->buf);
446 printf("One less: OK\n");
450 jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
451 if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
452 printf("One greater failed!!!! Got:%s\n", jcr1->buf);
454 printf("One greater: OK\n");
458 jcr->buf = bstrdup("AAA");
459 if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
460 printf("Search for AAA got %s\n", jcr1->buf);
462 printf("Search for AAA not found\n");
466 jcr->buf = bstrdup("ZZZ");
467 if ((jcr1 = (MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
468 printf("Search for ZZZ got %s\n", jcr1->buf);
470 printf("Search for ZZZ not found\n");
476 printf("Find each of %d items in tree.\n", count);
477 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((void *)jcr)) ) {
478 // printf("Got: %s\n", jcr->buf);
479 if (!jcr_chain->search((void *)jcr, my_compare)) {
480 printf("rblist binary_search item not found = %s\n", jcr->buf);
483 printf("Free each of %d items in tree.\n", count);
484 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((void *)jcr)) ) {
485 // printf("Free: %p %s\n", jcr, jcr->buf);
489 printf("num_items=%d\n", jcr_chain->size());