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

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