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

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