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

   1 /*
   2  *  Written by Kern Sibbald MMIV
   3  *
   4  *   Version $Id$
   5  */
   6 /*
   7    Bacula® - The Network Backup Solution
   8
   9    Copyright (C) 2004-2006 Free Software Foundation Europe e.V.
  10
  11    The main author of Bacula is Kern Sibbald, with contributions from
  12    many others, a complete list can be found in the file AUTHORS.
  13    This program is Free Software; you can redistribute it and/or
  14    modify it under the terms of version two of the GNU General Public
  15    License as published by the Free Software Foundation plus additions
  16    that are listed in the file LICENSE.
  17
  18    This program is distributed in the hope that it will be useful, but
  19    WITHOUT ANY WARRANTY; without even the implied warranty of
  20    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  21    General Public License for more details.
  22
  23    You should have received a copy of the GNU General Public License
  24    along with this program; if not, write to the Free Software
  25    Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
  26    02110-1301, USA.
  27
  28    Bacula® is a registered trademark of John Walker.
  29    The licensor of Bacula is the Free Software Foundation Europe
  30    (FSFE), Fiduciary Program, Sumatrastrasse 25, 8006 Zürich,
  31    Switzerland, email:ftf@fsfeurope.org.
  32 */
  33
  34
  35 /* ========================================================================
  36  *
  37  *   Doubly linked list  -- dlist
  38  *
  39  *    Kern Sibbald, MMIV
  40  *
  41  */
  42
  43 #define M_ABORT 1
  44
  45 /* In case you want to specifically specify the offset to the link */
  46 #define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
  47 /*
  48  * There is a lot of extra casting here to work around the fact
  49  * that some compilers (Sun and Visual C++) do not accept
  50  * (void *) as an lvalue on the left side of an equal.
  51  *
  52  * Loop var through each member of list
  53  */
  54 #ifdef HAVE_TYPEOF
  55 #define foreach_dlist(var, list) \
  56         for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); )
  57 #else
  58 #define foreach_dlist(var, list) \
  59     for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
  60 #endif
  61
  62
  63
  64 struct dlink {
  65    void *next;
  66    void *prev;
  67 };
  68
  69 class dlist : public SMARTALLOC {
  70    void *head;
  71    void *tail;
  72    int16_t loffset;
  73    uint32_t num_items;
  74 public:
  75    dlist(void *item, dlink *link);
  76    dlist(void);
  77    ~dlist() { destroy(); }
  78    void init(void *item, dlink *link);
  79    void prepend(void *item);
  80    void append(void *item);
  81    void insert_before(void *item, void *where);
  82    void insert_after(void *item, void *where);
  83    void *binary_insert(void *item, int compare(void *item1, void *item2));
  84    void *binary_search(void *item, int compare(void *item1, void *item2));
  85    void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
  86    void remove(void *item);
  87    bool empty() const;
  88    int  size() const;
  89    void *next(const void *item) const;
  90    void *prev(const void *item) const;
  91    void destroy();
  92    void *first() const;
  93    void *last() const;
  94 };
  95
  96
  97 /*
  98  * This allows us to do explicit initialization,
  99  *   allowing us to mix C++ classes inside malloc'ed
 100  *   C structures. Define before called in constructor.
 101  */
 102 inline void dlist::init(void *item, dlink *link)
 103 {
 104    head = tail = NULL;
 105    loffset = (int)((char *)link - (char *)item);
 106    if (loffset < 0 || loffset > 5000) {
 107       Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
 108    }
 109    num_items = 0;
 110 }
 111
 112 /*
 113  * Constructor called with the address of a
 114  *   member of the list (not the list head), and
 115  *   the address of the link within that member.
 116  * If the link is at the beginning of the list member,
 117  *   then there is no need to specify the link address
 118  *   since the offset is zero.
 119  */
 120 inline dlist::dlist(void *item, dlink *link)
 121 {
 122    init(item, link);
 123 }
 124
 125 /* Constructor with link at head of item */
 126 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 127 {
 128 }
 129
 130 inline bool dlist::empty() const
 131 {
 132    return head == NULL;
 133 }
 134
 135 inline int dlist::size() const
 136 {
 137    return num_items;
 138 }
 139
 140
 141
 142 inline void * dlist::first() const
 143 {
 144    return head;
 145 }
 146
 147 inline void * dlist::last() const
 148 {
 149    return tail;
 150 }