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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2004-2007 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 plus additions
  11    that are listed 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 John Walker.
  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 prepend(void *item);
  81    void append(void *item);
  82    void set_prev(void *item, void *prev);
  83    void set_next(void *item, void *next);
  84    void insert_before(void *item, void *where);
  85    void insert_after(void *item, void *where);
  86    void *binary_insert(void *item, int compare(void *item1, void *item2));
  87    void *binary_search(void *item, int compare(void *item1, void *item2));
  88    void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
  89    void remove(void *item);
  90    bool empty() const;
  91    int  size() const;
  92    void *next(const void *item) const;
  93    void *prev(const void *item) const;
  94    void destroy();
  95    void *first() const;
  96    void *last() const;
  97 };
  98
  99
 100 /*
 101  * This allows us to do explicit initialization,
 102  *   allowing us to mix C++ classes inside malloc'ed
 103  *   C structures. Define before called in constructor.
 104  */
 105 inline void dlist::init(void *item, dlink *link)
 106 {
 107    head = tail = NULL;
 108    loffset = (int)((char *)link - (char *)item);
 109    if (loffset < 0 || loffset > 5000) {
 110       Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
 111    }
 112    num_items = 0;
 113 }
 114
 115 /*
 116  * Constructor called with the address of a
 117  *   member of the list (not the list head), and
 118  *   the address of the link within that member.
 119  * If the link is at the beginning of the list member,
 120  *   then there is no need to specify the link address
 121  *   since the offset is zero.
 122  */
 123 inline dlist::dlist(void *item, dlink *link)
 124 {
 125    init(item, link);
 126 }
 127
 128 /* Constructor with link at head of item */
 129 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 130 {
 131 }
 132
 133 inline void dlist::set_prev(void *item, void *prev)
 134 {
 135    ((dlink *)(((char *)item)+loffset))->prev = prev;
 136 }
 137
 138 inline void dlist::set_next(void *item, void *next)
 139 {
 140    ((dlink *)(((char *)item)+loffset))->next = next;
 141 }
 142
 143
 144
 145 inline bool dlist::empty() const
 146 {
 147    return head == NULL;
 148 }
 149
 150 inline int dlist::size() const
 151 {
 152    return num_items;
 153 }
 154
 155
 156
 157 inline void * dlist::first() const
 158 {
 159    return head;
 160 }
 161
 162 inline void * dlist::last() const
 163 {
 164    return tail;
 165 }
 166
 167 /*
 168  * C string helper routines for dlist
 169  *   The string (char *) is kept in the node
 170  *
 171  *   Kern Sibbald, February 2007
 172  *
 173  */
 174 class dlistString : public dlink
 175 {
 176 public:
 177    char *c_str() { return m_str; };
 178
 179 private:
 180    char m_str[1];
 181    /* !!! Don't put anything after this as this space is used
 182     *     to hold the string in inline
 183     */
 184 };
 185
 186 extern dlistString *new_dlistString(const char *str, int len);
 187 extern dlistString *new_dlistString(const char *str);