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

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