git.sur5r.net Git - bacula/bacula/blob - bacula/src/lib/dlist.h

   1 /*
   2  *   Version $Id$
   3  */
   4
   5 /*
   6    Copyright (C) 2000-2003 Kern Sibbald and John Walker
   7
   8    This program is free software; you can redistribute it and/or
   9    modify it under the terms of the GNU General Public License as
  10    published by the Free Software Foundation; either version 2 of
  11    the License, or (at your option) any later version.
  12
  13    This program is distributed in the hope that it will be useful,
  14    but WITHOUT ANY WARRANTY; without even the implied warranty of
  15    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  16    General Public License for more details.
  17
  18    You should have received a copy of the GNU General Public
  19    License along with this program; if not, write to the Free
  20    Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  21    MA 02111-1307, USA.
  22
  23  */
  24
  25 /* ========================================================================
  26  *
  27  *   Doubly linked list  -- dlist
  28  *
  29  */
  30
  31 /* In case you want to specifically specify the offset to the link */
  32 #define OFFSET(item, link) ((char *)(link) - (char *)(item))
  33 /*
  34  * There is a lot of extra casting here to work around the fact
  35  * that some compilers (Sun and Visual C++) do not accept
  36  * (void *) as an lvalue on the left side of an equal.
  37  *
  38  * Loop var through each member of list
  39  */
  40 #define foreach_dlist(var, list) \
  41     for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
  42
  43 #ifdef the_old_way
  44 #define foreach_dlist(var, list) \
  45         for((var)=NULL; (((void *)(var))=(list)->next(var)); )
  46 #endif
  47
  48 struct dlink {
  49    void *next;
  50    void *prev;
  51 };
  52
  53
  54 class dlist {
  55    void *head;
  56    void *tail;
  57    uint16_t loffset;
  58    uint32_t num_items;
  59 public:
  60    dlist(void *item, void *link);
  61    dlist(void);
  62    ~dlist() { destroy(); }
  63    void init(void *item, void *link);
  64    void prepend(void *item);
  65    void append(void *item);
  66    void insert_before(void *item, void *where);
  67    void insert_after(void *item, void *where);
  68    void *unique_binary_insert(void *item, int compare(void *item1, void *item2));
  69    void binary_insert(void *item, int compare(void *item1, void *item2));
  70    void remove(void *item);
  71    bool empty();
  72    int  size();
  73    void *next(void *item);
  74    void *prev(void *item);
  75    void destroy();
  76    void *first();
  77    void *last();
  78    void * operator new(size_t);
  79    void operator delete(void *);
  80 };
  81
  82 /*
  83  * This allows us to do explicit initialization,
  84  *   allowing us to mix C++ classes inside malloc'ed
  85  *   C structures. Define before called in constructor.
  86  */
  87 inline void dlist::init(void *item, void *link)
  88 {
  89    head = tail = NULL;
  90    loffset = (char *)link - (char *)item;
  91    num_items = 0;
  92 }
  93
  94 /* Constructor */
  95 inline dlist::dlist(void *item, void *link)
  96 {
  97    this->init(item, link);
  98 }
  99
 100 inline dlist::dlist(void)
 101 {
 102    memset(this, 0, sizeof(dlist));
 103 }
 104
 105 inline bool dlist::empty()
 106 {
 107    return head == NULL;
 108 }
 109
 110 inline int dlist::size()
 111 {
 112    return num_items;
 113 }
 114
 115
 116 inline void * dlist::operator new(size_t)
 117 {
 118    return malloc(sizeof(dlist));
 119 }
 120
 121 inline void dlist::operator delete(void  *item)
 122 {
 123    ((dlist *)item)->destroy();
 124    free(item);
 125 }
 126
 127
 128 inline void * dlist::first()
 129 {
 130    return head;
 131 }
 132
 133 inline void * dlist::last()
 134 {
 135    return tail;
 136 }