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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2004-2014 Free Software Foundation Europe e.V.
   5
   6    The main author of Bacula is Kern Sibbald, with contributions from many
   7    others, a complete list can be found in the file AUTHORS.
   8
   9    You may use this file and others of this release according to the
  10    license defined in the LICENSE file, which includes the Affero General
  11    Public License, v3.0 ("AGPLv3") and some additional permissions and
  12    terms pursuant to its AGPLv3 Section 7.
  13
  14    Bacula® is a registered trademark of Kern Sibbald.
  15 */
  16 /*
  17  *  Written by Kern Sibbald MMIV
  18  *
  19  */
  20
  21
  22 /* ========================================================================
  23  *
  24  *   Doubly linked list  -- dlist
  25  *
  26  *   See the end of the file for the dlistString class which
  27  *     facilitates storing strings in a dlist.
  28  *
  29  *    Kern Sibbald, MMIV and MMVII
  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) (int)((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 #ifdef HAVE_TYPEOF
  45 #define foreach_dlist(var, list) \
  46         for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); )
  47 #else
  48 #define foreach_dlist(var, list) \
  49     for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
  50 #endif
  51
  52 struct dlink {
  53    void *next;
  54    void *prev;
  55 };
  56
  57 class dlist : public SMARTALLOC {
  58    void *head;
  59    void *tail;
  60    int16_t loffset;
  61    uint32_t num_items;
  62 public:
  63    dlist(void *item, dlink *link);
  64    dlist(void);
  65    ~dlist() { destroy(); }
  66    void init(void *item, dlink *link);
  67    void init();
  68    void prepend(void *item);
  69    void append(void *item);
  70    void set_prev(void *item, void *prev);
  71    void set_next(void *item, void *next);
  72    void *get_prev(void *item);
  73    void *get_next(void *item);
  74    dlink *get_link(void *item);
  75    void insert_before(void *item, void *where);
  76    void insert_after(void *item, void *where);
  77    void *binary_insert(void *item, int compare(void *item1, void *item2));
  78    void *binary_search(void *item, int compare(void *item1, void *item2));
  79    void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
  80    void remove(void *item);
  81    bool empty() const;
  82    int  size() const;
  83    void *next(void *item);
  84    void *prev(void *item);
  85    void destroy();
  86    void *first() const;
  87    void *last() const;
  88 };
  89
  90
  91 /*
  92  * This allows us to do explicit initialization,
  93  *   allowing us to mix C++ classes inside malloc'ed
  94  *   C structures. Define before called in constructor.
  95  */
  96 inline void dlist::init(void *item, dlink *link)
  97 {
  98    head = tail = NULL;
  99    loffset = (int)((char *)link - (char *)item);
 100    if (loffset < 0 || loffset > 5000) {
 101       Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
 102    }
 103    num_items = 0;
 104 }
 105
 106 inline void dlist::init()
 107 {
 108    head = tail = NULL;
 109    loffset = 0;
 110    num_items = 0;
 111 }
 112
 113
 114 /*
 115  * Constructor called with the address of a
 116  *   member of the list (not the list head), and
 117  *   the address of the link within that member.
 118  * If the link is at the beginning of the list member,
 119  *   then there is no need to specify the link address
 120  *   since the offset is zero.
 121  */
 122 inline dlist::dlist(void *item, dlink *link)
 123 {
 124    init(item, link);
 125 }
 126
 127 /* Constructor with link at head of item */
 128 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 129 {
 130 }
 131
 132 inline void dlist::set_prev(void *item, void *prev)
 133 {
 134    ((dlink *)(((char *)item)+loffset))->prev = prev;
 135 }
 136
 137 inline void dlist::set_next(void *item, void *next)
 138 {
 139    ((dlink *)(((char *)item)+loffset))->next = next;
 140 }
 141
 142 inline void *dlist::get_prev(void *item)
 143 {
 144    return ((dlink *)(((char *)item)+loffset))->prev;
 145 }
 146
 147 inline void *dlist::get_next(void *item)
 148 {
 149    return ((dlink *)(((char *)item)+loffset))->next;
 150 }
 151
 152
 153 inline dlink *dlist::get_link(void *item)
 154 {
 155    return (dlink *)(((char *)item)+loffset);
 156 }
 157
 158
 159
 160 inline bool dlist::empty() const
 161 {
 162    return head == NULL;
 163 }
 164
 165 inline int dlist::size() const
 166 {
 167    return num_items;
 168 }
 169
 170
 171
 172 inline void * dlist::first() const
 173 {
 174    return head;
 175 }
 176
 177 inline void * dlist::last() const
 178 {
 179    return tail;
 180 }
 181
 182 /*
 183  * C string helper routines for dlist
 184  *   The string (char *) is kept in the node
 185  *
 186  *   Kern Sibbald, February 2007
 187  *
 188  */
 189 class dlistString
 190 {
 191 public:
 192    char *c_str() { return m_str; };
 193
 194 private:
 195    dlink m_link;
 196    char m_str[1];
 197    /* !!! Don't put anything after this as this space is used
 198     *     to hold the string in inline
 199     */
 200 };
 201
 202 extern dlistString *new_dlistString(const char *str, int len);
 203 extern dlistString *new_dlistString(const char *str);