SPLAY_ENTRY(3bsd)

1tree(3bsd)                           LOCAL                          tree(3bsd)
2

NAME

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

LIBRARY

15     Utility functions from BSD systems (libbsd, -lbsd)
16

SYNOPSIS

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

DESCRIPTION

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

SPLAY TREES

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

RED-BLACK TREES

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

EXAMPLES

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

NOTES

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

AUTHORS

405     The author of the tree macros is Niels Provos.
406
407BSD                              May 10, 2019                              BSD