diff options
Diffstat (limited to '')
-rw-r--r-- | libraries/eina/src/lib/eina_rbtree.c | 518 |
1 files changed, 518 insertions, 0 deletions
diff --git a/libraries/eina/src/lib/eina_rbtree.c b/libraries/eina/src/lib/eina_rbtree.c new file mode 100644 index 0000000..c0c9f9e --- /dev/null +++ b/libraries/eina/src/lib/eina_rbtree.c | |||
@@ -0,0 +1,518 @@ | |||
1 | /* EINA - EFL data type library | ||
2 | * Copyright (C) 2008 Cedric Bail | ||
3 | * | ||
4 | * This library is free software; you can redistribute it and/or | ||
5 | * modify it under the terms of the GNU Lesser General Public | ||
6 | * License as published by the Free Software Foundation; either | ||
7 | * version 2.1 of the License, or (at your option) any later version. | ||
8 | * | ||
9 | * This library is distributed in the hope that it will be useful, | ||
10 | * but WITHOUT ANY WARRANTY; without even the implied warranty of | ||
11 | * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
12 | * Lesser General Public License for more details. | ||
13 | * | ||
14 | * You should have received a copy of the GNU Lesser General Public | ||
15 | * License along with this library; | ||
16 | * if not, see <http://www.gnu.org/licenses/>. | ||
17 | */ | ||
18 | |||
19 | #ifdef HAVE_CONFIG_H | ||
20 | # include "config.h" | ||
21 | #endif | ||
22 | |||
23 | #include <stdlib.h> | ||
24 | #include <stdio.h> | ||
25 | #include <string.h> | ||
26 | |||
27 | #include "eina_config.h" | ||
28 | #include "eina_private.h" | ||
29 | #include "eina_array.h" | ||
30 | |||
31 | /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ | ||
32 | #include "eina_safety_checks.h" | ||
33 | #include "eina_rbtree.h" | ||
34 | |||
35 | /*============================================================================* | ||
36 | * Local * | ||
37 | *============================================================================*/ | ||
38 | |||
39 | #define EINA_RBTREE_ITERATOR_PREFIX_MASK 0x1 | ||
40 | #define EINA_RBTREE_ITERATOR_INFIX_MASK 0x2 | ||
41 | #define EINA_RBTREE_ITERATOR_POSTFIX_MASK 0x4 | ||
42 | |||
43 | typedef struct _Eina_Iterator_Rbtree Eina_Iterator_Rbtree; | ||
44 | typedef struct _Eina_Iterator_Rbtree_List Eina_Iterator_Rbtree_List; | ||
45 | |||
46 | struct _Eina_Iterator_Rbtree | ||
47 | { | ||
48 | Eina_Iterator iterator; | ||
49 | |||
50 | Eina_Array *stack; | ||
51 | |||
52 | unsigned char mask; | ||
53 | }; | ||
54 | |||
55 | struct _Eina_Iterator_Rbtree_List | ||
56 | { | ||
57 | Eina_Rbtree *tree; | ||
58 | |||
59 | Eina_Rbtree_Direction dir : 1; | ||
60 | Eina_Bool up : 1; | ||
61 | }; | ||
62 | |||
63 | static Eina_Iterator_Rbtree_List * | ||
64 | _eina_rbtree_iterator_list_new(const Eina_Rbtree *tree) | ||
65 | { | ||
66 | Eina_Iterator_Rbtree_List *new; | ||
67 | |||
68 | eina_error_set(0); | ||
69 | new = malloc(sizeof (Eina_Iterator_Rbtree_List)); | ||
70 | if (!new) | ||
71 | { | ||
72 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
73 | return NULL; | ||
74 | } | ||
75 | |||
76 | new->tree = (Eina_Rbtree *)tree; | ||
77 | new->dir = EINA_RBTREE_RIGHT; | ||
78 | new->up = EINA_FALSE; | ||
79 | |||
80 | return new; | ||
81 | } | ||
82 | |||
83 | static Eina_Rbtree * | ||
84 | _eina_rbtree_iterator_get_content(Eina_Iterator_Rbtree *it) | ||
85 | { | ||
86 | if (eina_array_count_get(it->stack) <= 0) | ||
87 | return NULL; | ||
88 | |||
89 | return eina_array_data_get(it->stack, 0); | ||
90 | } | ||
91 | |||
92 | static void | ||
93 | _eina_rbtree_iterator_free(Eina_Iterator_Rbtree *it) | ||
94 | { | ||
95 | Eina_Iterator_Rbtree_List *item; | ||
96 | Eina_Array_Iterator et; | ||
97 | unsigned int i; | ||
98 | |||
99 | EINA_ARRAY_ITER_NEXT(it->stack, i, item, et) | ||
100 | free(item); | ||
101 | |||
102 | eina_array_free(it->stack); | ||
103 | free(it); | ||
104 | } | ||
105 | |||
106 | static Eina_Bool | ||
107 | _eina_rbtree_iterator_next(Eina_Iterator_Rbtree *it, void **data) | ||
108 | { | ||
109 | Eina_Iterator_Rbtree_List *last; | ||
110 | Eina_Iterator_Rbtree_List *new; | ||
111 | Eina_Rbtree *tree; | ||
112 | |||
113 | if (eina_array_count_get(it->stack) <= 0) | ||
114 | return EINA_FALSE; | ||
115 | |||
116 | last = eina_array_data_get(it->stack, eina_array_count_get(it->stack) - 1); | ||
117 | tree = last->tree; | ||
118 | |||
119 | if (!last->tree || last->up == EINA_TRUE) | ||
120 | { | ||
121 | last = eina_array_pop(it->stack); | ||
122 | while (last->dir == EINA_RBTREE_LEFT | ||
123 | || !last->tree) | ||
124 | { | ||
125 | if (tree) | ||
126 | if ((it->mask & EINA_RBTREE_ITERATOR_POSTFIX_MASK) == | ||
127 | EINA_RBTREE_ITERATOR_POSTFIX_MASK) | ||
128 | { | ||
129 | free(last); | ||
130 | |||
131 | if (eina_array_count_get(it->stack) > 0) | ||
132 | { | ||
133 | last = eina_array_data_get(it->stack, | ||
134 | eina_array_count_get( | ||
135 | it-> | ||
136 | stack) | ||
137 | - 1); | ||
138 | last->up = EINA_TRUE; | ||
139 | } | ||
140 | |||
141 | goto onfix; | ||
142 | } | ||
143 | |||
144 | free(last); | ||
145 | |||
146 | last = eina_array_pop(it->stack); | ||
147 | if (!last) | ||
148 | return EINA_FALSE; | ||
149 | |||
150 | tree = last->tree; | ||
151 | } | ||
152 | |||
153 | last->dir = EINA_RBTREE_LEFT; | ||
154 | last->up = EINA_FALSE; | ||
155 | |||
156 | eina_array_push(it->stack, last); | ||
157 | |||
158 | if ((it->mask & EINA_RBTREE_ITERATOR_INFIX_MASK) == | ||
159 | EINA_RBTREE_ITERATOR_INFIX_MASK) | ||
160 | goto onfix; | ||
161 | } | ||
162 | |||
163 | new = _eina_rbtree_iterator_list_new(last->tree->son[last->dir]); | ||
164 | if (!new) | ||
165 | return EINA_FALSE; | ||
166 | |||
167 | eina_array_push(it->stack, new); | ||
168 | |||
169 | if (last->dir == EINA_RBTREE_RIGHT) | ||
170 | if ((it->mask & EINA_RBTREE_ITERATOR_PREFIX_MASK) == | ||
171 | EINA_RBTREE_ITERATOR_PREFIX_MASK) | ||
172 | goto onfix; | ||
173 | |||
174 | return _eina_rbtree_iterator_next(it, data); | ||
175 | |||
176 | onfix: | ||
177 | *data = tree; | ||
178 | return EINA_TRUE; | ||
179 | } | ||
180 | |||
181 | static Eina_Iterator * | ||
182 | _eina_rbtree_iterator_build(const Eina_Rbtree *root, unsigned char mask) | ||
183 | { | ||
184 | Eina_Iterator_Rbtree_List *first; | ||
185 | Eina_Iterator_Rbtree *it; | ||
186 | |||
187 | eina_error_set(0); | ||
188 | it = calloc(1, sizeof (Eina_Iterator_Rbtree)); | ||
189 | if (!it) | ||
190 | { | ||
191 | eina_error_set(EINA_ERROR_OUT_OF_MEMORY); | ||
192 | return NULL; | ||
193 | } | ||
194 | |||
195 | it->stack = eina_array_new(8); | ||
196 | if (!it->stack) | ||
197 | goto on_error2; | ||
198 | |||
199 | first = _eina_rbtree_iterator_list_new(root); | ||
200 | if (!first) | ||
201 | goto on_error; | ||
202 | |||
203 | eina_array_push(it->stack, first); | ||
204 | |||
205 | it->mask = mask; | ||
206 | |||
207 | it->iterator.version = EINA_ITERATOR_VERSION; | ||
208 | it->iterator.next = FUNC_ITERATOR_NEXT(_eina_rbtree_iterator_next); | ||
209 | it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( | ||
210 | _eina_rbtree_iterator_get_content); | ||
211 | it->iterator.free = FUNC_ITERATOR_FREE(_eina_rbtree_iterator_free); | ||
212 | |||
213 | EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); | ||
214 | |||
215 | return &it->iterator; | ||
216 | |||
217 | on_error: | ||
218 | eina_array_free(it->stack); | ||
219 | on_error2: | ||
220 | free(it); | ||
221 | |||
222 | return NULL; | ||
223 | } | ||
224 | |||
225 | static void | ||
226 | _eina_rbtree_node_init(Eina_Rbtree *node) | ||
227 | { | ||
228 | if (!node) | ||
229 | return; | ||
230 | |||
231 | node->son[0] = NULL; | ||
232 | node->son[1] = NULL; | ||
233 | |||
234 | node->color = EINA_RBTREE_RED; | ||
235 | } | ||
236 | |||
237 | static inline Eina_Bool | ||
238 | _eina_rbtree_is_red(Eina_Rbtree *node) | ||
239 | { | ||
240 | return !!node && node->color == EINA_RBTREE_RED; | ||
241 | } | ||
242 | |||
243 | static inline Eina_Rbtree * | ||
244 | _eina_rbtree_inline_single_rotation(Eina_Rbtree *node, | ||
245 | Eina_Rbtree_Direction dir) | ||
246 | { | ||
247 | Eina_Rbtree *save = node->son[!dir]; | ||
248 | |||
249 | node->son[!dir] = save->son[dir]; | ||
250 | save->son[dir] = node; | ||
251 | |||
252 | node->color = EINA_RBTREE_RED; | ||
253 | save->color = EINA_RBTREE_BLACK; | ||
254 | |||
255 | return save; | ||
256 | } | ||
257 | |||
258 | static inline Eina_Rbtree * | ||
259 | _eina_rbtree_inline_double_rotation(Eina_Rbtree *node, | ||
260 | Eina_Rbtree_Direction dir) | ||
261 | { | ||
262 | node->son[!dir] = _eina_rbtree_inline_single_rotation(node->son[!dir], !dir); | ||
263 | return _eina_rbtree_inline_single_rotation(node, dir); | ||
264 | } | ||
265 | |||
266 | /*============================================================================* | ||
267 | * Global * | ||
268 | *============================================================================*/ | ||
269 | |||
270 | /*============================================================================* | ||
271 | * API * | ||
272 | *============================================================================*/ | ||
273 | |||
274 | EAPI Eina_Rbtree * | ||
275 | eina_rbtree_inline_insert(Eina_Rbtree *root, | ||
276 | Eina_Rbtree *node, | ||
277 | Eina_Rbtree_Cmp_Node_Cb cmp, | ||
278 | const void *data) | ||
279 | { | ||
280 | Eina_Rbtree head; | ||
281 | Eina_Rbtree *g, *t; /* Grandparent & parent */ | ||
282 | Eina_Rbtree *p, *q; /* Iterator & parent */ | ||
283 | /* WARNING: | ||
284 | Compiler is not able to understand the underlying algorithm and don't know that | ||
285 | first top node is always black, so it will never use last before running the loop | ||
286 | one time. | ||
287 | */ | ||
288 | Eina_Rbtree_Direction dir, last; | ||
289 | |||
290 | EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); | ||
291 | EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); | ||
292 | |||
293 | if (!node) | ||
294 | return root; | ||
295 | |||
296 | _eina_rbtree_node_init(node); | ||
297 | |||
298 | if (!root) | ||
299 | { | ||
300 | root = node; | ||
301 | goto end_add; | ||
302 | } | ||
303 | |||
304 | memset(&head, 0, sizeof (Eina_Rbtree)); | ||
305 | last = dir = EINA_RBTREE_LEFT; | ||
306 | |||
307 | /* Set up helpers */ | ||
308 | t = &head; | ||
309 | g = p = NULL; | ||
310 | q = t->son[1] = root; | ||
311 | |||
312 | /* Search down the tree */ | ||
313 | for (;; ) | ||
314 | { | ||
315 | if (!q) | ||
316 | /* Insert new node at the bottom */ | ||
317 | p->son[dir] = q = node; | ||
318 | else if (_eina_rbtree_is_red(q->son[0]) | ||
319 | && _eina_rbtree_is_red(q->son[1])) | ||
320 | { | ||
321 | /* Color flip */ | ||
322 | q->color = EINA_RBTREE_RED; | ||
323 | q->son[0]->color = EINA_RBTREE_BLACK; | ||
324 | q->son[1]->color = EINA_RBTREE_BLACK; | ||
325 | } | ||
326 | |||
327 | /* Fix red violation */ | ||
328 | if (_eina_rbtree_is_red(q) && _eina_rbtree_is_red(p)) | ||
329 | { | ||
330 | Eina_Rbtree_Direction dir2; | ||
331 | |||
332 | dir2 = (t->son[1] == g) ? EINA_RBTREE_RIGHT : EINA_RBTREE_LEFT; | ||
333 | |||
334 | if (q == p->son[last]) | ||
335 | t->son[dir2] = _eina_rbtree_inline_single_rotation(g, !last); | ||
336 | else | ||
337 | t->son[dir2] = _eina_rbtree_inline_double_rotation(g, !last); | ||
338 | } | ||
339 | |||
340 | /* Stop if found */ | ||
341 | if (q == node) | ||
342 | break; | ||
343 | |||
344 | last = dir; | ||
345 | dir = cmp(q, node, (void *)data); | ||
346 | |||
347 | /* Update helpers */ | ||
348 | if ( g ) | ||
349 | t = g; | ||
350 | |||
351 | g = p, p = q; | ||
352 | q = q->son[dir]; | ||
353 | } | ||
354 | |||
355 | root = head.son[1]; | ||
356 | |||
357 | end_add: | ||
358 | /* Make root black */ | ||
359 | root->color = EINA_RBTREE_BLACK; | ||
360 | |||
361 | return root; | ||
362 | } | ||
363 | |||
364 | EAPI Eina_Rbtree * | ||
365 | eina_rbtree_inline_remove(Eina_Rbtree *root, | ||
366 | Eina_Rbtree *node, | ||
367 | Eina_Rbtree_Cmp_Node_Cb cmp, | ||
368 | const void *data) | ||
369 | { | ||
370 | Eina_Rbtree head; | ||
371 | Eina_Rbtree *q, *p; | ||
372 | Eina_Rbtree *f = NULL; | ||
373 | Eina_Rbtree_Direction dir; | ||
374 | |||
375 | EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); | ||
376 | EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); | ||
377 | |||
378 | if (!root || !node) | ||
379 | return root; | ||
380 | |||
381 | memset(&head, 0, sizeof(Eina_Rbtree)); | ||
382 | |||
383 | dir = EINA_RBTREE_RIGHT; | ||
384 | q = &head; | ||
385 | p = NULL; | ||
386 | q->son[EINA_RBTREE_RIGHT] = root; | ||
387 | |||
388 | /* Search and push a red down */ | ||
389 | while (q->son[dir]) | ||
390 | { | ||
391 | Eina_Rbtree_Direction last = dir; | ||
392 | Eina_Rbtree *g; | ||
393 | |||
394 | /* Update helpers */ | ||
395 | g = p; p = q; | ||
396 | q = q->son[dir]; | ||
397 | dir = cmp(q, node, (void *)data); | ||
398 | |||
399 | /* Save parent node found */ | ||
400 | if (q == node) | ||
401 | f = p; | ||
402 | |||
403 | /* Push the red node down */ | ||
404 | if (!_eina_rbtree_is_red(q) | ||
405 | && !_eina_rbtree_is_red(q->son[dir])) | ||
406 | { | ||
407 | if (_eina_rbtree_is_red(q->son[!dir])) | ||
408 | q = p->son[last] = _eina_rbtree_inline_single_rotation(q, dir); | ||
409 | else if (!_eina_rbtree_is_red(q->son[!dir])) | ||
410 | { | ||
411 | Eina_Rbtree *s = p->son[!last]; | ||
412 | |||
413 | if (s) | ||
414 | { | ||
415 | if (!_eina_rbtree_is_red(s->son[EINA_RBTREE_LEFT]) | ||
416 | && !_eina_rbtree_is_red(s->son[EINA_RBTREE_RIGHT])) | ||
417 | { | ||
418 | /* Color flip */ | ||
419 | p->color = EINA_RBTREE_BLACK; | ||
420 | p->son[EINA_RBTREE_LEFT]->color = EINA_RBTREE_RED; | ||
421 | p->son[EINA_RBTREE_RIGHT]->color = EINA_RBTREE_RED; | ||
422 | } | ||
423 | else | ||
424 | { | ||
425 | Eina_Rbtree_Direction dir2; | ||
426 | |||
427 | dir2 = g->son[1] == | ||
428 | p ? EINA_RBTREE_RIGHT : EINA_RBTREE_LEFT; | ||
429 | |||
430 | if (_eina_rbtree_is_red(s->son[last])) | ||
431 | { | ||
432 | g->son[dir2] = | ||
433 | _eina_rbtree_inline_double_rotation(p, last); | ||
434 | if (f == g) | ||
435 | { | ||
436 | p = g->son[dir2]->son[last]; | ||
437 | f = g->son[dir2]; | ||
438 | } | ||
439 | } | ||
440 | else if (_eina_rbtree_is_red(s->son[!last])) | ||
441 | { | ||
442 | g->son[dir2] = | ||
443 | _eina_rbtree_inline_single_rotation(p, last); | ||
444 | if (f == g) | ||
445 | { | ||
446 | p = g->son[dir2]->son[last]; | ||
447 | f = g->son[dir2]; | ||
448 | } | ||
449 | } | ||
450 | |||
451 | /* Ensure correct coloring */ | ||
452 | q->color = g->son[dir2]->color = EINA_RBTREE_RED; | ||
453 | g->son[dir2]->son[EINA_RBTREE_LEFT]->color = | ||
454 | EINA_RBTREE_BLACK; | ||
455 | g->son[dir2]->son[EINA_RBTREE_RIGHT]->color = | ||
456 | EINA_RBTREE_BLACK; | ||
457 | } | ||
458 | } | ||
459 | } | ||
460 | } | ||
461 | } | ||
462 | |||
463 | /* Replace and remove if found */ | ||
464 | if (f) | ||
465 | { | ||
466 | /* 'q' should take the place of 'node' parent */ | ||
467 | f->son[f->son[1] == node] = q; | ||
468 | |||
469 | /* Switch the link from the parent to q's son */ | ||
470 | p->son[p->son[1] == q] = q->son[!q->son[0]]; | ||
471 | |||
472 | /* Put q at the place of node */ | ||
473 | q->son[0] = node->son[0]; | ||
474 | q->son[1] = node->son[1]; | ||
475 | q->color = node->color; | ||
476 | |||
477 | /* Reset node link */ | ||
478 | node->son[0] = NULL; | ||
479 | node->son[1] = NULL; | ||
480 | } | ||
481 | |||
482 | root = head.son[1]; | ||
483 | if (root) | ||
484 | root->color = EINA_RBTREE_BLACK; | ||
485 | |||
486 | return root; | ||
487 | } | ||
488 | |||
489 | EAPI Eina_Iterator * | ||
490 | eina_rbtree_iterator_prefix(const Eina_Rbtree *root) | ||
491 | { | ||
492 | return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_PREFIX_MASK); | ||
493 | } | ||
494 | |||
495 | EAPI Eina_Iterator * | ||
496 | eina_rbtree_iterator_infix(const Eina_Rbtree *root) | ||
497 | { | ||
498 | return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_INFIX_MASK); | ||
499 | } | ||
500 | |||
501 | EAPI Eina_Iterator * | ||
502 | eina_rbtree_iterator_postfix(const Eina_Rbtree *root) | ||
503 | { | ||
504 | return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_POSTFIX_MASK); | ||
505 | } | ||
506 | |||
507 | EAPI void | ||
508 | eina_rbtree_delete(Eina_Rbtree *root, Eina_Rbtree_Free_Cb func, void *data) | ||
509 | { | ||
510 | if (!root) | ||
511 | return; | ||
512 | |||
513 | EINA_SAFETY_ON_NULL_RETURN(func); | ||
514 | |||
515 | eina_rbtree_delete(root->son[0], func, data); | ||
516 | eina_rbtree_delete(root->son[1], func, data); | ||
517 | func(root, data); | ||
518 | } | ||