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-2003 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 }
  52
  53 /*
  54  * Append an item to the list
  55  */
  56 void dlist::prepend(void *item)
  57 {
  58    ((dlink *)((char *)item+loffset))->next = head;
  59    ((dlink *)((char *)item+loffset))->prev = NULL;
  60    if (head) {
  61       ((dlink *)((char *)head+loffset))->prev = item;
  62    }
  63    head = item;
  64    if (tail == NULL) {                /* if empty list, */
  65       tail = item;                    /* item is tail too */
  66    }
  67 }
  68
  69 void dlist::insert_before(void *item, void *where)
  70 {
  71    dlink *where_link = (dlink *)((char *)where+loffset);
  72
  73    ((dlink *)((char *)item+loffset))->next = where;
  74    ((dlink *)((char *)item+loffset))->prev = where_link->prev;
  75
  76    if (where_link->prev) {
  77       ((dlink *)((char *)(where_link->prev)+loffset))->next = item;
  78       where_link->prev = item;
  79    }
  80    if (head == where) {
  81       head = item;
  82    }
  83 }
  84
  85 void dlist::insert_after(void *item, void *where)
  86 {
  87    dlink *where_link = (dlink *)((char *)where+loffset);
  88
  89    ((dlink *)((char *)item+loffset))->next = where_link->next;
  90    ((dlink *)((char *)item+loffset))->prev = where;
  91
  92    if (where_link->next) {
  93       ((dlink *)((char *)(where_link->next)+loffset))->prev = item;
  94       where_link->next = item;
  95    }
  96    if (tail == where) {
  97       tail = item;
  98    }
  99 }
 100
 101
 102 void dlist::remove(void *item)
 103 {
 104    void *xitem;
 105    dlink *ilink = (dlink *)((char *)item+loffset);   /* item's link */
 106    if (item == head) {
 107       head = ilink->next;
 108       ((dlink *)((char *)head+loffset))->prev = NULL;
 109    } else if (item == tail) {
 110       tail = ilink->prev;
 111       ((dlink *)((char *)tail+loffset))->next = NULL;
 112    } else {
 113       xitem = ilink->next;
 114       ((dlink *)((char *)xitem+loffset))->prev = ilink->prev;
 115       xitem = ilink->prev;
 116       ((dlink *)((char *)xitem+loffset))->next = ilink->next;
 117    }
 118    free(item);
 119 }
 120
 121 void * dlist::next(void *item)
 122 {
 123    if (item == NULL) {
 124       return head;
 125    }
 126    return ((dlink *)((char *)item+loffset))->next;
 127 }
 128
 129 void * dlist::prev(void *item)
 130 {
 131    if (item == NULL) {
 132       return tail;
 133    }
 134    return ((dlink *)((char *)item+loffset))->prev;
 135 }
 136
 137
 138 /* Destroy the list and its contents */
 139 void dlist::destroy()
 140 {
 141    for (void *n=head; n; ) {
 142       void *ni = ((dlink *)((char *)n+loffset))->next;
 143       free(n);
 144       n = ni;
 145    }
 146 }
 147
 148
 149
 150 #ifdef TEST_PROGRAM
 151
 152 struct MYJCR {
 153    char *buf;
 154    dlist link;
 155 };
 156
 157 int main()
 158 {
 159    char buf[30];
 160    dlist *jcr_chain;
 161    MYJCR *jcr = NULL;
 162    MYJCR *save_jcr = NULL;
 163    MYJCR *next_jcr;
 164
 165    jcr_chain = (dlist *)malloc(sizeof(dlist));
 166    jcr_chain->init(jcr, &jcr->link);
 167
 168    printf("Prepend 20 items 0-19\n");
 169    for (int i=0; i<20; i++) {
 170       sprintf(buf, "This is dlist item %d", i);
 171       jcr = (MYJCR *)malloc(sizeof(MYJCR));
 172       jcr->buf = bstrdup(buf);
 173       jcr_chain->prepend(jcr);
 174       if (i == 10) {
 175          save_jcr = jcr;
 176       }
 177    }
 178
 179    next_jcr = (MYJCR *)jcr_chain->next(save_jcr);
 180    printf("11th item=%s\n", next_jcr->buf);
 181    jcr = (MYJCR *)malloc(sizeof(MYJCR));
 182    jcr->buf = save_jcr->buf;
 183    printf("Remove 10th item\n");
 184    jcr_chain->remove(save_jcr);
 185    printf("Re-insert 10th item\n");
 186    jcr_chain->insert_before(jcr, next_jcr);
 187
 188    printf("Print remaining list.\n");
 189    for (MYJCR *jcr=NULL; (jcr=(MYJCR *)jcr_chain->next(jcr)); ) {
 190       printf("Dlist item = %s\n", jcr->buf);
 191       free(jcr->buf);
 192    }
 193    jcr_chain->destroy();
 194    free(jcr_chain);
 195
 196    sm_dump(False);
 197
 198 }
 199 #endif