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

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