src/tests/eina_test_rbtree.c

   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 <time.h>
  26
  27 #include "eina_suite.h"
  28 #include "Eina.h"
  29
  30 static inline Eina_Bool
  31 _eina_rbtree_is_red(Eina_Rbtree *tree)
  32 {
  33    return tree != NULL && tree->color == EINA_RBTREE_RED;
  34 }
  35
  36 static int
  37 _eina_rbtree_black_height(Eina_Rbtree *tree, Eina_Rbtree_Cmp_Node_Cb cmp)
  38 {
  39    Eina_Rbtree *left;
  40    Eina_Rbtree *right;
  41    Eina_Rbtree_Direction dir;
  42    int left_height;
  43    int right_height;
  44
  45    if (!tree)
  46       return 1;
  47
  48    left = tree->son[EINA_RBTREE_LEFT];
  49    right = tree->son[EINA_RBTREE_RIGHT];
  50
  51    /* Consecutive red links. */
  52         fail_if(_eina_rbtree_is_red(tree) &&
  53            (_eina_rbtree_is_red(left) || _eina_rbtree_is_red(right)));
  54
  55    left_height = _eina_rbtree_black_height(left, cmp);
  56    right_height = _eina_rbtree_black_height(right, cmp);
  57
  58    /* Check binary search tree. */
  59    if (left)
  60      {
  61         dir = cmp(tree, left, NULL);
  62         fail_if(dir != EINA_RBTREE_LEFT);
  63      }
  64
  65    if (right)
  66      {
  67         dir = cmp(tree, right, NULL);
  68         fail_if(dir != EINA_RBTREE_RIGHT);
  69      }
  70
  71    /* Check black height */
  72    if (left_height != right_height)
  73       fprintf(stderr, "%i != %i\n", left_height, right_height);
  74
  75    fail_if(left_height != right_height);
  76
  77    return _eina_rbtree_is_red(tree) ? left_height : left_height + 1;
  78 }
  79
  80 typedef struct _Eina_Rbtree_Int Eina_Rbtree_Int;
  81 struct _Eina_Rbtree_Int
  82 {
  83    Eina_Rbtree node;
  84    int value;
  85 };
  86
  87 static Eina_Rbtree_Direction
  88 eina_rbtree_int_cmp(const Eina_Rbtree_Int *left,
  89                     const Eina_Rbtree_Int *right,
  90                     __UNUSED__ void *data)
  91 {
  92    fail_if(!left);
  93    fail_if(!right);
  94
  95    if (left->value < right->value)
  96       return EINA_RBTREE_LEFT;
  97
  98    return EINA_RBTREE_RIGHT;
  99 }
 100
 101 static int
 102 eina_rbtree_int_key(const Eina_Rbtree_Int *node,
 103                     const int *key,
 104                     __UNUSED__ int length,
 105                     __UNUSED__ void *data)
 106 {
 107    fail_if(!node);
 108    return node->value - *key;
 109 }
 110
 111 static Eina_Rbtree_Int *
 112 _eina_rbtree_int_new(int value)
 113 {
 114    Eina_Rbtree_Int *it;
 115
 116    it = malloc(sizeof (Eina_Rbtree_Int));
 117    fail_if(!it);
 118
 119    it->value = value;
 120
 121    return it;
 122 }
 123
 124 START_TEST(eina_rbtree_insertion)
 125 {
 126    Eina_Rbtree_Int *root = NULL;
 127    Eina_Rbtree_Int *item;
 128    int i;
 129
 130    srand(time(NULL));
 131
 132    for (i = 0; i < 500; ++i)
 133      {
 134         item = _eina_rbtree_int_new(rand());
 135         root = (Eina_Rbtree_Int *)eina_rbtree_inline_insert(
 136               &root->node,
 137               &item->node,
 138               EINA_RBTREE_CMP_NODE_CB(
 139                  eina_rbtree_int_cmp),
 140               NULL);
 141      }
 142
 143    _eina_rbtree_black_height(&root->node,
 144                              EINA_RBTREE_CMP_NODE_CB(
 145                                 eina_rbtree_int_cmp));
 146 }
 147 END_TEST
 148
 149 START_TEST(eina_rbtree_lookup)
 150 {
 151    Eina_Rbtree_Int *root = NULL;
 152    Eina_Rbtree_Int *item;
 153    int list[] = { 50, 100, 10, 43, 23 };
 154    unsigned int i;
 155
 156    for (i = 0; i < sizeof (list) / sizeof (int); ++i)
 157      {
 158         item = _eina_rbtree_int_new(list[i]);
 159         root = (Eina_Rbtree_Int *)eina_rbtree_inline_insert(
 160               &root->node,
 161               &item->node,
 162                              EINA_RBTREE_CMP_NODE_CB(
 163                  eina_rbtree_int_cmp),
 164               NULL);
 165      }
 166
 167    item = (Eina_Rbtree_Int *)eina_rbtree_inline_lookup(&root->node,
 168                                                        &list[0],
 169                                                        sizeof(int),
 170                                                        EINA_RBTREE_CMP_KEY_CB(
 171                                                           eina_rbtree_int_key),
 172                                                        NULL);
 173    fail_if(!item);
 174
 175    i = 42;
 176    item =
 177       (Eina_Rbtree_Int *)eina_rbtree_inline_lookup(&root->node,
 178                                                    &i,
 179                                                    sizeof(int),
 180                                                    EINA_RBTREE_CMP_KEY_CB(
 181                                                       eina_rbtree_int_key),
 182                                                    NULL);
 183    fail_if(item);
 184 }
 185 END_TEST
 186
 187 START_TEST(eina_rbtree_remove)
 188 {
 189    Eina_Rbtree_Int *root = NULL;
 190    Eina_Rbtree_Int *item;
 191    Eina_Array *ea;
 192    Eina_Array_Iterator it;
 193    unsigned int i;
 194
 195    eina_init();
 196
 197    ea = eina_array_new(11);
 198    fail_if(!ea);
 199
 200    srand(time(NULL));
 201
 202    for (i = 0; i < 500; ++i)
 203      {
 204         item = _eina_rbtree_int_new(rand());
 205         eina_array_push(ea, item);
 206         root = (Eina_Rbtree_Int *)eina_rbtree_inline_insert(
 207               &root->node,
 208               &item->node,
 209               EINA_RBTREE_CMP_NODE_CB(
 210                  eina_rbtree_int_cmp),
 211               NULL);
 212      }
 213
 214    _eina_rbtree_black_height(&root->node,
 215                              EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 216
 217    EINA_ARRAY_ITER_NEXT(ea, i, item, it)
 218      {
 219         root = (Eina_Rbtree_Int *)eina_rbtree_inline_remove(
 220               &root->node,
 221               &item->node,
 222               EINA_RBTREE_CMP_NODE_CB(
 223                  eina_rbtree_int_cmp),
 224               NULL);
 225         _eina_rbtree_black_height(&root->node,
 226                                   EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 227      }
 228
 229    fail_if(root != NULL);
 230
 231    eina_shutdown();
 232 }
 233 END_TEST
 234
 235 START_TEST(eina_rbtree_simple_remove)
 236 {
 237    Eina_Rbtree *root = NULL;
 238    Eina_Rbtree *lookup;
 239    int i;
 240
 241    root =
 242       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 243                                    10),
 244                                 EINA_RBTREE_CMP_NODE_CB(
 245                                    eina_rbtree_int_cmp), NULL);
 246    root =
 247       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 248                                    42),
 249                                 EINA_RBTREE_CMP_NODE_CB(
 250                                    eina_rbtree_int_cmp), NULL);
 251    root =
 252       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 253                                    69),
 254                                 EINA_RBTREE_CMP_NODE_CB(
 255                                    eina_rbtree_int_cmp), NULL);
 256    root =
 257       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 258                                    1337),
 259                                 EINA_RBTREE_CMP_NODE_CB(
 260                                    eina_rbtree_int_cmp), NULL);
 261    _eina_rbtree_black_height(root,
 262                              EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 263
 264    fail_if(root == NULL);
 265
 266    i = 69;
 267    lookup = eina_rbtree_inline_lookup(root,
 268                                       &i,
 269                                       sizeof (int),
 270                                       EINA_RBTREE_CMP_KEY_CB(
 271                                          eina_rbtree_int_key),
 272                                       NULL);
 273    _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 274    fail_if(lookup == NULL);
 275
 276    root =
 277       eina_rbtree_inline_remove(root, lookup, EINA_RBTREE_CMP_NODE_CB(
 278                                    eina_rbtree_int_cmp), NULL);
 279
 280    _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 281 }
 282 END_TEST
 283
 284 START_TEST(eina_rbtree_simple_remove2)
 285 {
 286    Eina_Rbtree *root = NULL;
 287    Eina_Rbtree *lookup;
 288    int i;
 289
 290    root =
 291       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 292                                    10),
 293                                 EINA_RBTREE_CMP_NODE_CB(
 294                                    eina_rbtree_int_cmp), NULL);
 295    root =
 296       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 297                                    42),
 298                                 EINA_RBTREE_CMP_NODE_CB(
 299                                    eina_rbtree_int_cmp), NULL);
 300    root =
 301       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 302                                    69),
 303                                 EINA_RBTREE_CMP_NODE_CB(
 304                                    eina_rbtree_int_cmp), NULL);
 305    root =
 306       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 307                                    1337),
 308                                 EINA_RBTREE_CMP_NODE_CB(
 309                                    eina_rbtree_int_cmp), NULL);
 310    root =
 311       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 312                                    77),
 313                                 EINA_RBTREE_CMP_NODE_CB(
 314                                    eina_rbtree_int_cmp), NULL);
 315    root =
 316       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 317                                    75),
 318                                 EINA_RBTREE_CMP_NODE_CB(
 319                                    eina_rbtree_int_cmp), NULL);
 320    root =
 321       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 322                                    81),
 323                                 EINA_RBTREE_CMP_NODE_CB(
 324                                    eina_rbtree_int_cmp), NULL);
 325    _eina_rbtree_black_height(root,
 326                              EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 327
 328    fail_if(root == NULL);
 329
 330    i = 69;
 331    lookup = eina_rbtree_inline_lookup(root,
 332                                       &i,
 333                                       sizeof (int),
 334                                       EINA_RBTREE_CMP_KEY_CB(
 335                                          eina_rbtree_int_key),
 336                                       NULL);
 337    _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 338    fail_if(lookup == NULL);
 339
 340    root =
 341       eina_rbtree_inline_remove(root, lookup, EINA_RBTREE_CMP_NODE_CB(
 342                                    eina_rbtree_int_cmp), NULL);
 343
 344    _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 345 }
 346 END_TEST
 347
 348 START_TEST(eina_rbtree_simple_remove3)
 349 {
 350    Eina_Rbtree *root = NULL;
 351    Eina_Rbtree *lookup;
 352    int i;
 353
 354    root =
 355       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 356                                    1113497590),
 357                                 EINA_RBTREE_CMP_NODE_CB(
 358                                    eina_rbtree_int_cmp), NULL);
 359    root =
 360       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 361                                    499187507),
 362                                 EINA_RBTREE_CMP_NODE_CB(
 363                                    eina_rbtree_int_cmp), NULL);
 364    root =
 365       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 366                                    1693860487),
 367                                 EINA_RBTREE_CMP_NODE_CB(
 368                                    eina_rbtree_int_cmp), NULL);
 369    root =
 370       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 371                                    26211080),
 372                                 EINA_RBTREE_CMP_NODE_CB(
 373                                    eina_rbtree_int_cmp), NULL);
 374    root =
 375       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 376                                    797272577),
 377                                 EINA_RBTREE_CMP_NODE_CB(
 378                                    eina_rbtree_int_cmp), NULL);
 379    root =
 380       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 381                                    1252184882),
 382                                 EINA_RBTREE_CMP_NODE_CB(
 383                                    eina_rbtree_int_cmp), NULL);
 384    root =
 385       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 386                                    1448158229),
 387                                 EINA_RBTREE_CMP_NODE_CB(
 388                                    eina_rbtree_int_cmp), NULL);
 389    root =
 390       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 391                                    1821884856),
 392                                 EINA_RBTREE_CMP_NODE_CB(
 393                                    eina_rbtree_int_cmp), NULL);
 394    root =
 395       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 396                                    346086006),
 397                                 EINA_RBTREE_CMP_NODE_CB(
 398                                    eina_rbtree_int_cmp), NULL);
 399    root =
 400       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 401                                    936357333),
 402                                 EINA_RBTREE_CMP_NODE_CB(
 403                                    eina_rbtree_int_cmp), NULL);
 404    root =
 405       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 406                                    1462073936),
 407                                 EINA_RBTREE_CMP_NODE_CB(
 408                                    eina_rbtree_int_cmp), NULL);
 409    root =
 410       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 411                                    1717320055),
 412                                 EINA_RBTREE_CMP_NODE_CB(
 413                                    eina_rbtree_int_cmp), NULL);
 414    root =
 415       eina_rbtree_inline_insert(root, (Eina_Rbtree *)_eina_rbtree_int_new(
 416                                    1845524606),
 417                                 EINA_RBTREE_CMP_NODE_CB(
 418                                    eina_rbtree_int_cmp), NULL);
 419    _eina_rbtree_black_height(root,
 420                              EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 421
 422    fail_if(root == NULL);
 423
 424    i = 1113497590;
 425    lookup = eina_rbtree_inline_lookup(root,
 426                                       &i,
 427                                       sizeof (int),
 428                                       EINA_RBTREE_CMP_KEY_CB(
 429                                          eina_rbtree_int_key),
 430                                       NULL);
 431    _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 432    fail_if(lookup == NULL);
 433
 434    root =
 435       eina_rbtree_inline_remove(root, lookup, EINA_RBTREE_CMP_NODE_CB(
 436                                    eina_rbtree_int_cmp), NULL);
 437
 438    _eina_rbtree_black_height(root, EINA_RBTREE_CMP_NODE_CB(eina_rbtree_int_cmp));
 439 }
 440 END_TEST
 441
 442 void
 443 eina_test_rbtree(TCase *tc)
 444 {
 445    tcase_add_test(tc, eina_rbtree_insertion);
 446    tcase_add_test(tc, eina_rbtree_lookup);
 447    tcase_add_test(tc, eina_rbtree_remove);
 448    tcase_add_test(tc, eina_rbtree_simple_remove);
 449    tcase_add_test(tc, eina_rbtree_simple_remove2);
 450    tcase_add_test(tc, eina_rbtree_simple_remove3);
 451 }
 452