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

   1 /*
   2  *   Version $Id$
   3  */
   4 /*
   5    Copyright (C) 2004-2006 Kern Sibbald
   6
   7    This program is free software; you can redistribute it and/or
   8    modify it under the terms of the GNU General Public License
   9    version 2 as amended with additional clauses defined in the
  10    file LICENSE in the main source directory.
  11
  12    This program is distributed in the hope that it will be useful,
  13    but WITHOUT ANY WARRANTY; without even the implied warranty of
  14    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  15    the file LICENSE for additional details.
  16
  17  */
  18
  19
  20 /* ========================================================================
  21  *
  22  *   Doubly linked list  -- dlist
  23  *
  24  *    Kern Sibbald, MMIV
  25  *
  26  */
  27
  28 #define M_ABORT 1
  29
  30 /* In case you want to specifically specify the offset to the link */
  31 #define OFFSET(item, link) (int)((char *)(link) - (char *)(item))
  32 /*
  33  * There is a lot of extra casting here to work around the fact
  34  * that some compilers (Sun and Visual C++) do not accept
  35  * (void *) as an lvalue on the left side of an equal.
  36  *
  37  * Loop var through each member of list
  38  */
  39 #ifdef HAVE_TYPEOF
  40 #define foreach_dlist(var, list) \
  41         for((var)=NULL; ((var)=(typeof(var))(list)->next(var)); )
  42 #else
  43 #define foreach_dlist(var, list) \
  44     for((var)=NULL; (*((void **)&(var))=(void*)((list)->next(var))); )
  45 #endif
  46
  47
  48
  49 struct dlink {
  50    void *next;
  51    void *prev;
  52 };
  53
  54 class dlist : public SMARTALLOC {
  55    void *head;
  56    void *tail;
  57    int16_t loffset;
  58    uint32_t num_items;
  59 public:
  60    dlist(void *item, dlink *link);
  61    dlist(void);
  62    ~dlist() { destroy(); }
  63    void init(void *item, dlink *link);
  64    void prepend(void *item);
  65    void append(void *item);
  66    void insert_before(void *item, void *where);
  67    void insert_after(void *item, void *where);
  68    void *binary_insert(void *item, int compare(void *item1, void *item2));
  69    void *binary_search(void *item, int compare(void *item1, void *item2));
  70    void binary_insert_multiple(void *item, int compare(void *item1, void *item2));
  71    void remove(void *item);
  72    bool empty() const;
  73    int  size() const;
  74    void *next(const void *item) const;
  75    void *prev(const void *item) const;
  76    void destroy();
  77    void *first() const;
  78    void *last() const;
  79 };
  80
  81
  82 /*
  83  * This allows us to do explicit initialization,
  84  *   allowing us to mix C++ classes inside malloc'ed
  85  *   C structures. Define before called in constructor.
  86  */
  87 inline void dlist::init(void *item, dlink *link)
  88 {
  89    head = tail = NULL;
  90    loffset = (int)((char *)link - (char *)item);
  91    if (loffset < 0 || loffset > 5000) {
  92       Emsg0(M_ABORT, 0, "Improper dlist initialization.\n");
  93    }
  94    num_items = 0;
  95 }
  96
  97 /*
  98  * Constructor called with the address of a
  99  *   member of the list (not the list head), and
 100  *   the address of the link within that member.
 101  * If the link is at the beginning of the list member,
 102  *   then there is no need to specify the link address
 103  *   since the offset is zero.
 104  */
 105 inline dlist::dlist(void *item, dlink *link)
 106 {
 107    init(item, link);
 108 }
 109
 110 /* Constructor with link at head of item */
 111 inline dlist::dlist(void) : head(0), tail(0), loffset(0), num_items(0)
 112 {
 113 }
 114
 115 inline bool dlist::empty() const
 116 {
 117    return head == NULL;
 118 }
 119
 120 inline int dlist::size() const
 121 {
 122    return num_items;
 123 }
 124
 125
 126
 127 inline void * dlist::first() const
 128 {
 129    return head;
 130 }
 131
 132 inline void * dlist::last() const
 133 {
 134    return tail;
 135 }