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

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