1 /*
2 * MOC - music on console
3 * Copyright (C) 2005 Damian Pietras <daper@daper.net>
4 *
5 * This program is free software; you can redistribute it and/or modify
6 * it under the terms of the GNU General Public License as published by
7 * the Free Software Foundation; either version 2 of the License, or
8 * (at your option) any later version.
9 *
10 * Functions based on pseudocode from "Introduction to Algorithms"
11 * The only modification is that we avoid to modify fields of the nil value.
12 *
13 */
14
15 #ifdef HAVE_CONFIG_H
16 # include "config.h"
17 #endif
18
19 #include <stdlib.h>
20 #include <assert.h>
21
22 #include "common.h"
23 #include "rbtree.h"
24
25 /* item used as a null value */
26 static struct rb_node rb_null = { NULL, NULL, NULL, RB_BLACK, NULL };
27
rb_left_rotate(struct rb_node ** root,struct rb_node * x)28 static void rb_left_rotate (struct rb_node **root, struct rb_node *x)
29 {
30 struct rb_node *y = x->right;
31
32 assert (y != &rb_null);
33
34 x->right = y->left;
35 if (y->left != &rb_null)
36 y->left->parent = x;
37 y->parent = x->parent;
38
39 if (x->parent == &rb_null)
40 *root = y;
41 else {
42 if (x == x->parent->left)
43 x->parent->left = y;
44 else
45 x->parent->right = y;
46 }
47
48 y->left = x;
49 x->parent = y;
50 }
51
rb_right_rotate(struct rb_node ** root,struct rb_node * x)52 static void rb_right_rotate (struct rb_node **root, struct rb_node *x)
53 {
54 struct rb_node *y = x->left;
55
56 assert (y != &rb_null);
57
58 x->left = y->right;
59 if (y->right != &rb_null)
60 y->right->parent = x;
61 y->parent = x->parent;
62
63 if (x->parent == &rb_null)
64 *root = y;
65 else {
66 if (x == x->parent->right)
67 x->parent->right = y;
68 else
69 x->parent->left = y;
70 }
71
72 y->right = x;
73 x->parent = y;
74 }
75
rb_insert_fixup(struct rb_node ** root,struct rb_node * z)76 static void rb_insert_fixup (struct rb_node **root, struct rb_node *z)
77 {
78 while (z->parent->color == RB_RED)
79 if (z->parent == z->parent->parent->left) {
80 struct rb_node *y = z->parent->parent->right;
81
82 if (y->color == RB_RED) {
83 z->parent->color = RB_BLACK;
84 y->color = RB_BLACK;
85 z->parent->parent->color = RB_RED;
86 z = z->parent->parent;
87 }
88 else {
89 if (z == z->parent->right) {
90 z = z->parent;
91 rb_left_rotate (root, z);
92 }
93
94 z->parent->color = RB_BLACK;
95 z->parent->parent->color = RB_RED;
96 rb_right_rotate (root, z->parent->parent);
97 }
98 }
99 else {
100 struct rb_node *y = z->parent->parent->left;
101
102 if (y->color == RB_RED) {
103 z->parent->color = RB_BLACK;
104 y->color = RB_BLACK;
105 z->parent->parent->color = RB_RED;
106 z = z->parent->parent;
107 }
108 else {
109 if (z == z->parent->left) {
110 z = z->parent;
111 rb_right_rotate (root, z);
112 }
113
114 z->parent->color = RB_BLACK;
115 z->parent->parent->color = RB_RED;
116 rb_left_rotate (root, z->parent->parent);
117 }
118 }
119
120 (*root)->color = RB_BLACK;
121 }
122
rb_delete_fixup(struct rb_node ** root,struct rb_node * x,struct rb_node * parent)123 static void rb_delete_fixup (struct rb_node **root, struct rb_node *x,
124 struct rb_node *parent)
125 {
126 struct rb_node *w;
127
128 while (x != *root && x->color == RB_BLACK) {
129 if (x == parent->left) {
130 w = parent->right;
131
132 if (w->color == RB_RED) {
133 w->color = RB_BLACK;
134 parent->color = RB_RED;
135 rb_left_rotate (root, parent);
136 w = parent->right;
137 }
138
139 if (w->left->color == RB_BLACK
140 && w->right->color == RB_BLACK) {
141 w->color = RB_RED;
142 x = parent;
143 parent = x->parent;
144 }
145 else {
146 if (w->right->color == RB_BLACK) {
147 w->left->color = RB_BLACK;
148 w->color = RB_RED;
149 rb_right_rotate (root, w);
150 w = parent->right;
151 }
152
153 w->color = parent->color;
154 parent->color = RB_BLACK;
155 w->right->color = RB_BLACK;
156 rb_left_rotate (root, parent);
157 x = *root;
158 }
159 }
160 else {
161 w = parent->left;
162
163 if (w->color == RB_RED) {
164 w->color = RB_BLACK;
165 parent->color = RB_RED;
166 rb_right_rotate (root, parent);
167 w = parent->left;
168 }
169
170 if (w->right->color == RB_BLACK
171 && w->left->color == RB_BLACK) {
172 w->color = RB_RED;
173 x = parent;
174 parent = x->parent;
175 }
176 else {
177 if (w->left->color == RB_BLACK) {
178 w->right->color = RB_BLACK;
179 w->color = RB_RED;
180 rb_left_rotate (root, w);
181 w = parent->left;
182 }
183
184 w->color = parent->color;
185 parent->color = RB_BLACK;
186 w->left->color = RB_BLACK;
187 rb_right_rotate (root, parent);
188 x = *root;
189 }
190 }
191
192 }
193
194 x->color = RB_BLACK;
195 }
196
rb_insert(struct rb_tree * t,void * data)197 void rb_insert (struct rb_tree *t, void *data)
198 {
199 struct rb_node *x, *y, *z;
200
201 assert (t != NULL);
202 assert (t->root != NULL);
203
204 x = t->root;
205 y = &rb_null;
206 z = (struct rb_node *)xmalloc (sizeof(struct rb_node));
207
208 z->data = data;
209
210 while (x != &rb_null) {
211 int cmp = t->cmp_func(z->data, x->data, t->adata);
212
213 y = x;
214 if (cmp < 0)
215 x = x->left;
216 else if (cmp > 0)
217 x = x->right;
218 else
219 abort ();
220 }
221
222 z->parent = y;
223 if (y == &rb_null)
224 t->root = z;
225 else {
226 if (t->cmp_func(z->data, y->data, t->adata) < 0)
227 y->left = z;
228 else
229 y->right = z;
230 }
231
232 z->left = &rb_null;
233 z->right = &rb_null;
234 z->color = RB_RED;
235
236 rb_insert_fixup (&t->root, z);
237 }
238
rb_search(struct rb_tree * t,const void * key)239 struct rb_node *rb_search (struct rb_tree *t, const void *key)
240 {
241 struct rb_node *x;
242
243 assert (t != NULL);
244 assert (t->root != NULL);
245 assert (key != NULL);
246
247 x = t->root;
248
249 while (x != &rb_null) {
250 int cmp = t->cmp_key_func (key, x->data, t->adata);
251
252 if (cmp < 0)
253 x = x->left;
254 else if (cmp > 0)
255 x = x->right;
256 else
257 break;
258 }
259
260 return x;
261 }
262
rb_is_null(const struct rb_node * n)263 int rb_is_null (const struct rb_node *n)
264 {
265 return n == &rb_null;
266 }
267
rb_min_internal(struct rb_node * n)268 static struct rb_node *rb_min_internal (struct rb_node *n)
269 {
270 if (n == &rb_null)
271 return &rb_null;
272
273 while (n->left != &rb_null)
274 n = n->left;
275
276 return n;
277 }
278
rb_min(struct rb_tree * t)279 struct rb_node *rb_min (struct rb_tree *t)
280 {
281 assert (t != NULL);
282 assert (t->root != NULL);
283
284 return rb_min_internal (t->root);
285 }
286
rb_next(struct rb_node * x)287 struct rb_node *rb_next (struct rb_node *x)
288 {
289 struct rb_node *y;
290
291 if (x->right != &rb_null)
292 return rb_min_internal (x->right);
293
294 y = x->parent;
295 while (y != &rb_null && x == y->right) {
296 x = y;
297 y = y->parent;
298 }
299
300 return y;
301 }
302
rb_delete(struct rb_tree * t,const void * key)303 void rb_delete (struct rb_tree *t, const void *key)
304 {
305 struct rb_node *z;
306
307 assert (t != NULL);
308 assert (t->root != NULL);
309 assert (key != NULL);
310
311 z = rb_search (t, key);
312
313 if (z != &rb_null) {
314 struct rb_node *x, *y, *parent;
315
316 if (z->left == &rb_null || z->right == &rb_null)
317 y = z;
318 else
319 y = rb_next (z);
320
321 if (y->left != &rb_null)
322 x = y->left;
323 else
324 x = y->right;
325
326 parent = y->parent;
327 if (x != &rb_null)
328 x->parent = parent;
329
330 if (y->parent == &rb_null)
331 t->root = x;
332 else {
333 if (y == y->parent->left)
334 y->parent->left = x;
335 else
336 y->parent->right = x;
337 }
338
339 if (y != z)
340 z->data = y->data;
341
342 if (y->color == RB_BLACK)
343 rb_delete_fixup (&t->root, x, parent);
344
345 free (y);
346 }
347 }
348
rb_init_tree(struct rb_tree * t,int (* cmp_func)(const void * a,const void * b,void * adata),int (* cmp_key_func)(const void * key,const void * data,void * adata),void * adata)349 void rb_init_tree (struct rb_tree *t,
350 int (*cmp_func)(const void *a, const void *b, void *adata),
351 int (*cmp_key_func)(const void *key, const void *data,
352 void *adata),
353 void *adata)
354 {
355 assert (t != NULL);
356 assert (cmp_func != NULL);
357 assert (cmp_key_func != NULL);
358
359 t->root = &rb_null;
360 t->cmp_func = cmp_func;
361 t->cmp_key_func = cmp_key_func;
362 t->adata = adata;
363 }
364
rb_destroy(struct rb_node * n)365 static void rb_destroy (struct rb_node *n)
366 {
367 if (n != &rb_null) {
368 rb_destroy (n->right);
369 rb_destroy (n->left);
370 free (n);
371 }
372 }
373
rb_clear(struct rb_tree * t)374 void rb_clear (struct rb_tree *t)
375 {
376 assert (t != NULL);
377 assert (t->root != NULL);
378
379 if (t->root != &rb_null) {
380 rb_destroy (t->root->left);
381 rb_destroy (t->root->right);
382 free (t->root);
383 t->root = &rb_null;
384 }
385 }
386