src/lib/ecore/ecore_hash.c

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