src/lib/eina_rbtree.c

   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 }