src/tests/ecore_hash.c

   1 #ifdef HAVE_CONFIG_H
   2 # include <config.h>
   3 #endif
   4
   5 #include <stdlib.h>
   6 #include <stdio.h>
   7 #include <string.h>
   8
   9 #include "Ecore_Data.h"
  10
  11 #define PRIME_TABLE_MAX 21
  12 #define PRIME_MIN 17
  13 #define PRIME_MAX 16777213
  14
  15 #define ECORE_HASH_CHAIN_MAX 3
  16
  17 #define ECORE_COMPUTE_HASH(hash, key) hash->hash_func(key) % \
  18    ecore_prime_table[hash->size];
  19
  20 #define ECORE_HASH_INCREASE(hash) ((hash && ecore_prime_table[hash->size] < \
  21                                     PRIME_MAX) ? \
  22                                    (hash->nodes / \
  23                                     ecore_prime_table[hash->size]) > \
  24                                    ECORE_HASH_CHAIN_MAX : FALSE)
  25 #define ECORE_HASH_REDUCE(hash) ((hash && ecore_prime_table[hash->size] > \
  26                                   PRIME_MIN) ? \
  27                                  (double)hash->nodes / \
  28                                  (double)ecore_prime_table[hash->size - 1] \
  29                                  < ((double)ECORE_HASH_CHAIN_MAX * \
  30                                     0.375) : FALSE)
  31
  32
  33 static const unsigned int ecore_prime_table[] =
  34 {
  35    17, 31, 61, 127, 257, 509, 1021,
  36    2053, 4093, 8191, 16381, 32771, 65537, 131071, 262147, 524287, 1048573,
  37    2097143, 4194301, 8388617, 16777213
  38 };
  39
  40
  41 /* Private hash manipulation functions */
  42 static int                     _ecore_hash_node_add(Ecore_Hash *hash,
  43                                                     Ecore_Hash_Node *node);
  44 static Ecore_Hash_Node *       _ecore_hash_node_get(Ecore_Hash *hash,
  45                                                     const void *key);
  46 static int                     _ecore_hash_increase(Ecore_Hash *hash);
  47 static int                     _ecore_hash_decrease(Ecore_Hash *hash);
  48 static inline int              _ecore_hash_rehash(Ecore_Hash *hash,
  49                                                   Ecore_Hash_Node **old_table,
  50                                                   int old_size);
  51 static int                     _ecore_hash_bucket_destroy(Ecore_Hash_Node *list,
  52                                                           Ecore_Free_Cb keyd,
  53                                                           Ecore_Free_Cb valued);
  54 static inline Ecore_Hash_Node *_ecore_hash_bucket_get(Ecore_Hash *hash,
  55                                                       Ecore_Hash_Node *bucket,
  56                                                       const void *key);
  57
  58 static Ecore_Hash_Node *       _ecore_hash_node_new(void *key, void *value);
  59 static int                     _ecore_hash_node_init(Ecore_Hash_Node *node,
  60                                                      void *key,
  61                                                      void *value);
  62 static int                     _ecore_hash_node_destroy(Ecore_Hash_Node *node,
  63                                                         Ecore_Free_Cb keyd,
  64                                                         Ecore_Free_Cb valued);
  65
  66 /**
  67  * @defgroup Ecore_Data_Hash_ADT_Creation_Group Hash Creation Functions
  68  *
  69  * Functions that create hash tables.
  70  */
  71
  72 /**
  73  * Creates and initializes a new hash
  74  * @param hash_func The function for determining hash position.
  75  * @param compare   The function for comparing node keys.
  76  * @return @c NULL on error, a new hash on success.
  77  * @ingroup Ecore_Data_Hash_ADT_Creation_Group
  78  */
  79 EAPI Ecore_Hash *
  80 ecore_hash_new(Ecore_Hash_Cb hash_func, Ecore_Compare_Cb compare)
  81 {
  82    Ecore_Hash *new_hash = (Ecore_Hash *)malloc(sizeof(Ecore_Hash));
  83    if (!new_hash)
  84       return NULL;
  85
  86    if (!ecore_hash_init(new_hash, hash_func, compare))
  87      {
  88         FREE(new_hash);
  89         return NULL;
  90      }
  91
  92    return new_hash;
  93 }
  94
  95 /**
  96  * Initializes the given hash.
  97  * @param   hash       The given hash.
  98  * @param   hash_func  The function used for hashing node keys.
  99  * @param   compare    The function used for comparing node keys.
 100  * @return  @c TRUE on success, @c FALSE on an error.
 101  * @ingroup Ecore_Data_Hash_ADT_Creation_Group
 102  */
 103 EAPI int
 104 ecore_hash_init(Ecore_Hash *hash,
 105                 Ecore_Hash_Cb hash_func,
 106                 Ecore_Compare_Cb compare)
 107 {
 108    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 109
 110    memset(hash, 0, sizeof(Ecore_Hash));
 111
 112    hash->hash_func = hash_func;
 113    hash->compare = compare;
 114
 115    hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[0],
 116                                               sizeof(Ecore_Hash_Node *));
 117
 118    return TRUE;
 119 }
 120
 121 /**
 122  * @defgroup Ecore_Data_Hash_ADT_Destruction_Group Hash Destruction Functions
 123  *
 124  * Functions that destroy hash tables and their contents.
 125  */
 126
 127 /**
 128  * Sets the function to destroy the keys of the given hash.
 129  * @param   hash     The given hash.
 130  * @param   function The function used to free the node keys. NULL is a
 131  *          valid value and means that no function will be called.
 132  * @return  @c TRUE on success, @c FALSE on error.
 133  * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
 134  */
 135 EAPI int
 136 ecore_hash_free_key_cb_set(Ecore_Hash *hash, Ecore_Free_Cb function)
 137 {
 138    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 139
 140    hash->free_key = function;
 141
 142    return TRUE;
 143 }
 144
 145 /**
 146  * Sets the function to destroy the values in the given hash.
 147  * @param   hash     The given hash.
 148  * @param   function The function that will free the node values. NULL is a
 149  *          valid value and means that no function will be called.
 150  * @return  @c TRUE on success, @c FALSE on error
 151  * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
 152  */
 153 EAPI int
 154 ecore_hash_free_value_cb_set(Ecore_Hash *hash, Ecore_Free_Cb function)
 155 {
 156    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 157
 158    hash->free_value = function;
 159
 160    return TRUE;
 161 }
 162
 163 /**
 164  * @defgroup Ecore_Data_Hash_ADT_Data_Group Hash Data Functions
 165  *
 166  * Functions that set, access and delete values from the hash tables.
 167  */
 168
 169 /**
 170  * Sets a key-value pair in the given hash table.
 171  * @param   hash    The given hash table.
 172  * @param   key     The key.
 173  * @param   value   The value.
 174  * @return  @c TRUE if successful, @c FALSE if not.
 175  * @ingroup Ecore_Data_Hash_ADT_Data_Group
 176  */
 177 EAPI int
 178 ecore_hash_set(Ecore_Hash *hash, void *key, void *value)
 179 {
 180    int ret = FALSE;
 181    Ecore_Hash_Node *node;
 182
 183    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 184
 185    node = _ecore_hash_node_get(hash, key);
 186    if (node)
 187      {
 188         if (hash->free_key)
 189            hash->free_key(key);
 190
 191         if (node->value && hash->free_value)
 192            hash->free_value(node->value);
 193
 194         node->value = value;
 195         ret = TRUE;
 196      }
 197    else
 198      {
 199         node = _ecore_hash_node_new(key, value);
 200         if (node)
 201            ret = _ecore_hash_node_add(hash, node);
 202      }
 203
 204    return ret;
 205 }
 206
 207 /**
 208  * Sets all key-value pairs from set in the given hash table.
 209  * @param   hash    The given hash table.
 210  * @param   set     The hash table to import.
 211  * @return  @c TRUE if successful, @c FALSE if not.
 212  * @ingroup Ecore_Data_Hash_ADT_Data_Group
 213  */
 214 EAPI int
 215 ecore_hash_hash_set(Ecore_Hash *hash, Ecore_Hash *set)
 216 {
 217    unsigned int i;
 218    Ecore_Hash_Node *node, *old;
 219
 220    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 221    CHECK_PARAM_POINTER_RETURN("set",  set,  FALSE);
 222
 223    for (i = 0; i < ecore_prime_table[set->size]; i++)
 224      {
 225         /* Hash into a new list to avoid loops of rehashing the same nodes */
 226         while ((old = set->buckets[i]))
 227           {
 228              set->buckets[i] = old->next;
 229              old->next = NULL;
 230              node = _ecore_hash_node_get(hash, old->key);
 231              if (node)
 232                {
 233                   /* This key already exists. Delete the old and add the new
 234                    * value */
 235                   if (hash->free_key)
 236                      hash->free_key(node->key);
 237
 238                   if (hash->free_value)
 239                      hash->free_key(node->value);
 240
 241                   node->key = old->key;
 242                   node->value = old->value;
 243                   free(old);
 244                }
 245              else
 246                 _ecore_hash_node_add(hash, old);
 247           }
 248      }
 249    FREE(set->buckets);
 250    ecore_hash_init(set, set->hash_func, set->compare);
 251    return TRUE;
 252 }
 253
 254 /**
 255  * Frees the hash table and the data contained inside it.
 256  * @param   hash The hash table to destroy.
 257  * @return  @c TRUE on success, @c FALSE on error.
 258  * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
 259  */
 260 EAPI void
 261 ecore_hash_destroy(Ecore_Hash *hash)
 262 {
 263    unsigned int i = 0;
 264
 265    CHECK_PARAM_POINTER("hash", hash);
 266
 267    if (hash->buckets)
 268      {
 269         while (i < ecore_prime_table[hash->size])
 270           {
 271              if (hash->buckets[i])
 272                {
 273                   Ecore_Hash_Node *bucket;
 274
 275                   /*
 276                    * Remove the bucket list to avoid possible recursion
 277                    * on the free callbacks.
 278                    */
 279                   bucket = hash->buckets[i];
 280                   hash->buckets[i] = NULL;
 281                   _ecore_hash_bucket_destroy(bucket,
 282                                              hash->free_key,
 283                                              hash->free_value);
 284                }
 285
 286              i++;
 287           }
 288
 289         FREE(hash->buckets);
 290      }
 291
 292         FREE(hash);
 293
 294    return;
 295 }
 296
 297 /**
 298  * @defgroup Ecore_Data_Hash_ADT_Traverse_Group Hash Traverse Functions
 299  *
 300  * Functions that iterate through hash tables.
 301  */
 302
 303 /**
 304  * Counts the number of nodes in a hash table.
 305  * @param   hash The hash table to count current nodes.
 306  * @return  The number of nodes in the hash.
 307  * @ingroup Ecore_Data_Hash_ADT_Destruction_Group
 308  */
 309 EAPI int
 310 ecore_hash_count(Ecore_Hash *hash)
 311 {
 312    CHECK_PARAM_POINTER_RETURN("hash", hash, 0);
 313
 314    return hash->nodes;
 315 }
 316
 317 /**
 318  * Runs the @p for_each_func function on each entry in the given hash.
 319  * @param   hash          The given hash.
 320  * @param   for_each_func The function that each entry is passed to.
 321  * @param               user_data                       a pointer passed to calls of for_each_func
 322  * @return  TRUE on success, FALSE otherwise.
 323  * @ingroup Ecore_Data_Hash_ADT_Traverse_Group
 324  */
 325 EAPI int
 326 ecore_hash_for_each_node(Ecore_Hash *hash,
 327                          Ecore_For_Each for_each_func,
 328                          void *user_data)
 329 {
 330    unsigned int i = 0;
 331
 332    CHECK_PARAM_POINTER_RETURN("hash",          hash,          FALSE);
 333    CHECK_PARAM_POINTER_RETURN("for_each_func", for_each_func, FALSE);
 334
 335    while (i < ecore_prime_table[hash->size])
 336      {
 337         if (hash->buckets[i])
 338           {
 339              Ecore_Hash_Node *node;
 340
 341              for (node = hash->buckets[i]; node; node = node->next)
 342                {
 343                   for_each_func(node, user_data);
 344                }
 345           }
 346
 347         i++;
 348      }
 349
 350    return TRUE;
 351 }
 352
 353 /**
 354  * Retrieves an ecore_list of all keys in the given hash.
 355  * @param   hash          The given hash.
 356  * @return  new ecore_list on success, NULL otherwise
 357  * @ingroup Ecore_Data_Hash_ADT_Traverse_Group
 358  */
 359 EAPI Ecore_List *
 360 ecore_hash_keys(Ecore_Hash *hash)
 361 {
 362    unsigned int i = 0;
 363    Ecore_List *keys;
 364
 365    CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
 366
 367    keys = ecore_list_new();
 368    while (i < ecore_prime_table[hash->size])
 369      {
 370         if (hash->buckets[i])
 371           {
 372              Ecore_Hash_Node *node;
 373
 374              for (node = hash->buckets[i]; node; node = node->next)
 375                {
 376                   ecore_list_append(keys, node->key);
 377                }
 378           }
 379
 380         i++;
 381      }
 382    ecore_list_first_goto(keys);
 383
 384    return keys;
 385 }
 386
 387 /**
 388  * Prints the distribution of the given hash table for graphing.
 389  * @param hash The given hash table.
 390  */
 391 EAPI void
 392 ecore_hash_dump_graph(Ecore_Hash *hash)
 393 {
 394    unsigned int i;
 395
 396    for (i = 0; i < ecore_prime_table[hash->size]; i++)
 397       if (hash->buckets[i])
 398         {
 399            int n = 0;
 400            Ecore_Hash_Node *node;
 401            for (node = hash->buckets[i]; node; node = node->next)
 402               n++;
 403            printf("%d\t%u", i, n);
 404         }
 405       else
 406            printf("%d\t0",  i);
 407
 408 }
 409
 410 /**
 411  * Prints the distribution of the given hash table for graphing.
 412  * @param hash The given hash table.
 413  */
 414 EAPI void
 415 ecore_hash_dump_stats(Ecore_Hash *hash)
 416 {
 417    unsigned int i;
 418    double variance, sum_n_2 = 0, sum_n = 0;
 419
 420    for (i = 0; i < ecore_prime_table[hash->size]; i++)
 421      {
 422         if (hash->buckets[i])
 423           {
 424              int n = 0;
 425              Ecore_Hash_Node *node;
 426              for (node = hash->buckets[i]; node; node = node->next)
 427                 n++;
 428              sum_n_2 += ((double)n * (double)n);
 429              sum_n += (double)n;
 430           }
 431      }
 432    variance = (sum_n_2 - ((sum_n * sum_n) / (double)i)) / (double)i;
 433            printf("Average length: %f\n\tvariance^2: %f", (sum_n / (double)i),
 434           variance);
 435 }
 436
 437 static int
 438 _ecore_hash_bucket_destroy(Ecore_Hash_Node *list,
 439                            Ecore_Free_Cb keyd,
 440                            Ecore_Free_Cb valued)
 441 {
 442    Ecore_Hash_Node *node;
 443
 444    CHECK_PARAM_POINTER_RETURN("list", list, FALSE);
 445
 446    for (node = list; node; node = list)
 447      {
 448         list = list->next;
 449         _ecore_hash_node_destroy(node, keyd, valued);
 450      }
 451
 452    return TRUE;
 453 }
 454
 455 /*
 456  * @brief Add the node to the hash table
 457  * @param hash: the hash table to add the key
 458  * @param node: the node to add to the hash table
 459  * @return Returns FALSE on error, TRUE on success
 460  */
 461 static int
 462 _ecore_hash_node_add(Ecore_Hash *hash, Ecore_Hash_Node *node)
 463 {
 464    unsigned long hash_val;
 465
 466    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 467    CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 468
 469    /* Check to see if the hash needs to be resized */
 470    if (ECORE_HASH_INCREASE(hash))
 471       _ecore_hash_increase(hash);
 472
 473    /* Compute the position in the table */
 474    if (!hash->hash_func)
 475       hash_val = (unsigned long)node->key % ecore_prime_table[hash->size];
 476    else
 477       hash_val = ECORE_COMPUTE_HASH(hash, node->key);
 478
 479    /* Prepend the node to the list at the index position */
 480    node->next = hash->buckets[hash_val];
 481    hash->buckets[hash_val] = node;
 482    hash->nodes++;
 483
 484    return TRUE;
 485 }
 486
 487 /**
 488  * Retrieves the value associated with the given key from the given hash
 489  * table.
 490  * @param   hash The given hash table.
 491  * @param   key  The key to search for.
 492  * @return  The value corresponding to key on success, @c NULL otherwise.
 493  * @ingroup Ecore_Data_Hash_ADT_Data_Group
 494  */
 495 EAPI void *
 496 ecore_hash_get(Ecore_Hash *hash, const void *key)
 497 {
 498    void *data;
 499    Ecore_Hash_Node *node;
 500
 501    CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
 502
 503    node = _ecore_hash_node_get(hash, key);
 504    if (!node)
 505       return NULL;
 506
 507    data = node->value;
 508
 509    return data;
 510 }
 511
 512 /**
 513  * Removes the value associated with the given key in the given hash
 514  * table.
 515  * @param   hash The given hash table.
 516  * @param   key  The key to search for.
 517  * @return  The value corresponding to the key on success.  @c NULL is
 518  *          returned if there is an error.
 519  * @ingroup Ecore_Data_Hash_ADT_Data_Group
 520  */
 521 EAPI void *
 522 ecore_hash_remove(Ecore_Hash *hash, const void *key)
 523 {
 524    Ecore_Hash_Node *node = NULL;
 525    Ecore_Hash_Node *list;
 526    unsigned long hash_val;
 527    void *ret = NULL;
 528
 529    CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
 530
 531    /* Compute the position in the table */
 532    if (!hash->hash_func)
 533       hash_val = (unsigned long )key % ecore_prime_table[hash->size];
 534    else
 535       hash_val = ECORE_COMPUTE_HASH(hash, key);
 536
 537    /*
 538     * If their is a list that could possibly hold the key/value pair
 539     * traverse it and remove the hash node.
 540     */
 541    if (hash->buckets[hash_val])
 542      {
 543         list = hash->buckets[hash_val];
 544
 545         /*
 546          * Traverse the list to find the specified key
 547          */
 548         node = list;
 549         if (hash->compare)
 550            while ((node) && (hash->compare(node->key, key) != 0))
 551              {
 552                 list = node;
 553                 node = node->next;
 554              }
 555         else
 556            while ((node) && (node->key != key))
 557              {
 558                 list = node;
 559                 node = node->next;
 560              }
 561
 562         /*
 563          * Remove the node with the matching key and free it's memory
 564          */
 565         if (node)
 566           {
 567              if (list == node)
 568                 hash->buckets[hash_val] = node->next;
 569              else
 570                 list->next = node->next;
 571
 572              ret = node->value;
 573              node->value = NULL;
 574              _ecore_hash_node_destroy(node, hash->free_key, NULL);
 575              hash->nodes--;
 576           }
 577      }
 578
 579    if (ECORE_HASH_REDUCE(hash))
 580       _ecore_hash_decrease(hash);
 581
 582    return ret;
 583 }
 584
 585 /**
 586  * Retrieves the first value that matches
 587  * table.
 588  * @param   hash The given hash table.
 589  * @param   key  The key to search for.
 590  * @return  The value corresponding to key on success, @c NULL otherwise.
 591  * @ingroup Ecore_Data_Hash_ADT_Data_Group
 592  */
 593 EAPI void *
 594 ecore_hash_find(Ecore_Hash *hash, Ecore_Compare_Cb compare, const void *value)
 595 {
 596    unsigned int i = 0;
 597
 598    CHECK_PARAM_POINTER_RETURN("hash",    hash,    NULL);
 599    CHECK_PARAM_POINTER_RETURN("compare", compare, NULL);
 600    CHECK_PARAM_POINTER_RETURN("value",   value,   NULL);
 601
 602    while (i < ecore_prime_table[hash->size])
 603      {
 604         if (hash->buckets[i])
 605           {
 606              Ecore_Hash_Node *node;
 607
 608              for (node = hash->buckets[i]; node; node = node->next)
 609                {
 610                   if (!compare(node->value, value))
 611                      return node->value;
 612                }
 613           }
 614
 615         i++;
 616      }
 617
 618    return NULL;
 619 }
 620
 621 /*
 622  * @brief Retrieve the node associated with key
 623  * @param hash: the hash table to search for the key
 624  * @param key: the key to search for in the hash table
 625  * @return Returns NULL on error, node corresponding to key on success
 626  */
 627 static Ecore_Hash_Node *
 628 _ecore_hash_node_get(Ecore_Hash *hash, const void *key)
 629 {
 630    unsigned long hash_val;
 631    Ecore_Hash_Node *node = NULL;
 632
 633    CHECK_PARAM_POINTER_RETURN("hash", hash, NULL);
 634
 635    if (!hash->buckets)
 636       return NULL;
 637
 638    /* Compute the position in the table */
 639    if (!hash->hash_func)
 640       hash_val = (unsigned long)key % ecore_prime_table[hash->size];
 641    else
 642       hash_val = ECORE_COMPUTE_HASH(hash, key);
 643
 644    /* Grab the bucket at the specified position */
 645    if (hash->buckets[hash_val])
 646      {
 647         node = _ecore_hash_bucket_get(hash, hash->buckets[hash_val], key);
 648         /*
 649          * Move matched node to the front of the list as it's likely
 650          * to be searched for again soon.
 651          */
 652         if (node && node != hash->buckets[hash_val])
 653           {
 654              node->next = hash->buckets[hash_val];
 655              hash->buckets[hash_val] = node;
 656           }
 657      }
 658
 659    return node;
 660 }
 661
 662 /*
 663  * @brief Search the hash bucket for a specified key
 664  * @param hash: the hash table to retrieve the comparison function
 665  * @param bucket: the list to search for the key
 666  * @param key: the key to search for in the list
 667  * @return Returns NULL on error or not found, the found node on success
 668  */
 669 static inline Ecore_Hash_Node *
 670 _ecore_hash_bucket_get(Ecore_Hash *hash,
 671                        Ecore_Hash_Node *bucket,
 672                        const void *key)
 673 {
 674    Ecore_Hash_Node *prev = NULL;
 675    Ecore_Hash_Node *node = NULL;
 676
 677    /*
 678     * Traverse the list to find the desired node, if the node is in the
 679     * list, then return the node.
 680     */
 681    if (hash->compare)
 682       for (node = bucket; node; node = node->next)
 683         {
 684            if (hash->compare(node->key, key) == 0)
 685               break;
 686
 687            prev = node;
 688         }
 689    else
 690       for (node = bucket; node; node = node->next)
 691         {
 692            if (node->key == key)
 693               break;
 694
 695            prev = node;
 696         }
 697
 698    /*
 699     * Remove node from the list to replace it at the beginning.
 700     */
 701    if (node && prev)
 702      {
 703         prev->next = node->next;
 704         node->next = NULL;
 705      }
 706
 707    return node;
 708 }
 709
 710 /*
 711  * @brief Increase the size of the hash table by approx.  2 * current size
 712  * @param hash: the hash table to increase the size of
 713  * @return Returns TRUE on success, FALSE on error
 714  */
 715 static int
 716 _ecore_hash_increase(Ecore_Hash *hash)
 717 {
 718    void *old;
 719
 720    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 721
 722    /* Max size reached so return FALSE */
 723    if ((ecore_prime_table[hash->size] == PRIME_MAX) ||
 724        (hash->size == PRIME_TABLE_MAX))
 725       return FALSE;
 726
 727    /*
 728     * Increase the size of the hash and save a pointer to the old data
 729     */
 730    hash->size++;
 731    old = hash->buckets;
 732
 733    /*
 734     * Allocate a new bucket area, of the new larger size
 735     */
 736    hash->buckets =
 737       calloc(ecore_prime_table[hash->size], sizeof(Ecore_Hash_Node *));
 738
 739    /*
 740     * Make sure the allocation succeeded, if not replace the old data and
 741     * return a failure.
 742     */
 743    if (!hash->buckets)
 744      {
 745         hash->buckets = old;
 746         hash->size--;
 747         return FALSE;
 748      }
 749
 750    hash->nodes = 0;
 751
 752    /*
 753     * Now move all of the old data into the new bucket area
 754     */
 755    if (_ecore_hash_rehash(hash, old, hash->size - 1))
 756      {
 757         FREE(old);
 758         return TRUE;
 759      }
 760
 761    /*
 762     * Free the old buckets regardless of success.
 763     */
 764         FREE(old);
 765
 766    return FALSE;
 767 }
 768
 769 /*
 770  * @brief Decrease the size of the hash table by < 1/2 * current size
 771  * @param hash: the hash table to decrease the size of
 772  * @return Returns TRUE on success, FALSE on error
 773  */
 774 static int
 775 _ecore_hash_decrease(Ecore_Hash *hash)
 776 {
 777    Ecore_Hash_Node **old;
 778
 779    CHECK_PARAM_POINTER_RETURN("hash", hash, FALSE);
 780
 781    if (ecore_prime_table[hash->size] == PRIME_MIN)
 782       return FALSE;
 783
 784    /*
 785     * Decrease the hash size and store a pointer to the old data
 786     */
 787    hash->size--;
 788    old = hash->buckets;
 789
 790    /*
 791     * Allocate a new area to store the data
 792     */
 793    hash->buckets = (Ecore_Hash_Node **)calloc(ecore_prime_table[hash->size],
 794                                               sizeof(Ecore_Hash_Node *));
 795
 796    /*
 797     * Make sure allocation succeeded otherwise rreturn to the previous
 798     * state
 799     */
 800    if (!hash->buckets)
 801      {
 802         hash->buckets = old;
 803         hash->size++;
 804         return FALSE;
 805      }
 806
 807    hash->nodes = 0;
 808
 809    if (_ecore_hash_rehash(hash, old, hash->size + 1))
 810      {
 811         FREE(old);
 812         return TRUE;
 813      }
 814
 815    return FALSE;
 816 }
 817
 818 /*
 819  * @brief Rehash the nodes of a table into the hash table
 820  * @param hash: the hash to place the nodes of the table
 821  * @param table: the table to remove the nodes from and place in hash
 822  * @return Returns TRUE on success, FALSE on error
 823  */
 824 static inline int
 825 _ecore_hash_rehash(Ecore_Hash *hash, Ecore_Hash_Node **old_table, int old_size)
 826 {
 827    unsigned int i;
 828    Ecore_Hash_Node *old;
 829
 830    CHECK_PARAM_POINTER_RETURN("hash",      hash,      FALSE);
 831    CHECK_PARAM_POINTER_RETURN("old_table", old_table, FALSE);
 832
 833    for (i = 0; i < ecore_prime_table[old_size]; i++)
 834      {
 835         /* Hash into a new list to avoid loops of rehashing the same nodes */
 836         while ((old = old_table[i]))
 837           {
 838              old_table[i] = old->next;
 839              old->next = NULL;
 840              _ecore_hash_node_add(hash, old);
 841           }
 842      }
 843
 844    return TRUE;
 845 }
 846
 847 /*
 848  * @brief Create a new hash node for key and value storage
 849  * @param key: the key for this node
 850  * @param value: the value that the key references
 851  * @return Returns NULL on error, a new hash node on success
 852  */
 853 static Ecore_Hash_Node *
 854 _ecore_hash_node_new(void *key, void *value)
 855 {
 856    Ecore_Hash_Node *node;
 857
 858    node = (Ecore_Hash_Node *)malloc(sizeof(Ecore_Hash_Node));
 859    if (!node)
 860       return NULL;
 861
 862    if (!_ecore_hash_node_init(node, key, value))
 863      {
 864         FREE(node);
 865         return NULL;
 866      }
 867
 868    return node;
 869 }
 870
 871 /*
 872  * @brief Initialize a hash node to some sane default values
 873  * @param node: the node to set the values
 874  * @param key: the key to reference this node
 875  * @param value: the value that key refers to
 876  * @return Returns TRUE on success, FALSE on error
 877  */
 878 static int
 879 _ecore_hash_node_init(Ecore_Hash_Node *node, void *key, void *value)
 880 {
 881       CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 882
 883    node->key = key;
 884    node->value = value;
 885
 886    return TRUE;
 887 }
 888
 889 /*
 890  * @brief Destroy a node and call the specified callbacks to free data
 891  * @param node: the node to be destroyed
 892  * @param keyd: the function to free the key
 893  * @param valued: the function  to free the value
 894  * @return Returns TRUE on success, FALSE on error
 895  */
 896 static int
 897 _ecore_hash_node_destroy(Ecore_Hash_Node *node,
 898                          Ecore_Free_Cb keyd,
 899                          Ecore_Free_Cb valued)
 900 {
 901       CHECK_PARAM_POINTER_RETURN("node", node, FALSE);
 902
 903    if (keyd)
 904       keyd(node->key);
 905
 906    if (valued)
 907       valued(node->value);
 908
 909    FREE(node);
 910
 911    return TRUE;
 912 }
 913
 914 int
 915 ecore_str_compare(const void *key1, const void *key2)
 916 {
 917    const char *k1, *k2;
 918
 919    if (!key1 || !key2)
 920       return ecore_direct_compare(key1, key2);
 921    else if (key1 == key2)
 922       return 0;
 923
 924    k1 = key1;
 925    k2 = key2;
 926
 927    return strcmp(k1, k2);
 928 }
 929
 930 unsigned int
 931 ecore_str_hash(const void *key)
 932 {
 933    int i;
 934    unsigned int mask;
 935    unsigned int value = 0;
 936    const char *k = key;
 937
 938    if (!k)
 939       return 0;
 940
 941    mask = (sizeof(unsigned int) * 8) - 1;
 942
 943    for (i = 0; k[i] != '\0'; i++)
 944      {
 945         value ^= ((unsigned int)k[i] << ((i * 5) & mask));
 946      }
 947
 948    return value;
 949 }