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