1 /*
2 BAREOS® - Backup Archiving REcovery Open Sourced
3
4 Copyright (C) 2005-2007 Free Software Foundation Europe e.V.
5 Copyright (C) 2016-2019 Bareos GmbH & Co. KG
6
7 This program is Free Software; you can redistribute it and/or
8 modify it under the terms of version three of the GNU Affero General Public
9 License as published by the Free Software Foundation and included
10 in the file LICENSE.
11
12 This program is distributed in the hope that it will be useful, but
13 WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Affero General Public License for more details.
16
17 You should have received a copy of the GNU Affero General Public License
18 along with this program; if not, write to the Free Software
19 Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.
21 */
22 /*
23 * Kern Sibbald, MMV
24 */
25 /**
26 * @file
27 * red-black binary tree routines -- rblist.h
28 */
29 #ifndef BAREOS_LIB_RBLIST_H_
30 #define BAREOS_LIB_RBLIST_H_
31
32
33 #define M_ABORT 1
34
35 /**
36 * There is a lot of extra casting here to work around the fact
37 * that some compilers (Sun and Visual C++) do not accept
38 * (bnode *) as an lvalue on the left side of an equal.
39 *
40 * Loop var through each member of list
41 */
42 #ifdef HAVE_TYPEOF
43 # define foreach_rblist(var, tree) \
44 for (((var) = (typeof(var))(tree)->first()); (var); \
45 ((var) = (typeof(var))(tree)->next(var)))
46 #else
47 # define foreach_rblist(var, tree) \
48 for ((*((void**)&(var)) = (void*)((tree)->first())); (var); \
49 (*((void**)&(var)) = (void*)((tree)->next(var))))
50 #endif
51
52 struct rblink {
53 void* parent = nullptr;
54 void* left = nullptr;
55 void* right = nullptr;
56 bool red = false;
57 };
58
59 class rblist {
60 public:
61 rblist() = default;
62 rblist(void* item, rblink* link);
~rblist(void)63 ~rblist(void) { destroy(); }
64 void* insert(void* item, int compare(void* item1, void* item2));
65 int size(void) const;
66 bool empty(void) const;
67 void* first(void);
68 void* next(void* item);
69 void* search(void* item, int compare(void* item1, void* item2));
70 void remove(void* item);
71
72 private:
73 void* head = nullptr;
74 int16_t loffset = 0;
75 uint32_t num_items = 0;
76 bool down = false;
77 void LeftRotate(void* item);
78 void RightRotate(void* item);
79 void SetParent(void* item, void* parent);
80 void init(void* item, rblink* link);
81 void SetLeft(void* item, void* left);
82 void SetRight(void* item, void* right);
83 void SetRed(void* item, bool red);
84 void* parent(const void* item) const;
85 void* left(const void* item) const;
86 void* right(const void* item) const;
87 bool red(const void* item) const;
88 void* any(void* item);
89 void destroy(void);
90 };
91
92
93 /**
94 * This allows us to do explicit initialization,
95 * allowing us to mix C++ classes inside malloc'ed
96 * C structures. Define before called in constructor.
97 */
init(void * item,rblink * link)98 inline void rblist::init(void* item, rblink* link)
99 {
100 head = NULL;
101 loffset = (int)((char*)link - (char*)item);
102 if (loffset < 0 || loffset > 5000) {
103 Emsg0(M_ABORT, 0, "Improper rblist initialization.\n");
104 }
105 num_items = 0;
106 }
107
rblist(void * item,rblink * link)108 inline rblist::rblist(void* item, rblink* link) { init(item, link); }
109
SetParent(void * item,void * parent)110 inline void rblist::SetParent(void* item, void* parent)
111 {
112 ((rblink*)(((char*)item) + loffset))->parent = parent;
113 }
114
SetLeft(void * item,void * left)115 inline void rblist::SetLeft(void* item, void* left)
116 {
117 ((rblink*)(((char*)item) + loffset))->left = left;
118 }
119
SetRight(void * item,void * right)120 inline void rblist::SetRight(void* item, void* right)
121 {
122 ((rblink*)(((char*)item) + loffset))->right = right;
123 }
124
SetRed(void * item,bool red)125 inline void rblist::SetRed(void* item, bool red)
126 {
127 ((rblink*)(((char*)item) + loffset))->red = red;
128 }
129
empty(void)130 inline bool rblist::empty(void) const { return head == NULL; }
131
size()132 inline int rblist::size() const { return num_items; }
133
parent(const void * item)134 inline void* rblist::parent(const void* item) const
135 {
136 return ((rblink*)(((char*)item) + loffset))->parent;
137 }
138
left(const void * item)139 inline void* rblist::left(const void* item) const
140 {
141 return ((rblink*)(((char*)item) + loffset))->left;
142 }
143
right(const void * item)144 inline void* rblist::right(const void* item) const
145 {
146 return ((rblink*)(((char*)item) + loffset))->right;
147 }
148
red(const void * item)149 inline bool rblist::red(const void* item) const
150 {
151 return ((rblink*)(((char*)item) + loffset))->red;
152 }
153
154 #endif /* BAREOS_LIB_RBLIST_H_ */
155