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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2005-2010 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    x = item;
 254    if ((down && !left(x) && right(x)) || (!down && right(x))) {
 255       /* Move down to right one */
 256       down = true;
 257       x = right(x);
 258       /* Then all the way down left */
 259       while (left(x))  {
 260          x = left(x);
 261       }
 262       return x;
 263    }
 264
 265    /* We have gone down all we can, so now go up */
 266    for ( ;; ) {
 267       /* If at head, we are done */
 268       if (!parent(x)) {
 269          return NULL;
 270       }
 271       down = false;
 272       /* Go up one and return parent */
 273       return parent(x);
 274    }
 275 }
 276
 277
 278 /* x is item, y is below and to right, then rotated to below left */
 279 void rblist::left_rotate(void *item)
 280 {
 281    void *y;
 282    void *x;
 283
 284    x = item;
 285    y = right(x);
 286    set_right(x, left(y));
 287    if (left(y)) {
 288       set_parent(left(y), x);
 289    }
 290    set_parent(y, parent(x));
 291    /* if no parent then we have a new head */
 292    if (!parent(x)) {
 293       head = y;
 294    } else if (x == left(parent(x))) {
 295       set_left(parent(x), y);
 296    } else {
 297       set_right(parent(x), y);
 298    }
 299    set_left(y, x);
 300    set_parent(x, y);
 301 }
 302
 303 void rblist::right_rotate(void *item)
 304 {
 305    void *x, *y;
 306
 307    y = item;
 308    x = left(y);
 309    set_left(y, right(x));
 310    if (right(x)) {
 311       set_parent(right(x), y);
 312    }
 313    set_parent(x, parent(y));
 314    /* if no parent then we have a new head */
 315    if (!parent(y)) {
 316       head = x;
 317    } else if (y == left(parent(y))) {
 318       set_left(parent(y), x);
 319    } else {
 320       set_right(parent(y), x);
 321    }
 322    set_right(x, y);
 323    set_parent(y, x);
 324 }
 325
 326
 327 void rblist::remove(void *item)
 328 {
 329 }
 330
 331 /* Destroy the tree contents.  Not totally working */
 332 void rblist::destroy()
 333 {
 334    void *x, *y = NULL;
 335
 336    x = first();
 337 // printf("head=%p first=%p left=%p right=%p\n", head, x, left(x), right(x));
 338
 339    for (  ; (y=any(x)); ) {
 340       /* Prune the last item */
 341       if (parent(x)) {
 342          if (x == left(parent(x))) {
 343             set_left(parent(x), NULL);
 344          } else if (x == right(parent(x))) {
 345             set_right(parent(x), NULL);
 346          }
 347       }
 348       if (!left(x) && !right(x)) {
 349          if (head == x) {
 350             head = NULL;
 351          }
 352 //       if (num_items<30) {
 353 //          printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, left(x), right(x));
 354 //       }
 355          free((void *)x);      /* free previous node */
 356          num_items--;
 357       }
 358       x = y;                  /* save last node */
 359    }
 360    if (x) {
 361       if (x == head) {
 362          head = NULL;
 363       }
 364 //    printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x, left(x), right(x));
 365       free((void *)x);
 366       num_items--;
 367    }
 368    if (head) {
 369 //    printf("Free head\n");
 370       free((void *)head);
 371    }
 372 // printf("free nitems=%d\n", num_items);
 373
 374    head = NULL;
 375 }
 376
 377
 378
 379 #ifdef TEST_PROGRAM
 380
 381 struct MYJCR {
 382    void link;
 383    char *buf;
 384 };
 385
 386 static int my_compare(void *item1, void *item2)
 387 {
 388    MYJCR *jcr1, *jcr2;
 389    int comp;
 390    jcr1 = (MYJCR *)item1;
 391    jcr2 = (MYJCR *)item2;
 392    comp = strcmp(jcr1->buf, jcr2->buf);
 393  //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
 394    return comp;
 395 }
 396
 397 int main()
 398 {
 399    char buf[30];
 400    rblist *jcr_chain;
 401    MYJCR *jcr = NULL;
 402    MYJCR *jcr1;
 403
 404
 405    /* Now do a binary insert for the tree */
 406    jcr_chain = New(rblist());
 407 #define CNT 26
 408    printf("append %d items\n", CNT*CNT*CNT);
 409    strcpy(buf, "ZZZ");
 410    int count = 0;
 411    for (int i=0; i<CNT; i++) {
 412       for (int j=0; j<CNT; j++) {
 413          for (int k=0; k<CNT; k++) {
 414             count++;
 415             if ((count & 0x3FF) == 0) {
 416                Dmsg1(000, "At %d\n", count);
 417             }
 418             jcr = (MYJCR *)malloc(sizeof(MYJCR));
 419             memset(jcr, 0, sizeof(MYJCR));
 420             jcr->buf = bstrdup(buf);
 421 //          printf("buf=%p %s\n", jcr, jcr->buf);
 422             jcr1 = (MYJCR *)jcr_chain->insert((void *)jcr, my_compare);
 423             if (jcr != jcr1) {
 424                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 425             }
 426             buf[1]--;
 427          }
 428          buf[1] = 'Z';
 429          buf[2]--;
 430       }
 431       buf[2] = 'Z';
 432       buf[0]--;
 433    }
 434    printf("%d items appended\n", CNT*CNT*CNT);
 435    printf("num_items=%d\n", jcr_chain->size());
 436
 437    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 438    memset(jcr, 0, sizeof(MYJCR));
 439
 440    jcr->buf = bstrdup("a");
 441    if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
 442       printf("One less failed!!!! Got: %s\n", jcr1->buf);
 443    } else {
 444       printf("One less: OK\n");
 445    }
 446    free(jcr->buf);
 447
 448    jcr->buf = bstrdup("ZZZZZZZZZZZZZZZZ");
 449    if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
 450       printf("One greater failed!!!! Got:%s\n", jcr1->buf);
 451    } else {
 452       printf("One greater: OK\n");
 453    }
 454    free(jcr->buf);
 455
 456    jcr->buf = bstrdup("AAA");
 457    if ((jcr1=(MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
 458       printf("Search for AAA got %s\n", jcr1->buf);
 459    } else {
 460       printf("Search for AAA not found\n");
 461    }
 462    free(jcr->buf);
 463
 464    jcr->buf = bstrdup("ZZZ");
 465    if ((jcr1 = (MYJCR *)jcr_chain->search((void *)jcr, my_compare))) {
 466       printf("Search for ZZZ got %s\n", jcr1->buf);
 467    } else {
 468       printf("Search for ZZZ not found\n");
 469    }
 470    free(jcr->buf);
 471    free(jcr);
 472
 473
 474    printf("Find each of %d items in tree.\n", count);
 475    for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((void *)jcr)) ) {
 476 //    printf("Got: %s\n", jcr->buf);
 477       if (!jcr_chain->search((void *)jcr, my_compare)) {
 478          printf("rblist binary_search item not found = %s\n", jcr->buf);
 479       }
 480    }
 481    printf("Free each of %d items in tree.\n", count);
 482    for (jcr=(MYJCR *)jcr_chain->first(); jcr; (jcr=(MYJCR *)jcr_chain->next((void *)jcr)) ) {
 483 //    printf("Free: %p %s\n", jcr, jcr->buf);
 484       free(jcr->buf);
 485       jcr->buf = NULL;
 486    }
 487    printf("num_items=%d\n", jcr_chain->size());
 488    delete jcr_chain;
 489
 490
 491    sm_dump(true);      /* unit test */
 492
 493 }
 494 #endif