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