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    Bacula® - The Network Backup Solution
  14
  15    Copyright (C) 2003-2006 Free Software Foundation Europe e.V.
  16
  17    The main author of Bacula is Kern Sibbald, with contributions from
  18    many others, a complete list can be found in the file AUTHORS.
  19    This program is Free Software; you can redistribute it and/or
  20    modify it under the terms of version two of the GNU General Public
  21    License as published by the Free Software Foundation plus additions
  22    that are listed in the file LICENSE.
  23
  24    This program is distributed in the hope that it will be useful, but
  25    WITHOUT ANY WARRANTY; without even the implied warranty of
  26    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  27    General Public License for more details.
  28
  29    You should have received a copy of the GNU General Public License
  30    along with this program; if not, write to the Free Software
  31    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  32    02110-1301, USA.
  33
  34    Bacula® is a registered trademark of John Walker.
  35    The licensor of Bacula is the Free Software Foundation Europe
  36    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  37    Switzerland, email:ftf@fsfeurope.org.
  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    ((dlink *)(((char *)item)+loffset))->next = NULL;
  52    ((dlink *)(((char *)item)+loffset))->prev = tail;
  53    if (tail) {
  54       ((dlink *)(((char *)tail)+loffset))->next = 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    ((dlink *)(((char *)item)+loffset))->next = head;
  69    ((dlink *)(((char *)item)+loffset))->prev = NULL;
  70    if (head) {
  71       ((dlink *)(((char *)head)+loffset))->prev = 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    ((dlink *)(((char *)item)+loffset))->next = where;
  85    ((dlink *)(((char *)item)+loffset))->prev = where_link->prev;
  86
  87    if (where_link->prev) {
  88       ((dlink *)(((char *)(where_link->prev))+loffset))->next = 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    ((dlink *)(((char *)item)+loffset))->next = where_link->next;
 102    ((dlink *)(((char *)item)+loffset))->prev = where;
 103
 104    if (where_link->next) {
 105       ((dlink *)(((char *)(where_link->next))+loffset))->prev = 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          ((dlink *)(((char *)head)+loffset))->prev = NULL;
 298       }
 299       if (item == tail) {
 300          tail = ilink->prev;
 301       }
 302    } else if (item == tail) {
 303       tail = ilink->prev;
 304       if (tail) {
 305          ((dlink *)(((char *)tail)+loffset))->next = NULL;
 306       }
 307    } else {
 308       xitem = ilink->next;
 309       ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
 310       xitem = ilink->prev;
 311       ((dlink *)(((char *)xitem)+loffset))->next = 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
 349
 350 #ifdef TEST_PROGRAM
 351
 352 struct MYJCR {
 353    char *buf;
 354    dlink link;
 355 };
 356
 357 static int my_compare(void *item1, void *item2)
 358 {
 359    MYJCR *jcr1, *jcr2;
 360    int comp;
 361    jcr1 = (MYJCR *)item1;
 362    jcr2 = (MYJCR *)item2;
 363    comp = strcmp(jcr1->buf, jcr2->buf);
 364  //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
 365    return comp;
 366 }
 367
 368 int main()
 369 {
 370    char buf[30];
 371    dlist *jcr_chain;
 372    MYJCR *jcr = NULL;
 373    MYJCR *jcr1;
 374    MYJCR *save_jcr = NULL;
 375    MYJCR *next_jcr;
 376
 377    jcr_chain = (dlist *)malloc(sizeof(dlist));
 378    jcr_chain->init(jcr, &jcr->link);
 379
 380    printf("Prepend 20 items 0-19\n");
 381    for (int i=0; i<20; i++) {
 382       sprintf(buf, "This is dlist item %d", i);
 383       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 384       jcr->buf = bstrdup(buf);
 385       jcr_chain->prepend(jcr);
 386       if (i == 10) {
 387          save_jcr = jcr;
 388       }
 389    }
 390
 391    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 392    printf("11th item=%s\n", next_jcr->buf);
 393    jcr1 = (MYJCR *)malloc(sizeof(MYJCR));
 394    jcr1->buf = save_jcr->buf;
 395    printf("Remove 10th item\n");
 396    jcr_chain->remove(save_jcr);
 397    free(save_jcr);
 398    printf("Re-insert 10th item\n");
 399    jcr_chain->insert_before(jcr1, next_jcr);
 400
 401    printf("Print remaining list.\n");
 402    foreach_dlist(jcr, jcr_chain) {
 403       printf("Dlist item = %s\n", jcr->buf);
 404       free(jcr->buf);
 405    }
 406    jcr_chain->destroy();
 407    free(jcr_chain);
 408
 409    jcr_chain = New(dlist(jcr, &jcr->link));
 410    printf("append 20 items 0-19\n");
 411    for (int i=0; i<20; i++) {
 412       sprintf(buf, "This is dlist item %d", i);
 413       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 414       jcr->buf = bstrdup(buf);
 415       jcr_chain->append(jcr);
 416       if (i == 10) {
 417          save_jcr = jcr;
 418       }
 419    }
 420
 421    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 422    printf("11th item=%s\n", next_jcr->buf);
 423    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 424    jcr->buf = save_jcr->buf;
 425    printf("Remove 10th item\n");
 426    jcr_chain->remove(save_jcr);
 427    free(save_jcr);
 428    printf("Re-insert 10th item\n");
 429    jcr_chain->insert_before(jcr, next_jcr);
 430
 431    printf("Print remaining list.\n");
 432    foreach_dlist (jcr, jcr_chain) {
 433       printf("Dlist item = %s\n", jcr->buf);
 434       free(jcr->buf);
 435    }
 436
 437    delete jcr_chain;
 438
 439
 440    /* Now do a binary insert for the list */
 441    jcr_chain = New(dlist(jcr, &jcr->link));
 442 #define CNT 26
 443    printf("append %d items\n", CNT*CNT*CNT);
 444    strcpy(buf, "ZZZ");
 445    int count = 0;
 446    for (int i=0; i<CNT; i++) {
 447       for (int j=0; j<CNT; j++) {
 448          for (int k=0; k<CNT; k++) {
 449             count++;
 450             if ((count & 0x3FF) == 0) {
 451                Dmsg1(000, "At %d\n", count);
 452             }
 453             jcr = (MYJCR *)malloc(sizeof(MYJCR));
 454             jcr->buf = bstrdup(buf);
 455             jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
 456             if (jcr != jcr1) {
 457                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 458             }
 459             buf[1]--;
 460          }
 461          buf[1] = 'Z';
 462          buf[2]--;
 463       }
 464       buf[2] = 'Z';
 465       buf[0]--;
 466    }
 467
 468    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 469    strcpy(buf, "a");
 470    jcr->buf = bstrdup(buf);
 471    if (jcr_chain->binary_search(jcr, my_compare)) {
 472       printf("One less failed!!!!\n");
 473    } else {
 474       printf("One less: OK\n");
 475    }
 476    free(jcr->buf);
 477    strcpy(buf, "ZZZZZZZZZZZZZZZZ");
 478    jcr->buf = bstrdup(buf);
 479    if (jcr_chain->binary_search(jcr, my_compare)) {
 480       printf("One greater failed!!!!\n");
 481    } else {
 482       printf("One greater: OK\n");
 483    }
 484    free(jcr->buf);
 485    free(jcr);
 486
 487
 488    printf("Find each of %d items in list.\n", count);
 489    foreach_dlist (jcr, jcr_chain) {
 490       if (!jcr_chain->binary_search(jcr, my_compare)) {
 491          printf("Dlist binary_search item not found = %s\n", jcr->buf);
 492       }
 493    }
 494    printf("Free each of %d items in list.\n", count);
 495    foreach_dlist (jcr, jcr_chain) {
 496       free(jcr->buf);
 497       jcr->buf = NULL;
 498    }
 499    delete jcr_chain;
 500
 501
 502    sm_dump(false);
 503
 504 }
 505 #endif