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

   1 /*
   2    Bacula® - The Network Backup Solution
   3
   4    Copyright (C) 2005-2014 Free Software Foundation Europe e.V.
   5
   6    The main author of Bacula is Kern Sibbald, with contributions from many
   7    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    Bacula® is a registered trademark of Kern Sibbald.
  15 */
  16
  17 /*
  18  *   Version $Id$
  19  */
  20
  21 /* ========================================================================
  22  *
  23  *   red-black binary tree routines -- rblist.h
  24  *
  25  *    Kern Sibbald, MMV
  26  *
  27  */
  28
  29 #define M_ABORT 1
  30
  31 /*
  32  * There is a lot of extra casting here to work around the fact
  33  * that some compilers (Sun and Visual C++) do not accept
  34  * (bnode *) as an lvalue on the left side of an equal.
  35  *
  36  * Loop var through each member of list
  37  */
  38 #ifdef HAVE_TYPEOF
  39 #define foreach_rblist(var, tree) \
  40    for (((var)=(typeof(var))(tree)->first()); (var); ((var)=(typeof(var))(tree)->next(var)))
  41 #else
  42 #define foreach_rblist(var, tree) \
  43    for ((*((void **)&(var))=(void*)((tree)->first())); (var); (*((void **)&(var))=(void*)((tree)->next(var))))
  44 #endif
  45
  46 struct rblink {
  47    void *parent;
  48    void *left;
  49    void *right;
  50    bool red;
  51 };
  52
  53 class rblist : public SMARTALLOC {
  54    void *head;
  55    int16_t loffset;
  56    uint32_t num_items;
  57    bool down;
  58    void left_rotate(void *item);
  59    void right_rotate(void *item);
  60 public:
  61    rblist(void *item, rblink *link);
  62    rblist(void);
  63    ~rblist(void) { destroy(); }
  64    void init(void *item, rblink *link);
  65    void set_parent(void *item, void *parent);
  66    void set_left(void *item, void *left);
  67    void set_right(void *item, void *right);
  68    void set_red(void *item, bool red);
  69    void *parent(const void *item) const;
  70    void *left(const void *item) const;
  71    void *right(const void *item) const;
  72    bool red(const void *item) const;
  73    void *insert(void *item, int compare(void *item1, void *item2));
  74    void *search(void *item, int compare(void *item1, void *item2));
  75    void *first(void);
  76    void *next(void *item);
  77    void *any(void *item);
  78    void remove(void *item);
  79    bool empty(void) const;
  80    int size(void) const;
  81    void destroy(void);
  82 };
  83
  84
  85 /*
  86  * This allows us to do explicit initialization,
  87  *   allowing us to mix C++ classes inside malloc'ed
  88  *   C structures. Define before called in constructor.
  89  */
  90 inline void rblist::init(void *item, rblink *link)
  91 {
  92    head = NULL;
  93    loffset = (int)((char *)link - (char *)item);
  94    if (loffset < 0 || loffset > 5000) {
  95       Emsg0(M_ABORT, 0, "Improper rblist initialization.\n");
  96    }
  97    num_items = 0;
  98 }
  99
 100 inline rblist::rblist(void *item, rblink *link)
 101 {
 102    init(item, link);
 103 }
 104
 105 /* Constructor with link at head of item */
 106 inline rblist::rblist(void): head(0), loffset(0), num_items(0)
 107 {
 108 }
 109
 110 inline void rblist::set_parent(void *item, void *parent)
 111 {
 112    ((rblink *)(((char *)item)+loffset))->parent = parent;
 113 }
 114
 115 inline void rblist::set_left(void *item, void *left)
 116 {
 117    ((rblink *)(((char *)item)+loffset))->left = left;
 118 }
 119
 120 inline void rblist::set_right(void *item, void *right)
 121 {
 122    ((rblink *)(((char *)item)+loffset))->right = right;
 123 }
 124
 125 inline void rblist::set_red(void *item, bool red)
 126 {
 127    ((rblink *)(((char *)item)+loffset))->red = red;
 128 }
 129
 130 inline bool rblist::empty(void) const
 131 {
 132    return head == NULL;
 133 }
 134
 135 inline int rblist::size() const
 136 {
 137    return num_items;
 138 }
 139
 140 inline void *rblist::parent(const void *item) const
 141 {
 142    return ((rblink *)(((char *)item)+loffset))->parent;
 143 }
 144
 145 inline void *rblist::left(const void *item) const
 146 {
 147    return ((rblink *)(((char *)item)+loffset))->left;
 148 }
 149
 150 inline void *rblist::right(const void *item) const
 151 {
 152    return ((rblink *)(((char *)item)+loffset))->right;
 153 }
 154
 155 inline bool rblist::red(const void *item) const
 156 {
 157    return ((rblink *)(((char *)item)+loffset))->red;
 158 }