| rev |
line source |
|
nuclear@7
|
1 /*
|
|
nuclear@7
|
2 rbtree - simple balanced binary search tree (red-black tree) library.
|
|
nuclear@7
|
3 Copyright (C) 2011-2014 John Tsiombikas <nuclear@member.fsf.org>
|
|
nuclear@7
|
4
|
|
nuclear@7
|
5 rbtree is free software, feel free to use, modify, and redistribute it, under
|
|
nuclear@7
|
6 the terms of the 3-clause BSD license. See COPYING for details.
|
|
nuclear@7
|
7 */
|
|
nuclear@7
|
8 #include <stdio.h>
|
|
nuclear@7
|
9 #include <stdlib.h>
|
|
nuclear@7
|
10 #include <stdint.h>
|
|
nuclear@7
|
11 #include <string.h>
|
|
nuclear@7
|
12 #include "rbtree.h"
|
|
nuclear@7
|
13
|
|
nuclear@7
|
14 #define INT2PTR(x) ((void*)(intptr_t)(x))
|
|
nuclear@7
|
15 #define PTR2INT(x) ((int)(intptr_t)(x))
|
|
nuclear@7
|
16
|
|
nuclear@7
|
17 struct rbtree {
|
|
nuclear@7
|
18 struct rbnode *root;
|
|
nuclear@7
|
19
|
|
nuclear@7
|
20 rb_alloc_func_t alloc;
|
|
nuclear@7
|
21 rb_free_func_t free;
|
|
nuclear@7
|
22
|
|
nuclear@7
|
23 rb_cmp_func_t cmp;
|
|
nuclear@7
|
24 rb_del_func_t del;
|
|
nuclear@7
|
25 void *del_cls;
|
|
nuclear@7
|
26
|
|
nuclear@7
|
27 struct rbnode *rstack, *iter;
|
|
nuclear@7
|
28 };
|
|
nuclear@7
|
29
|
|
nuclear@7
|
30 static int cmpaddr(const void *ap, const void *bp);
|
|
nuclear@7
|
31 static int cmpint(const void *ap, const void *bp);
|
|
nuclear@7
|
32
|
|
nuclear@7
|
33 static int count_nodes(struct rbnode *node);
|
|
nuclear@7
|
34 static void del_tree(struct rbnode *node, void (*delfunc)(struct rbnode*, void*), void *cls);
|
|
nuclear@7
|
35 static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data);
|
|
nuclear@7
|
36 static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key);
|
|
nuclear@7
|
37 /*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key);*/
|
|
nuclear@7
|
38 static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls);
|
|
nuclear@7
|
39
|
|
nuclear@7
|
40 struct rbtree *rb_create(rb_cmp_func_t cmp_func)
|
|
nuclear@7
|
41 {
|
|
nuclear@7
|
42 struct rbtree *rb;
|
|
nuclear@7
|
43
|
|
nuclear@7
|
44 if(!(rb = malloc(sizeof *rb))) {
|
|
nuclear@7
|
45 return 0;
|
|
nuclear@7
|
46 }
|
|
nuclear@7
|
47 if(rb_init(rb, cmp_func) == -1) {
|
|
nuclear@7
|
48 free(rb);
|
|
nuclear@7
|
49 return 0;
|
|
nuclear@7
|
50 }
|
|
nuclear@7
|
51 return rb;
|
|
nuclear@7
|
52 }
|
|
nuclear@7
|
53
|
|
nuclear@7
|
54 void rb_free(struct rbtree *rb)
|
|
nuclear@7
|
55 {
|
|
nuclear@7
|
56 rb_destroy(rb);
|
|
nuclear@7
|
57 free(rb);
|
|
nuclear@7
|
58 }
|
|
nuclear@7
|
59
|
|
nuclear@7
|
60
|
|
nuclear@7
|
61 int rb_init(struct rbtree *rb, rb_cmp_func_t cmp_func)
|
|
nuclear@7
|
62 {
|
|
nuclear@7
|
63 memset(rb, 0, sizeof *rb);
|
|
nuclear@7
|
64
|
|
nuclear@7
|
65 if(cmp_func == RB_KEY_INT) {
|
|
nuclear@7
|
66 rb->cmp = cmpint;
|
|
nuclear@7
|
67 } else if(cmp_func == RB_KEY_STRING) {
|
|
nuclear@7
|
68 rb->cmp = (rb_cmp_func_t)strcmp;
|
|
nuclear@7
|
69 } else {
|
|
nuclear@7
|
70 rb->cmp = cmpaddr;
|
|
nuclear@7
|
71 }
|
|
nuclear@7
|
72
|
|
nuclear@7
|
73 rb->alloc = malloc;
|
|
nuclear@7
|
74 rb->free = free;
|
|
nuclear@7
|
75 return 0;
|
|
nuclear@7
|
76 }
|
|
nuclear@7
|
77
|
|
nuclear@7
|
78 void rb_destroy(struct rbtree *rb)
|
|
nuclear@7
|
79 {
|
|
nuclear@7
|
80 del_tree(rb->root, rb->del, rb->del_cls);
|
|
nuclear@7
|
81 }
|
|
nuclear@7
|
82
|
|
nuclear@7
|
83 void rb_set_allocator(struct rbtree *rb, rb_alloc_func_t alloc, rb_free_func_t free)
|
|
nuclear@7
|
84 {
|
|
nuclear@7
|
85 rb->alloc = alloc;
|
|
nuclear@7
|
86 rb->free = free;
|
|
nuclear@7
|
87 }
|
|
nuclear@7
|
88
|
|
nuclear@7
|
89
|
|
nuclear@7
|
90 void rb_set_compare_func(struct rbtree *rb, rb_cmp_func_t func)
|
|
nuclear@7
|
91 {
|
|
nuclear@7
|
92 rb->cmp = func;
|
|
nuclear@7
|
93 }
|
|
nuclear@7
|
94
|
|
nuclear@7
|
95 void rb_set_delete_func(struct rbtree *rb, rb_del_func_t func, void *cls)
|
|
nuclear@7
|
96 {
|
|
nuclear@7
|
97 rb->del = func;
|
|
nuclear@7
|
98 rb->del_cls = cls;
|
|
nuclear@7
|
99 }
|
|
nuclear@7
|
100
|
|
nuclear@7
|
101
|
|
nuclear@7
|
102 void rb_clear(struct rbtree *rb)
|
|
nuclear@7
|
103 {
|
|
nuclear@7
|
104 del_tree(rb->root, rb->del, rb->del_cls);
|
|
nuclear@7
|
105 rb->root = 0;
|
|
nuclear@7
|
106 }
|
|
nuclear@7
|
107
|
|
nuclear@7
|
108 int rb_copy(struct rbtree *dest, struct rbtree *src)
|
|
nuclear@7
|
109 {
|
|
nuclear@7
|
110 struct rbnode *node;
|
|
nuclear@7
|
111
|
|
nuclear@7
|
112 rb_clear(dest);
|
|
nuclear@7
|
113 rb_begin(src);
|
|
nuclear@7
|
114 while((node = rb_next(src))) {
|
|
nuclear@7
|
115 if(rb_insert(dest, node->key, node->data) == -1) {
|
|
nuclear@7
|
116 return -1;
|
|
nuclear@7
|
117 }
|
|
nuclear@7
|
118 }
|
|
nuclear@7
|
119 return 0;
|
|
nuclear@7
|
120 }
|
|
nuclear@7
|
121
|
|
nuclear@7
|
122 int rb_size(struct rbtree *rb)
|
|
nuclear@7
|
123 {
|
|
nuclear@7
|
124 return count_nodes(rb->root);
|
|
nuclear@7
|
125 }
|
|
nuclear@7
|
126
|
|
nuclear@7
|
127 int rb_insert(struct rbtree *rb, void *key, void *data)
|
|
nuclear@7
|
128 {
|
|
nuclear@7
|
129 rb->root = insert(rb, rb->root, key, data);
|
|
nuclear@7
|
130 rb->root->red = 0;
|
|
nuclear@7
|
131 return 0;
|
|
nuclear@7
|
132 }
|
|
nuclear@7
|
133
|
|
nuclear@7
|
134 int rb_inserti(struct rbtree *rb, int key, void *data)
|
|
nuclear@7
|
135 {
|
|
nuclear@7
|
136 rb->root = insert(rb, rb->root, INT2PTR(key), data);
|
|
nuclear@7
|
137 rb->root->red = 0;
|
|
nuclear@7
|
138 return 0;
|
|
nuclear@7
|
139 }
|
|
nuclear@7
|
140
|
|
nuclear@7
|
141
|
|
nuclear@7
|
142 int rb_delete(struct rbtree *rb, void *key)
|
|
nuclear@7
|
143 {
|
|
nuclear@7
|
144 rb->root = delete(rb, rb->root, key);
|
|
nuclear@7
|
145 rb->root->red = 0;
|
|
nuclear@7
|
146 return 0;
|
|
nuclear@7
|
147 }
|
|
nuclear@7
|
148
|
|
nuclear@7
|
149 int rb_deletei(struct rbtree *rb, int key)
|
|
nuclear@7
|
150 {
|
|
nuclear@7
|
151 rb->root = delete(rb, rb->root, INT2PTR(key));
|
|
nuclear@7
|
152 rb->root->red = 0;
|
|
nuclear@7
|
153 return 0;
|
|
nuclear@7
|
154 }
|
|
nuclear@7
|
155
|
|
nuclear@7
|
156
|
|
nuclear@7
|
157 void *rb_find(struct rbtree *rb, void *key)
|
|
nuclear@7
|
158 {
|
|
nuclear@7
|
159 struct rbnode *node = rb->root;
|
|
nuclear@7
|
160
|
|
nuclear@7
|
161 while(node) {
|
|
nuclear@7
|
162 int cmp = rb->cmp(key, node->key);
|
|
nuclear@7
|
163 if(cmp == 0) {
|
|
nuclear@7
|
164 return node->data;
|
|
nuclear@7
|
165 }
|
|
nuclear@7
|
166 node = cmp < 0 ? node->left : node->right;
|
|
nuclear@7
|
167 }
|
|
nuclear@7
|
168 return 0;
|
|
nuclear@7
|
169 }
|
|
nuclear@7
|
170
|
|
nuclear@7
|
171 void *rb_findi(struct rbtree *rb, int key)
|
|
nuclear@7
|
172 {
|
|
nuclear@7
|
173 return rb_find(rb, INT2PTR(key));
|
|
nuclear@7
|
174 }
|
|
nuclear@7
|
175
|
|
nuclear@7
|
176
|
|
nuclear@7
|
177 void rb_foreach(struct rbtree *rb, void (*func)(struct rbnode*, void*), void *cls)
|
|
nuclear@7
|
178 {
|
|
nuclear@7
|
179 traverse(rb->root, func, cls);
|
|
nuclear@7
|
180 }
|
|
nuclear@7
|
181
|
|
nuclear@7
|
182
|
|
nuclear@7
|
183 struct rbnode *rb_root(struct rbtree *rb)
|
|
nuclear@7
|
184 {
|
|
nuclear@7
|
185 return rb->root;
|
|
nuclear@7
|
186 }
|
|
nuclear@7
|
187
|
|
nuclear@7
|
188 void rb_begin(struct rbtree *rb)
|
|
nuclear@7
|
189 {
|
|
nuclear@7
|
190 rb->rstack = 0;
|
|
nuclear@7
|
191 rb->iter = rb->root;
|
|
nuclear@7
|
192 }
|
|
nuclear@7
|
193
|
|
nuclear@7
|
194 #define push(sp, x) ((x)->next = (sp), (sp) = (x))
|
|
nuclear@7
|
195 #define pop(sp) ((sp) = (sp)->next)
|
|
nuclear@7
|
196 #define top(sp) (sp)
|
|
nuclear@7
|
197
|
|
nuclear@7
|
198 struct rbnode *rb_next(struct rbtree *rb)
|
|
nuclear@7
|
199 {
|
|
nuclear@7
|
200 struct rbnode *res = 0;
|
|
nuclear@7
|
201
|
|
nuclear@7
|
202 while(rb->rstack || rb->iter) {
|
|
nuclear@7
|
203 if(rb->iter) {
|
|
nuclear@7
|
204 push(rb->rstack, rb->iter);
|
|
nuclear@7
|
205 rb->iter = rb->iter->left;
|
|
nuclear@7
|
206 } else {
|
|
nuclear@7
|
207 rb->iter = top(rb->rstack);
|
|
nuclear@7
|
208 pop(rb->rstack);
|
|
nuclear@7
|
209 res = rb->iter;
|
|
nuclear@7
|
210 rb->iter = rb->iter->right;
|
|
nuclear@7
|
211 break;
|
|
nuclear@7
|
212 }
|
|
nuclear@7
|
213 }
|
|
nuclear@7
|
214 return res;
|
|
nuclear@7
|
215 }
|
|
nuclear@7
|
216
|
|
nuclear@7
|
217 void *rb_node_key(struct rbnode *node)
|
|
nuclear@7
|
218 {
|
|
nuclear@7
|
219 return node ? node->key : 0;
|
|
nuclear@7
|
220 }
|
|
nuclear@7
|
221
|
|
nuclear@7
|
222 int rb_node_keyi(struct rbnode *node)
|
|
nuclear@7
|
223 {
|
|
nuclear@7
|
224 return node ? PTR2INT(node->key) : 0;
|
|
nuclear@7
|
225 }
|
|
nuclear@7
|
226
|
|
nuclear@7
|
227 void *rb_node_data(struct rbnode *node)
|
|
nuclear@7
|
228 {
|
|
nuclear@7
|
229 return node ? node->data : 0;
|
|
nuclear@7
|
230 }
|
|
nuclear@7
|
231
|
|
nuclear@7
|
232 static int cmpaddr(const void *ap, const void *bp)
|
|
nuclear@7
|
233 {
|
|
nuclear@7
|
234 return ap < bp ? -1 : (ap > bp ? 1 : 0);
|
|
nuclear@7
|
235 }
|
|
nuclear@7
|
236
|
|
nuclear@7
|
237 static int cmpint(const void *ap, const void *bp)
|
|
nuclear@7
|
238 {
|
|
nuclear@7
|
239 return PTR2INT(ap) - PTR2INT(bp);
|
|
nuclear@7
|
240 }
|
|
nuclear@7
|
241
|
|
nuclear@7
|
242
|
|
nuclear@7
|
243 /* ---- left-leaning 2-3 red-black implementation ---- */
|
|
nuclear@7
|
244
|
|
nuclear@7
|
245 /* helper prototypes */
|
|
nuclear@7
|
246 static int is_red(struct rbnode *tree);
|
|
nuclear@7
|
247 static void color_flip(struct rbnode *tree);
|
|
nuclear@7
|
248 static struct rbnode *rot_left(struct rbnode *a);
|
|
nuclear@7
|
249 static struct rbnode *rot_right(struct rbnode *a);
|
|
nuclear@7
|
250 static struct rbnode *find_min(struct rbnode *tree);
|
|
nuclear@7
|
251 static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree);
|
|
nuclear@7
|
252 /*static struct rbnode *move_red_right(struct rbnode *tree);*/
|
|
nuclear@7
|
253 static struct rbnode *move_red_left(struct rbnode *tree);
|
|
nuclear@7
|
254 static struct rbnode *fix_up(struct rbnode *tree);
|
|
nuclear@7
|
255
|
|
nuclear@7
|
256 static int count_nodes(struct rbnode *node)
|
|
nuclear@7
|
257 {
|
|
nuclear@7
|
258 if(!node)
|
|
nuclear@7
|
259 return 0;
|
|
nuclear@7
|
260
|
|
nuclear@7
|
261 return 1 + count_nodes(node->left) + count_nodes(node->right);
|
|
nuclear@7
|
262 }
|
|
nuclear@7
|
263
|
|
nuclear@7
|
264 static void del_tree(struct rbnode *node, rb_del_func_t delfunc, void *cls)
|
|
nuclear@7
|
265 {
|
|
nuclear@7
|
266 if(!node)
|
|
nuclear@7
|
267 return;
|
|
nuclear@7
|
268
|
|
nuclear@7
|
269 del_tree(node->left, delfunc, cls);
|
|
nuclear@7
|
270 del_tree(node->right, delfunc, cls);
|
|
nuclear@7
|
271
|
|
nuclear@7
|
272 if(delfunc) {
|
|
nuclear@7
|
273 delfunc(node, cls);
|
|
nuclear@7
|
274 }
|
|
nuclear@7
|
275 free(node);
|
|
nuclear@7
|
276 }
|
|
nuclear@7
|
277
|
|
nuclear@7
|
278 static struct rbnode *insert(struct rbtree *rb, struct rbnode *tree, void *key, void *data)
|
|
nuclear@7
|
279 {
|
|
nuclear@7
|
280 int cmp;
|
|
nuclear@7
|
281
|
|
nuclear@7
|
282 if(!tree) {
|
|
nuclear@7
|
283 struct rbnode *node = rb->alloc(sizeof *node);
|
|
nuclear@7
|
284 node->red = 1;
|
|
nuclear@7
|
285 node->key = key;
|
|
nuclear@7
|
286 node->data = data;
|
|
nuclear@7
|
287 node->left = node->right = 0;
|
|
nuclear@7
|
288 return node;
|
|
nuclear@7
|
289 }
|
|
nuclear@7
|
290
|
|
nuclear@7
|
291 cmp = rb->cmp(key, tree->key);
|
|
nuclear@7
|
292
|
|
nuclear@7
|
293 if(cmp < 0) {
|
|
nuclear@7
|
294 tree->left = insert(rb, tree->left, key, data);
|
|
nuclear@7
|
295 } else if(cmp > 0) {
|
|
nuclear@7
|
296 tree->right = insert(rb, tree->right, key, data);
|
|
nuclear@7
|
297 } else {
|
|
nuclear@7
|
298 tree->data = data;
|
|
nuclear@7
|
299 }
|
|
nuclear@7
|
300
|
|
nuclear@7
|
301 /* fix right-leaning reds */
|
|
nuclear@7
|
302 if(is_red(tree->right)) {
|
|
nuclear@7
|
303 tree = rot_left(tree);
|
|
nuclear@7
|
304 }
|
|
nuclear@7
|
305 /* fix two reds in a row */
|
|
nuclear@7
|
306 if(is_red(tree->left) && is_red(tree->left->left)) {
|
|
nuclear@7
|
307 tree = rot_right(tree);
|
|
nuclear@7
|
308 }
|
|
nuclear@7
|
309
|
|
nuclear@7
|
310 /* if 4-node, split it by color inversion */
|
|
nuclear@7
|
311 if(is_red(tree->left) && is_red(tree->right)) {
|
|
nuclear@7
|
312 color_flip(tree);
|
|
nuclear@7
|
313 }
|
|
nuclear@7
|
314
|
|
nuclear@7
|
315 return tree;
|
|
nuclear@7
|
316 }
|
|
nuclear@7
|
317
|
|
nuclear@7
|
318 static struct rbnode *delete(struct rbtree *rb, struct rbnode *tree, void *key)
|
|
nuclear@7
|
319 {
|
|
nuclear@7
|
320 int cmp;
|
|
nuclear@7
|
321
|
|
nuclear@7
|
322 if(!tree) {
|
|
nuclear@7
|
323 return 0;
|
|
nuclear@7
|
324 }
|
|
nuclear@7
|
325
|
|
nuclear@7
|
326 cmp = rb->cmp(key, tree->key);
|
|
nuclear@7
|
327
|
|
nuclear@7
|
328 if(cmp < 0) {
|
|
nuclear@7
|
329 if(!is_red(tree->left) && !is_red(tree->left->left)) {
|
|
nuclear@7
|
330 tree = move_red_left(tree);
|
|
nuclear@7
|
331 }
|
|
nuclear@7
|
332 tree->left = delete(rb, tree->left, key);
|
|
nuclear@7
|
333 } else {
|
|
nuclear@7
|
334 /* need reds on the right */
|
|
nuclear@7
|
335 if(is_red(tree->left)) {
|
|
nuclear@7
|
336 tree = rot_right(tree);
|
|
nuclear@7
|
337 }
|
|
nuclear@7
|
338
|
|
nuclear@7
|
339 /* found it at the bottom (XXX what certifies left is null?) */
|
|
nuclear@7
|
340 if(cmp == 0 && !tree->right) {
|
|
nuclear@7
|
341 if(rb->del) {
|
|
nuclear@7
|
342 rb->del(tree, rb->del_cls);
|
|
nuclear@7
|
343 }
|
|
nuclear@7
|
344 rb->free(tree);
|
|
nuclear@7
|
345 return 0;
|
|
nuclear@7
|
346 }
|
|
nuclear@7
|
347
|
|
nuclear@7
|
348 if(!is_red(tree->right) && !is_red(tree->right->left)) {
|
|
nuclear@7
|
349 tree = move_red_left(tree);
|
|
nuclear@7
|
350 }
|
|
nuclear@7
|
351
|
|
nuclear@7
|
352 if(key == tree->key) {
|
|
nuclear@7
|
353 struct rbnode *rmin = find_min(tree->right);
|
|
nuclear@7
|
354 tree->key = rmin->key;
|
|
nuclear@7
|
355 tree->data = rmin->data;
|
|
nuclear@7
|
356 tree->right = del_min(rb, tree->right);
|
|
nuclear@7
|
357 } else {
|
|
nuclear@7
|
358 tree->right = delete(rb, tree->right, key);
|
|
nuclear@7
|
359 }
|
|
nuclear@7
|
360 }
|
|
nuclear@7
|
361
|
|
nuclear@7
|
362 return fix_up(tree);
|
|
nuclear@7
|
363 }
|
|
nuclear@7
|
364
|
|
nuclear@7
|
365 /*static struct rbnode *find(struct rbtree *rb, struct rbnode *node, void *key)
|
|
nuclear@7
|
366 {
|
|
nuclear@7
|
367 int cmp;
|
|
nuclear@7
|
368
|
|
nuclear@7
|
369 if(!node)
|
|
nuclear@7
|
370 return 0;
|
|
nuclear@7
|
371
|
|
nuclear@7
|
372 if((cmp = rb->cmp(key, node->key)) == 0) {
|
|
nuclear@7
|
373 return node;
|
|
nuclear@7
|
374 }
|
|
nuclear@7
|
375 return find(rb, cmp < 0 ? node->left : node->right, key);
|
|
nuclear@7
|
376 }*/
|
|
nuclear@7
|
377
|
|
nuclear@7
|
378 static void traverse(struct rbnode *node, void (*func)(struct rbnode*, void*), void *cls)
|
|
nuclear@7
|
379 {
|
|
nuclear@7
|
380 if(!node)
|
|
nuclear@7
|
381 return;
|
|
nuclear@7
|
382
|
|
nuclear@7
|
383 traverse(node->left, func, cls);
|
|
nuclear@7
|
384 func(node, cls);
|
|
nuclear@7
|
385 traverse(node->right, func, cls);
|
|
nuclear@7
|
386 }
|
|
nuclear@7
|
387
|
|
nuclear@7
|
388 /* helpers */
|
|
nuclear@7
|
389
|
|
nuclear@7
|
390 static int is_red(struct rbnode *tree)
|
|
nuclear@7
|
391 {
|
|
nuclear@7
|
392 return tree && tree->red;
|
|
nuclear@7
|
393 }
|
|
nuclear@7
|
394
|
|
nuclear@7
|
395 static void color_flip(struct rbnode *tree)
|
|
nuclear@7
|
396 {
|
|
nuclear@7
|
397 tree->red = !tree->red;
|
|
nuclear@7
|
398 tree->left->red = !tree->left->red;
|
|
nuclear@7
|
399 tree->right->red = !tree->right->red;
|
|
nuclear@7
|
400 }
|
|
nuclear@7
|
401
|
|
nuclear@7
|
402 static struct rbnode *rot_left(struct rbnode *a)
|
|
nuclear@7
|
403 {
|
|
nuclear@7
|
404 struct rbnode *b = a->right;
|
|
nuclear@7
|
405 a->right = b->left;
|
|
nuclear@7
|
406 b->left = a;
|
|
nuclear@7
|
407 b->red = a->red;
|
|
nuclear@7
|
408 a->red = 1;
|
|
nuclear@7
|
409 return b;
|
|
nuclear@7
|
410 }
|
|
nuclear@7
|
411
|
|
nuclear@7
|
412 static struct rbnode *rot_right(struct rbnode *a)
|
|
nuclear@7
|
413 {
|
|
nuclear@7
|
414 struct rbnode *b = a->left;
|
|
nuclear@7
|
415 a->left = b->right;
|
|
nuclear@7
|
416 b->right = a;
|
|
nuclear@7
|
417 b->red = a->red;
|
|
nuclear@7
|
418 a->red = 1;
|
|
nuclear@7
|
419 return b;
|
|
nuclear@7
|
420 }
|
|
nuclear@7
|
421
|
|
nuclear@7
|
422 static struct rbnode *find_min(struct rbnode *tree)
|
|
nuclear@7
|
423 {
|
|
nuclear@7
|
424 struct rbnode *node = tree;
|
|
nuclear@7
|
425
|
|
nuclear@7
|
426 if(!tree)
|
|
nuclear@7
|
427 return 0;
|
|
nuclear@7
|
428
|
|
nuclear@7
|
429 while(node->left) {
|
|
nuclear@7
|
430 node = node->left;
|
|
nuclear@7
|
431 }
|
|
nuclear@7
|
432 return node;
|
|
nuclear@7
|
433 }
|
|
nuclear@7
|
434
|
|
nuclear@7
|
435 static struct rbnode *del_min(struct rbtree *rb, struct rbnode *tree)
|
|
nuclear@7
|
436 {
|
|
nuclear@7
|
437 if(!tree->left) {
|
|
nuclear@7
|
438 if(rb->del) {
|
|
nuclear@7
|
439 rb->del(tree->left, rb->del_cls);
|
|
nuclear@7
|
440 }
|
|
nuclear@7
|
441 rb->free(tree->left);
|
|
nuclear@7
|
442 return 0;
|
|
nuclear@7
|
443 }
|
|
nuclear@7
|
444
|
|
nuclear@7
|
445 /* make sure we've got red (3/4-nodes) at the left side so we can delete at the bottom */
|
|
nuclear@7
|
446 if(!is_red(tree->left) && !is_red(tree->left->left)) {
|
|
nuclear@7
|
447 tree = move_red_left(tree);
|
|
nuclear@7
|
448 }
|
|
nuclear@7
|
449 tree->left = del_min(rb, tree->left);
|
|
nuclear@7
|
450
|
|
nuclear@7
|
451 /* fix right-reds, red-reds, and split 4-nodes on the way up */
|
|
nuclear@7
|
452 return fix_up(tree);
|
|
nuclear@7
|
453 }
|
|
nuclear@7
|
454
|
|
nuclear@7
|
455 #if 0
|
|
nuclear@7
|
456 /* push a red link on this node to the right */
|
|
nuclear@7
|
457 static struct rbnode *move_red_right(struct rbnode *tree)
|
|
nuclear@7
|
458 {
|
|
nuclear@7
|
459 /* flipping it makes both children go red, so we have a red to the right */
|
|
nuclear@7
|
460 color_flip(tree);
|
|
nuclear@7
|
461
|
|
nuclear@7
|
462 /* if after the flip we've got a red-red situation to the left, fix it */
|
|
nuclear@7
|
463 if(is_red(tree->left->left)) {
|
|
nuclear@7
|
464 tree = rot_right(tree);
|
|
nuclear@7
|
465 color_flip(tree);
|
|
nuclear@7
|
466 }
|
|
nuclear@7
|
467 return tree;
|
|
nuclear@7
|
468 }
|
|
nuclear@7
|
469 #endif
|
|
nuclear@7
|
470
|
|
nuclear@7
|
471 /* push a red link on this node to the left */
|
|
nuclear@7
|
472 static struct rbnode *move_red_left(struct rbnode *tree)
|
|
nuclear@7
|
473 {
|
|
nuclear@7
|
474 /* flipping it makes both children go red, so we have a red to the left */
|
|
nuclear@7
|
475 color_flip(tree);
|
|
nuclear@7
|
476
|
|
nuclear@7
|
477 /* if after the flip we've got a red-red on the right-left, fix it */
|
|
nuclear@7
|
478 if(is_red(tree->right->left)) {
|
|
nuclear@7
|
479 tree->right = rot_right(tree->right);
|
|
nuclear@7
|
480 tree = rot_left(tree);
|
|
nuclear@7
|
481 color_flip(tree);
|
|
nuclear@7
|
482 }
|
|
nuclear@7
|
483 return tree;
|
|
nuclear@7
|
484 }
|
|
nuclear@7
|
485
|
|
nuclear@7
|
486 static struct rbnode *fix_up(struct rbnode *tree)
|
|
nuclear@7
|
487 {
|
|
nuclear@7
|
488 /* fix right-leaning */
|
|
nuclear@7
|
489 if(is_red(tree->right)) {
|
|
nuclear@7
|
490 tree = rot_left(tree);
|
|
nuclear@7
|
491 }
|
|
nuclear@7
|
492 /* change invalid red-red pairs into a proper 4-node */
|
|
nuclear@7
|
493 if(is_red(tree->left) && is_red(tree->left->left)) {
|
|
nuclear@7
|
494 tree = rot_right(tree);
|
|
nuclear@7
|
495 }
|
|
nuclear@7
|
496 /* split 4-nodes */
|
|
nuclear@7
|
497 if(is_red(tree->left) && is_red(tree->right)) {
|
|
nuclear@7
|
498 color_flip(tree);
|
|
nuclear@7
|
499 }
|
|
nuclear@7
|
500 return tree;
|
|
nuclear@7
|
501 }
|
