1 /*
2 BAREOS® - Backup Archiving REcovery Open Sourced
3
4 Copyright (C) 2005-2011 Free Software Foundation Europe e.V.
5 Copyright (C) 2013-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 * BAREOS red-black binary tree routines.
24 *
25 * rblist is a binary tree with the links being in the data item.
26 *
27 * Developed in part from ideas obtained from several online University courses.
28 *
29 * Kern Sibbald, November MMV
30 */
31
32 #include "include/bareos.h"
33 #include "lib/rblist.h"
34
35 /*
36 * Insert an item in the tree, but only if it is unique
37 * otherwise, the item is returned non inserted
38 * The big trick is keeping the tree balanced after the
39 * insert. We use a parent pointer to make it simpler and
40 * to avoid recursion.
41 *
42 * Returns: item if item inserted
43 * other_item if same value already exists (item not inserted)
44 */
insert(void * item,int compare (void * item1,void * item2))45 void* rblist::insert(void* item, int compare(void* item1, void* item2))
46 {
47 void *x, *y;
48 void* last = NULL; /* last leaf if not found */
49 void* found = NULL;
50 int comp = 0;
51
52 /* Search */
53 x = head;
54 while (x && !found) {
55 last = x;
56 comp = compare(item, x);
57 if (comp < 0) {
58 x = left(x);
59 } else if (comp > 0) {
60 x = right(x);
61 } else {
62 found = x;
63 }
64 }
65
66 if (found) { /* found? */
67 return found; /* yes, return item found */
68 }
69 SetLeft(item, NULL);
70 SetRight(item, NULL);
71 SetParent(item, NULL);
72 SetRed(item, false);
73 /* Handle empty tree */
74 if (num_items == 0) {
75 head = item;
76 num_items++;
77 return item;
78 }
79 x = last;
80 /* Not found, so insert it on appropriate side of tree */
81 if (comp < 0) {
82 SetLeft(last, item);
83 } else {
84 SetRight(last, item);
85 }
86 SetRed(last, true);
87 SetParent(item, last);
88 num_items++;
89
90 /* Now we must walk up the tree balancing it */
91 x = last;
92 while (x != head && red(parent(x))) {
93 if (parent(x) == left(parent(parent(x)))) {
94 /* Look at the right side of our grandparent */
95 y = right(parent(parent(x)));
96 if (y && red(y)) {
97 /* our parent must be black */
98 SetRed(parent(x), false);
99 SetRed(y, false);
100 SetRed(parent(parent(x)), true);
101 x = parent(parent(x)); /* move up to grandpa */
102 } else {
103 if (x == right(parent(x))) { /* right side of parent? */
104 x = parent(x);
105 LeftRotate(x);
106 }
107 /* make parent black too */
108 SetRed(parent(x), false);
109 SetRed(parent(parent(x)), true);
110 RightRotate(parent(parent(x)));
111 }
112 } else {
113 /* Look at left side of our grandparent */
114 y = left(parent(parent(x)));
115 if (y && red(y)) {
116 SetRed(parent(x), false);
117 SetRed(y, false);
118 SetRed(parent(parent(x)), true);
119 x = parent(parent(x)); /* move up to grandpa */
120 } else {
121 if (x == left(parent(x))) {
122 x = parent(x);
123 RightRotate(x);
124 }
125 /* make parent black too */
126 SetRed(parent(x), false);
127 SetRed(parent(parent(x)), true);
128 LeftRotate(parent(parent(x)));
129 }
130 }
131 }
132 /* Make sure the head is always black */
133 SetRed(head, false);
134 return item;
135 }
136
137 /*
138 * Search for item
139 */
search(void * item,int compare (void * item1,void * item2))140 void* rblist::search(void* item, int compare(void* item1, void* item2))
141 {
142 void* found = NULL;
143 void* x;
144 int comp;
145
146 x = head;
147 while (x) {
148 comp = compare(item, x);
149 if (comp < 0) {
150 x = left(x);
151 } else if (comp > 0) {
152 x = right(x);
153 } else {
154 found = x;
155 break;
156 }
157 }
158 return found;
159 }
160
161 /*
162 * Get first item (i.e. lowest value)
163 */
first(void)164 void* rblist::first(void)
165 {
166 void* x;
167
168 x = head;
169 down = true;
170 while (x) {
171 if (left(x)) {
172 x = left(x);
173 continue;
174 }
175 return x;
176 }
177 /* Tree is empty */
178 return NULL;
179 }
180
181 /*
182 * This is a non-recursive btree walk routine that returns
183 * the items one at a time in order. I've never seen a
184 * non-recursive tree walk routine published that returns
185 * one item at a time rather than doing a callback.
186 *
187 * Return the next item in sorted order. We assume first()
188 * was called once before calling this routine.
189 * We always go down as far as we can to the left, then up, and
190 * down one to the right, and again down as far as we can to the
191 * left. etc.
192 *
193 * Returns: pointer to next larger item
194 * NULL when no more items in tree
195 */
next(void * item)196 void* rblist::next(void* item)
197 {
198 void* x;
199
200 if (!item) { return first(); }
201
202 x = item;
203 if ((down && !left(x) && right(x)) || (!down && right(x))) {
204 /* Move down to right one */
205 down = true;
206 x = right(x);
207 /* Then all the way down left */
208 while (left(x)) { x = left(x); }
209 return x;
210 }
211
212 /* We have gone down all we can, so now go up */
213 for (;;) {
214 /* If at head, we are done */
215 if (!parent(x)) { return NULL; }
216 /* Move up in tree */
217 down = false;
218 /* if coming from right, continue up */
219 if (right(parent(x)) == x) {
220 x = parent(x);
221 continue;
222 }
223 /* Coming from left, go up one -- ie. return parent */
224 return parent(x);
225 }
226 }
227
228 /*
229 * Similer to next(), but visits all right nodes when
230 * coming up the tree.
231 */
any(void * item)232 void* rblist::any(void* item)
233 {
234 void* x;
235
236 if (!item) { return NULL; }
237
238 x = item;
239 if ((down && !left(x) && right(x)) || (!down && right(x))) {
240 /* Move down to right one */
241 down = true;
242 x = right(x);
243 /* Then all the way down left */
244 while (left(x)) { x = left(x); }
245 return x;
246 }
247
248 /* We have gone down all we can, so now go up */
249 for (;;) {
250 /* If at head, we are done */
251 if (!parent(x)) { return NULL; }
252 down = false;
253 /* Go up one and return parent */
254 return parent(x);
255 }
256 }
257
258
259 /* x is item, y is below and to right, then rotated to below left */
LeftRotate(void * item)260 void rblist::LeftRotate(void* item)
261 {
262 void* y;
263 void* x;
264
265 x = item;
266 y = right(x);
267 SetRight(x, left(y));
268 if (left(y)) { SetParent(left(y), x); }
269 SetParent(y, parent(x));
270 /* if no parent then we have a new head */
271 if (!parent(x)) {
272 head = y;
273 } else if (x == left(parent(x))) {
274 SetLeft(parent(x), y);
275 } else {
276 SetRight(parent(x), y);
277 }
278 SetLeft(y, x);
279 SetParent(x, y);
280 }
281
RightRotate(void * item)282 void rblist::RightRotate(void* item)
283 {
284 void *x, *y;
285
286 y = item;
287 x = left(y);
288 SetLeft(y, right(x));
289 if (right(x)) { SetParent(right(x), y); }
290 SetParent(x, parent(y));
291 /* if no parent then we have a new head */
292 if (!parent(y)) {
293 head = x;
294 } else if (y == left(parent(y))) {
295 SetLeft(parent(y), x);
296 } else {
297 SetRight(parent(y), x);
298 }
299 SetRight(x, y);
300 SetParent(y, x);
301 }
302
303
remove(void * item)304 void rblist::remove(void* item) {}
305
306 /* Destroy the tree contents. Not totally working */
destroy()307 void rblist::destroy()
308 {
309 void *x, *y = NULL;
310
311 x = first();
312 // printf("head=%p first=%p left=%p right=%p\n", head, x, left(x), right(x));
313 for (; (y = any(x));) {
314 /* Prune the last item */
315 if (parent(x)) {
316 if (x == left(parent(x))) {
317 SetLeft(parent(x), NULL);
318 } else if (x == right(parent(x))) {
319 SetRight(parent(x), NULL);
320 }
321 }
322 if (!left(x) && !right(x)) {
323 if (head == x) { head = NULL; }
324 // if (num_items<30) {
325 // printf("free nitems=%d item=%p left=%p right=%p\n",
326 // num_items, x, left(x), right(x));
327 // }
328 free((void*)x); /* free previous node */
329 num_items--;
330 }
331 x = y; /* save last node */
332 }
333 if (x) {
334 if (x == head) { head = NULL; }
335 // printf("free nitems=%d item=%p left=%p right=%p\n", num_items, x,
336 // left(x), right(x));
337 free((void*)x);
338 num_items--;
339 }
340 if (head) {
341 // printf("Free head\n");
342 free((void*)head);
343 }
344 // printf("free nitems=%d\n", num_items);
345
346 head = NULL;
347 }
348