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 && !found) {
 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       }
 154    }
 155    return found;
 156 }
 157
 158 /*
 159  * Get first item (i.e. lowest value)
 160  */
 161 bnode *btree::first(void)
 162 {
 163    bnode *x;
 164
 165    x = head;
 166    down = true;
 167    while (x) {
 168       if (x->left) {
 169          x = x->left;
 170          continue;
 171       }
 172       return x;
 173    }
 174    /* Tree is empty */
 175    return NULL;
 176 }
 177
 178 /*
 179  * This is a non-recursive btree walk routine that returns
 180  *  the items one at a time in order. I've never seen a
 181  *  non-recursive tree walk routine published that returns
 182  *  one item at a time rather than doing a callback.
 183  *
 184  * Return the next item in sorted order.  We assume first()
 185  *  was called once before calling this routine.
 186  *  We always go down as far as we can to the left, then up, and
 187  *  down one to the right, and again down as far as we can to the
 188  *  left.  etc.
 189  *
 190  * Returns: pointer to next larger item
 191  *          NULL when no more items in tree
 192  */
 193 bnode *btree::next(bnode *item)
 194 {
 195    bnode *x;
 196
 197    x = item;
 198    if ((down && !x->left && x->right) || (!down && x->right)) {
 199       /* Move down to right one */
 200       down = true;
 201       x = x->right;
 202       /* Then all the way down left */
 203       while (x->left)  {
 204          x = x->left;
 205       }
 206       return x;
 207    }
 208
 209    /* We have gone down all we can, so now go up */
 210    for ( ;; ) {
 211       /* If at head, we are done */
 212       if (!x->parent) {
 213          return NULL;
 214       }
 215       /* Move up in tree */
 216       down = false;
 217       /* if coming from right, continue up */
 218       if (x->parent->right == x) {
 219          x = x->parent;
 220          continue;
 221       }
 222       /* Coming from left, go up one -- ie. return parent */
 223       return x->parent;
 224    }
 225 }
 226
 227 /*
 228  * Similer to next(), but visits all right nodes when
 229  *  coming up the tree.
 230  */
 231 bnode *btree::any(bnode *item)
 232 {
 233    bnode *x;
 234
 235    x = item;
 236    if ((down && !x->left && x->right) || (!down && x->right)) {
 237       /* Move down to right one */
 238       down = true;
 239       x = x->right;
 240       /* Then all the way down left */
 241       while (x->left)  {
 242          x = x->left;
 243       }
 244       return x;
 245    }
 246
 247    /* We have gone down all we can, so now go up */
 248    for ( ;; ) {
 249       /* If at head, we are done */
 250       if (!x->parent) {
 251          return NULL;
 252       }
 253       /* Move up in tree */
 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    for (x=first(); (y=any(x)); ) {
 320       /* Prune the last item */
 321       if (!x->parent) {
 322          head = x;
 323       } else if (x == x->parent->left) {
 324          x->parent->left = NULL;
 325       } else if (x == x->parent->right) {
 326          x->parent->right = NULL;
 327       }
 328       if (!x->left && !x->right) {
 329          free((void *)x);      /* free previous node */
 330       }
 331       x = y;                  /* save last node */
 332    }
 333    if (x) {
 334       free((void *)x);
 335    }
 336    if (y) {
 337       free((void *)y);
 338    }
 339
 340    num_items = 0;
 341    head = NULL;
 342 }
 343
 344
 345
 346 #ifdef TEST_PROGRAM
 347
 348 struct MYJCR {
 349    bnode link;
 350    char *buf;
 351 };
 352
 353 static int my_compare(bnode *item1, bnode *item2)
 354 {
 355    MYJCR *jcr1, *jcr2;
 356    int comp;
 357    jcr1 = (MYJCR *)item1;
 358    jcr2 = (MYJCR *)item2;
 359    comp = strcmp(jcr1->buf, jcr2->buf);
 360  //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
 361    return comp;
 362 }
 363
 364 int main()
 365 {
 366    char buf[30];
 367    btree *jcr_chain;
 368    MYJCR *jcr = NULL;
 369    MYJCR *jcr1;
 370
 371
 372    /* Now do a binary insert for the tree */
 373    jcr_chain = New(btree());
 374 #define CNT 26
 375    printf("append %d items\n", CNT*CNT*CNT);
 376    strcpy(buf, "ZZZ");
 377    int count = 0;
 378    for (int i=0; i<CNT; i++) {
 379       for (int j=0; j<CNT; j++) {
 380          for (int k=0; k<CNT; k++) {
 381             count++;
 382             if ((count & 0x3FF) == 0) {
 383                Dmsg1(000, "At %d\n", count);
 384             }
 385             jcr = (MYJCR *)malloc(sizeof(MYJCR));
 386             memset(jcr, 0, sizeof(MYJCR));
 387             jcr->buf = bstrdup(buf);
 388             jcr1 = (MYJCR *)jcr_chain->insert((bnode *)jcr, my_compare);
 389             if (jcr != jcr1) {
 390                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 391             }
 392             buf[1]--;
 393          }
 394          buf[1] = 'Z';
 395          buf[2]--;
 396       }
 397       buf[2] = 'Z';
 398       buf[0]--;
 399    }
 400    printf("%d items appended\n", CNT*CNT*CNT);
 401    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 402    memset(jcr, 0, sizeof(MYJCR));
 403    strcpy(buf, "a");
 404    jcr->buf = bstrdup(buf);
 405    if (jcr_chain->search((bnode *)jcr, my_compare)) {
 406       printf("One less failed!!!!\n");
 407    } else {
 408       printf("One less: OK\n");
 409    }
 410    free(jcr->buf);
 411    strcpy(buf, "ZZZZZZZZZZZZZZZZ");
 412    jcr->buf = bstrdup(buf);
 413    if (jcr_chain->search((bnode *)jcr, my_compare)) {
 414       printf("One greater failed!!!!\n");
 415    } else {
 416       printf("One greater: OK\n");
 417    }
 418    free(jcr->buf);
 419    strcpy(buf, "AAA");
 420    jcr->buf = bstrdup(buf);
 421    if (jcr_chain->search((bnode *)jcr, my_compare)) {
 422       printf("Search for AAA failed!!!!\n");
 423    } else {
 424       printf("AAA: OK\n");
 425    }
 426    free(jcr->buf);
 427    strcpy(buf, "ZZZ");
 428    jcr->buf = bstrdup(buf);
 429    if (jcr_chain->search((bnode *)jcr, my_compare)) {
 430       printf("Search for ZZZ failed!!!!\n");
 431    } else {
 432       printf("ZZZ: OK\n");
 433    }
 434    free(jcr->buf);
 435
 436    free(jcr);
 437
 438
 439    printf("Find each of %d items in tree.\n", count);
 440    for (jcr=(MYJCR *)jcr_chain->first(); (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)); ) {
 441 //    printf("Got: %s\n", jcr->buf);
 442       if (!jcr_chain->search((bnode *)jcr, my_compare)) {
 443          printf("btree binary_search item not found = %s\n", jcr->buf);
 444       }
 445    }
 446    printf("Free each of %d items in tree.\n", count);
 447    for (jcr=(MYJCR *)jcr_chain->first(); (jcr=(MYJCR *)jcr_chain->next((bnode *)jcr)); ) {
 448       free(jcr->buf);
 449       jcr->buf = NULL;
 450    }
 451    delete jcr_chain;
 452
 453
 454    sm_dump(true);
 455
 456 }
 457 #endif