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

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