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 void dlist::remove(void *item)
 107 {
 108    void *xitem;
 109    dlink *ilink = (dlink *)(((char *)item)+loffset);   /* item's link */
 110    if (item == head) {
 111       head = ilink->next;
 112       if (head) {
 113          ((dlink *)(((char *)head)+loffset))->prev = NULL;
 114       }
 115       if (item == tail) {
 116          tail = ilink->prev;
 117       }
 118    } else if (item == tail) {
 119       tail = ilink->prev;
 120       if (tail) {
 121          ((dlink *)(((char *)tail)+loffset))->next = NULL;
 122       }
 123    } else {
 124       xitem = ilink->next;
 125       ((dlink *)(((char *)xitem)+loffset))->prev = ilink->prev;
 126       xitem = ilink->prev;
 127       ((dlink *)(((char *)xitem)+loffset))->next = ilink->next;
 128    }
 129    num_items--;
 130    if (num_items == 0) {
 131       head = tail = NULL;
 132    }
 133 }
 134
 135 void * dlist::next(void *item)
 136 {
 137    if (item == NULL) {
 138       return head;
 139    }
 140    return ((dlink *)(((char *)item)+loffset))->next;
 141 }
 142
 143 void * dlist::prev(void *item)
 144 {
 145    if (item == NULL) {
 146       return tail;
 147    }
 148    return ((dlink *)(((char *)item)+loffset))->prev;
 149 }
 150
 151
 152 /* Destroy the list contents */
 153 void dlist::destroy()
 154 {
 155    for (void *n=head; n; ) {
 156       void *ni = ((dlink *)(((char *)n)+loffset))->next;
 157       free(n);
 158       n = ni;
 159    }
 160    num_items = 0;
 161    head = tail = NULL;
 162 }
 163
 164
 165
 166 #ifdef TEST_PROGRAM
 167
 168 struct MYJCR {
 169    char *buf;
 170    dlink link;
 171 };
 172
 173 int main()
 174 {
 175    char buf[30];
 176    dlist *jcr_chain;
 177    MYJCR *jcr = NULL;
 178    MYJCR *save_jcr = NULL;
 179    MYJCR *next_jcr;
 180
 181    jcr_chain = (dlist *)malloc(sizeof(dlist));
 182    jcr_chain->init(jcr, &jcr->link);
 183
 184    printf("Prepend 20 items 0-19\n");
 185    for (int i=0; i<20; i++) {
 186       sprintf(buf, "This is dlist item %d", i);
 187       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 188       jcr->buf = bstrdup(buf);
 189       jcr_chain->prepend(jcr);
 190       if (i == 10) {
 191          save_jcr = jcr;
 192       }
 193    }
 194
 195    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 196    printf("11th item=%s\n", next_jcr->buf);
 197    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 198    jcr->buf = save_jcr->buf;
 199    printf("Remove 10th item\n");
 200    jcr_chain->remove(save_jcr);
 201    printf("Re-insert 10th item\n");
 202    jcr_chain->insert_before(jcr, next_jcr);
 203
 204    printf("Print remaining list.\n");
 205    foreach_dlist (jcr, jcr_chain) {
 206       printf("Dlist item = %s\n", jcr->buf);
 207       free(jcr->buf);
 208    }
 209    jcr_chain->destroy();
 210    free(jcr_chain);
 211
 212    jcr_chain = new dlist(jcr, &jcr->link);
 213    printf("append 20 items 0-19\n");
 214    for (int i=0; i<20; i++) {
 215       sprintf(buf, "This is dlist item %d", i);
 216       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 217       jcr->buf = bstrdup(buf);
 218       jcr_chain->append(jcr);
 219       if (i == 10) {
 220          save_jcr = jcr;
 221       }
 222    }
 223
 224    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 225    printf("11th item=%s\n", next_jcr->buf);
 226    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 227    jcr->buf = save_jcr->buf;
 228    printf("Remove 10th item\n");
 229    jcr_chain->remove(save_jcr);
 230    printf("Re-insert 10th item\n");
 231    jcr_chain->insert_before(jcr, next_jcr);
 232
 233    printf("Print remaining list.\n");
 234    foreach_dlist (jcr, jcr_chain) {
 235       printf("Dlist item = %s\n", jcr->buf);
 236       free(jcr->buf);
 237    }
 238
 239    delete jcr_chain;
 240
 241    sm_dump(false);
 242
 243 }
 244 #endif