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

   1 /*
   2    Bacula(R) - The Network Backup Solution
   3
   4    Copyright (C) 2000-2017 Kern Sibbald
   5
   6    The original author of Bacula is Kern Sibbald, with contributions
   7    from many others, a complete list can be found in the file AUTHORS.
   8
   9    You may use this file and others of this release according to the
  10    license defined in the LICENSE file, which includes the Affero General
  11    Public License, v3.0 ("AGPLv3") and some additional permissions and
  12    terms pursuant to its AGPLv3 Section 7.
  13
  14    This notice must be preserved when any source code is
  15    conveyed and/or propagated.
  16
  17    Bacula(R) is a registered trademark of Kern Sibbald.
  18 */
  19 /*
  20  *  Bacula array list routines
  21  *
  22  *    alist is a simple malloc'ed array of pointers.  For the moment,
  23  *      it simply malloc's a bigger array controlled by num_grow.
  24  *      Default is to realloc the pointer array for each new member.
  25  *
  26  *    Note: the list can have holes (empty items). This is done by
  27  *      using get() and put().  If you are using this kind of indexed
  28  *      list, you cannot use: prepend() and remove() as they will
  29  *      reorder the list. So, in the ilist array, these functions are
  30  *      disabled and the put method is defined.
  31  *
  32  *   Kern Sibbald, June MMIII
  33  *
  34  */
  35
  36 #include "bacula.h"
  37
  38 /*
  39  * Private grow list function. Used to insure that
  40  *   at least one more "slot" is available.
  41  */
  42 void baselist::grow_list()
  43 {
  44    int i;
  45    int new_max_items;
  46
  47    /* put() can insert and item anywhere in the list so
  48    it's important to allocate at least last_item+1 items */
  49    int min_grow = MAX(10, last_item+1);
  50    if (num_grow < min_grow) {
  51       num_grow = min_grow;               /* default if not initialized */
  52    }
  53
  54    if (items == NULL) {
  55       items = (void **)malloc(num_grow * sizeof(void *));
  56       for (i=0; i<num_grow; i++) {
  57          items[i] = NULL;
  58       }
  59       max_items = num_grow;
  60    } else if (last_item >= max_items) {
  61       new_max_items = last_item + num_grow;
  62       items = (void **)realloc(items, new_max_items * sizeof(void *));
  63       for (i=max_items; i<new_max_items; i++) {
  64          items[i] = NULL;
  65       }
  66       max_items = new_max_items;
  67    }
  68 }
  69
  70 void *alist::first()
  71 {
  72    cur_item = 1;
  73    if (num_items == 0) {
  74       return NULL;
  75    } else {
  76       return items[0];
  77    }
  78 }
  79
  80 void *alist::last()
  81 {
  82    if (num_items == 0) {
  83       return NULL;
  84    } else {
  85       cur_item = last_item;
  86       return items[last_item-1];
  87    }
  88 }
  89
  90 void *alist::next()
  91 {
  92    if (cur_item >= last_item) {
  93       return NULL;
  94    } else {
  95       return items[cur_item++];
  96    }
  97 }
  98
  99 void *alist::prev()
 100 {
 101    if (cur_item <= 1) {
 102       return NULL;
 103    } else {
 104       return items[--cur_item];
 105    }
 106 }
 107
 108 /*
 109  * prepend an item to the list -- i.e. add to beginning
 110  */
 111 void alist::prepend(void *item)
 112 {
 113    grow_list();
 114    if (num_items == 0) {
 115       items[num_items++] = item;
 116       if (num_items > last_item) {
 117          last_item = num_items;
 118       }
 119       return;
 120    }
 121    for (int i=last_item; i > 0; i--) {
 122       items[i] = items[i-1];
 123    }
 124    items[0] = item;
 125    num_items++;
 126    last_item++;
 127 }
 128
 129
 130 /*
 131  * Append an item to the list
 132  */
 133 void baselist::append(void *item)
 134 {
 135    grow_list();
 136    items[last_item++] = item;
 137    num_items++;
 138 }
 139
 140 /*
 141  * Put an item at a particular index
 142  */
 143 void ilist::put(int index, void *item)
 144 {
 145    if (index > last_item) {
 146       last_item = index;
 147    }
 148    grow_list();
 149    if (items[index] == NULL) {
 150       num_items++;
 151    }
 152    items[index] = item;
 153 }
 154
 155
 156 /*
 157  * Remove an item from the list
 158  * Note: you must free the item when
 159  *   you are done with it.
 160  */
 161 void * baselist::remove_item(int index)
 162 {
 163    void *item;
 164    if (index < 0 || index >= last_item) {
 165       return NULL;
 166    }
 167    item = items[index];
 168
 169    /* last_item is from 1..n, we work from 0..n-1 */
 170    for (int i=index; i < (last_item-1); i++) {
 171       items[i] = items[i+1];
 172    }
 173
 174    items[last_item-1] = NULL;   /* The last item is shifted by one, the last slot is always free */
 175
 176    last_item--;                 /* We have shifted all items by 1 */
 177    num_items--;                 /* We have 1 item less */
 178
 179    return item;
 180 }
 181
 182
 183 /* Get the index item -- we should probably allow real indexing here */
 184 void * baselist::get(int index)
 185 {
 186    if (items == NULL || index < 0 || index > last_item) {
 187       return NULL;
 188    }
 189    return items[index];
 190 }
 191
 192 /* Destroy the list and its contents */
 193 void baselist::destroy()
 194 {
 195    if (items) {
 196       if (own_items) {
 197          for (int i=0; i<max_items; i++) {
 198             if (items[i]) {
 199                free(items[i]);
 200                items[i] = NULL;
 201             }
 202          }
 203       }
 204       free(items);
 205       items = NULL;
 206    }
 207    num_items = 0;
 208    last_item = 0;
 209    max_items = 0;
 210    num_grow = 0;
 211 }
 212
 213 #ifdef TEST_PROGRAM
 214
 215
 216 struct FILESET {
 217    alist mylist;
 218 };
 219
 220 int main()
 221 {
 222    FILESET *fileset;
 223    char buf[30];
 224    alist *mlist;
 225    char *bp;
 226
 227    fileset = (FILESET *)malloc(sizeof(FILESET));
 228    bmemzero(fileset, sizeof(FILESET));
 229    fileset->mylist.init();
 230
 231    printf("Manual allocation/destruction of list:\n");
 232
 233    for (int i=0; i<20; i++) {
 234       sprintf(buf, "This is item %d", i);
 235       fileset->mylist.append(bstrdup(buf));
 236    }
 237    for (int i=0; i< fileset->mylist.size(); i++) {
 238       printf("Item %d = %s\n", i, (char *)fileset->mylist[i]);
 239    }
 240    fileset->mylist.destroy();
 241    free(fileset);
 242
 243    printf("Allocation/destruction using new delete\n");
 244    mlist = New(alist(50));
 245
 246    for (int i=0; i<20; i++) {
 247       sprintf(buf, "This is item %d", i);
 248       mlist->append(bstrdup(buf));
 249    }
 250    for (int i=0; i< mlist->size(); i++) {
 251       printf("Item %d = %s\n", i, (char *)mlist->get(i));
 252    }
 253    printf("\nIndexed test. Insert 210 items.\n");
 254    /* Test indexed list */
 255    mlist->destroy();
 256    delete mlist;
 257
 258    {
 259       printf("Test remove()\n");
 260       char *elt;
 261       int i=0;
 262       alist *alst = New(alist(10, owned_by_alist));
 263       alst->append(bstrdup("trash"));
 264       alst->append(bstrdup("0"));
 265       alst->append(bstrdup("1"));
 266       alst->append(bstrdup("2"));
 267       alst->append(bstrdup("3"));
 268       free(alst->remove(0));
 269       foreach_alist(elt, alst) {
 270          int nb = atoi(elt);
 271          ASSERT(nb == i);
 272          printf("%d %s\n", i++, elt);
 273       }
 274       delete alst;
 275    }
 276
 277    {
 278       char *elt;
 279       int i=0;
 280       alist *alst = New(alist(10, owned_by_alist));
 281       alst->append(bstrdup("0"));
 282       alst->append(bstrdup("1"));
 283       alst->append(bstrdup("2"));
 284       alst->append(bstrdup("trash"));
 285       alst->append(bstrdup("3"));
 286       free(alst->remove(3));
 287       foreach_alist(elt, alst) {
 288          int nb = atoi(elt);
 289          ASSERT(nb == i);
 290          printf("%d %s\n", i++, elt);
 291       }
 292       delete alst;
 293    }
 294
 295    {
 296       char *elt;
 297       int i=0;
 298       alist *alst = New(alist(10, owned_by_alist));
 299       alst->append(bstrdup("0"));
 300       alst->append(bstrdup("1"));
 301       alst->append(bstrdup("2"));
 302       alst->append(bstrdup("3"));
 303       alst->append(bstrdup("trash"));
 304       free(alst->remove(4));
 305       foreach_alist(elt, alst) {
 306          int nb = atoi(elt);
 307          ASSERT(nb == i);
 308          printf("%d %s\n", i++, elt);
 309       }
 310       delete alst;
 311    }
 312
 313    {
 314       char *elt;
 315       int i=0;
 316       alist *alst = New(alist(10, owned_by_alist));
 317       alst->append(bstrdup("0"));
 318       alst->append(bstrdup("1"));
 319       alst->append(bstrdup("2"));
 320       alst->append(bstrdup("3"));
 321       alst->append(bstrdup("4"));
 322       ASSERT(alst->remove(5) == NULL);
 323       foreach_alist(elt, alst) {
 324          int nb = atoi(elt);
 325          ASSERT(nb == i);
 326          printf("%d %s\n", i++, elt);
 327       }
 328       delete alst;
 329    }
 330
 331    {
 332       printf("Test pop()\n");
 333       char *elt;
 334       int i=0;
 335       alist *alst = New(alist(10, owned_by_alist));
 336       alst->append(bstrdup("0"));
 337       alst->append(bstrdup("1"));
 338       alst->append(bstrdup("2"));
 339       alst->append(bstrdup("3"));
 340       alst->append(bstrdup("trash"));
 341       ASSERT(alst->last_index() == 5);
 342       free(alst->pop());
 343       ASSERT(alst->last_index() == 4);
 344       foreach_alist(elt, alst) {
 345          int nb = atoi(elt);
 346          ASSERT(nb == i);
 347          printf("%d %s\n", i++, elt);
 348       }
 349       delete alst;
 350    }
 351    {
 352       ilist *ilst = New(ilist(10, owned_by_alist));
 353       sprintf(buf, "This is item 10");
 354       ilst->put(10, bstrdup(buf));
 355       printf("ilst size is %d. last_item=%d.  max_items=%d\n",
 356          ilst->size(), ilst->last_index(), ilst->max_size());
 357       ASSERT(ilst->size() == 1);
 358       delete ilst;
 359    }
 360
 361    {
 362       ilist *ilst = New(ilist(10, not_owned_by_alist));
 363       ilst->put(15, (char *)"something");
 364       printf("ilst size is %d. last_item=%d.  max_items=%d\n",
 365          ilst->size(), ilst->last_index(), ilst->max_size());
 366       ASSERT(ilst->size() == 1);
 367       ASSERT(ilst->last_index() == 15);
 368       delete ilst;
 369    }
 370
 371    ilist *ilst = New(ilist(50));
 372    for (int i=0; i<115; i++) {
 373       sprintf(buf, "This is item %d", i);
 374       ilst->put(i, bstrdup(buf));
 375       printf("%s\n", buf);
 376    }
 377    printf("ilst size is %d. last_item=%d.  max_items=%d\n",
 378        ilst->size(), ilst->last_index(), ilst->max_size());
 379    for (int i=0; i< ilst->size(); i++) {
 380       printf("Item %d = %s\n", i, (char *)ilst->get(i));
 381    }
 382
 383    delete ilst;
 384
 385    printf("Test alist push().\n");
 386    mlist = New(alist(10));
 387
 388    printf("mlist size is %d. last_item=%d.  max_items=%d\n",
 389        mlist->size(), mlist->last_index(), mlist->max_size());
 390    for (int i=0; i<20; i++) {
 391       sprintf(buf, "This is item %d", i);
 392       mlist->push(bstrdup(buf));
 393       printf("mlist size is %d. last_item=%d.  max_items=%d\n",
 394           mlist->size(), mlist->last_index(), mlist->max_size());
 395    }
 396    printf("Test alist pop()\n");
 397    for (int i=0; (bp=(char *)mlist->pop()); i++) {
 398       printf("Item %d = %s\n", i, bp);
 399       free(bp);
 400    }
 401    printf("mlist size is %d. last_item=%d.  max_items=%d\n",
 402        mlist->size(), mlist->last_index(), mlist->max_size());
 403
 404    for (int i=0; i<mlist->max_size(); i++) {
 405       bp = (char *) mlist->get(i);
 406       if (bp != NULL) {
 407          printf("Big problem. Item %d item=%p, but should be NULL\n", i, bp);
 408       }
 409    }
 410    printf("Done push() pop() tests\n");
 411
 412    delete mlist;
 413
 414    ilst = New(ilist(10, not_owned_by_alist));
 415    ilst->put(1, ilst);
 416    ilst->append((void*)1);
 417    //ilist->first();
 418    //ilist->remove(1);
 419    delete ilst;
 420    {
 421       ilist a(4, not_owned_by_alist);
 422       a.append((void*)"test1");
 423
 424       ilist b(4, not_owned_by_alist);
 425       bmemzero(&b, sizeof b);
 426       b.append((void*)"test1");
 427    }
 428    sm_dump(false);       /* test program */
 429 }
 430 #endif