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) 2000-2005 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 ammended 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::unique_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 /*
 200  *  Insert an item in the list, regardless if it is unique
 201  *  or not.
 202  */
 203 void dlist::binary_insert(void *item, int compare(void *item1, void *item2))
 204 {
 205    void *ins_item = unique_binary_insert(item, compare);
 206    /* If identical, insert after the one found */
 207    if (ins_item != item) {
 208       insert_after(item, ins_item);
 209    }
 210 }
 211
 212
 213 void dlist::remove(void *item)
 214 {
 215    void *xitem;
 216    dlink *ilink = (dlink *)(((char *)item)+loffset);   /* item's link */
 217    if (item == head) {
 218       head = ilink->next;
 219       if (head) {
 220          ((dlink *)(((char *)head)+loffset))->prev = NULL;
 221       }
 222       if (item == tail) {
 223          tail = ilink->prev;
 224       }
 225    } else if (item == tail) {
 226       tail = ilink->prev;
 227       if (tail) {
 228          ((dlink *)(((char *)tail)+loffset))->next = NULL;
 229       }
 230    } else {
 231       xitem = ilink->next;
 232       ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
 233       xitem = ilink->prev;
 234       ((dlink *)(((char *)xitem)+loffset))->next = ilink->next;
 235    }
 236    num_items--;
 237    if (num_items == 0) {
 238       head = tail = NULL;
 239    }
 240 }
 241
 242 void * dlist::next(const void *item) const
 243 {
 244    if (item == NULL) {
 245       return head;
 246    }
 247    return ((dlink *)(((char *)item)+loffset))->next;
 248 }
 249
 250 void * dlist::prev(const void *item) const
 251 {
 252    if (item == NULL) {
 253       return tail;
 254    }
 255    return ((dlink *)(((char *)item)+loffset))->prev;
 256 }
 257
 258
 259 /* Destroy the list contents */
 260 void dlist::destroy()
 261 {
 262    for (void *n=head; n; ) {
 263       void *ni = ((dlink *)(((char *)n)+loffset))->next;
 264       free(n);
 265       n = ni;
 266    }
 267    num_items = 0;
 268    head = tail = NULL;
 269 }
 270
 271
 272
 273 #ifdef TEST_PROGRAM
 274
 275 struct MYJCR {
 276    char *buf;
 277    dlink link;
 278 };
 279
 280 static int my_compare(void *item1, void *item2)
 281 {
 282    MYJCR *jcr1, *jcr2;
 283    int comp;
 284    jcr1 = (MYJCR *)item1;
 285    jcr2 = (MYJCR *)item2;
 286    comp = strcmp(jcr1->buf, jcr2->buf);
 287  //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
 288    return comp;
 289 }
 290
 291 int main()
 292 {
 293    char buf[30];
 294    dlist *jcr_chain;
 295    MYJCR *jcr = NULL;
 296    MYJCR *jcr1;
 297    MYJCR *save_jcr = NULL;
 298    MYJCR *next_jcr;
 299
 300    jcr_chain = (dlist *)malloc(sizeof(dlist));
 301    jcr_chain->init(jcr, &jcr->link);
 302
 303    printf("Prepend 20 items 0-19\n");
 304    for (int i=0; i<20; i++) {
 305       sprintf(buf, "This is dlist item %d", i);
 306       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 307       jcr->buf = bstrdup(buf);
 308       jcr_chain->prepend(jcr);
 309       if (i == 10) {
 310          save_jcr = jcr;
 311       }
 312    }
 313
 314    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 315    printf("11th item=%s\n", next_jcr->buf);
 316    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 317    jcr->buf = save_jcr->buf;
 318    printf("Remove 10th item\n");
 319    jcr_chain->remove(save_jcr);
 320    printf("Re-insert 10th item\n");
 321    jcr_chain->insert_before(jcr, next_jcr);
 322
 323    printf("Print remaining list.\n");
 324    foreach_dlist (jcr, jcr_chain) {
 325       printf("Dlist item = %s\n", jcr->buf);
 326       free(jcr->buf);
 327    }
 328    jcr_chain->destroy();
 329    free(jcr_chain);
 330
 331    jcr_chain = New(dlist(jcr, &jcr->link));
 332    printf("append 20 items 0-19\n");
 333    for (int i=0; i<20; i++) {
 334       sprintf(buf, "This is dlist item %d", i);
 335       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 336       jcr->buf = bstrdup(buf);
 337       jcr_chain->append(jcr);
 338       if (i == 10) {
 339          save_jcr = jcr;
 340       }
 341    }
 342
 343    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 344    printf("11th item=%s\n", next_jcr->buf);
 345    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 346    jcr->buf = save_jcr->buf;
 347    printf("Remove 10th item\n");
 348    jcr_chain->remove(save_jcr);
 349    printf("Re-insert 10th item\n");
 350    jcr_chain->insert_before(jcr, next_jcr);
 351
 352    printf("Print remaining list.\n");
 353    foreach_dlist (jcr, jcr_chain) {
 354       printf("Dlist item = %s\n", jcr->buf);
 355       free(jcr->buf);
 356    }
 357
 358    delete jcr_chain;
 359
 360
 361    /* Now do a binary insert for the list */
 362    jcr_chain = New(dlist(jcr, &jcr->link));
 363 #define CNT 26
 364    printf("append %d items\n", CNT*CNT*CNT);
 365    strcpy(buf, "ZZZ");
 366    int count = 0;
 367    for (int i=0; i<CNT; i++) {
 368       for (int j=0; j<CNT; j++) {
 369          for (int k=0; k<CNT; k++) {
 370             count++;
 371             if ((count & 0x3FF) == 0) {
 372                Dmsg1(000, "At %d\n", count);
 373             }
 374             jcr = (MYJCR *)malloc(sizeof(MYJCR));
 375             jcr->buf = bstrdup(buf);
 376             jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
 377             if (jcr != jcr1) {
 378                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 379             }
 380             buf[1]--;
 381          }
 382          buf[1] = 'Z';
 383          buf[2]--;
 384       }
 385       buf[2] = 'Z';
 386       buf[0]--;
 387    }
 388
 389    printf("Print sorted list.\n");
 390    foreach_dlist (jcr, jcr_chain) {
 391       printf("Dlist item = %s\n", jcr->buf);
 392       free(jcr->buf);
 393    }
 394
 395    delete jcr_chain;
 396
 397
 398    sm_dump(false);
 399
 400 }
 401 #endif