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

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