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    Bacula® - The Network Backup Solution
  16
  17    Copyright (C) 2005-2006 Free Software Foundation Europe e.V.
  18
  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.
  25
  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.
  30
  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
  34    02110-1301, USA.
  35
  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.
  40 */
  41
  42 #include "bacula.h"
  43 #include "btree.h"
  44
  45 /* ===================================================================
  46  *    btree
  47  */
  48
  49 /*
  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
  54  *   to avoid recursion.
  55  *
  56  * Returns: item         if item inserted
  57  *          other_item   if same value already exists (item not inserted)
  58  */
  59 bnode *btree::insert(bnode *item, int compare(bnode *item1, bnode *item2))
  60 {
  61    bnode *x, *y;
  62    bnode *last = NULL;        /* last leaf if not found */
  63    bnode *found = NULL;
  64    int comp = 0;
  65
  66    /* Search */
  67    x = head;
  68    while (x && !found) {
  69       last = x;
  70       comp = compare(item, x);
  71       if (comp < 0) {
  72          x = x->left;
  73       } else if (comp > 0) {
  74          x = x->right;
  75       } else {
  76          found = x;
  77       }
  78    }
  79
  80    if (found) {                    /* found? */
  81       return found;                /* yes, return item found */
  82    }
  83    /* Handle empty tree */
  84    if (num_items == 0) {
  85       head = item;
  86       num_items++;
  87       return item;
  88    }
  89    x = last;
  90    /* Not found, so insert it on appropriate side of tree */
  91    if (comp < 0) {
  92       last->left = item;
  93    } else {
  94       last->right = item;
  95    }
  96    last->red = true;
  97    item->parent = last;
  98    num_items++;
  99
 100    /* Now we must walk up the tree balancing it */
 101    x = last;
 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;
 106          if (y && y->red) {
 107             /* our parent must be black */
 108             x->parent->red = false;
 109             y->red = false;
 110             x->parent->parent->red = true;
 111             x = x->parent->parent;       /* move up to grandpa */
 112          } else {
 113             if (x == x->parent->right) { /* right side of parent? */
 114                x = x->parent;
 115                left_rotate(x);
 116             }
 117             /* make parent black too */
 118             x->parent->red = false;
 119             x->parent->parent->red = true;
 120             right_rotate(x->parent->parent);
 121          }
 122       } else {
 123          /* Look at left side of our grandparent */
 124          y = x->parent->parent->left;
 125          if (y && y->red) {
 126             x->parent->red = false;
 127             y->red = false;
 128             x->parent->parent->red = true;
 129             x = x->parent->parent;       /* move up to grandpa */
 130          } else {
 131             if (x == x->parent->left) {
 132                x = x->parent;
 133                right_rotate(x);
 134             }
 135             /* make parent black too */
 136             x->parent->red = false;
 137             x->parent->parent->red = true;
 138             left_rotate(x->parent->parent);
 139          }
 140       }
 141    }
 142    /* Make sure the head is always black */
 143    head->red = false;
 144    return item;
 145 }
 146
 147
 148 /*
 149  * Search for item
 150  */
 151 bnode *btree::search(bnode *item, int compare(bnode *item1, bnode *item2))
 152 {
 153    bnode *found = NULL;
 154    bnode *x;
 155    int comp;
 156
 157    x = head;
 158    while (x) {
 159       comp = compare(item, x);
 160       if (comp < 0) {
 161          x = x->left;
 162       } else if (comp > 0) {
 163          x = x->right;
 164       } else {
 165          found = x;
 166          break;
 167       }
 168    }
 169    return found;
 170 }
 171
 172 /*
 173  * Get first item (i.e. lowest value)
 174  */
 175 bnode *btree::first(void)
 176 {
 177    bnode *x;
 178
 179    x = head;
 180    down = true;
 181    while (x) {
 182       if (x->left) {
 183          x = x->left;
 184          continue;
 185       }
 186       return x;
 187    }
 188    /* Tree is empty */
 189    return NULL;
 190 }
 191
 192 /*
 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.
 197  *
 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
 202  *  left.  etc.
 203  *
 204  * Returns: pointer to next larger item
 205  *          NULL when no more items in tree
 206  */
 207 bnode *btree::next(bnode *item)
 208 {
 209    bnode *x;
 210
 211    x = item;
 212    if ((down && !x->left && x->right) || (!down && x->right)) {
 213       /* Move down to right one */
 214       down = true;
 215       x = x->right;
 216       /* Then all the way down left */
 217       while (x->left)  {
 218          x = x->left;
 219       }
 220       return x;
 221    }
 222
 223    /* We have gone down all we can, so now go up */
 224    for ( ;; ) {
 225       /* If at head, we are done */
 226       if (!x->parent) {
 227          return NULL;
 228       }
 229       /* Move up in tree */
 230       down = false;
 231       /* if coming from right, continue up */
 232       if (x->parent->right == x) {
 233          x = x->parent;
 234          continue;
 235       }
 236       /* Coming from left, go up one -- ie. return parent */
 237       return x->parent;
 238    }
 239 }
 240
 241 /*
 242  * Similer to next(), but visits all right nodes when
 243  *  coming up the tree.
 244  */
 245 bnode *btree::any(bnode *item)
 246 {
 247    bnode *x;
 248
 249    x = item;
 250    if ((down && !x->left && x->right) || (!down && x->right)) {
 251       /* Move down to right one */
 252       down = true;
 253       x = x->right;
 254       /* Then all the way down left */
 255       while (x->left)  {
 256          x = x->left;
 257       }
 258       return x;
 259    }
 260
 261    /* We have gone down all we can, so now go up */
 262    for ( ;; ) {
 263       /* If at head, we are done */
 264       if (!x->parent) {
 265          return NULL;
 266       }
 267       down = false;
 268       /* Go up one and return parent */
 269       return x->parent;
 270    }
 271 }
 272
 273
 274 /* x is item, y is below and to right, then rotated to below left */
 275 void btree::left_rotate(bnode *item)
 276 {
 277    bnode *y;
 278    bnode *x;
 279
 280    x = item;
 281    y = x->right;
 282    x->right = y->left;
 283    if (y->left) {
 284       y->left->parent = x;
 285    }
 286    y->parent = x->parent;
 287    /* if no parent then we have a new head */
 288    if (!x->parent) {
 289       head = y;
 290    } else if (x == x->parent->left) {
 291       x->parent->left = y;
 292    } else {
 293       x->parent->right = y;
 294    }
 295    y->left = x;
 296    x->parent = y;
 297 }
 298
 299 void btree::right_rotate(bnode *item)
 300 {
 301    bnode *x, *y;
 302
 303    y = item;
 304    x = y->left;
 305    y->left = x->right;
 306    if (x->right) {
 307       x->right->parent = y;
 308    }
 309    x->parent = y->parent;
 310    /* if no parent then we have a new head */
 311    if (!y->parent) {
 312       head = x;
 313    } else if (y == y->parent->left) {
 314       y->parent->left = x;
 315    } else {
 316       y->parent->right = x;
 317    }
 318    x->right = y;
 319    y->parent = x;
 320 }
 321
 322
 323 void btree::remove(bnode *item)
 324 {
 325 }
 326
 327 /* Destroy the tree contents.  Not totally working */
 328 void btree::destroy()
 329 {
 330    bnode *x, *y = NULL;
 331
 332    x = first();
 333 // printf("head=%p first=%p left=%p right=%p\n", head, x, x->left, x->right);
 334
 335    for (  ; (y=any(x)); ) {
 336       /* Prune the last item */
 337       if (x->parent) {
 338          if (x == x->parent->left) {
 339             x->parent->left = NULL;
 340          } else if (x == x->parent->right) {
 341             x->parent->right = NULL;
 342          }
 343       }
 344       if (!x->left && !x->right) {
 345          if (head == x) {
 346             head = NULL;
 347          }
 348 //       if (num_items<30) {
 349 //          printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
 350 //       }
 351          free((void *)x);      /* free previous node */
 352          num_items--;
 353       }
 354       x = y;                  /* save last node */
 355    }
 356    if (x) {
 357       if (x == head) {
 358          head = NULL;
 359       }
 360 //    printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, x->left, x->right);
 361       free((void *)x);
 362       num_items--;
 363    }
 364    if (head) {
 365 //    printf("Free head\n");
 366       free((void *)head);
 367    }
 368 // printf("free nitems=%d\n", num_items);
 369
 370    head = NULL;
 371 }
 372
 373
 374
 375 #ifdef TEST_PROGRAM
 376
 377 struct MYJCR {
 378    bnode link;
 379    char *buf;
 380 };
 381
 382 static int my_compare(bnode *item1, bnode *item2)
 383 {
 384    MYJCR *jcr1, *jcr2;
 385    int comp;
 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);
 390    return comp;
 391 }
 392
 393 int main()
 394 {
 395    char buf[30];
 396    btree *jcr_chain;
 397    MYJCR *jcr = NULL;
 398    MYJCR *jcr1;
 399
 400
 401    /* Now do a binary insert for the tree */
 402    jcr_chain = New(btree());
 403 #define CNT 26
 404    printf("append %d items\n", CNT*CNT*CNT);
 405    strcpy(buf, "ZZZ");
 406    int count = 0;
 407    for (int i=0; i<CNT; i++) {
 408       for (int j=0; j<CNT; j++) {
 409          for (int k=0; k<CNT; k++) {
 410             count++;
 411             if ((count & 0x3FF) == 0) {
 412                Dmsg1(000, "At %d\n", count);
 413             }
 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);
 419             if (jcr != jcr1) {
 420                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 421             }
 422             buf[1]--;
 423          }
 424          buf[1] = 'Z';
 425          buf[2]--;
 426       }
 427       buf[2] = 'Z';
 428       buf[0]--;
 429    }
 430    printf("%d items appended\n", CNT*CNT*CNT);
 431    printf("num_items=%d\n", jcr_chain->size());
 432
 433    foreach_btree(jcr, jcr_chain) {
 434 //    printf("%s\n", jcr->buf);   /* turn on if you want lots of output */
 435    }
 436
 437    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 438    memset(jcr, 0, sizeof(MYJCR));
 439
 440    jcr->buf = bstrdup("a");
 441    if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
 442       printf("One less failed!!!! Got: %s\n", jcr1->buf);
 443    } else {
 444       printf("One less: OK\n");
 445    }
 446    free(jcr->buf);
 447
 448    jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
 449    if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
 450       printf("One greater failed!!!! Got:%s\n", jcr1->buf);
 451    } else {
 452       printf("One greater: OK\n");
 453    }
 454    free(jcr->buf);
 455
 456    jcr->buf = bstrdup("AAA");
 457    if ((jcr1=(MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
 458       printf("Search for AAA got %s\n", jcr1->buf);
 459    } else {
 460       printf("Search for AAA not found\n");
 461    }
 462    free(jcr->buf);
 463
 464    jcr->buf = bstrdup("ZZZ");
 465    if ((jcr1 = (MYJCR *)jcr_chain->search((bnode *)jcr, my_compare))) {
 466       printf("Search for ZZZ got %s\n", jcr1->buf);
 467    } else {
 468       printf("Search for ZZZ not found\n");
 469    }
 470    free(jcr->buf);
 471    free(jcr);
 472
 473
 474    printf("Find each of %d items in tree.\n", count);
 475    for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
 476 //    printf("Got: %s\n", jcr->buf);
 477       if (!jcr_chain->search((bnode *)jcr, my_compare)) {
 478          printf("btree binary_search item not found = %s\n", jcr->buf);
 479       }
 480    }
 481    printf("Free each of %d items in tree.\n", count);
 482    for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)) ) {
 483 //    printf("Free: %p %s\n", jcr, jcr->buf);
 484       free(jcr->buf);
 485       jcr->buf = NULL;
 486    }
 487    printf("num_items=%d\n", jcr_chain->size());
 488    delete jcr_chain;
 489
 490
 491    sm_dump(true);
 492
 493 }
 494 #endif