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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2003-2007 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 two of the GNU General Public
  10    License as published by the Free Software Foundation plus additions
  11    that are listed 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 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 John Walker.
  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 doubly linked list routines.
  30  *
  31  *    dlist is a doubly linked list with the links being in the
  32  *       list data item.
  33  *
  34  *   Kern Sibbald, July MMIII
  35  *
  36  *   Version $Id$
  37  *
  38  */
  39
  40 #include "bacula.h"
  41
  42 /* ===================================================================
  43  *    dlist
  44  */
  45
  46 /*
  47  * Append an item to the list
  48  */
  49 void dlist::append(void *item)
  50 {
  51    set_next(item, NULL);
  52    set_prev(item, tail);
  53    if (tail) {
  54       set_next(tail, item);
  55    }
  56    tail = item;
  57    if (head == NULL) {                /* if empty list, */
  58       head = item;                    /* item is head as well */
  59    }
  60    num_items++;
  61 }
  62
  63 /*
  64  * Append an item to the list
  65  */
  66 void dlist::prepend(void *item)
  67 {
  68    set_next(item, head);
  69    set_prev(item, NULL);
  70    if (head) {
  71       set_prev(head, item);
  72    }
  73    head = item;
  74    if (tail == NULL) {                /* if empty list, */
  75       tail = item;                    /* item is tail too */
  76    }
  77    num_items++;
  78 }
  79
  80 void dlist::insert_before(void *item, void *where)
  81 {
  82    dlink *where_link = (dlink *)((char *)where+loffset);
  83
  84    set_next(item, where);
  85    set_prev(item, where_link->prev);
  86
  87    if (where_link->prev) {
  88       set_next(where_link->prev, item);
  89    }
  90    where_link->prev = item;
  91    if (head == where) {
  92       head = item;
  93    }
  94    num_items++;
  95 }
  96
  97 void dlist::insert_after(void *item, void *where)
  98 {
  99    dlink *where_link = (dlink *)((char *)where+loffset);
 100
 101    set_next(item, where_link->next);
 102    set_prev(item, where);
 103
 104    if (where_link->next) {
 105       set_prev(where_link->next, item);
 106    }
 107    where_link->next = item;
 108    if (tail == where) {
 109       tail = item;
 110    }
 111    num_items++;
 112 }
 113
 114 /*
 115  *  Insert an item in the list, but only if it is unique
 116  *  otherwise, the item is returned non inserted
 117  *
 118  * Returns: item         if item inserted
 119  *          other_item   if same value already exists (item not inserted)
 120  */
 121 void *dlist::binary_insert(void *item, int compare(void *item1, void *item2))
 122 {
 123    int comp;
 124    int low, high, cur;
 125    void *cur_item;
 126
 127    if (num_items == 0) {
 128     //Dmsg0(000, "Append first.\n");
 129       append(item);
 130       return item;
 131    }
 132    if (num_items == 1) {
 133       comp = compare(item, first());
 134       if (comp < 0) {
 135          prepend(item);
 136        //Dmsg0(000, "Insert before first.\n");
 137          return item;
 138       } else if (comp > 0) {
 139          insert_after(item, first());
 140        //Dmsg0(000, "Insert after first.\n");
 141          return item;
 142       } else {
 143        //Dmsg0(000, "Same as first.\n");
 144          return first();
 145       }
 146    }
 147    /* Check against last item */
 148    comp = compare(item, last());
 149    if (comp > 0) {
 150       append(item);
 151     //Dmsg0(000, "Appended item.\n");
 152       return item;
 153    } else if (comp == 0) {
 154     //Dmsg0(000, "Same as last.\n");
 155       return last();
 156    }
 157    /* Check against first item */
 158    comp = compare(item, first());
 159    if (comp < 0) {
 160       prepend(item);
 161     //Dmsg0(000, "Inserted item before.\n");
 162       return item;
 163    } else if (comp == 0) {
 164     //Dmsg0(000, "Same as first.\n");
 165       return first();
 166    }
 167    if (num_items == 2) {
 168       insert_after(item, first());
 169     //Dmsg0(000, "Inserted item after.\n");
 170       return item;
 171    }
 172    low = 1;
 173    high = num_items;
 174    cur = 1;
 175    cur_item = first();
 176    while (low < high) {
 177       int nxt;
 178       nxt = (low + high) / 2;
 179       while (nxt > cur) {
 180          cur_item = next(cur_item);
 181          cur++;
 182       }
 183       while (nxt < cur) {
 184          cur_item = prev(cur_item);
 185          cur--;
 186       }
 187     //Dmsg1(000, "Compare item to %d\n", cur);
 188       comp = compare(item, cur_item);
 189     //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
 190       if (comp < 0) {
 191          high = cur;
 192        //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
 193       } else if (comp > 0) {
 194          low = cur + 1;
 195        //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
 196       } else {
 197        //Dmsg1(000, "Same as item %d\n", cur);
 198          return cur_item;
 199       }
 200    }
 201    if (high == cur) {
 202       insert_before(item, cur_item);
 203     //Dmsg1(000, "Insert before item %d\n", cur);
 204    } else {
 205       insert_after(item, cur_item);
 206     //Dmsg1(000, "Insert after item %d\n", cur);
 207    }
 208    return item;
 209 }
 210
 211 /*
 212  *  Insert an item in the list, regardless if it is unique
 213  *  or not.
 214  */
 215 void dlist::binary_insert_multiple(void *item, int compare(void *item1, void *item2))
 216 {
 217    void *ins_item = binary_insert(item, compare);
 218    /* If identical, insert after the one found */
 219    if (ins_item != item) {
 220       insert_after(item, ins_item);
 221    }
 222 }
 223
 224 /*
 225  * Search for item
 226  */
 227 void *dlist::binary_search(void *item, int compare(void *item1, void *item2))
 228 {
 229    int comp;
 230    int low, high, cur;
 231    void *cur_item;
 232
 233
 234    if (num_items == 0) {
 235       return NULL;
 236    }
 237    cur_item = first();
 238    if (num_items == 1) {
 239       comp = compare(item, cur_item);
 240       if (comp == 0) {
 241          return cur_item;
 242       } else {
 243          return NULL;
 244       }
 245    }
 246    low = 1;
 247    high = num_items;
 248    cur = 1;
 249    cur_item = first();
 250    while (low < high) {
 251       int nxt;
 252       nxt = (low + high) / 2;
 253       /* Now get cur pointing to nxt */
 254       while (nxt > cur) {
 255          cur_item = next(cur_item);
 256          cur++;
 257       }
 258       while (nxt < cur) {
 259          cur_item = prev(cur_item);
 260          cur--;
 261       }
 262       comp = compare(item, cur_item);
 263       //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
 264       if (comp < 0) {
 265          high = cur;
 266          //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
 267       } else if (comp > 0) {
 268          low = cur + 1;
 269          //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
 270       } else {
 271          return cur_item;
 272       }
 273    }
 274    /*
 275     * low == high can only happen if low just
 276     *   got incremented from cur, and we have
 277     *   not yet tested cur+1
 278     */
 279    if (low == high) {
 280       cur_item = next(cur_item);
 281       comp = compare(item, cur_item);
 282       if (comp == 0) {
 283          return cur_item;
 284       }
 285    }
 286    return NULL;
 287 }
 288
 289
 290 void dlist::remove(void *item)
 291 {
 292    void *xitem;
 293    dlink *ilink = (dlink *)(((char *)item)+loffset);   /* item's link */
 294    if (item == head) {
 295       head = ilink->next;
 296       if (head) {
 297          set_prev(head, NULL);
 298       }
 299       if (item == tail) {
 300          tail = ilink->prev;
 301       }
 302    } else if (item == tail) {
 303       tail = ilink->prev;
 304       if (tail) {
 305          set_next(tail, NULL);
 306       }
 307    } else {
 308       xitem = ilink->next;
 309       set_prev(xitem, ilink->prev);
 310       xitem = ilink->prev;
 311       set_next(xitem, ilink->next);
 312    }
 313    num_items--;
 314    if (num_items == 0) {
 315       head = tail = NULL;
 316    }
 317 }
 318
 319 void * dlist::next(const void *item) const
 320 {
 321    if (item == NULL) {
 322       return head;
 323    }
 324    return ((dlink *)(((char *)item)+loffset))->next;
 325 }
 326
 327 void * dlist::prev(const void *item) const
 328 {
 329    if (item == NULL) {
 330       return tail;
 331    }
 332    return ((dlink *)(((char *)item)+loffset))->prev;
 333 }
 334
 335
 336 /* Destroy the list contents */
 337 void dlist::destroy()
 338 {
 339    for (void *n=head; n; ) {
 340       void *ni = ((dlink *)(((char *)n)+loffset))->next;
 341       free(n);
 342       n = ni;
 343    }
 344    num_items = 0;
 345    head = tail = NULL;
 346 }
 347
 348 /* String helpers for dlist usage */
 349
 350 dlistString *new_dlistString(const char *str)
 351 {
 352    return new_dlistString(str, strlen(str));
 353 }
 354
 355 dlistString *new_dlistString(const char *str, int len)
 356 {
 357    dlistString *node;
 358    node = (dlistString *)malloc(sizeof(dlistString) + len);
 359    bstrncpy(node->c_str(), str, len);
 360    return node;
 361 }
 362
 363 #ifdef TEST_PROGRAM
 364
 365 struct MYJCR {
 366    char *buf;
 367    dlink link;
 368 };
 369
 370 static int my_compare(void *item1, void *item2)
 371 {
 372    MYJCR *jcr1, *jcr2;
 373    int comp;
 374    jcr1 = (MYJCR *)item1;
 375    jcr2 = (MYJCR *)item2;
 376    comp = strcmp(jcr1->buf, jcr2->buf);
 377  //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
 378    return comp;
 379 }
 380
 381 int main()
 382 {
 383    char buf[30];
 384    dlist *jcr_chain;
 385    MYJCR *jcr = NULL;
 386    MYJCR *jcr1;
 387    MYJCR *save_jcr = NULL;
 388    MYJCR *next_jcr;
 389    int count;
 390
 391    jcr_chain = (dlist *)malloc(sizeof(dlist));
 392    jcr_chain->init(jcr, &jcr->link);
 393
 394    printf("Prepend 20 items 0-19\n");
 395    for (int i=0; i<20; i++) {
 396       sprintf(buf, "This is dlist item %d", i);
 397       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 398       jcr->buf = bstrdup(buf);
 399       jcr_chain->prepend(jcr);
 400       if (i == 10) {
 401          save_jcr = jcr;
 402       }
 403    }
 404
 405    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 406    printf("11th item=%s\n", next_jcr->buf);
 407    jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
 408    jcr1->buf = save_jcr->buf;
 409    printf("Remove 10th item\n");
 410    jcr_chain->remove(save_jcr);
 411    free(save_jcr);
 412    printf("Re-insert 10th item\n");
 413    jcr_chain->insert_before(jcr1, next_jcr);
 414
 415    printf("Print remaining list.\n");
 416    foreach_dlist(jcr, jcr_chain) {
 417       printf("Dlist item = %s\n", jcr->buf);
 418       free(jcr->buf);
 419    }
 420    jcr_chain->destroy();
 421    free(jcr_chain);
 422
 423    /* The following may seem a bit odd, but we create a chaing
 424     *  of jcr objects.  Within a jcr object, there is a buf
 425     *  that points to a malloced string containing data
 426     */
 427    jcr_chain = New(dlist(jcr, &jcr->link));
 428    printf("append 20 items 0-19\n");
 429    for (int i=0; i<20; i++) {
 430       sprintf(buf, "This is dlist item %d", i);
 431       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 432       jcr->buf = bstrdup(buf);
 433       jcr_chain->append(jcr);
 434       if (i == 10) {
 435          save_jcr = jcr;
 436       }
 437    }
 438
 439    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 440    printf("11th item=%s\n", next_jcr->buf);
 441    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 442    jcr->buf = save_jcr->buf;
 443    printf("Remove 10th item\n");
 444    jcr_chain->remove(save_jcr);
 445    free(save_jcr);
 446    printf("Re-insert 10th item\n");
 447    jcr_chain->insert_before(jcr, next_jcr);
 448
 449    printf("Print remaining list.\n");
 450    foreach_dlist (jcr, jcr_chain) {
 451       printf("Dlist item = %s\n", jcr->buf);
 452       free(jcr->buf);
 453    }
 454
 455    delete jcr_chain;
 456
 457
 458    /* Now do a binary insert for the list */
 459    jcr_chain = New(dlist(jcr, &jcr->link));
 460 #define CNT 26
 461    printf("append %d items\n", CNT*CNT*CNT);
 462    strcpy(buf, "ZZZ");
 463    count = 0;
 464    for (int i=0; i<CNT; i++) {
 465       for (int j=0; j<CNT; j++) {
 466          for (int k=0; k<CNT; k++) {
 467             count++;
 468             if ((count & 0x3FF) == 0) {
 469                Dmsg1(000, "At %d\n", count);
 470             }
 471             jcr = (MYJCR *)malloc(sizeof(MYJCR));
 472             jcr->buf = bstrdup(buf);
 473             jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
 474             if (jcr != jcr1) {
 475                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 476             }
 477             buf[1]--;
 478          }
 479          buf[1] = 'Z';
 480          buf[2]--;
 481       }
 482       buf[2] = 'Z';
 483       buf[0]--;
 484    }
 485
 486    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 487    strcpy(buf, "a");
 488    jcr->buf = bstrdup(buf);
 489    if (jcr_chain->binary_search(jcr, my_compare)) {
 490       printf("One less failed!!!!\n");
 491    } else {
 492       printf("One less: OK\n");
 493    }
 494    free(jcr->buf);
 495    strcpy(buf, "ZZZZZZZZZZZZZZZZ");
 496    jcr->buf = bstrdup(buf);
 497    if (jcr_chain->binary_search(jcr, my_compare)) {
 498       printf("One greater failed!!!!\n");
 499    } else {
 500       printf("One greater: OK\n");
 501    }
 502    free(jcr->buf);
 503    free(jcr);
 504
 505
 506    printf("Find each of %d items in list.\n", count);
 507    foreach_dlist (jcr, jcr_chain) {
 508       if (!jcr_chain->binary_search(jcr, my_compare)) {
 509          printf("Dlist binary_search item not found = %s\n", jcr->buf);
 510       }
 511    }
 512    printf("Free each of %d items in list.\n", count);
 513    foreach_dlist (jcr, jcr_chain) {
 514       free(jcr->buf);
 515       jcr->buf = NULL;
 516    }
 517    delete jcr_chain;
 518
 519    /* Finally, do a test using the dlistString string helper, which
 520     *  allocates a dlist node and stores the string directly in
 521     *  it.
 522     */
 523    dlist chain;
 524    dlistString *node;
 525 #define CNT 26
 526    printf("append %d dlistString items\n", CNT*CNT*CNT);
 527    strcpy(buf, "ZZZ");
 528    count = 0;
 529    for (int i=0; i<CNT; i++) {
 530       for (int j=0; j<CNT; j++) {
 531          for (int k=0; k<CNT; k++) {
 532             count++;
 533             if ((count & 0x3FF) == 0) {
 534                Dmsg1(000, "At %d\n", count);
 535             }
 536             node = new_dlistString(buf);
 537             chain.append(node);
 538             buf[1]--;
 539          }
 540          buf[1] = 'Z';
 541          buf[2]--;
 542       }
 543       buf[2] = 'Z';
 544       buf[0]--;
 545    }
 546    printf("dlistString items appended, walking chain\n");
 547    foreach_dlist(node, &chain) {
 548       printf("%s\n", node->c_str());
 549    }
 550    printf("destroy dlistString chain\n");
 551    chain.destroy();
 552
 553    sm_dump(false);
 554
 555 }
 556 #endif