git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/btree.c

   1 /*
   2  *  Bacula red-black binary tree routines.
   3  *
   4  *    btree is a binary tree with the links being in the data item.
   5  *
   6  *   Developped in part from ideas obtained from several online University
   7  *    courses.
   8  *
   9  *   Kern Sibbald, November MMV
  10  *
  11  *   Version $Id$
  12  *
  13  */
  14 /*
  15    Copyright (C) 2005 Kern Sibbald
  16
  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.
  21
  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.
  26
  27  */
  28
  29 #include "bacula.h"
  30 #include "btree.h"
  31
  32 /* ===================================================================
  33  *    btree
  34  */
  35
  36 /*
  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
  41  *   to avoid recursion.
  42  *
  43  * Returns: item         if item inserted
  44  *          other_item   if same value already exists (item not inserted)
  45  */
  46 bnode *btree::insert(bnode *item, int compare(bnode *item1, bnode *item2))
  47 {
  48    bnode *x, *y;
  49    bnode *last = NULL;        /* last leaf if not found */
  50    bnode *found = NULL;
  51    int comp = 0;
  52
  53    /* Search */
  54    x = head;
  55    while (x && !found) {
  56       last = x;
  57       comp = compare(item, x);
  58       if (comp < 0) {
  59          x = x->left;
  60       } else if (comp > 0) {
  61          x = x->right;
  62       } else {
  63          found = x;
  64       }
  65    }
  66
  67    if (found) {                    /* found? */
  68       return found;                /* yes, return item found */
  69    }
  70    /* Handle empty tree */
  71    if (num_items == 0) {
  72       head = item;
  73       num_items++;
  74       return item;
  75    }
  76    x = last;
  77    /* Not found, so insert it on appropriate side of tree */
  78    if (comp < 0) {
  79       last->left = item;
  80    } else {
  81       last->right = item;
  82    }
  83    last->red = true;
  84    item->parent = last;
  85    num_items++;
  86
  87    /* Now we must walk up the tree balancing it */
  88    x = last;
  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;
  93          if (y && y->red) {
  94             /* our parent must be black */
  95             x->parent->red = false;
  96             y->red = false;
  97             x->parent->parent->red = true;
  98             x = x->parent->parent;       /* move up to grandpa */
  99          } else {
 100             if (x == x->parent->right) { /* right side of parent? */
 101                x = x->parent;
 102                left_rotate(x);
 103             }
 104             /* make parent black too */
 105             x->parent->red = false;
 106             x->parent->parent->red = true;
 107             right_rotate(x->parent->parent);
 108          }
 109       } else {
 110          /* Look at left side of our grandparent */
 111          y = x->parent->parent->left;
 112          if (y && y->red) {
 113             x->parent->red = false;
 114             y->red = false;
 115             x->parent->parent->red = true;
 116             x = x->parent->parent;       /* move up to grandpa */
 117          } else {
 118             if (x == x->parent->left) {
 119                x = x->parent;
 120                right_rotate(x);
 121             }
 122             /* make parent black too */
 123             x->parent->red = false;
 124             x->parent->parent->red = true;
 125             left_rotate(x->parent->parent);
 126          }
 127       }
 128    }
 129    /* Make sure the head is always black */
 130    head->red = false;
 131    return item;
 132 }
 133
 134
 135 /*
 136  * Search for item
 137  */
 138 bnode *btree::search(bnode *item, int compare(bnode *item1, bnode *item2))
 139 {
 140    bnode *found = NULL;
 141    bnode *x;
 142    int comp;
 143
 144    x = head;
 145    while (x) {
 146       comp = compare(item, x);
 147       if (comp < 0) {
 148          x = x->left;
 149       } else if (comp > 0) {
 150          x = x->right;
 151       } else {
 152          found = x;
 153          break;
 154       }
 155    }
 156    return found;
 157 }
 158
 159 /*
 160  * Get first item (i.e. lowest value)
 161  */
 162 bnode *btree::first(void)
 163 {
 164    bnode *x;
 165
 166    x = head;
 167    down = true;
 168    while (x) {
 169       if (x->left) {
 170          x = x->left;
 171          continue;
 172       }
 173       return x;
 174    }
 175    /* Tree is empty */
 176    return NULL;
 177 }
 178
 179 /*
 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.
 184  *
 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
 189  *  left.  etc.
 190  *
 191  * Returns: pointer to next larger item
 192  *          NULL when no more items in tree
 193  */
 194 bnode *btree::next(bnode *item)
 195 {
 196    bnode *x;
 197
 198    x = item;
 199    if ((down && !x->left && x->right) || (!down && x->right)) {
 200       /* Move down to right one */
 201       down = true;
 202       x = x->right;
 203       /* Then all the way down left */
 204       while (x->left)  {
 205          x = x->left;
 206       }
 207       return x;
 208    }
 209
 210    /* We have gone down all we can, so now go up */
 211    for ( ;; ) {
 212       /* If at head, we are done */
 213       if (!x->parent) {
 214          return NULL;
 215       }
 216       /* Move up in tree */
 217       down = false;
 218       /* if coming from right, continue up */
 219       if (x->parent->right == x) {
 220          x = x->parent;
 221          continue;
 222       }
 223       /* Coming from left, go up one -- ie. return parent */
 224       return x->parent;
 225    }
 226 }
 227
 228 /*
 229  * Similer to next(), but visits all right nodes when
 230  *  coming up the tree.
 231  */
 232 bnode *btree::any(bnode *item)
 233 {
 234    bnode *x;
 235
 236    x = item;
 237    if ((down && !x->left && x->right) || (!down && x->right)) {
 238       /* Move down to right one */
 239       down = true;
 240       x = x->right;
 241       /* Then all the way down left */
 242       while (x->left)  {
 243          x = x->left;
 244       }
 245       return x;
 246    }
 247
 248    /* We have gone down all we can, so now go up */
 249    for ( ;; ) {
 250       /* If at head, we are done */
 251       if (!x->parent) {
 252          return NULL;
 253       }
 254       down = false;
 255       /* Go up one and return parent */
 256       return x->parent;
 257    }
 258 }
 259
 260
 261 /* x is item, y is below and to right, then rotated to below left */
 262 void btree::left_rotate(bnode *item)
 263 {
 264    bnode *y;
 265    bnode *x;
 266
 267    x = item;
 268    y = x->right;
 269    x->right = y->left;
 270    if (y->left) {
 271       y->left->parent = x;
 272    }
 273    y->parent = x->parent;
 274    /* if no parent then we have a new head */
 275    if (!x->parent) {
 276       head = y;
 277    } else if (x == x->parent->left) {
 278       x->parent->left = y;
 279    } else {
 280       x->parent->right = y;
 281    }
 282    y->left = x;
 283    x->parent = y;
 284 }
 285
 286 void btree::right_rotate(bnode *item)
 287 {
 288    bnode *x, *y;
 289
 290    y = item;
 291    x = y->left;
 292    y->left = x->right;
 293    if (x->right) {
 294       x->right->parent = y;
 295    }
 296    x->parent = y->parent;
 297    /* if no parent then we have a new head */
 298    if (!y->parent) {
 299       head = x;
 300    } else if (y == y->parent->left) {
 301       y->parent->left = x;
 302    } else {
 303       y->parent->right = x;
 304    }
 305    x->right = y;
 306    y->parent = x;
 307 }
 308
 309
 310 void btree::remove(bnode *item)
 311 {
 312 }
 313
 314 /* Destroy the tree contents.  Not totally working */
 315 void btree::destroy()
 316 {
 317    bnode *x, *y = NULL;
 318
 319    x = first();
 320 // printf("head=%p first=%p left=%p right=%p\n", head, x, x->left, x->right);
 321
 322    for (  ; (y=any(x)); ) {
 323       /* Prune the last item */
 324       if (x->parent) {
 325          if (x == x->parent->left) {
 326             x->parent->left = NULL;
 327          } else if (x == x->parent->right) {
 328             x->parent->right = NULL;
 329          }
 330       }
 331       if (!x->left && !x->right) {
 332          if (head == x) {
 333             head = NULL;
 334          }
 335 //       if (num_items<30) {
 336 //          printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
 337 //       }
 338          free((void *)x);      /* free previous node */
 339          num_items--;
 340       }
 341       x = y;                  /* save last node */
 342    }
 343    if (x) {
 344       if (x == head) {
 345          head = NULL;
 346       }
 347 //    printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
 348       free((void *)x);
 349       num_items--;
 350    }
 351    if (head) {
 352 //    printf("Free head\n");
 353       free((void *)head);
 354    }
 355 // printf("free nitems=%d\n", num_items);
 356
 357    head = NULL;
 358 }
 359
 360
 361
 362 #ifdef TEST_PROGRAM
 363
 364 struct MYJCR {
 365    bnode link;
 366    char *buf;
 367 };
 368
 369 static int my_compare(bnode *item1, bnode *item2)
 370 {
 371    MYJCR *jcr1, *jcr2;
 372    int comp;
 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);
 377    return comp;
 378 }
 379
 380 int main()
 381 {
 382    char buf[30];
 383    btree *jcr_chain;
 384    MYJCR *jcr = NULL;
 385    MYJCR *jcr1;
 386
 387
 388    /* Now do a binary insert for the tree */
 389    jcr_chain = New(btree());
 390 #define CNT 26
 391    printf("append %d items\n", CNT*CNT*CNT);
 392    strcpy(buf, "ZZZ");
 393    int count = 0;
 394    for (int i=0; i<CNT; i++) {
 395       for (int j=0; j<CNT; j++) {
 396          for (int k=0; k<CNT; k++) {
 397             count++;
 398             if ((count & 0x3FF) == 0) {
 399                Dmsg1(000, "At %d\n", count);
 400             }
 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);
 406             if (jcr != jcr1) {
 407                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 408             }
 409             buf[1]--;
 410          }
 411          buf[1] = 'Z';
 412          buf[2]--;
 413       }
 414       buf[2] = 'Z';
 415       buf[0]--;
 416    }
 417    printf("%d items appended\n", CNT*CNT*CNT);
 418    printf("num_items=%d\n", jcr_chain->size());
 419
 420    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 421    memset(jcr, 0, sizeof(MYJCR));
 422
 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);
 426    } else {
 427       printf("One less: OK\n");
 428    }
 429    free(jcr->buf);
 430
 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);
 434    } else {
 435       printf("One greater: OK\n");
 436    }
 437    free(jcr->buf);
 438
 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);
 442    } else {
 443       printf("Search for AAA not found\n");
 444    }
 445    free(jcr->buf);
 446
 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);
 450    } else {
 451       printf("Search for ZZZ not found\n");
 452    }
 453    free(jcr->buf);
 454    free(jcr);
 455
 456
 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);
 462       }
 463    }
 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);
 467       free(jcr->buf);
 468       jcr->buf = NULL;
 469    }
 470    printf("num_items=%d\n", jcr_chain->size());
 471    delete jcr_chain;
 472
 473
 474    sm_dump(true);
 475
 476 }
 477 #endif