1gg-tree(3) GGI gg-tree(3)
2
6 gg-tree, GG_SPLAY_PROTOTYPE, GG_SPLAY_GENERATE, GG_SPLAY_ENTRY,
7 GG_SPLAY_HEAD, GG_SPLAY_INITIALIZER, GG_SPLAY_ROOT, GG_SPLAY_EMPTY,
8 GG_SPLAY_NEXT, GG_SPLAY_MIN, GG_SPLAY_MAX, GG_SPLAY_FIND,
9 GG_SPLAY_LEFT, GG_SPLAY_RIGHT, GG_SPLAY_FOREACH, GG_SPLAY_INIT,
10 GG_SPLAY_INSERT, GG_SPLAY_REMOVE, GG_RB_PROTOTYPE, GG_RB_GENERATE,
11 GG_RB_ENTRY, GG_RB_HEAD, GG_RB_INITIALIZER, GG_RB_ROOT, GG_RB_EMPTY,
12 GG_RB_NEXT, GG_RB_MIN, GG_RB_MAX, GG_RB_FIND, GG_RB_LEFT, GG_RB_RIGHT,
13 GG_RB_PARENT, GG_RB_FOREACH, GG_RB_INIT, GG_RB_INSERT, GG_RB_REMOVE :
14 implementations of splay and red-black trees
15
17 #include <ggi/gg-tree.h>
18 GG_SPLAY_PROTOTYPE(NAME, TYPE, FIELD, CMP);
20 GG_SPLAY_GENERATE(NAME, TYPE, FIELD, CMP);
22 GG_SPLAY_ENTRY(TYPE);
24 GG_SPLAY_HEAD(HEADNAME, TYPE);
26 struct TYPE *
28 GG_SPLAY_INITIALIZER(GG_SPLAY_HEAD *head);
29 GG_SPLAY_ROOT(GG_SPLAY_HEAD *head);
31 bool
33 GG_SPLAY_EMPTY(GG_SPLAY_HEAD *head);
34 struct TYPE *
36 GG_SPLAY_NEXT(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);
37 struct TYPE *
39 GG_SPLAY_MIN(NAME, GG_SPLAY_HEAD *head);
40 struct TYPE *
42 GG_SPLAY_MAX(NAME, GG_SPLAY_HEAD *head);
43 struct TYPE *
45 GG_SPLAY_FIND(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);
46 struct TYPE *
48 GG_SPLAY_LEFT(struct TYPE *elm, GG_SPLAY_ENTRY NAME);
49 struct TYPE *
51 GG_SPLAY_RIGHT(struct TYPE *elm, GG_SPLAY_ENTRY NAME);
52 GG_SPLAY_FOREACH(VARNAME, NAME, GG_SPLAY_HEAD *head);
54 void
56 GG_SPLAY_INIT(GG_SPLAY_HEAD *head);
57 struct TYPE *
59 GG_SPLAY_INSERT(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);
60 struct TYPE *
62 GG_SPLAY_REMOVE(NAME, GG_SPLAY_HEAD *head, struct TYPE *elm);
63 GG_RB_PROTOTYPE(NAME, TYPE, FIELD, CMP);
65 GG_RB_GENERATE(NAME, TYPE, FIELD, CMP);
67 GG_RB_ENTRY(TYPE);
69 GG_RB_HEAD(HEADNAME, TYPE);
71 GG_RB_INITIALIZER(GG_RB_HEAD *head);
73 struct TYPE *
75 GG_RB_ROOT(GG_RB_HEAD *head);
76 bool
78 GG_RB_EMPTY(GG_RB_HEAD *head);
79 struct TYPE *
81 GG_RB_NEXT(NAME, GG_RB_HEAD *head, struct TYPE *elm);
82 struct TYPE *
84 GG_RB_MIN(NAME, GG_RB_HEAD *head);
85 struct TYPE *
87 GG_RB_MAX(NAME, GG_RB_HEAD *head);
88 struct TYPE *
90 GG_RB_FIND(NAME, GG_RB_HEAD *head, struct TYPE *elm);
91 struct TYPE *
93 GG_RB_LEFT(struct TYPE *elm, GG_RB_ENTRY NAME);
94 struct TYPE *
96 GG_RB_RIGHT(struct TYPE *elm, GG_RB_ENTRY NAME);
97 struct TYPE *
99 GG_RB_PARENT(struct TYPE *elm, GG_RB_ENTRY NAME);
100 GG_RB_FOREACH(VARNAME, NAME, GG_RB_HEAD *head);
102 void
104 GG_RB_INIT(GG_RB_HEAD *head);
105 struct TYPE *
107 GG_RB_INSERT(NAME, GG_RB_HEAD *head, struct TYPE *elm);
108 struct TYPE *
110 GG_RB_REMOVE(NAME, GG_RB_HEAD *head, struct TYPE *elm);
111
114 These macros define data structures for different types of trees: splay
115 trees and red-black trees.
116 In the macro definitions, TYPE is the name tag of a user defined struc‐
118 ture that must contain a field of type GG_SPLAY_ENTRY, or GG_RB_ENTRY,
119 named ENTRYNAME. The argument HEADNAME is the name tag of a user
120 defined structure that must be declared using the macros GG_SPLAY_HEAD
121 or GG_RB_HEAD. The argument NAME has to be a unique name prefix for
122 every tree that is defined.
123 The function prototypes are declared with either GG_SPLAY_PROTOTYPE or
125 GG_RB_PROTOTYPE. The function bodies are generated with either
126 GG_SPLAY_GENERATE or GG_RB_GENERATE. See the examples below for further
127 explanation of how these macros are used.
128
130 A splay tree is a self-organizing data structure. Every operation on
131 the tree causes a splay to happen. The splay moves the requested node
132 to the root of the tree and partly rebalances it.
133 This has the benefit that request locality causes faster lookups as the
135 requested nodes move to the top of the tree. On the other hand, every
136 lookup causes memory writes.
137 The Balance Theorem bounds the total access time for m operations and n
139 inserts on an initially empty tree as O((m + n)lg n). The amortized
140 cost for a sequence of m accesses to a splay tree is O(lg n).
141 A splay tree is headed by a structure defined by the SPLAY_HEAD macro.
143 A GG_SPLAY_HEAD structure is declared as follows:
144 GG_SPLAY_HEAD(HEADNAME, TYPE) head;
146 where HEADNAME is the name of the structure to be defined, and struct
148 TYPE is the type of the elements to be inserted into the tree.
149 The GG_SPLAY_ENTRY macro declares a structure that allows elements to
151 be connected in the tree.
152 In order to use the functions that manipulate the tree structure, their
154 prototypes need to be declared with the GG_SPLAY_PROTOTYPE macro, where
155 NAME is a unique identifier for this particular tree. The TYPE argu‐
156 ment is the type of the structure that is being managed by the tree.
157 The FIELD argument is the name of the element defined by
158 GG_SPLAY_ENTRY.
159 The function bodies are generated with the GG_SPLAY_GENERATE macro. It
161 takes the same arguments as the GG_SPLAY_PROTOTYPE macro, but should be
162 used only once.
163 Finally, the CMP argument is the name of a function used to compare
165 trees noded with each other. The function takes two arguments of type
166 struct TYPE *. If the first argument is smaller than the second, the
167 function returns a value smaller than zero. If they are equal, the
168 function returns zero. Otherwise, it should return a value greater
169 than zero. The compare function defines the order of the tree ele‐
170 ments.
171 The GG_SPLAY_INIT macro initializes the tree referenced by head.
173 The splay tree can also be initialized statically by using the
175 GG_SPLAY_INITIALIZER macro like this:
176 GG_SPLAY_HEAD(HEADNAME, TYPE) head = GG_SPLAY_INITIALIZER(&head);
178 The GG_SPLAY_INSERT macro inserts the new element elm into the tree.
180 The GG_SPLAY_REMOVE macro removes the element elm from the tree pointed
182 by head.
183 The GG_SPLAY_FIND macro can be used to find a particular element in the
185 tree.:
186 struct TYPE find, *res;
188 find.key = 30;
189 res = GG_SPLAY_FIND(NAME, head, &find);
190 The GG_SPLAY_ROOT, GG_SPLAY_MIN, GG_SPLAY_MAX, and GG_SPLAY_NEXT macros
192 can be used to traverse the tree:
193 for (np = GG_SPLAY_MIN(NAME, &head); np != NULL; np = GG_SPLAY_NEXT(NAME, &head, np))
195 Or, for simplicity, one can use the GG_SPLAY_FOREACH macro:
197 GG_SPLAY_FOREACH(np, NAME, head)
199 The GG_SPLAY_EMPTY macro should be used to check whether a splay tree
201 is empty.
202
204 A red-black tree is a binary search tree with the node color as an
205 extra attribute. It fulfills a set of conditions:
206 1 every search path from the root to a leaf consists of the same num‐
208 ber of black nodes,
209 2 each red node (except for the root) has a black parent,
211 3 each leaf node is black.
213 Every operation on a red-black tree is bounded as O(lg n). The maximum
215 height of a red-black tree is 2lg (n+1).
216 A red-black tree is headed by a structure defined by the GG_RB_HEAD
218 macro. A GG_RB_HEAD structure is declared as follows:
219 GG_RB_HEAD(HEADNAME, TYPE) head;
221 where HEADNAME is the name of the structure to be defined, and struct
223 TYPE is the type of the elements to be inserted into the tree.
224 The GG_RB_ENTRY macro declares a structure that allows elements to be
226 connected in the tree.
227 In order to use the functions that manipulate the tree structure, their
229 prototypes need to be declared with the GG_RB_PROTOTYPE macro, where
230 NAME is a unique identifier for this particular tree. The TYPE argument
231 is the type of the structure that is being managed by the tree. The
232 FIELD argument is the name of the element defined by GG_RB_ENTRY.
233 The function bodies are generated with the GG_RB_GENERATE macro. It
235 takes the same arguments as the GG_RB_PROTOTYPE macro, but should be
236 used only once.
237 Finally, the CMP argument is the name of a function used to compare
239 trees noded with each other. The function takes two arguments of type
240 struct TYPE *. If the first argument is smaller than the second, the
241 function returns a value smaller than zero. If they are equal, the
242 function returns zero. Otherwise, it should return a value greater
243 than zero. The compare function defines the order of the tree ele‐
244 ments.
245 The GG_RB_INIT macro initializes the tree referenced by head.
247 The redblack tree can also be initialized statically by using the
249 GG_RB_INITIALIZER macro like this:
250 GG_RB_HEAD(HEADNAME, TYPE) head = GG_RB_INITIALIZER(&head);
252 The GG_RB_INSERT macro inserts the new element elm into the tree.
254 The GG_RB_REMOVE macro removes the element elm from the tree pointed by
256 head.
257 The GG_RB_FIND macro can be used to find a particular element in the
259 tree.:
260 struct TYPE find, *res;
262 find.key = 30;
263 res = GG_RB_FIND(NAME, head, &find);
264 The GG_RB_ROOT, GG_RB_MIN, GG_RB_MAX, and GG_RB_NEXT macros can be used
266 to traverse the tree:
267 for (np = RB_MIN(NAME, &head); np != NULL; np = RB_NEXT(NAME, &head, np))
269 Or, for simplicity, one can use the RB_FOREACH macro:
271 GG_RB_FOREACH(np, NAME, head)
273 The GG_RB_EMPTY macro should be used to check whether a red-black tree
275 is empty.
276
278 Trying to free a tree in the following way is a common error:
279 GG_SPLAY_FOREACH(var, NAME, head) {
281 GG_SPLAY_REMOVE(NAME, head, var);
282 free(var);
283 }
284 free(head);
285 Since var is free'd, the FOREACH macro refers to a pointer that may
287 have been reallocated already. Proper code needs a second variable.:
288 for (var = GG_SPLAY_MIN(NAME, head); var != NULL; var = nxt) {
290 nxt = GG_SPLAY_NEXT(NAME, head, var);
291 GG_SPLAY_REMOVE(NAME, head, var);
292 free(var);
293 }
294 Both GG_RB_INSERT and GG_SPLAY_INSERT return NULL if the element was
296 inserted in the tree successfully, otherwise they return a pointer to
297 the element with the colliding key.
298 Accordingly, GG_RB_REMOVE and GG_SPLAY_REMOVE return the pointer to the
300 removed element, otherwise they return NULL to indicate an error.
301
303 gg-queue(3)
304libgg-1.0.x 2005-08-26 gg-tree(3)