From dd7595a3475407a7fa96a97393bae8c5220e8762 Mon Sep 17 00:00:00 2001 From: David Walter Seikel Date: Wed, 4 Jan 2012 18:41:13 +1000 Subject: Add the base Enlightenment Foundation Libraries - eina, eet, evas, ecore, embryo, and edje. Note that embryo wont be used, but I'm not sure yet if you can build edje without it. --- libraries/eina/src/lib/eina_rbtree.c | 518 +++++++++++++++++++++++++++++++++++ 1 file changed, 518 insertions(+) create mode 100644 libraries/eina/src/lib/eina_rbtree.c (limited to 'libraries/eina/src/lib/eina_rbtree.c') 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 @@ +/* EINA - EFL data type library + * Copyright (C) 2008 Cedric Bail + * + * This library is free software; you can redistribute it and/or + * modify it under the terms of the GNU Lesser General Public + * License as published by the Free Software Foundation; either + * version 2.1 of the License, or (at your option) any later version. + * + * This library is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + * Lesser General Public License for more details. + * + * You should have received a copy of the GNU Lesser General Public + * License along with this library; + * if not, see . + */ + +#ifdef HAVE_CONFIG_H +# include "config.h" +#endif + +#include +#include +#include + +#include "eina_config.h" +#include "eina_private.h" +#include "eina_array.h" + +/* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */ +#include "eina_safety_checks.h" +#include "eina_rbtree.h" + +/*============================================================================* +* Local * +*============================================================================*/ + +#define EINA_RBTREE_ITERATOR_PREFIX_MASK 0x1 +#define EINA_RBTREE_ITERATOR_INFIX_MASK 0x2 +#define EINA_RBTREE_ITERATOR_POSTFIX_MASK 0x4 + +typedef struct _Eina_Iterator_Rbtree Eina_Iterator_Rbtree; +typedef struct _Eina_Iterator_Rbtree_List Eina_Iterator_Rbtree_List; + +struct _Eina_Iterator_Rbtree +{ + Eina_Iterator iterator; + + Eina_Array *stack; + + unsigned char mask; +}; + +struct _Eina_Iterator_Rbtree_List +{ + Eina_Rbtree *tree; + + Eina_Rbtree_Direction dir : 1; + Eina_Bool up : 1; +}; + +static Eina_Iterator_Rbtree_List * +_eina_rbtree_iterator_list_new(const Eina_Rbtree *tree) +{ + Eina_Iterator_Rbtree_List *new; + + eina_error_set(0); + new = malloc(sizeof (Eina_Iterator_Rbtree_List)); + if (!new) + { + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + return NULL; + } + + new->tree = (Eina_Rbtree *)tree; + new->dir = EINA_RBTREE_RIGHT; + new->up = EINA_FALSE; + + return new; +} + +static Eina_Rbtree * +_eina_rbtree_iterator_get_content(Eina_Iterator_Rbtree *it) +{ + if (eina_array_count_get(it->stack) <= 0) + return NULL; + + return eina_array_data_get(it->stack, 0); +} + +static void +_eina_rbtree_iterator_free(Eina_Iterator_Rbtree *it) +{ + Eina_Iterator_Rbtree_List *item; + Eina_Array_Iterator et; + unsigned int i; + + EINA_ARRAY_ITER_NEXT(it->stack, i, item, et) + free(item); + + eina_array_free(it->stack); + free(it); +} + +static Eina_Bool +_eina_rbtree_iterator_next(Eina_Iterator_Rbtree *it, void **data) +{ + Eina_Iterator_Rbtree_List *last; + Eina_Iterator_Rbtree_List *new; + Eina_Rbtree *tree; + + if (eina_array_count_get(it->stack) <= 0) + return EINA_FALSE; + + last = eina_array_data_get(it->stack, eina_array_count_get(it->stack) - 1); + tree = last->tree; + + if (!last->tree || last->up == EINA_TRUE) + { + last = eina_array_pop(it->stack); + while (last->dir == EINA_RBTREE_LEFT + || !last->tree) + { + if (tree) + if ((it->mask & EINA_RBTREE_ITERATOR_POSTFIX_MASK) == + EINA_RBTREE_ITERATOR_POSTFIX_MASK) + { + free(last); + + if (eina_array_count_get(it->stack) > 0) + { + last = eina_array_data_get(it->stack, + eina_array_count_get( + it-> + stack) + - 1); + last->up = EINA_TRUE; + } + + goto onfix; + } + + free(last); + + last = eina_array_pop(it->stack); + if (!last) + return EINA_FALSE; + + tree = last->tree; + } + + last->dir = EINA_RBTREE_LEFT; + last->up = EINA_FALSE; + + eina_array_push(it->stack, last); + + if ((it->mask & EINA_RBTREE_ITERATOR_INFIX_MASK) == + EINA_RBTREE_ITERATOR_INFIX_MASK) + goto onfix; + } + + new = _eina_rbtree_iterator_list_new(last->tree->son[last->dir]); + if (!new) + return EINA_FALSE; + + eina_array_push(it->stack, new); + + if (last->dir == EINA_RBTREE_RIGHT) + if ((it->mask & EINA_RBTREE_ITERATOR_PREFIX_MASK) == + EINA_RBTREE_ITERATOR_PREFIX_MASK) + goto onfix; + + return _eina_rbtree_iterator_next(it, data); + +onfix: + *data = tree; + return EINA_TRUE; +} + +static Eina_Iterator * +_eina_rbtree_iterator_build(const Eina_Rbtree *root, unsigned char mask) +{ + Eina_Iterator_Rbtree_List *first; + Eina_Iterator_Rbtree *it; + + eina_error_set(0); + it = calloc(1, sizeof (Eina_Iterator_Rbtree)); + if (!it) + { + eina_error_set(EINA_ERROR_OUT_OF_MEMORY); + return NULL; + } + + it->stack = eina_array_new(8); + if (!it->stack) + goto on_error2; + + first = _eina_rbtree_iterator_list_new(root); + if (!first) + goto on_error; + + eina_array_push(it->stack, first); + + it->mask = mask; + + it->iterator.version = EINA_ITERATOR_VERSION; + it->iterator.next = FUNC_ITERATOR_NEXT(_eina_rbtree_iterator_next); + it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER( + _eina_rbtree_iterator_get_content); + it->iterator.free = FUNC_ITERATOR_FREE(_eina_rbtree_iterator_free); + + EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR); + + return &it->iterator; + +on_error: + eina_array_free(it->stack); +on_error2: + free(it); + + return NULL; +} + +static void +_eina_rbtree_node_init(Eina_Rbtree *node) +{ + if (!node) + return; + + node->son[0] = NULL; + node->son[1] = NULL; + + node->color = EINA_RBTREE_RED; +} + +static inline Eina_Bool +_eina_rbtree_is_red(Eina_Rbtree *node) +{ + return !!node && node->color == EINA_RBTREE_RED; +} + +static inline Eina_Rbtree * +_eina_rbtree_inline_single_rotation(Eina_Rbtree *node, + Eina_Rbtree_Direction dir) +{ + Eina_Rbtree *save = node->son[!dir]; + + node->son[!dir] = save->son[dir]; + save->son[dir] = node; + + node->color = EINA_RBTREE_RED; + save->color = EINA_RBTREE_BLACK; + + return save; +} + +static inline Eina_Rbtree * +_eina_rbtree_inline_double_rotation(Eina_Rbtree *node, + Eina_Rbtree_Direction dir) +{ + node->son[!dir] = _eina_rbtree_inline_single_rotation(node->son[!dir], !dir); + return _eina_rbtree_inline_single_rotation(node, dir); +} + +/*============================================================================* +* Global * +*============================================================================*/ + +/*============================================================================* +* API * +*============================================================================*/ + +EAPI Eina_Rbtree * +eina_rbtree_inline_insert(Eina_Rbtree *root, + Eina_Rbtree *node, + Eina_Rbtree_Cmp_Node_Cb cmp, + const void *data) +{ + Eina_Rbtree head; + Eina_Rbtree *g, *t; /* Grandparent & parent */ + Eina_Rbtree *p, *q; /* Iterator & parent */ + /* WARNING: + Compiler is not able to understand the underlying algorithm and don't know that + first top node is always black, so it will never use last before running the loop + one time. + */ + Eina_Rbtree_Direction dir, last; + + EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); + EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); + + if (!node) + return root; + + _eina_rbtree_node_init(node); + + if (!root) + { + root = node; + goto end_add; + } + + memset(&head, 0, sizeof (Eina_Rbtree)); + last = dir = EINA_RBTREE_LEFT; + + /* Set up helpers */ + t = &head; + g = p = NULL; + q = t->son[1] = root; + + /* Search down the tree */ + for (;; ) + { + if (!q) + /* Insert new node at the bottom */ + p->son[dir] = q = node; + else if (_eina_rbtree_is_red(q->son[0]) + && _eina_rbtree_is_red(q->son[1])) + { + /* Color flip */ + q->color = EINA_RBTREE_RED; + q->son[0]->color = EINA_RBTREE_BLACK; + q->son[1]->color = EINA_RBTREE_BLACK; + } + + /* Fix red violation */ + if (_eina_rbtree_is_red(q) && _eina_rbtree_is_red(p)) + { + Eina_Rbtree_Direction dir2; + + dir2 = (t->son[1] == g) ? EINA_RBTREE_RIGHT : EINA_RBTREE_LEFT; + + if (q == p->son[last]) + t->son[dir2] = _eina_rbtree_inline_single_rotation(g, !last); + else + t->son[dir2] = _eina_rbtree_inline_double_rotation(g, !last); + } + + /* Stop if found */ + if (q == node) + break; + + last = dir; + dir = cmp(q, node, (void *)data); + + /* Update helpers */ + if ( g ) + t = g; + + g = p, p = q; + q = q->son[dir]; + } + + root = head.son[1]; + +end_add: + /* Make root black */ + root->color = EINA_RBTREE_BLACK; + + return root; +} + +EAPI Eina_Rbtree * +eina_rbtree_inline_remove(Eina_Rbtree *root, + Eina_Rbtree *node, + Eina_Rbtree_Cmp_Node_Cb cmp, + const void *data) +{ + Eina_Rbtree head; + Eina_Rbtree *q, *p; + Eina_Rbtree *f = NULL; + Eina_Rbtree_Direction dir; + + EINA_SAFETY_ON_NULL_RETURN_VAL(node, root); + EINA_SAFETY_ON_NULL_RETURN_VAL( cmp, root); + + if (!root || !node) + return root; + + memset(&head, 0, sizeof(Eina_Rbtree)); + + dir = EINA_RBTREE_RIGHT; + q = &head; + p = NULL; + q->son[EINA_RBTREE_RIGHT] = root; + + /* Search and push a red down */ + while (q->son[dir]) + { + Eina_Rbtree_Direction last = dir; + Eina_Rbtree *g; + + /* Update helpers */ + g = p; p = q; + q = q->son[dir]; + dir = cmp(q, node, (void *)data); + + /* Save parent node found */ + if (q == node) + f = p; + + /* Push the red node down */ + if (!_eina_rbtree_is_red(q) + && !_eina_rbtree_is_red(q->son[dir])) + { + if (_eina_rbtree_is_red(q->son[!dir])) + q = p->son[last] = _eina_rbtree_inline_single_rotation(q, dir); + else if (!_eina_rbtree_is_red(q->son[!dir])) + { + Eina_Rbtree *s = p->son[!last]; + + if (s) + { + if (!_eina_rbtree_is_red(s->son[EINA_RBTREE_LEFT]) + && !_eina_rbtree_is_red(s->son[EINA_RBTREE_RIGHT])) + { +/* Color flip */ + p->color = EINA_RBTREE_BLACK; + p->son[EINA_RBTREE_LEFT]->color = EINA_RBTREE_RED; + p->son[EINA_RBTREE_RIGHT]->color = EINA_RBTREE_RED; + } + else + { + Eina_Rbtree_Direction dir2; + + dir2 = g->son[1] == + p ? EINA_RBTREE_RIGHT : EINA_RBTREE_LEFT; + + if (_eina_rbtree_is_red(s->son[last])) + { + g->son[dir2] = + _eina_rbtree_inline_double_rotation(p, last); + if (f == g) + { + p = g->son[dir2]->son[last]; + f = g->son[dir2]; + } + } + else if (_eina_rbtree_is_red(s->son[!last])) + { + g->son[dir2] = + _eina_rbtree_inline_single_rotation(p, last); + if (f == g) + { + p = g->son[dir2]->son[last]; + f = g->son[dir2]; + } + } + +/* Ensure correct coloring */ + q->color = g->son[dir2]->color = EINA_RBTREE_RED; + g->son[dir2]->son[EINA_RBTREE_LEFT]->color = + EINA_RBTREE_BLACK; + g->son[dir2]->son[EINA_RBTREE_RIGHT]->color = + EINA_RBTREE_BLACK; + } + } + } + } + } + + /* Replace and remove if found */ + if (f) + { + /* 'q' should take the place of 'node' parent */ + f->son[f->son[1] == node] = q; + + /* Switch the link from the parent to q's son */ + p->son[p->son[1] == q] = q->son[!q->son[0]]; + + /* Put q at the place of node */ + q->son[0] = node->son[0]; + q->son[1] = node->son[1]; + q->color = node->color; + + /* Reset node link */ + node->son[0] = NULL; + node->son[1] = NULL; + } + + root = head.son[1]; + if (root) + root->color = EINA_RBTREE_BLACK; + + return root; +} + +EAPI Eina_Iterator * +eina_rbtree_iterator_prefix(const Eina_Rbtree *root) +{ + return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_PREFIX_MASK); +} + +EAPI Eina_Iterator * +eina_rbtree_iterator_infix(const Eina_Rbtree *root) +{ + return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_INFIX_MASK); +} + +EAPI Eina_Iterator * +eina_rbtree_iterator_postfix(const Eina_Rbtree *root) +{ + return _eina_rbtree_iterator_build(root, EINA_RBTREE_ITERATOR_POSTFIX_MASK); +} + +EAPI void +eina_rbtree_delete(Eina_Rbtree *root, Eina_Rbtree_Free_Cb func, void *data) +{ + if (!root) + return; + + EINA_SAFETY_ON_NULL_RETURN(func); + + eina_rbtree_delete(root->son[0], func, data); + eina_rbtree_delete(root->son[1], func, data); + func(root, data); +} -- cgit v1.1