1tree(3bsd) LOCAL tree(3bsd)
2
4 SPLAY_PROTOTYPE, SPLAY_GENERATE, SPLAY_ENTRY, SPLAY_HEAD,
5 SPLAY_INITIALIZER, SPLAY_ROOT, SPLAY_EMPTY, SPLAY_NEXT, SPLAY_MIN,
6 SPLAY_MAX, SPLAY_FIND, SPLAY_LEFT, SPLAY_RIGHT, SPLAY_FOREACH,
7 SPLAY_INIT, SPLAY_INSERT, SPLAY_REMOVE, RB_PROTOTYPE,
8 RB_PROTOTYPE_STATIC, RB_GENERATE, RB_GENERATE_STATIC, RB_ENTRY, RB_HEAD,
9 RB_INITIALIZER, RB_ROOT, RB_EMPTY, RB_NEXT, RB_PREV, RB_MIN, RB_MAX,
10 RB_FIND, RB_NFIND, RB_LEFT, RB_RIGHT, RB_PARENT, RB_FOREACH,
11 RB_FOREACH_SAFE, RB_FOREACH_REVERSE, RB_FOREACH_REVERSE_SAFE, RB_INIT,
12 RB_INSERT, RB_REMOVE — implementations of splay and red-black trees
13
15 Utility functions from BSD systems (libbsd, -lbsd)
16
18 #include <sys/tree.h>
19 (See libbsd(7) for include usage.)
20
21 SPLAY_PROTOTYPE(NAME, TYPE, FIELD, CMP);
22
23 SPLAY_GENERATE(NAME, TYPE, FIELD, CMP);
24
25 SPLAY_ENTRY(TYPE);
26
27 SPLAY_HEAD(HEADNAME, TYPE);
28
29 struct TYPE *
30 SPLAY_INITIALIZER(SPLAY_HEAD *head);
31
32 SPLAY_ROOT(SPLAY_HEAD *head);
33
34 int
35 SPLAY_EMPTY(SPLAY_HEAD *head);
36
37 struct TYPE *
38 SPLAY_NEXT(NAME, SPLAY_HEAD *head, struct TYPE *elm);
39
40 struct TYPE *
41 SPLAY_MIN(NAME, SPLAY_HEAD *head);
42
43 struct TYPE *
44 SPLAY_MAX(NAME, SPLAY_HEAD *head);
45
46 struct TYPE *
47 SPLAY_FIND(NAME, SPLAY_HEAD *head, struct TYPE *elm);
48
49 struct TYPE *
50 SPLAY_LEFT(struct TYPE *elm, SPLAY_ENTRY NAME);
51
52 struct TYPE *
53 SPLAY_RIGHT(struct TYPE *elm, SPLAY_ENTRY NAME);
54
55 SPLAY_FOREACH(VARNAME, NAME, SPLAY_HEAD *head);
56
57 void
58 SPLAY_INIT(SPLAY_HEAD *head);
59
60 struct TYPE *
61 SPLAY_INSERT(NAME, SPLAY_HEAD *head, struct TYPE *elm);
62
63 struct TYPE *
64 SPLAY_REMOVE(NAME, SPLAY_HEAD *head, struct TYPE *elm);
65
66 RB_PROTOTYPE(NAME, TYPE, FIELD, CMP);
67
68 RB_PROTOTYPE_STATIC(NAME, TYPE, FIELD, CMP);
69
70 RB_GENERATE(NAME, TYPE, FIELD, CMP);
71
72 RB_GENERATE_STATIC(NAME, TYPE, FIELD, CMP);
73
74 RB_ENTRY(TYPE);
75
76 RB_HEAD(HEADNAME, TYPE);
77
78 RB_INITIALIZER(RB_HEAD *head);
79
80 struct TYPE *
81 RB_ROOT(RB_HEAD *head);
82
83 int
84 RB_EMPTY(RB_HEAD *head);
85
86 struct TYPE *
87 RB_NEXT(NAME, RB_HEAD *head, struct TYPE *elm);
88
89 struct TYPE *
90 RB_PREV(NAME, RB_HEAD *head, struct TYPE *elm);
91
92 struct TYPE *
93 RB_MIN(NAME, RB_HEAD *head);
94
95 struct TYPE *
96 RB_MAX(NAME, RB_HEAD *head);
97
98 struct TYPE *
99 RB_FIND(NAME, RB_HEAD *head, struct TYPE *elm);
100
101 struct TYPE *
102 RB_NFIND(NAME, RB_HEAD *head, struct TYPE *elm);
103
104 struct TYPE *
105 RB_LEFT(struct TYPE *elm, RB_ENTRY NAME);
106
107 struct TYPE *
108 RB_RIGHT(struct TYPE *elm, RB_ENTRY NAME);
109
110 struct TYPE *
111 RB_PARENT(struct TYPE *elm, RB_ENTRY NAME);
112
113 RB_FOREACH(VARNAME, NAME, RB_HEAD *head);
114
115 RB_FOREACH_SAFE(VARNAME, NAME, RB_HEAD *head, TEMP_VARNAME);
116
117 RB_FOREACH_REVERSE(VARNAME, NAME, RB_HEAD *head);
118
119 RB_FOREACH_REVERSE_SAFE(VARNAME, NAME, RB_HEAD *head, TEMP_VARNAME);
120
121 void
122 RB_INIT(RB_HEAD *head);
123
124 struct TYPE *
125 RB_INSERT(NAME, RB_HEAD *head, struct TYPE *elm);
126
127 struct TYPE *
128 RB_REMOVE(NAME, RB_HEAD *head, struct TYPE *elm);
129
131 These macros define data structures for different types of trees: splay
132 trees and red-black trees.
133
134 In the macro definitions, TYPE is the name tag of a user defined struc‐
135 ture that must contain a field named FIELD, of type SPLAY_ENTRY or
136 RB_ENTRY. The argument HEADNAME is the name tag of a user defined struc‐
137 ture that must be declared using the macros SPLAY_HEAD() or RB_HEAD().
138 The argument NAME has to be a unique name prefix for every tree that is
139 defined.
140
141 The function prototypes are declared with SPLAY_PROTOTYPE, RB_PROTOTYPE,
142 or RB_PROTOTYPE_STATIC. The function bodies are generated with
143 SPLAY_GENERATE, RB_GENERATE, or RB_GENERATE_STATIC. See the examples be‐
144 low for further explanation of how these macros are used.
145
147 A splay tree is a self-organizing data structure. Every operation on the
148 tree causes a splay to happen. The splay moves the requested node to the
149 root of the tree and partly rebalances it.
150
151 This has the benefit that request locality causes faster lookups as the
152 requested nodes move to the top of the tree. On the other hand, every
153 lookup causes memory writes.
154
155 The Balance Theorem bounds the total access time for m operations and n
156 inserts on an initially empty tree as O((m + n)lg n). The amortized cost
157 for a sequence of m accesses to a splay tree is O(lg n).
158
159 A splay tree is headed by a structure defined by the SPLAY_HEAD() macro.
160 A SPLAY_HEAD structure is declared as follows:
161
162 SPLAY_HEAD(HEADNAME, TYPE) head;
163
164 where HEADNAME is the name of the structure to be defined, and struct
165 TYPE is the type of the elements to be inserted into the tree.
166
167 The SPLAY_ENTRY() macro declares a structure that allows elements to be
168 connected in the tree.
169
170 In order to use the functions that manipulate the tree structure, their
171 prototypes need to be declared with the SPLAY_PROTOTYPE() macro, where
172 NAME is a unique identifier for this particular tree. The TYPE argument
173 is the type of the structure that is being managed by the tree. The
174 FIELD argument is the name of the element defined by SPLAY_ENTRY().
175
176 The function bodies are generated with the SPLAY_GENERATE() macro. It
177 takes the same arguments as the SPLAY_PROTOTYPE() macro, but should be
178 used only once.
179
180 Finally, the CMP argument is the name of a function used to compare
181 trees' nodes with each other. The function takes two arguments of type
182 struct TYPE *. If the first argument is smaller than the second, the
183 function returns a value smaller than zero. If they are equal, the func‐
184 tion returns zero. Otherwise, it should return a value greater than
185 zero. The compare function defines the order of the tree elements.
186
187 The SPLAY_INIT() macro initializes the tree referenced by head.
188
189 The splay tree can also be initialized statically by using the
190 SPLAY_INITIALIZER() macro like this:
191
192 SPLAY_HEAD(HEADNAME, TYPE) head = SPLAY_INITIALIZER(&head);
193
194 The SPLAY_INSERT() macro inserts the new element elm into the tree. Upon
195 success, NULL is returned. If a matching element already exists in the
196 tree, the insertion is aborted, and a pointer to the existing element is
197 returned.
198
199 The SPLAY_REMOVE() macro removes the element elm from the tree pointed by
200 head. Upon success, a pointer to the removed element is returned. NULL
201 is returned if elm is not present in the tree.
202
203 The SPLAY_FIND() macro can be used to find a particular element in the
204 tree.
205
206 struct TYPE find, *res;
207 find.key = 30;
208 res = SPLAY_FIND(NAME, &head, &find);
209
210 The SPLAY_ROOT(), SPLAY_MIN(), SPLAY_MAX(), and SPLAY_NEXT() macros can
211 be used to traverse the tree:
212
213 for (np = SPLAY_MIN(NAME, &head); np != NULL; np = SPLAY_NEXT(NAME, &head, np))
214
215 Or, for simplicity, one can use the SPLAY_FOREACH() macro:
216
217 SPLAY_FOREACH(np, NAME, &head)
218
219 The SPLAY_EMPTY() macro should be used to check whether a splay tree is
220 empty.
221
223 A red-black tree is a binary search tree with the node color as an extra
224 attribute. It fulfills a set of conditions:
225
226 1. every search path from the root to a leaf consists of the same
227 number of black nodes,
228 2. each red node (except for the root) has a black parent,
229 3. each leaf node is black.
230
231 Every operation on a red-black tree is bounded as O(lg n). The maximum
232 height of a red-black tree is 2lg (n+1).
233
234 A red-black tree is headed by a structure defined by the RB_HEAD() macro.
235 A RB_HEAD structure is declared as follows:
236
237 RB_HEAD(HEADNAME, TYPE) head;
238
239 where HEADNAME is the name of the structure to be defined, and struct
240 TYPE is the type of the elements to be inserted into the tree.
241
242 The RB_ENTRY() macro declares a structure that allows elements to be con‐
243 nected in the tree.
244
245 In order to use the functions that manipulate the tree structure, their
246 prototypes need to be declared with the RB_PROTOTYPE() or
247 RB_PROTOTYPE_STATIC() macros, where NAME is a unique identifier for this
248 particular tree. The TYPE argument is the type of the structure that is
249 being managed by the tree. The FIELD argument is the name of the element
250 defined by RB_ENTRY().
251
252 The function bodies are generated with the RB_GENERATE() or
253 RB_GENERATE_STATIC() macros. These macros take the same arguments as the
254 RB_PROTOTYPE() and RB_PROTOTYPE_STATIC() macros, but should be used only
255 once.
256
257 Finally, the CMP argument is the name of a function used to compare
258 trees' nodes with each other. The function takes two arguments of type
259 struct TYPE *. If the first argument is smaller than the second, the
260 function returns a value smaller than zero. If they are equal, the func‐
261 tion returns zero. Otherwise, it should return a value greater than
262 zero. The compare function defines the order of the tree elements.
263
264 The RB_INIT() macro initializes the tree referenced by head.
265
266 The red-black tree can also be initialized statically by using the
267 RB_INITIALIZER() macro like this:
268
269 RB_HEAD(HEADNAME, TYPE) head = RB_INITIALIZER(&head);
270
271 The RB_INSERT() macro inserts the new element elm into the tree. Upon
272 success, NULL is returned. If a matching element already exists in the
273 tree, the insertion is aborted, and a pointer to the existing element is
274 returned.
275
276 The RB_REMOVE() macro removes the element elm from the tree pointed by
277 head. RB_REMOVE() returns elm.
278
279 The RB_FIND() and RB_NFIND() macros can be used to find a particular ele‐
280 ment in the tree. RB_FIND() finds the node with the same key as elm.
281 RB_NFIND() finds the first node greater than or equal to the search key.
282
283 struct TYPE find, *res;
284 find.key = 30;
285 res = RB_FIND(NAME, &head, &find);
286
287 The RB_ROOT(), RB_MIN(), RB_MAX(), RB_NEXT(), and RB_PREV() macros can be
288 used to traverse the tree:
289
290 for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))
291
292 Or, for simplicity, one can use the RB_FOREACH() or RB_FOREACH_REVERSE()
293 macros:
294
295 RB_FOREACH(np, NAME, &head)
296
297 The macros RB_FOREACH_SAFE() and RB_FOREACH_REVERSE_SAFE() traverse the
298 tree referenced by head in a forward or reverse direction respectively,
299 assigning each element in turn to np. However, unlike their unsafe coun‐
300 terparts, they permit both the removal of np as well as freeing it from
301 within the loop safely without interfering with the traversal.
302
303 The RB_EMPTY() macro should be used to check whether a red-black tree is
304 empty.
305
307 The following example demonstrates how to declare a red-black tree hold‐
308 ing integers. Values are inserted into it and the contents of the tree
309 are printed in order. Lastly, the internal structure of the tree is
310 printed.
311
312 #include <sys/tree.h>
313 #include <err.h>
314 #include <stdio.h>
315 #include <stdlib.h>
316
317 struct node {
318 RB_ENTRY(node) entry;
319 int i;
320 };
321
322 int intcmp(struct node *, struct node *);
323 void print_tree(struct node *);
324
325 int
326 intcmp(struct node *e1, struct node *e2)
327 {
328 return (e1->i < e2->i ? -1 : e1->i > e2->i);
329 }
330
331 RB_HEAD(inttree, node) head = RB_INITIALIZER(&head);
332 RB_PROTOTYPE(inttree, node, entry, intcmp)
333 RB_GENERATE(inttree, node, entry, intcmp)
334
335 int testdata[] = {
336 20, 16, 17, 13, 3, 6, 1, 8, 2, 4, 10, 19, 5, 9, 12, 15, 18,
337 7, 11, 14
338 };
339
340 void
341 print_tree(struct node *n)
342 {
343 struct node *left, *right;
344
345 if (n == NULL) {
346 printf("nil");
347 return;
348 }
349 left = RB_LEFT(n, entry);
350 right = RB_RIGHT(n, entry);
351 if (left == NULL && right == NULL)
352 printf("%d", n->i);
353 else {
354 printf("%d(", n->i);
355 print_tree(left);
356 printf(",");
357 print_tree(right);
358 printf(")");
359 }
360 }
361
362 int
363 main(void)
364 {
365 int i;
366 struct node *n;
367
368 for (i = 0; i < sizeof(testdata) / sizeof(testdata[0]); i++) {
369 if ((n = malloc(sizeof(struct node))) == NULL)
370 err(1, NULL);
371 n->i = testdata[i];
372 RB_INSERT(inttree, &head, n);
373 }
374
375 RB_FOREACH(n, inttree, &head) {
376 printf("%d\n", n->i);
377 }
378 print_tree(RB_ROOT(&head));
379 printf("\n");
380 return (0);
381 }
382
384 queue(3bsd)
385
387 Trying to free a tree in the following way is a common error:
388
389 SPLAY_FOREACH(var, NAME, &head) {
390 SPLAY_REMOVE(NAME, &head, var);
391 free(var);
392 }
393 free(head);
394
395 Since var is free'd, the FOREACH() macro refers to a pointer that may
396 have been reallocated already. Proper code needs a second variable.
397
398 for (var = SPLAY_MIN(NAME, &head); var != NULL; var = nxt) {
399 nxt = SPLAY_NEXT(NAME, &head, var);
400 SPLAY_REMOVE(NAME, &head, var);
401 free(var);
402 }
403
405 The author of the tree macros is Niels Provos.
406
407BSD May 10, 2019 BSD