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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2004-2008 Free Software Foundation Europe e.V.
   5
   6    The main author of Bacula is Kern Sibbald, with contributions from
   7    many others, a complete list can be found in the file AUTHORS.
   8    This program is Free Software; you can redistribute it and/or
   9    modify it under the terms of version two of the GNU General Public
  10    License as published by the Free Software Foundation and included
  11    in the file LICENSE.
  12
  13    This program is distributed in the hope that it will be useful, but
  14    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 License
  19    along with this program; if not, write to the Free Software
  20    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  21    02110-1301, USA.
  22
  23    Bacula® is a registered trademark of Kern Sibbald.
  24    The licensor of Bacula is the Free Software Foundation Europe
  25    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  26    Switzerland, email:ftf@fsfeurope.org.
  27 */
  28 /*
  29  *  Written by Kern Sibbald MMIV
  30  *
  31  *   Version $Id$
  32  */
  33
  34
  35 /* ========================================================================
  36  *
  37  *   Doubly linked list  -- dlist
  38  *
  39  *   See the end of the file for the dlistString class which
  40  *     facilitates storing strings in a dlist.
  41  *
  42  *    Kern Sibbald, MMIV and MMVII
  43  *
  44  */
  45
  46 #define M_ABORT 1
  47
  48 /* In case you want to specifically specify the offset to the link */
  49 #define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
  50 /*
  51  * There is a lot of extra casting here to work around the fact
  52  * that some compilers (Sun and Visual C++) do not accept
  53  * (void *) as an lvalue on the left side of an equal.
  54  *
  55  * Loop var through each member of list
  56  */
  57 #ifdef HAVE_TYPEOF
  58 #define foreach_dlist(var, list) \
  59         for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); )
  60 #else
  61 #define foreach_dlist(var, list) \
  62     for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
  63 #endif
  64
  65 struct dlink {
  66    void *next;
  67    void *prev;
  68 };
  69
  70 class dlist : public SMARTALLOC {
  71    void *head;
  72    void *tail;
  73    int16_t loffset;
  74    uint32_t num_items;
  75 public:
  76    dlist(void *item, dlink *link);
  77    dlist(void);
  78    ~dlist() { destroy(); }
  79    void init(void *item, dlink *link);
  80    void init();
  81    void prepend(void *item);
  82    void append(void *item);
  83    void set_prev(void *item, void *prev);
  84    void set_next(void *item, void *next);
  85    void *get_prev(void *item);
  86    void *get_next(void *item);
  87    dlink *get_link(void *item);
  88    void insert_before(void *item, void *where);
  89    void insert_after(void *item, void *where);
  90    void *binary_insert(void *item, int compare(void *item1, void *item2));
  91    void *binary_search(void *item, int compare(void *item1, void *item2));
  92    void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
  93    void remove(void *item);
  94    bool empty() const;
  95    int  size() const;
  96    void *next(void *item);
  97    void *prev(void *item);
  98    void destroy();
  99    void *first() const;
 100    void *last() const;
 101 };
 102
 103
 104 /*
 105  * This allows us to do explicit initialization,
 106  *   allowing us to mix C++ classes inside malloc'ed
 107  *   C structures. Define before called in constructor.
 108  */
 109 inline void dlist::init(void *item, dlink *link)
 110 {
 111    head = tail = NULL;
 112    loffset = (int)((char *)link - (char *)item);
 113    if (loffset < 0 || loffset > 5000) {
 114       Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
 115    }
 116    num_items = 0;
 117 }
 118
 119 inline void dlist::init()
 120 {
 121    head = tail = NULL;
 122    loffset = 0;
 123    num_items = 0;
 124 }
 125
 126
 127 /*
 128  * Constructor called with the address of a
 129  *   member of the list (not the list head), and
 130  *   the address of the link within that member.
 131  * If the link is at the beginning of the list member,
 132  *   then there is no need to specify the link address
 133  *   since the offset is zero.
 134  */
 135 inline dlist::dlist(void *item, dlink *link)
 136 {
 137    init(item, link);
 138 }
 139
 140 /* Constructor with link at head of item */
 141 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 142 {
 143 }
 144
 145 inline void dlist::set_prev(void *item, void *prev)
 146 {
 147    ((dlink *)(((char *)item)+loffset))->prev = prev;
 148 }
 149
 150 inline void dlist::set_next(void *item, void *next)
 151 {
 152    ((dlink *)(((char *)item)+loffset))->next = next;
 153 }
 154
 155 inline void *dlist::get_prev(void *item)
 156 {
 157    return ((dlink *)(((char *)item)+loffset))->prev;
 158 }
 159
 160 inline void *dlist::get_next(void *item)
 161 {
 162    return ((dlink *)(((char *)item)+loffset))->next;
 163 }
 164
 165
 166 inline dlink *dlist::get_link(void *item)
 167 {
 168    return (dlink *)(((char *)item)+loffset);
 169 }
 170
 171
 172
 173 inline bool dlist::empty() const
 174 {
 175    return head == NULL;
 176 }
 177
 178 inline int dlist::size() const
 179 {
 180    return num_items;
 181 }
 182
 183
 184
 185 inline void * dlist::first() const
 186 {
 187    return head;
 188 }
 189
 190 inline void * dlist::last() const
 191 {
 192    return tail;
 193 }
 194
 195 /*
 196  * C string helper routines for dlist
 197  *   The string (char *) is kept in the node
 198  *
 199  *   Kern Sibbald, February 2007
 200  *
 201  */
 202 class dlistString
 203 {
 204 public:
 205    char *c_str() { return m_str; };
 206
 207 private:
 208    dlink m_link;
 209    char m_str[1];
 210    /* !!! Don't put anything after this as this space is used
 211     *     to hold the string in inline
 212     */
 213 };
 214
 215 extern dlistString *new_dlistString(const char *str, int len);
 216 extern dlistString *new_dlistString(const char *str);