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