2 Bacula(R) - The Network Backup Solution
4 Copyright (C) 2000-2017 Kern Sibbald
6 The original author of Bacula is Kern Sibbald, with contributions
7 from many others, a complete list can be found in the file AUTHORS.
9 You may use this file and others of this release according to the
10 license defined in the LICENSE file, which includes the Affero General
11 Public License, v3.0 ("AGPLv3") and some additional permissions and
12 terms pursuant to its AGPLv3 Section 7.
14 This notice must be preserved when any source code is
15 conveyed and/or propagated.
17 Bacula(R) is a registered trademark of Kern Sibbald.
20 * Bacula red-black binary tree routines.
22 * rblist is a binary tree with the links being in the data item.
24 * Developped in part from ideas obtained from several online University
27 * Kern Sibbald, November MMV
33 /* ===================================================================
38 * Insert an item in the tree, but only if it is unique
39 * otherwise, the item is returned non inserted
40 * The big trick is keeping the tree balanced after the
41 * insert. We use a parent pointer to make it simpler and
44 * Returns: item if item inserted
45 * other_item if same value already exists (item not inserted)
47 void *rblist::insert(void *item, int compare(void *item1, void *item2))
50 void *last = NULL; /* last leaf if not found */
58 comp = compare(item, x);
61 } else if (comp > 0) {
68 if (found) { /* found? */
69 return found; /* yes, return item found */
72 set_right(item, NULL);
73 set_parent(item, NULL);
75 /* Handle empty tree */
82 /* Not found, so insert it on appropriate side of tree */
86 set_right(last, item);
89 set_parent(item, last);
92 /* Now we must walk up the tree balancing it */
94 while (x != head && red(parent(x))) {
95 if (parent(x) == left(parent(parent(x)))) {
96 /* Look at the right side of our grandparent */
97 y = right(parent(parent(x)));
99 /* our parent must be black */
100 set_red(parent(x), false);
102 set_red(parent(parent(x)), true);
103 x = parent(parent(x)); /* move up to grandpa */
105 if (x == right(parent(x))) { /* right side of parent? */
109 /* make parent black too */
110 set_red(parent(x), false);
111 set_red(parent(parent(x)), true);
112 right_rotate(parent(parent(x)));
115 /* Look at left side of our grandparent */
116 y = left(parent(parent(x)));
118 set_red(parent(x), false);
120 set_red(parent(parent(x)), true);
121 x = parent(parent(x)); /* move up to grandpa */
123 if (x == left(parent(x))) {
127 /* make parent black too */
128 set_red(parent(x), false);
129 set_red(parent(parent(x)), true);
130 left_rotate(parent(parent(x)));
134 /* Make sure the head is always black */
135 set_red(head, false);
142 void *rblist::search(void *item, int compare(void *item1, void *item2))
150 comp = compare(item, x);
153 } else if (comp > 0) {
164 * Get first item (i.e. lowest value)
166 void *rblist::first(void)
184 * This is a non-recursive btree walk routine that returns
185 * the items one at a time in order. I've never seen a
186 * non-recursive tree walk routine published that returns
187 * one item at a time rather than doing a callback.
189 * Return the next item in sorted order. We assume first()
190 * was called once before calling this routine.
191 * We always go down as far as we can to the left, then up, and
192 * down one to the right, and again down as far as we can to the
195 * Returns: pointer to next larger item
196 * NULL when no more items in tree
198 void *rblist::next(void *item)
207 if ((down && !left(x) && right(x)) || (!down && right(x))) {
208 /* Move down to right one */
211 /* Then all the way down left */
218 /* We have gone down all we can, so now go up */
220 /* If at head, we are done */
224 /* Move up in tree */
226 /* if coming from right, continue up */
227 if (right(parent(x)) == x) {
231 /* Coming from left, go up one -- ie. return parent */
237 * Similer to next(), but visits all right nodes when
238 * coming up the tree.
240 void *rblist::any(void *item)
249 if ((down && !left(x) && right(x)) || (!down && right(x))) {
250 /* Move down to right one */
253 /* Then all the way down left */
260 /* We have gone down all we can, so now go up */
262 /* If at head, we are done */
267 /* Go up one and return parent */
273 /* x is item, y is below and to right, then rotated to below left */
274 void rblist::left_rotate(void *item)
281 set_right(x, left(y));
283 set_parent(left(y), x);
285 set_parent(y, parent(x));
286 /* if no parent then we have a new head */
289 } else if (x == left(parent(x))) {
290 set_left(parent(x), y);
292 set_right(parent(x), y);
298 void rblist::right_rotate(void *item)
304 set_left(y, right(x));
306 set_parent(right(x), y);
308 set_parent(x, parent(y));
309 /* if no parent then we have a new head */
312 } else if (y == left(parent(y))) {
313 set_left(parent(y), x);
315 set_right(parent(y), x);
322 void rblist::remove(void *item)
326 /* Destroy the tree contents. Not totally working */
327 void rblist::destroy()
332 // printf("head=%p first=%p left=%p right=%p\n", head, x, left(x), right(x));
333 for ( ; (y=any(x)); ) {
334 /* Prune the last item */
336 if (x == left(parent(x))) {
337 set_left(parent(x), NULL);
338 } else if (x == right(parent(x))) {
339 set_right(parent(x), NULL);
342 if (!left(x) && !right(x)) {
346 // if (num_items<30) {
347 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, left(x), right(x));
349 free((void *)x); /* free previous node */
352 x = y; /* save last node */
358 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, left(x), right(x));
363 // printf("Free head\n");
366 // printf("free nitems=%d\n", num_items);
380 static int my_compare(void *item1, void *item2)
384 jcr1 = (MYJCR *)item1;
385 jcr2 = (MYJCR *)item2;
386 comp = strcmp(jcr1->buf, jcr2->buf);
387 //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
399 /* Now do a binary insert for the tree */
400 jcr_chain = New(rblist());
402 printf("append %d items\n", CNT*CNT*CNT);
405 for (int i=0; i<CNT; i++) {
406 for (int j=0; j<CNT; j++) {
407 for (int k=0; k<CNT; k++) {
409 if ((count & 0x3FF) == 0) {
410 Dmsg1(000, "At %d\n", count);
412 jcr = (MYJCR *)malloc(sizeof(MYJCR));
413 bmemzero(jcr, sizeof(MYJCR));
414 jcr->buf = bstrdup(buf);
415 // printf("buf=%p %s\n", jcr, jcr->buf);
416 jcr1 = (MYJCR *)jcr_chain->insert((void *)jcr, my_compare);
418 Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
428 printf("%d items appended\n", CNT*CNT*CNT);
429 printf("num_items=%d\n", jcr_chain->size());
431 jcr = (MYJCR *)malloc(sizeof(MYJCR));
432 bmemzero(jcr, sizeof(MYJCR));
434 jcr->buf = bstrdup("a");
435 if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
436 printf("One less failed!!!! Got: %s\n", jcr1->buf);
438 printf("One less: OK\n");
442 jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
443 if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
444 printf("One greater failed!!!! Got:%s\n", jcr1->buf);
446 printf("One greater: OK\n");
450 jcr->buf = bstrdup("AAA");
451 if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
452 printf("Search for AAA got %s\n", jcr1->buf);
454 printf("Search for AAA not found\n");
458 jcr->buf = bstrdup("ZZZ");
459 if ((jcr1 = (MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
460 printf("Search for ZZZ got %s\n", jcr1->buf);
462 printf("Search for ZZZ not found\n");
468 printf("Find each of %d items in tree.\n", count);
469 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((void *)jcr)) ) {
470 // printf("Got: %s\n", jcr->buf);
471 if (!jcr_chain->search((void *)jcr, my_compare)) {
472 printf("rblist binary_search item not found = %s\n", jcr->buf);
475 printf("Free each of %d items in tree.\n", count);
476 for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((void *)jcr)) ) {
477 // printf("Free: %p %s\n", jcr, jcr->buf);
481 printf("num_items=%d\n", jcr_chain->size());
485 sm_dump(true); /* unit test */