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

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