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-2004 Kern Sibbald and John Walker
  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 as
  17    published by the Free Software Foundation; either version 2 of
  18    the License, or (at your option) any later version.
  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 GNU
  23    General Public License for more details.
  24
  25    You should have received a copy of the GNU General Public
  26    License along with this program; if not, write to the Free
  27    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  28    MA 02111-1307, USA.
  29
  30  */
  31
  32 #include "bacula.h"
  33
  34 /* ===================================================================
  35  *    dlist
  36  */
  37 /*
  38  * Append an item to the list
  39  */
  40 void dlist::append(void *item)
  41 {
  42    ((dlink *)(((char *)item)+loffset))->next = NULL;
  43    ((dlink *)(((char *)item)+loffset))->prev = tail;
  44    if (tail) {
  45       ((dlink *)(((char *)tail)+loffset))->next = item;
  46    }
  47    tail = item;
  48    if (head == NULL) {                /* if empty list, */
  49       head = item;                    /* item is head as well */
  50    }
  51    num_items++;
  52 }
  53
  54 /*
  55  * Append an item to the list
  56  */
  57 void dlist::prepend(void *item)
  58 {
  59    ((dlink *)(((char *)item)+loffset))->next = head;
  60    ((dlink *)(((char *)item)+loffset))->prev = NULL;
  61    if (head) {
  62       ((dlink *)(((char *)head)+loffset))->prev = item;
  63    }
  64    head = item;
  65    if (tail == NULL) {                /* if empty list, */
  66       tail = item;                    /* item is tail too */
  67    }
  68    num_items++;
  69 }
  70
  71 void dlist::insert_before(void *item, void *where)
  72 {
  73    dlink *where_link = (dlink *)((char *)where+loffset);
  74
  75    ((dlink *)(((char *)item)+loffset))->next = where;
  76    ((dlink *)(((char *)item)+loffset))->prev = where_link->prev;
  77
  78    if (where_link->prev) {
  79       ((dlink *)(((char *)(where_link->prev))+loffset))->next = item;
  80    }
  81    where_link->prev = item;
  82    if (head == where) {
  83       head = item;
  84    }
  85    num_items++;
  86 }
  87
  88 void dlist::insert_after(void *item, void *where)
  89 {
  90    dlink *where_link = (dlink *)((char *)where+loffset);
  91
  92    ((dlink *)(((char *)item)+loffset))->next = where_link->next;
  93    ((dlink *)(((char *)item)+loffset))->prev = where;
  94
  95    if (where_link->next) {
  96       ((dlink *)(((char *)(where_link->next))+loffset))->prev = item;
  97    }
  98    where_link->next = item;
  99    if (tail == where) {
 100       tail = item;
 101    }
 102    num_items++;
 103 }
 104
 105 /*
 106  *  Insert an item in the list, but only if it is unique
 107  *  otherwise, the item is returned non inserted
 108  *
 109  * Returns: item         if item inserted
 110  *          other_item   if same value already exists (item not inserted)
 111  */
 112 void *dlist::unique_binary_insert(void *item, int compare(void *item1, void *item2))
 113 {
 114    int comp;
 115    int low, high, cur;
 116    void *cur_item;
 117
 118    if (num_items == 0) {
 119     //Dmsg0(000, "Append first.\n");
 120       append(item);
 121       return item;
 122    }
 123    if (num_items == 1) {
 124       comp = compare(item, first());
 125       if (comp < 0) {
 126          prepend(item);
 127        //Dmsg0(000, "Insert before first.\n");
 128          return item;
 129       } else if (comp > 0) {
 130          insert_after(item, first());
 131        //Dmsg0(000, "Insert after first.\n");
 132          return item;
 133       } else {
 134        //Dmsg0(000, "Same as first.\n");
 135          return first();
 136       }
 137    }
 138    /* Check against last item */
 139    comp = compare(item, last());
 140    if (comp > 0) {
 141       append(item);
 142     //Dmsg0(000, "Appended item.\n");
 143       return item;
 144    } else if (comp == 0) {
 145     //Dmsg0(000, "Same as last.\n");
 146       return last();
 147    }
 148    /* Check against first item */
 149    comp = compare(item, first());
 150    if (comp < 0) {
 151       prepend(item);
 152     //Dmsg0(000, "Inserted item before.\n");
 153       return item;
 154    } else if (comp == 0) {
 155     //Dmsg0(000, "Same as first.\n");
 156       return first();
 157    }
 158    if (num_items == 2) {
 159       insert_after(item, first());
 160     //Dmsg0(000, "Inserted item after.\n");
 161       return item;
 162    }
 163    low = 1;
 164    high = num_items;
 165    cur = 1;
 166    cur_item = first();
 167    while (low < high) {
 168       int nxt;
 169       nxt = (low + high) / 2;
 170       while (nxt > cur) {
 171          cur_item = next(cur_item);
 172          cur++;
 173       }
 174       while (nxt < cur) {
 175          cur_item = prev(cur_item);
 176          cur--;
 177       }
 178     //Dmsg1(000, "Compare item to %d\n", cur);
 179       comp = compare(item, cur_item);
 180     //Dmsg2(000, "Compare item to %d = %d\n", cur, comp);
 181       if (comp < 0) {
 182          high = cur;
 183        //Dmsg2(000, "set high; low=%d high=%d\n", low, high);
 184       } else if (comp > 0) {
 185          low = cur + 1;
 186        //Dmsg2(000, "set low; low=%d high=%d\n", low, high);
 187       } else {
 188        //Dmsg1(000, "Same as item %d\n", cur);
 189          return cur_item;
 190       }
 191    }
 192    if (high == cur) {
 193       insert_before(item, cur_item);
 194     //Dmsg1(000, "Insert before item %d\n", cur);
 195    } else {
 196       insert_after(item, cur_item);
 197     //Dmsg1(000, "Insert after item %d\n", cur);
 198    }
 199    return item;
 200 }
 201
 202
 203 /*
 204  *  Insert an item in the list, regardless if it is unique
 205  *  or not.
 206  */
 207 void dlist::binary_insert(void *item, int compare(void *item1, void *item2))
 208 {
 209    void *ins_item = unique_binary_insert(item, compare);
 210    /* If identical, insert after the one found */
 211    if (ins_item != item) {
 212       insert_after(item, ins_item);
 213    }
 214 }
 215
 216
 217 void dlist::remove(void *item)
 218 {
 219    void *xitem;
 220    dlink *ilink = (dlink *)(((char *)item)+loffset);   /* item's link */
 221    if (item == head) {
 222       head = ilink->next;
 223       if (head) {
 224          ((dlink *)(((char *)head)+loffset))->prev = NULL;
 225       }
 226       if (item == tail) {
 227          tail = ilink->prev;
 228       }
 229    } else if (item == tail) {
 230       tail = ilink->prev;
 231       if (tail) {
 232          ((dlink *)(((char *)tail)+loffset))->next = NULL;
 233       }
 234    } else {
 235       xitem = ilink->next;
 236       ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
 237       xitem = ilink->prev;
 238       ((dlink *)(((char *)xitem)+loffset))->next = ilink->next;
 239    }
 240    num_items--;
 241    if (num_items == 0) {
 242       head = tail = NULL;
 243    }
 244 }
 245
 246 void * dlist::next(void *item)
 247 {
 248    if (item == NULL) {
 249       return head;
 250    }
 251    return ((dlink *)(((char *)item)+loffset))->next;
 252 }
 253
 254 void * dlist::prev(void *item)
 255 {
 256    if (item == NULL) {
 257       return tail;
 258    }
 259    return ((dlink *)(((char *)item)+loffset))->prev;
 260 }
 261
 262
 263 /* Destroy the list contents */
 264 void dlist::destroy()
 265 {
 266    for (void *n=head; n; ) {
 267       void *ni = ((dlink *)(((char *)n)+loffset))->next;
 268       free(n);
 269       n = ni;
 270    }
 271    num_items = 0;
 272    head = tail = NULL;
 273 }
 274
 275
 276
 277 #ifdef TEST_PROGRAM
 278
 279 struct MYJCR {
 280    char *buf;
 281    dlink link;
 282 };
 283
 284 static int my_compare(void *item1, void *item2)
 285 {
 286    MYJCR *jcr1, *jcr2;
 287    int comp;
 288    jcr1 = (MYJCR *)item1;
 289    jcr2 = (MYJCR *)item2;
 290    comp = strcmp(jcr1->buf, jcr2->buf);
 291  //Dmsg3(000, "compare=%d: %s to %s\n", comp, jcr1->buf, jcr2->buf);
 292    return comp;
 293 }
 294
 295 int main()
 296 {
 297    char buf[30];
 298    dlist *jcr_chain;
 299    MYJCR *jcr = NULL;
 300    MYJCR *jcr1;
 301    MYJCR *save_jcr = NULL;
 302    MYJCR *next_jcr;
 303
 304    jcr_chain = (dlist *)malloc(sizeof(dlist));
 305    jcr_chain->init(jcr, &jcr->link);
 306
 307    printf("Prepend 20 items 0-19\n");
 308    for (int i=0; i<20; i++) {
 309       sprintf(buf, "This is dlist item %d", i);
 310       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 311       jcr->buf = bstrdup(buf);
 312       jcr_chain->prepend(jcr);
 313       if (i == 10) {
 314          save_jcr = jcr;
 315       }
 316    }
 317
 318    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 319    printf("11th item=%s\n", next_jcr->buf);
 320    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 321    jcr->buf = save_jcr->buf;
 322    printf("Remove 10th item\n");
 323    jcr_chain->remove(save_jcr);
 324    printf("Re-insert 10th item\n");
 325    jcr_chain->insert_before(jcr, next_jcr);
 326
 327    printf("Print remaining list.\n");
 328    foreach_dlist (jcr, jcr_chain) {
 329       printf("Dlist item = %s\n", jcr->buf);
 330       free(jcr->buf);
 331    }
 332    jcr_chain->destroy();
 333    free(jcr_chain);
 334
 335    jcr_chain = new dlist(jcr, &jcr->link);
 336    printf("append 20 items 0-19\n");
 337    for (int i=0; i<20; i++) {
 338       sprintf(buf, "This is dlist item %d", i);
 339       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 340       jcr->buf = bstrdup(buf);
 341       jcr_chain->append(jcr);
 342       if (i == 10) {
 343          save_jcr = jcr;
 344       }
 345    }
 346
 347    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 348    printf("11th item=%s\n", next_jcr->buf);
 349    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 350    jcr->buf = save_jcr->buf;
 351    printf("Remove 10th item\n");
 352    jcr_chain->remove(save_jcr);
 353    printf("Re-insert 10th item\n");
 354    jcr_chain->insert_before(jcr, next_jcr);
 355
 356    printf("Print remaining list.\n");
 357    foreach_dlist (jcr, jcr_chain) {
 358       printf("Dlist item = %s\n", jcr->buf);
 359       free(jcr->buf);
 360    }
 361
 362    delete jcr_chain;
 363
 364
 365    /* Now do a binary insert for the list */
 366    jcr_chain = new dlist(jcr, &jcr->link);
 367 #define CNT 26
 368    printf("append %d items\n", CNT*CNT*CNT);
 369    strcpy(buf, "ZZZ");
 370    int count = 0;
 371    for (int i=0; i<CNT; i++) {
 372       for (int j=0; j<CNT; j++) {
 373          for (int k=0; k<CNT; k++) {
 374             count++;
 375             if ((count & 0x3FF) == 0) {
 376                Dmsg1(000, "At %d\n", count);
 377             }
 378             jcr = (MYJCR *)malloc(sizeof(MYJCR));
 379             jcr->buf = bstrdup(buf);
 380             jcr1 = (MYJCR *)jcr_chain->binary_insert(jcr, my_compare);
 381             if (jcr != jcr1) {
 382                Dmsg2(000, "Insert of %s vs %s failed.\n", jcr->buf, jcr1->buf);
 383             }
 384             buf[1]--;
 385          }
 386          buf[1] = 'Z';
 387          buf[2]--;
 388       }
 389       buf[2] = 'Z';
 390       buf[0]--;
 391    }
 392
 393    printf("Print sorted list.\n");
 394    foreach_dlist (jcr, jcr_chain) {
 395       printf("Dlist item = %s\n", jcr->buf);
 396       free(jcr->buf);
 397    }
 398
 399    delete jcr_chain;
 400
 401
 402    sm_dump(false);
 403
 404 }
 405 #endif