1 /*
2 Bacula(R) - The Network Backup Solution
3
4 Copyright (C) 2000-2020 Kern Sibbald
5
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.
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 This notice must be preserved when any source code is
15 conveyed and/or propagated.
16
17 Bacula(R) is a registered trademark of Kern Sibbald.
18 */
19 /* ========================================================================
20 *
21 * red-black binary tree routines -- rblist.h
22 *
23 * Kern Sibbald, MMV
24 *
25 */
26
27 #define M_ABORT 1
28
29 /*
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.
33 *
34 * Loop var through each member of list
35 */
36 #ifdef HAVE_TYPEOF
37 #define foreach_rblist(var, tree) \
38 for (((var)=(typeof(var))(tree)->first()); (var); ((var)=(typeof(var))(tree)->next(var)))
39 #else
40 #define foreach_rblist(var, tree) \
41 for ((*((void **)&(var))=(void*)((tree)->first())); (var); (*((void **)&(var))=(void*)((tree)->next(var))))
42 #endif
43
44 struct rblink {
45 void *parent;
46 void *left;
47 void *right;
48 bool red;
49 };
50
51 class rblist : public SMARTALLOC {
52 void *head;
53 int16_t loffset;
54 uint32_t num_items;
55 bool down;
56 void left_rotate(void *item);
57 void right_rotate(void *item);
58 public:
59 rblist(void *item, rblink *link);
60 rblist(void);
~rblist(void)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));
73 void *first(void);
74 void *next(void *item);
75 void *any(void *item);
76 void remove(void *item);
77 bool empty(void) const;
78 int size(void) const;
79 void destroy(void);
80 };
81
82
83 /*
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.
87 */
init(void * item,rblink * link)88 inline void rblist::init(void *item, rblink *link)
89 {
90 head = NULL;
91 loffset = (int)((char *)link - (char *)item);
92 if (loffset < 0 || loffset > 5000) {
93 Emsg0(M_ABORT, 0, "Improper rblist initialization.\n");
94 }
95 num_items = 0;
96 }
97
rblist(void * item,rblink * link)98 inline rblist::rblist(void *item, rblink *link)
99 {
100 init(item, link);
101 }
102
103 /* Constructor with link at head of item */
rblist(void)104 inline rblist::rblist(void): head(0), loffset(0), num_items(0)
105 {
106 }
107
set_parent(void * item,void * parent)108 inline void rblist::set_parent(void *item, void *parent)
109 {
110 ((rblink *)(((char *)item)+loffset))->parent = parent;
111 }
112
set_left(void * item,void * left)113 inline void rblist::set_left(void *item, void *left)
114 {
115 ((rblink *)(((char *)item)+loffset))->left = left;
116 }
117
set_right(void * item,void * right)118 inline void rblist::set_right(void *item, void *right)
119 {
120 ((rblink *)(((char *)item)+loffset))->right = right;
121 }
122
set_red(void * item,bool red)123 inline void rblist::set_red(void *item, bool red)
124 {
125 ((rblink *)(((char *)item)+loffset))->red = red;
126 }
127
empty(void)128 inline bool rblist::empty(void) const
129 {
130 return head == NULL;
131 }
132
size()133 inline int rblist::size() const
134 {
135 return num_items;
136 }
137
parent(const void * item)138 inline void *rblist::parent(const void *item) const
139 {
140 return ((rblink *)(((char *)item)+loffset))->parent;
141 }
142
left(const void * item)143 inline void *rblist::left(const void *item) const
144 {
145 return ((rblink *)(((char *)item)+loffset))->left;
146 }
147
right(const void * item)148 inline void *rblist::right(const void *item) const
149 {
150 return ((rblink *)(((char *)item)+loffset))->right;
151 }
152
red(const void * item)153 inline bool rblist::red(const void *item) const
154 {
155 return ((rblink *)(((char *)item)+loffset))->red;
156 }
157