aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/libraries/eina/src/lib/eina_rbtree.c
diff options
context:
space:
mode:
Diffstat (limited to 'libraries/eina/src/lib/eina_rbtree.c')
-rw-r--r--libraries/eina/src/lib/eina_rbtree.c519
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
45typedef struct _Eina_Iterator_Rbtree Eina_Iterator_Rbtree;
46typedef struct _Eina_Iterator_Rbtree_List Eina_Iterator_Rbtree_List;
47
48struct _Eina_Iterator_Rbtree
49{
50 Eina_Iterator iterator;
51
52 Eina_Array *stack;
53
54 unsigned char mask;
55};
56
57struct _Eina_Iterator_Rbtree_List
58{
59 Eina_Rbtree *tree;
60
61 Eina_Rbtree_Direction dir : 1;
62 Eina_Bool up : 1;
63};
64
65static 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
85static 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
94static 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
108static 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
178onfix:
179 *data = tree;
180 return EINA_TRUE;
181}
182
183static 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
219on_error:
220 eina_array_free(it->stack);
221on_error2:
222 free(it);
223
224 return NULL;
225}
226
227static 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
239static inline Eina_Bool
240_eina_rbtree_is_red(Eina_Rbtree *node)
241{
242 return !!node && node->color == EINA_RBTREE_RED;
243}
244
245static 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
260static 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
276EAPI Eina_Rbtree *
277eina_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
343EAPI Eina_Rbtree *
344eina_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
490EAPI Eina_Iterator *
491eina_rbtree_iterator_prefix(const Eina_Rbtree *root)
492{
493 return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_PREFIX_MASK);
494}
495
496EAPI Eina_Iterator *
497eina_rbtree_iterator_infix(const Eina_Rbtree *root)
498{
499 return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_INFIX_MASK);
500}
501
502EAPI Eina_Iterator *
503eina_rbtree_iterator_postfix(const Eina_Rbtree *root)
504{
505 return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_POSTFIX_MASK);
506}
507
508EAPI void
509eina_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}
generated by cgit v1.1 at 2024-08-30 18:32:14 +0000