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

   1 /*
   2  *   Version $Id$
   3  */
   4
   5 /*
   6    Copyright (C) 2004 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  *    Kern Sibbald, MMIV
  30  *
  31  */
  32
  33 #define M_ABORT 1
  34
  35 /* In case you want to specifically specify the offset to the link */
  36 #define OFFSET(item, link) ((char *)(link) - (char *)(item))
  37 /*
  38  * There is a lot of extra casting here to work around the fact
  39  * that some compilers (Sun and Visual C++) do not accept
  40  * (void *) as an lvalue on the left side of an equal.
  41  *
  42  * Loop var through each member of list
  43  */
  44 #define foreach_dlist(var, list) \
  45     for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
  46
  47 #ifdef the_old_way
  48 #define foreach_dlist(var, list) \
  49         for((var)=NULL; (((void *)(var))=(list)->next(var)); )
  50 #endif
  51
  52
  53 struct dlink {
  54    void *next;
  55    void *prev;
  56 };
  57
  58 class dlist : public SMARTALLOC {
  59    void *head;
  60    void *tail;
  61    int16_t loffset;
  62    uint32_t num_items;
  63 public:
  64    dlist(void *item, dlink *link);
  65    dlist(void);
  66    ~dlist() { destroy(); }
  67    void init(void *item, dlink *link);
  68    void prepend(void *item);
  69    void append(void *item);
  70    void insert_before(void *item, void *where);
  71    void insert_after(void *item, void *where);
  72    void *unique_binary_insert(void *item, int compare(void *item1, void *item2));
  73    void binary_insert(void *item, int compare(void *item1, void *item2));
  74    void remove(void *item);
  75    bool empty() const;
  76    int  size() const;
  77    void *next(const void *item) const;
  78    void *prev(const void *item) const;
  79    void destroy();
  80    void *first() const;
  81    void *last() const;
  82 };
  83
  84
  85 /*
  86  * This allows us to do explicit initialization,
  87  *   allowing us to mix C++ classes inside malloc'ed
  88  *   C structures. Define before called in constructor.
  89  */
  90 inline void dlist::init(void *item, dlink *link)
  91 {
  92    head = tail = NULL;
  93    loffset = (char *)link - (char *)item;
  94    if (loffset < 0 || loffset > 5000) {
  95       Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
  96    }
  97    num_items = 0;
  98 }
  99
 100 /*
 101  * Constructor called with the address of a
 102  *   member of the list (not the list head), and
 103  *   the address of the link within that member.
 104  * If the link is at the beginning of the list member,
 105  *   then there is no need to specify the link address
 106  *   since the offset is zero.
 107  */
 108 inline dlist::dlist(void *item, dlink *link)
 109 {
 110    init(item, link);
 111 }
 112
 113 /* Constructor with link at head of item */
 114 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 115 {
 116 }
 117
 118 inline bool dlist::empty() const
 119 {
 120    return head == NULL;
 121 }
 122
 123 inline int dlist::size() const
 124 {
 125    return num_items;
 126 }
 127
 128
 129
 130 inline void * dlist::first() const
 131 {
 132    return head;
 133 }
 134
 135 inline void * dlist::last() const
 136 {
 137    return tail;
 138 }