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

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