2 Bacula(R) - The Network Backup Solution
4 Copyright (C) 2000-2016 Kern Sibbald
6 The original author of Bacula is Kern Sibbald, with contributions
7 from many others, a complete list can be found in the file AUTHORS.
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.
14 This notice must be preserved when any source code is
15 conveyed and/or propagated.
17 Bacula(R) is a registered trademark of Kern Sibbald.
19 /* ========================================================================
21 * red-black binary tree routines -- rblist.h
30 * There is a lot of extra casting here to work around the fact
31 * that some compilers (Sun and Visual C++) do not accept
32 * (bnode *) as an lvalue on the left side of an equal.
34 * Loop var through each member of list
37 #define foreach_rblist(var, tree) \
38 for (((var)=(typeof(var))(tree)->first()); (var); ((var)=(typeof(var))(tree)->next(var)))
40 #define foreach_rblist(var, tree) \
41 for ((*((void **)&(var))=(void*)((tree)->first())); (var); (*((void **)&(var))=(void*)((tree)->next(var))))
51 class rblist : public SMARTALLOC {
56 void left_rotate(void *item);
57 void right_rotate(void *item);
59 rblist(void *item, rblink *link);
61 ~rblist(void) { destroy(); }
62 void init(void *item, rblink *link);
63 void set_parent(void *item, void *parent);
64 void set_left(void *item, void *left);
65 void set_right(void *item, void *right);
66 void set_red(void *item, bool red);
67 void *parent(const void *item) const;
68 void *left(const void *item) const;
69 void *right(const void *item) const;
70 bool red(const void *item) const;
71 void *insert(void *item, int compare(void *item1, void *item2));
72 void *search(void *item, int compare(void *item1, void *item2));
74 void *next(void *item);
75 void *any(void *item);
76 void remove(void *item);
77 bool empty(void) const;
84 * This allows us to do explicit initialization,
85 * allowing us to mix C++ classes inside malloc'ed
86 * C structures. Define before called in constructor.
88 inline void rblist::init(void *item, rblink *link)
91 loffset = (int)((char *)link - (char *)item);
92 if (loffset < 0 || loffset > 5000) {
93 Emsg0(M_ABORT, 0, "Improper rblist initialization.\n");
98 inline rblist::rblist(void *item, rblink *link)
103 /* Constructor with link at head of item */
104 inline rblist::rblist(void): head(0), loffset(0), num_items(0)
108 inline void rblist::set_parent(void *item, void *parent)
110 ((rblink *)(((char *)item)+loffset))->parent = parent;
113 inline void rblist::set_left(void *item, void *left)
115 ((rblink *)(((char *)item)+loffset))->left = left;
118 inline void rblist::set_right(void *item, void *right)
120 ((rblink *)(((char *)item)+loffset))->right = right;
123 inline void rblist::set_red(void *item, bool red)
125 ((rblink *)(((char *)item)+loffset))->red = red;
128 inline bool rblist::empty(void) const
133 inline int rblist::size() const
138 inline void *rblist::parent(const void *item) const
140 return ((rblink *)(((char *)item)+loffset))->parent;
143 inline void *rblist::left(const void *item) const
145 return ((rblink *)(((char *)item)+loffset))->left;
148 inline void *rblist::right(const void *item) const
150 return ((rblink *)(((char *)item)+loffset))->right;
153 inline bool rblist::red(const void *item) const
155 return ((rblink *)(((char *)item)+loffset))->red;