src/lib/eina/eina_hash.c

   1 /* EINA - EFL data type library
   2  * Copyright (C) 2002-2008 Carsten Haitzler, Gustavo Sverzut Barbieri,
   3  *                         Vincent Torri, Jorge Luis Zapata Muga, Cedric Bail
   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 <stdio.h>
  25 #include <stdlib.h>
  26 #include <stdint.h>
  27 #include <string.h>
  28
  29 #include "eina_config.h"
  30 #include "eina_private.h"
  31 #include "eina_rbtree.h"
  32
  33 /* undefs EINA_ARG_NONULL() so NULL checks are not compiled out! */
  34 #include "eina_safety_checks.h"
  35 #include "eina_hash.h"
  36 #include "eina_list.h"
  37
  38 /*============================================================================*
  39 *                                  Local                                     *
  40 *============================================================================*/
  41
  42 /**
  43  * @cond LOCAL
  44  */
  45
  46 #define EINA_MAGIC_CHECK_HASH(d)                    \
  47   do {                                              \
  48        if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_HASH)) { \
  49             EINA_MAGIC_FAIL(d, EINA_MAGIC_HASH); }  \
  50     } while (0)
  51
  52 #define EINA_MAGIC_CHECK_HASH_ITERATOR(d, ...)             \
  53   do {                                                     \
  54        if (!EINA_MAGIC_CHECK(d, EINA_MAGIC_HASH_ITERATOR)) \
  55          {                                                 \
  56             EINA_MAGIC_FAIL(d, EINA_MAGIC_HASH_ITERATOR);  \
  57             return __VA_ARGS__;                            \
  58          }                                                 \
  59     } while (0)
  60
  61 #define EINA_HASH_BUCKET_SIZE       8
  62 #define EINA_HASH_SMALL_BUCKET_SIZE 5
  63
  64 #define EINA_HASH_RBTREE_MASK       0xFFFF
  65
  66 typedef struct _Eina_Hash_Head         Eina_Hash_Head;
  67 typedef struct _Eina_Hash_Element      Eina_Hash_Element;
  68 typedef struct _Eina_Hash_Foreach_Data Eina_Hash_Foreach_Data;
  69 typedef struct _Eina_Iterator_Hash     Eina_Iterator_Hash;
  70 typedef struct _Eina_Hash_Each         Eina_Hash_Each;
  71
  72 struct _Eina_Hash
  73 {
  74    Eina_Key_Length key_length_cb;
  75    Eina_Key_Cmp    key_cmp_cb;
  76    Eina_Key_Hash   key_hash_cb;
  77    Eina_Free_Cb    data_free_cb;
  78
  79    Eina_Rbtree   **buckets;
  80    int             size;
  81    int             mask;
  82
  83    int             population;
  84
  85    int             buckets_power_size;
  86
  87    EINA_MAGIC
  88 };
  89
  90 struct _Eina_Hash_Head
  91 {
  92    EINA_RBTREE;
  93
  94    Eina_Rbtree *head;
  95
  96    int          hash;
  97 };
  98
  99 struct _Eina_Hash_Element
 100 {
 101    EINA_RBTREE;
 102    Eina_Hash_Tuple tuple;
 103 };
 104
 105 struct _Eina_Hash_Foreach_Data
 106 {
 107    Eina_Hash_Foreach cb;
 108    const void       *fdata;
 109 };
 110
 111 typedef void *(*Eina_Iterator_Get_Content_Callback)(Eina_Iterator_Hash *it);
 112 #define FUNC_ITERATOR_GET_CONTENT(Function) \
 113   ((Eina_Iterator_Get_Content_Callback)Function)
 114
 115 struct _Eina_Iterator_Hash
 116 {
 117    Eina_Iterator                      iterator;
 118
 119    Eina_Iterator_Get_Content_Callback get_content;
 120    const Eina_Hash                   *hash;
 121
 122    Eina_Iterator                     *current;
 123    Eina_Iterator                     *list;
 124    Eina_Hash_Head                    *hash_head;
 125    Eina_Hash_Element                 *hash_element;
 126    int                                bucket;
 127
 128    int                                index;
 129
 130    EINA_MAGIC
 131 };
 132
 133 struct _Eina_Hash_Each
 134 {
 135    Eina_Hash_Head          *hash_head;
 136    const Eina_Hash_Element *hash_element;
 137    const void              *data;
 138 };
 139
 140 #undef get16bits
 141 #if (defined(__GNUC__) && defined(__i386__)) || defined(__WATCOMC__) \
 142   || defined (__BORLANDC__) || defined (__TURBOC__)
 143 # define get16bits(d) (*((const uint16_t *)(d)))
 144 #endif
 145
 146 #if !defined (get16bits)
 147 # define get16bits(d) ((((uint32_t)(((const uint8_t *)(d))[1])) << 8) \
 148                        + (uint32_t)(((const uint8_t *)(d))[0]))
 149 #endif
 150
 151 static inline int
 152 _eina_hash_hash_rbtree_cmp_hash(const Eina_Hash_Head *hash_head,
 153                                 const int *hash,
 154                                 EINA_UNUSED int key_length,
 155                                 EINA_UNUSED void *data)
 156 {
 157    return hash_head->hash - *hash;
 158 }
 159
 160 static Eina_Rbtree_Direction
 161 _eina_hash_hash_rbtree_cmp_node(const Eina_Hash_Head *left,
 162                                 const Eina_Hash_Head *right,
 163                                 EINA_UNUSED void *data)
 164 {
 165    if (left->hash - right->hash < 0)
 166      return EINA_RBTREE_LEFT;
 167
 168    return EINA_RBTREE_RIGHT;
 169 }
 170
 171 static inline int
 172 _eina_hash_key_rbtree_cmp_key_data(const Eina_Hash_Element *hash_element,
 173                                    const Eina_Hash_Tuple *tuple,
 174                                    EINA_UNUSED unsigned int key_length,
 175                                    Eina_Key_Cmp cmp)
 176 {
 177    int result;
 178
 179    result = cmp(hash_element->tuple.key,
 180                 hash_element->tuple.key_length,
 181                 tuple->key,
 182                 tuple->key_length);
 183
 184    if (result == 0 && tuple->data && tuple->data != hash_element->tuple.data)
 185      return 1;
 186
 187    return result;
 188 }
 189
 190 static Eina_Rbtree_Direction
 191 _eina_hash_key_rbtree_cmp_node(const Eina_Hash_Element *left,
 192                                const Eina_Hash_Element *right,
 193                                Eina_Key_Cmp cmp)
 194 {
 195    int result;
 196
 197    result = cmp(left->tuple.key, left->tuple.key_length,
 198                 right->tuple.key, right->tuple.key_length);
 199
 200    if (result < 0)
 201      return EINA_RBTREE_LEFT;
 202
 203    return EINA_RBTREE_RIGHT;
 204 }
 205
 206 static inline Eina_Bool
 207 eina_hash_add_alloc_by_hash(Eina_Hash *hash,
 208                             const void *key, int key_length, int alloc_length,
 209                             int key_hash,
 210                             const void *data)
 211 {
 212    Eina_Hash_Element *new_hash_element = NULL;
 213    Eina_Hash_Head *hash_head;
 214    int hash_num;
 215
 216    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 217    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 218    EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
 219    EINA_MAGIC_CHECK_HASH(hash);
 220
 221    /* Apply eina mask to hash. */
 222    hash_num = key_hash & hash->mask;
 223    key_hash >>= hash->buckets_power_size;
 224    key_hash &= EINA_HASH_RBTREE_MASK;
 225
 226    if (!hash->buckets)
 227      {
 228         hash->buckets = calloc(sizeof (Eina_Rbtree *), hash->size);
 229         if (!hash->buckets) goto on_error;
 230
 231         hash_head = NULL;
 232      }
 233    else
 234      /* Look up for head node. */
 235      hash_head = (Eina_Hash_Head *)
 236        eina_rbtree_inline_lookup(hash->buckets[hash_num],
 237                                  &key_hash, 0,
 238                                  EINA_RBTREE_CMP_KEY_CB(
 239                                    _eina_hash_hash_rbtree_cmp_hash),
 240                                  NULL);
 241
 242    if (!hash_head)
 243      {
 244         /* If not found allocate it and an element. */
 245         hash_head = malloc(sizeof(Eina_Hash_Head));
 246         if (!hash_head)
 247           goto on_error;
 248
 249         hash_head->hash = key_hash;
 250         hash_head->head = NULL;
 251
 252         hash->buckets[hash_num] =
 253           eina_rbtree_inline_insert(hash->buckets[hash_num],
 254                                     EINA_RBTREE_GET(hash_head),
 255                                     EINA_RBTREE_CMP_NODE_CB(
 256                                       _eina_hash_hash_rbtree_cmp_node),
 257                                     NULL);
 258      }
 259
 260    /*
 261      Alloc a new element
 262      (No more lookup as we expect to support more than one item for one key).
 263    */
 264    new_hash_element = malloc(sizeof (Eina_Hash_Element) + alloc_length);
 265    if (!new_hash_element)
 266      goto on_error;
 267
 268    /* Setup the element */
 269    new_hash_element->tuple.key_length = key_length;
 270    new_hash_element->tuple.data = (void *)data;
 271    if (alloc_length > 0)
 272      {
 273         new_hash_element->tuple.key = (char *)(new_hash_element + 1);
 274         memcpy((char *)new_hash_element->tuple.key, key, alloc_length);
 275      }
 276    else
 277      new_hash_element->tuple.key = key;
 278
 279    /* add the new element to the hash. */
 280    hash_head->head = eina_rbtree_inline_insert(hash_head->head,
 281                                                EINA_RBTREE_GET(new_hash_element),
 282                                                EINA_RBTREE_CMP_NODE_CB(
 283                                                  _eina_hash_key_rbtree_cmp_node),
 284                                                (const void *)hash->key_cmp_cb);
 285    hash->population++;
 286    return EINA_TRUE;
 287
 288 on_error:
 289    return EINA_FALSE;
 290 }
 291
 292 static Eina_Bool
 293 _eina_hash_rbtree_each(EINA_UNUSED const Eina_Rbtree *container,
 294                        const Eina_Hash_Head *hash_head,
 295                        Eina_Hash_Each *data)
 296 {
 297    Eina_Iterator *it;
 298    Eina_Hash_Element *hash_element;
 299    Eina_Bool found = EINA_TRUE;
 300
 301    it = eina_rbtree_iterator_prefix(hash_head->head);
 302    EINA_ITERATOR_FOREACH(it, hash_element)
 303      {
 304         if (hash_element->tuple.data == data->data)
 305           {
 306              data->hash_element = hash_element;
 307              data->hash_head = (Eina_Hash_Head *)hash_head;
 308              found = EINA_FALSE;
 309              break;
 310           }
 311      }
 312
 313    eina_iterator_free(it);
 314    return found;
 315 }
 316
 317 static inline Eina_Hash_Element *
 318 _eina_hash_find_by_hash(const Eina_Hash *hash,
 319                         Eina_Hash_Tuple *tuple,
 320                         int key_hash,
 321                         Eina_Hash_Head **hash_head)
 322 {
 323    Eina_Hash_Element *hash_element;
 324    int rb_hash = (key_hash >> hash->buckets_power_size)
 325      & EINA_HASH_RBTREE_MASK;
 326
 327    key_hash &= hash->mask;
 328
 329    if (!hash->buckets)
 330      return NULL;
 331
 332    *hash_head = (Eina_Hash_Head *)
 333      eina_rbtree_inline_lookup(hash->buckets[key_hash],
 334                                &rb_hash, 0,
 335                                EINA_RBTREE_CMP_KEY_CB(
 336                                  _eina_hash_hash_rbtree_cmp_hash),
 337                                NULL);
 338    if (!*hash_head)
 339      return NULL;
 340
 341    hash_element = (Eina_Hash_Element *)
 342      eina_rbtree_inline_lookup((*hash_head)->head,
 343                                tuple, 0,
 344                                EINA_RBTREE_CMP_KEY_CB(
 345                                  _eina_hash_key_rbtree_cmp_key_data),
 346                                (const void *)hash->key_cmp_cb);
 347
 348    return hash_element;
 349 }
 350
 351 static inline Eina_Hash_Element *
 352 _eina_hash_find_by_data(const Eina_Hash *hash,
 353                         const void *data,
 354                         int *key_hash,
 355                         Eina_Hash_Head **hash_head)
 356 {
 357    Eina_Hash_Each each;
 358    Eina_Iterator *it;
 359    int hash_num;
 360
 361    if (!hash->buckets)
 362      return NULL;
 363
 364    each.hash_element = NULL;
 365    each.data = data;
 366
 367    for (hash_num = 0; hash_num < hash->size; hash_num++)
 368      {
 369         if (!hash->buckets[hash_num])
 370           continue;
 371
 372         it = eina_rbtree_iterator_prefix(hash->buckets[hash_num]);
 373         eina_iterator_foreach(it, EINA_EACH_CB(_eina_hash_rbtree_each), &each);
 374         eina_iterator_free(it);
 375
 376         if (each.hash_element)
 377           {
 378              *key_hash = hash_num;
 379              *hash_head = each.hash_head;
 380              return (Eina_Hash_Element *)each.hash_element;
 381           }
 382      }
 383
 384    return NULL;
 385 }
 386
 387 static void
 388 _eina_hash_el_free(Eina_Hash_Element *hash_element, Eina_Hash *hash)
 389 {
 390    if (hash->data_free_cb)
 391      hash->data_free_cb(hash_element->tuple.data);
 392
 393    free(hash_element);
 394 }
 395
 396 static void
 397 _eina_hash_head_free(Eina_Hash_Head *hash_head, Eina_Hash *hash)
 398 {
 399    eina_rbtree_delete(hash_head->head, EINA_RBTREE_FREE_CB(_eina_hash_el_free), hash);
 400    free(hash_head);
 401 }
 402
 403 static Eina_Bool
 404 _eina_hash_del_by_hash_el(Eina_Hash *hash,
 405                           Eina_Hash_Element *hash_element,
 406                           Eina_Hash_Head *hash_head,
 407                           int key_hash)
 408 {
 409    hash_head->head = eina_rbtree_inline_remove(hash_head->head, EINA_RBTREE_GET(
 410                                                  hash_element), EINA_RBTREE_CMP_NODE_CB(
 411                                                  _eina_hash_key_rbtree_cmp_node),
 412                                                (const void *)hash->key_cmp_cb);
 413
 414    if (!hash_head->head)
 415      {
 416         key_hash &= hash->mask;
 417
 418         hash->buckets[key_hash] =
 419           eina_rbtree_inline_remove(hash->buckets[key_hash], EINA_RBTREE_GET(
 420                                       hash_head),
 421                                     EINA_RBTREE_CMP_NODE_CB(
 422                                       _eina_hash_hash_rbtree_cmp_node), NULL);
 423         free(hash_head);
 424      }
 425
 426    hash->population--;
 427    if (hash->population == 0)
 428      {
 429         free(hash->buckets);
 430         hash->buckets = NULL;
 431      }
 432
 433    _eina_hash_el_free(hash_element, hash);
 434
 435    return EINA_TRUE;
 436 }
 437
 438 static Eina_Bool
 439 _eina_hash_del_by_key_hash(Eina_Hash *hash,
 440                            const void *key,
 441                            int key_length,
 442                            int key_hash,
 443                            const void *data)
 444 {
 445    Eina_Hash_Element *hash_element;
 446    Eina_Hash_Head *hash_head;
 447    Eina_Hash_Tuple tuple;
 448
 449    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 450    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 451    EINA_MAGIC_CHECK_HASH(hash);
 452
 453    if (!hash->buckets)
 454      return EINA_FALSE;
 455
 456    tuple.key = (void *)key;
 457    tuple.key_length = key_length;
 458    tuple.data = (void *)data;
 459
 460    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
 461    if (!hash_element)
 462      return EINA_FALSE;
 463
 464    return _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash);
 465 }
 466
 467 static void
 468 _eina_hash_compute(const Eina_Hash *hash, const void *key, int *key_length, int *key_hash)
 469 {
 470    *key_length = hash->key_length_cb ? hash->key_length_cb(key) : 0;
 471    *key_hash = hash->key_hash_cb(key, *key_length);
 472 }
 473
 474 static Eina_Bool
 475 _eina_hash_del_by_key(Eina_Hash *hash, const void *key, const void *data)
 476 {
 477    int key_length, key_hash;
 478
 479    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 480    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 481    EINA_MAGIC_CHECK_HASH(hash);
 482
 483    if (!hash->buckets)
 484      return EINA_FALSE;
 485
 486    _eina_hash_compute(hash, key, &key_length, &key_hash);
 487    return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data);
 488 }
 489
 490 static int
 491 _eina_stringshared_hash(const void *key, int key_length EINA_UNUSED)
 492 {
 493    return eina_hash_superfast((const void*) &key, sizeof (void*));
 494 }
 495
 496 static unsigned int
 497 _eina_string_key_length(const char *key)
 498 {
 499    if (!key)
 500      return 0;
 501
 502    return (int)strlen(key) + 1;
 503 }
 504
 505 static int
 506 _eina_string_key_cmp(const char *key1, int key1_length,
 507                      const char *key2, int key2_length)
 508 {
 509    int delta;
 510
 511    delta = key1_length - key2_length;
 512    if (delta) return delta;
 513    return strcmp(key1, key2);
 514 }
 515
 516 static int
 517 _eina_stringshared_key_cmp(const char *key1, EINA_UNUSED int key1_length,
 518                            const char *key2, EINA_UNUSED int key2_length)
 519 {
 520 // logically we want to do this:
 521 //   return key1 - key2;
 522 // but since they are ptrs and an int can't store the different of 2 ptrs in
 523 // either 32 or 64bit (signed hasn't got enough range for the diff of 2
 524 // 32bit values regardless of their type... we'd need 33bits or 65bits)
 525 // so do this...
 526    if (key1 == key2) return 0;
 527    if (key1 > key2) return 1;
 528    return -1;
 529 // NOTE: this seems odd. we don't sort by string content at all... we sort
 530 // by pointer location in memory. this seems odd at first, BUT this does
 531 // work because with stringshare each ptr holds a unique string and we
 532 // cannot have 2 ptrs in stringshare have the same string content thus we
 533 // can't go wrong and have 2 ptrs be different yet the string key be the
 534 // same, thus we can avoid walking the string, so sorting by ptr value is
 535 // frankly as good as anything. :) (this is only within the bucket too)
 536 }
 537
 538 static unsigned int
 539 _eina_int32_key_length(EINA_UNUSED const uint32_t *key)
 540 {
 541    return 4;
 542 }
 543
 544 static int
 545 _eina_int32_key_cmp(const uint32_t *key1, EINA_UNUSED int key1_length,
 546                     const uint32_t *key2, EINA_UNUSED int key2_length)
 547 {
 548    if (*key1 == *key2) return 0;
 549    if (*key1 > *key2) return 1;
 550    return -1;
 551 }
 552
 553 static unsigned int
 554 _eina_int64_key_length(EINA_UNUSED const uint64_t *key)
 555 {
 556    return sizeof(int64_t);
 557 }
 558
 559 static int
 560 _eina_int64_key_cmp(const uint64_t *key1, EINA_UNUSED int key1_length,
 561                     const uint64_t *key2, EINA_UNUSED int key2_length)
 562 {
 563    if (*key1 == *key2) return 0;
 564    if (*key1 > *key2) return 1;
 565    return -1;
 566 }
 567
 568 static Eina_Bool
 569 _eina_foreach_cb(const Eina_Hash *hash,
 570                  Eina_Hash_Tuple *data,
 571                  Eina_Hash_Foreach_Data *fdata)
 572 {
 573    return fdata->cb((Eina_Hash *)hash,
 574                     data->key,
 575                     data->data,
 576                     (void *)fdata->fdata);
 577 }
 578
 579 static void *
 580 _eina_hash_iterator_data_get_content(Eina_Iterator_Hash *it)
 581 {
 582    Eina_Hash_Element *stuff;
 583
 584    EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
 585
 586    stuff = it->hash_element;
 587
 588    if (!stuff)
 589      return NULL;
 590
 591    return stuff->tuple.data;
 592 }
 593
 594 static void *
 595 _eina_hash_iterator_key_get_content(Eina_Iterator_Hash *it)
 596 {
 597    Eina_Hash_Element *stuff;
 598
 599    EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
 600
 601    stuff = it->hash_element;
 602
 603    if (!stuff)
 604      return NULL;
 605
 606    return (void *)stuff->tuple.key;
 607 }
 608
 609 static Eina_Hash_Tuple *
 610 _eina_hash_iterator_tuple_get_content(Eina_Iterator_Hash *it)
 611 {
 612    Eina_Hash_Element *stuff;
 613
 614    EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
 615
 616    stuff = it->hash_element;
 617
 618    if (!stuff)
 619      return NULL;
 620
 621    return &stuff->tuple;
 622 }
 623
 624 static Eina_Bool
 625 _eina_hash_iterator_next(Eina_Iterator_Hash *it, void **data)
 626 {
 627    Eina_Bool ok;
 628    int bucket;
 629
 630    if (!(it->index < it->hash->population))
 631      return EINA_FALSE;
 632
 633    if (!it->current)
 634      {
 635         ok = EINA_FALSE;
 636         bucket = 0;
 637         it->index = -1;
 638      }
 639    else
 640      {
 641         ok = eina_iterator_next(it->list, (void **)(void *)&it->hash_element);
 642         if (!ok)
 643           {
 644              eina_iterator_free(it->list);
 645              it->list = NULL;
 646
 647              ok = eina_iterator_next(it->current, (void **)(void *)&it->hash_head);
 648              if (!ok)
 649                {
 650                   eina_iterator_free(it->current);
 651                   it->current = NULL;
 652                   it->bucket++;
 653                }
 654              else
 655                {
 656                   it->list = eina_rbtree_iterator_prefix(it->hash_head->head);
 657                   ok = eina_iterator_next(it->list, (void **)(void *)&it->hash_element);
 658                }
 659           }
 660
 661         bucket = it->bucket;
 662      }
 663
 664    if (ok == EINA_FALSE)
 665      {
 666         while (bucket < it->hash->size)
 667           {
 668              if (it->hash->buckets[bucket])
 669                {
 670                   it->current =
 671                     eina_rbtree_iterator_prefix(it->hash->buckets[bucket]);
 672                   ok = eina_iterator_next(it->current, (void **)(void *)&it->hash_head);
 673                   if (ok)
 674                     break;
 675
 676                   eina_iterator_free(it->current);
 677                   it->current = NULL;
 678                }
 679
 680              ++bucket;
 681           }
 682         if (it->list)
 683           eina_iterator_free(it->list);
 684
 685         it->list = eina_rbtree_iterator_prefix(it->hash_head->head);
 686         ok = eina_iterator_next(it->list, (void **)(void *)&it->hash_element);
 687         if (bucket == it->hash->size)
 688           ok = EINA_FALSE;
 689      }
 690
 691    it->index++;
 692    it->bucket = bucket;
 693
 694    if (ok)
 695      *data = it->get_content(it);
 696
 697    return ok;
 698 }
 699
 700 static void *
 701 _eina_hash_iterator_get_container(Eina_Iterator_Hash *it)
 702 {
 703    EINA_MAGIC_CHECK_HASH_ITERATOR(it, NULL);
 704    return (void *)it->hash;
 705 }
 706
 707 static void
 708 _eina_hash_iterator_free(Eina_Iterator_Hash *it)
 709 {
 710    EINA_MAGIC_CHECK_HASH_ITERATOR(it);
 711    if (it->current)
 712      eina_iterator_free(it->current);
 713
 714    if (it->list)
 715      eina_iterator_free(it->list);
 716
 717    free(it);
 718 }
 719
 720 /**
 721  * @endcond
 722  */
 723
 724 /*============================================================================*
 725 *                                 Global                                     *
 726 *============================================================================*/
 727
 728 /*============================================================================*
 729 *                                   API                                      *
 730 *============================================================================*/
 731
 732 EAPI void
 733 eina_hash_free_cb_set(Eina_Hash *hash, Eina_Free_Cb data_free_cb)
 734 {
 735    EINA_MAGIC_CHECK_HASH(hash);
 736    EINA_SAFETY_ON_NULL_RETURN(hash);
 737
 738    hash->data_free_cb = data_free_cb;
 739 }
 740
 741 EAPI Eina_Hash *
 742 eina_hash_new(Eina_Key_Length key_length_cb,
 743               Eina_Key_Cmp key_cmp_cb,
 744               Eina_Key_Hash key_hash_cb,
 745               Eina_Free_Cb data_free_cb,
 746               int buckets_power_size)
 747 {
 748    /* FIXME: Use mempool. */
 749    Eina_Hash *new;
 750
 751    EINA_SAFETY_ON_NULL_RETURN_VAL(key_cmp_cb, NULL);
 752    EINA_SAFETY_ON_NULL_RETURN_VAL(key_hash_cb, NULL);
 753    EINA_SAFETY_ON_TRUE_RETURN_VAL(buckets_power_size <= 2, NULL);
 754    EINA_SAFETY_ON_TRUE_RETURN_VAL(buckets_power_size >= 17, NULL);
 755
 756    new = malloc(sizeof (Eina_Hash));
 757    if (!new)
 758      goto on_error;
 759
 760    EINA_MAGIC_SET(new, EINA_MAGIC_HASH);
 761
 762    new->key_length_cb = key_length_cb;
 763    new->key_cmp_cb = key_cmp_cb;
 764    new->key_hash_cb = key_hash_cb;
 765    new->data_free_cb = data_free_cb;
 766    new->buckets = NULL;
 767    new->population = 0;
 768
 769    new->size = 1 << buckets_power_size;
 770    new->mask = new->size - 1;
 771    new->buckets_power_size = buckets_power_size;
 772
 773    return new;
 774
 775 on_error:
 776    return NULL;
 777 }
 778
 779 EAPI Eina_Hash *
 780 eina_hash_string_djb2_new(Eina_Free_Cb data_free_cb)
 781 {
 782    return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
 783                         EINA_KEY_CMP(_eina_string_key_cmp),
 784                         EINA_KEY_HASH(eina_hash_djb2),
 785                         data_free_cb,
 786                         EINA_HASH_BUCKET_SIZE);
 787 }
 788
 789 EAPI Eina_Hash *
 790 eina_hash_string_superfast_new(Eina_Free_Cb data_free_cb)
 791 {
 792    return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
 793                         EINA_KEY_CMP(_eina_string_key_cmp),
 794                         EINA_KEY_HASH(eina_hash_superfast),
 795                         data_free_cb,
 796                         EINA_HASH_BUCKET_SIZE);
 797 }
 798
 799 EAPI Eina_Hash *
 800 eina_hash_string_small_new(Eina_Free_Cb data_free_cb)
 801 {
 802    return eina_hash_new(EINA_KEY_LENGTH(_eina_string_key_length),
 803                         EINA_KEY_CMP(_eina_string_key_cmp),
 804                         EINA_KEY_HASH(eina_hash_superfast),
 805                         data_free_cb,
 806                         EINA_HASH_SMALL_BUCKET_SIZE);
 807 }
 808
 809 EAPI Eina_Hash *
 810 eina_hash_int32_new(Eina_Free_Cb data_free_cb)
 811 {
 812    return eina_hash_new(EINA_KEY_LENGTH(_eina_int32_key_length),
 813                         EINA_KEY_CMP(_eina_int32_key_cmp),
 814                         EINA_KEY_HASH(eina_hash_int32),
 815                         data_free_cb,
 816                         EINA_HASH_BUCKET_SIZE);
 817 }
 818
 819 EAPI Eina_Hash *
 820 eina_hash_int64_new(Eina_Free_Cb data_free_cb)
 821 {
 822    return eina_hash_new(EINA_KEY_LENGTH(_eina_int64_key_length),
 823                         EINA_KEY_CMP(_eina_int64_key_cmp),
 824                         EINA_KEY_HASH(eina_hash_int64),
 825                         data_free_cb,
 826                         EINA_HASH_BUCKET_SIZE);
 827 }
 828
 829 EAPI Eina_Hash *
 830 eina_hash_pointer_new(Eina_Free_Cb data_free_cb)
 831 {
 832 #ifdef EFL64
 833    return eina_hash_new(EINA_KEY_LENGTH(_eina_int64_key_length),
 834                         EINA_KEY_CMP(_eina_int64_key_cmp),
 835                         EINA_KEY_HASH(eina_hash_int64),
 836                         data_free_cb,
 837                         EINA_HASH_BUCKET_SIZE);
 838 #else
 839    return eina_hash_new(EINA_KEY_LENGTH(_eina_int32_key_length),
 840                         EINA_KEY_CMP(_eina_int32_key_cmp),
 841                         EINA_KEY_HASH(eina_hash_int32),
 842                         data_free_cb,
 843                         EINA_HASH_BUCKET_SIZE);
 844 #endif
 845 }
 846
 847 EAPI Eina_Hash *
 848 eina_hash_stringshared_new(Eina_Free_Cb data_free_cb)
 849 {
 850    return eina_hash_new(NULL,
 851                         EINA_KEY_CMP(_eina_stringshared_key_cmp),
 852                         EINA_KEY_HASH(_eina_stringshared_hash),
 853                         data_free_cb,
 854                         EINA_HASH_BUCKET_SIZE);
 855 }
 856
 857 EAPI int
 858 eina_hash_population(const Eina_Hash *hash)
 859 {
 860    if (!hash)
 861      return 0;
 862
 863    EINA_MAGIC_CHECK_HASH(hash);
 864    return hash->population;
 865 }
 866
 867 EAPI void
 868 eina_hash_free(Eina_Hash *hash)
 869 {
 870    int i;
 871
 872    if (!hash) return;
 873
 874    EINA_MAGIC_CHECK_HASH(hash);
 875
 876    if (hash->buckets)
 877      {
 878         for (i = 0; i < hash->size; i++)
 879           eina_rbtree_delete(hash->buckets[i], EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash);
 880         free(hash->buckets);
 881      }
 882    free(hash);
 883 }
 884
 885 EAPI void
 886 eina_hash_free_buckets(Eina_Hash *hash)
 887 {
 888    int i;
 889
 890    if (!hash) return;
 891
 892    EINA_MAGIC_CHECK_HASH(hash);
 893
 894    if (hash->buckets)
 895      {
 896         for (i = 0; i < hash->size; i++)
 897           eina_rbtree_delete(hash->buckets[i],
 898                              EINA_RBTREE_FREE_CB(_eina_hash_head_free), hash);
 899         free(hash->buckets);
 900         hash->buckets = NULL;
 901         hash->population = 0;
 902      }
 903 }
 904
 905 EAPI Eina_Bool
 906 eina_hash_add_by_hash(Eina_Hash *hash,
 907                       const void *key,
 908                       int key_length,
 909                       int key_hash,
 910                       const void *data)
 911 {
 912    return eina_hash_add_alloc_by_hash(hash,
 913                                       key,
 914                                       key_length,
 915                                       key_length,
 916                                       key_hash,
 917                                       data);
 918 }
 919
 920 EAPI Eina_Bool
 921 eina_hash_direct_add_by_hash(Eina_Hash *hash,
 922                              const void *key,
 923                              int key_length,
 924                              int key_hash,
 925                              const void *data)
 926 {
 927    return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data);
 928 }
 929
 930 EAPI Eina_Bool
 931 eina_hash_add(Eina_Hash *hash, const void *key, const void *data)
 932 {
 933    int key_length;
 934    int key_hash;
 935
 936    EINA_MAGIC_CHECK_HASH(hash);
 937    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 938    EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
 939    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 940    EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
 941
 942    _eina_hash_compute(hash, key, &key_length, &key_hash);
 943
 944    return eina_hash_add_alloc_by_hash(hash, key, key_length, key_length, key_hash, data);
 945 }
 946
 947 EAPI Eina_Bool
 948 eina_hash_direct_add(Eina_Hash *hash, const void *key, const void *data)
 949 {
 950    int key_length;
 951    int key_hash;
 952
 953    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 954    EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
 955    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 956    EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
 957    EINA_MAGIC_CHECK_HASH(hash);
 958
 959    _eina_hash_compute(hash, key, &key_length, &key_hash);
 960
 961    return eina_hash_add_alloc_by_hash(hash, key, key_length, 0, key_hash, data);
 962 }
 963
 964 EAPI Eina_Bool
 965 eina_hash_del_by_key_hash(Eina_Hash *hash,
 966                           const void *key,
 967                           int key_length,
 968                           int key_hash)
 969 {
 970    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 971    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 972
 973    return _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, NULL);
 974 }
 975
 976 EAPI Eina_Bool
 977 eina_hash_del_by_key(Eina_Hash *hash, const void *key)
 978 {
 979    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 980    EINA_SAFETY_ON_NULL_RETURN_VAL(key, EINA_FALSE);
 981
 982    return _eina_hash_del_by_key(hash, key, NULL);
 983 }
 984
 985 EAPI Eina_Bool
 986 eina_hash_del_by_data(Eina_Hash *hash, const void *data)
 987 {
 988    Eina_Hash_Element *hash_element;
 989    Eina_Hash_Head *hash_head;
 990    int key_hash;
 991
 992    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
 993    EINA_SAFETY_ON_NULL_RETURN_VAL(data, EINA_FALSE);
 994    EINA_MAGIC_CHECK_HASH(hash);
 995
 996    hash_element = _eina_hash_find_by_data(hash, data, &key_hash, &hash_head);
 997    if (!hash_element)
 998      goto error;
 999
1000    if (hash_element->tuple.data != data)
1001      goto error;
1002
1003    return _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash);
1004
1005 error:
1006    return EINA_FALSE;
1007 }
1008
1009 EAPI Eina_Bool
1010 eina_hash_del_by_hash(Eina_Hash *hash,
1011                       const void *key,
1012                       int key_length,
1013                       int key_hash,
1014                       const void *data)
1015 {
1016    Eina_Bool ret;
1017
1018    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1019    EINA_MAGIC_CHECK_HASH(hash);
1020
1021    if (key)
1022      ret = _eina_hash_del_by_key_hash(hash, key, key_length, key_hash, data);
1023    else
1024      ret = eina_hash_del_by_data(hash, data);
1025
1026    return ret;
1027 }
1028
1029 EAPI Eina_Bool
1030 eina_hash_del(Eina_Hash *hash, const void *key, const void *data)
1031 {
1032    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1033    EINA_MAGIC_CHECK_HASH(hash);
1034
1035    if (!key)
1036      return eina_hash_del_by_data(hash, data);
1037
1038    return _eina_hash_del_by_key(hash, key, data);
1039 }
1040
1041 EAPI void *
1042 eina_hash_find_by_hash(const Eina_Hash *hash,
1043                        const void *key,
1044                        int key_length,
1045                        int key_hash)
1046 {
1047    Eina_Hash_Head *hash_head;
1048    Eina_Hash_Element *hash_element;
1049    Eina_Hash_Tuple tuple;
1050
1051    if (!hash)
1052      return NULL;
1053
1054    EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1055    EINA_MAGIC_CHECK_HASH(hash);
1056
1057    tuple.key = key;
1058    tuple.key_length = key_length;
1059    tuple.data = NULL;
1060
1061    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1062    if (hash_element)
1063      return hash_element->tuple.data;
1064
1065    return NULL;
1066 }
1067
1068 EAPI void *
1069 eina_hash_find(const Eina_Hash *hash, const void *key)
1070 {
1071    int key_length;
1072    int key_hash;
1073
1074    if (!hash)
1075      return NULL;
1076
1077    EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1078    EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1079    EINA_MAGIC_CHECK_HASH(hash);
1080
1081    if (hash->population == 0)
1082      return NULL;
1083
1084    _eina_hash_compute(hash, key, &key_length, &key_hash);
1085
1086    return eina_hash_find_by_hash(hash, key, key_length, key_hash);
1087 }
1088
1089 EAPI void *
1090 eina_hash_modify_by_hash(Eina_Hash *hash,
1091                          const void *key,
1092                          int key_length,
1093                          int key_hash,
1094                          const void *data)
1095 {
1096    Eina_Hash_Head *hash_head;
1097    Eina_Hash_Element *hash_element;
1098    void *old_data = NULL;
1099    Eina_Hash_Tuple tuple;
1100
1101    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1102    EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1103    EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL);
1104    EINA_MAGIC_CHECK_HASH(hash);
1105
1106    tuple.key = key;
1107    tuple.key_length = key_length;
1108    tuple.data = NULL;
1109
1110    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1111    if (hash_element)
1112      {
1113         old_data = hash_element->tuple.data;
1114         hash_element->tuple.data = (void *)data;
1115      }
1116
1117    return old_data;
1118 }
1119
1120 EAPI void *
1121 eina_hash_set(Eina_Hash *hash, const void *key, const void *data)
1122 {
1123    Eina_Hash_Tuple tuple;
1124    Eina_Hash_Head *hash_head;
1125    Eina_Hash_Element *hash_element;
1126    int key_length;
1127    int key_hash;
1128
1129    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1130    EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1131    EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1132    EINA_MAGIC_CHECK_HASH(hash);
1133
1134    _eina_hash_compute(hash, key, &key_length, &key_hash);
1135
1136    tuple.key = key;
1137    tuple.key_length = key_length;
1138    tuple.data = NULL;
1139
1140    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1141    if (hash_element)
1142      {
1143         void *old_data = NULL;
1144
1145         old_data = hash_element->tuple.data;
1146
1147         if (data)
1148           {
1149              hash_element->tuple.data = (void *)data;
1150           }
1151         else
1152           {
1153              Eina_Free_Cb cb = hash->data_free_cb;
1154              hash->data_free_cb = NULL;
1155              _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash);
1156              hash->data_free_cb = cb;
1157           }
1158
1159         return old_data;
1160      }
1161
1162    if (!data) return NULL;
1163
1164    eina_hash_add_alloc_by_hash(hash,
1165                                key,
1166                                key_length,
1167                                key_length,
1168                                key_hash,
1169                                data);
1170    return NULL;
1171 }
1172
1173 EAPI void *
1174 eina_hash_modify(Eina_Hash *hash, const void *key, const void *data)
1175 {
1176    int key_length;
1177    int key_hash;
1178
1179    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, NULL);
1180    EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, NULL);
1181    EINA_SAFETY_ON_NULL_RETURN_VAL(key, NULL);
1182    EINA_SAFETY_ON_NULL_RETURN_VAL(data, NULL);
1183    EINA_MAGIC_CHECK_HASH(hash);
1184
1185    _eina_hash_compute(hash, key, &key_length, &key_hash);
1186
1187    return eina_hash_modify_by_hash(hash, key, key_length, key_hash, data);
1188 }
1189
1190 EAPI Eina_Bool
1191 eina_hash_move(Eina_Hash *hash, const void *old_key, const void *new_key)
1192 {
1193    Eina_Free_Cb hash_free_cb;
1194    const void *data;
1195    Eina_Bool result = EINA_FALSE;
1196
1197    EINA_SAFETY_ON_NULL_RETURN_VAL(hash, EINA_FALSE);
1198    EINA_SAFETY_ON_NULL_RETURN_VAL(hash->key_hash_cb, EINA_FALSE);
1199    EINA_SAFETY_ON_NULL_RETURN_VAL(old_key, EINA_FALSE);
1200    EINA_SAFETY_ON_NULL_RETURN_VAL(new_key, EINA_FALSE);
1201    EINA_MAGIC_CHECK_HASH(hash);
1202
1203    data = eina_hash_find(hash, old_key);
1204    if (!data) goto error;
1205
1206    hash_free_cb = hash->data_free_cb;
1207    hash->data_free_cb = NULL;
1208
1209    eina_hash_del(hash, old_key, data);
1210    result = eina_hash_add(hash, new_key, data);
1211
1212    hash->data_free_cb = hash_free_cb;
1213
1214 error:
1215    return result;
1216 }
1217
1218 /*============================================================================*
1219 *                                Iterator                                    *
1220 *============================================================================*/
1221
1222 EAPI void
1223 eina_hash_foreach(const Eina_Hash *hash,
1224                   Eina_Hash_Foreach func,
1225                   const void *fdata)
1226 {
1227    Eina_Iterator *it;
1228    Eina_Hash_Foreach_Data foreach;
1229
1230    EINA_MAGIC_CHECK_HASH(hash);
1231    EINA_SAFETY_ON_NULL_RETURN(hash);
1232    EINA_SAFETY_ON_NULL_RETURN(func);
1233
1234    foreach.cb = func;
1235    foreach.fdata = fdata;
1236
1237    it = eina_hash_iterator_tuple_new(hash);
1238    if (!it)
1239      return;
1240    eina_iterator_foreach(it, EINA_EACH_CB(_eina_foreach_cb), &foreach);
1241
1242    eina_iterator_free(it);
1243 }
1244
1245 EAPI Eina_Iterator *
1246 eina_hash_iterator_data_new(const Eina_Hash *hash)
1247 {
1248    Eina_Iterator_Hash *it;
1249
1250    if (!hash) return NULL;
1251    EINA_MAGIC_CHECK_HASH(hash);
1252
1253    it = calloc(1, sizeof (Eina_Iterator_Hash));
1254    if (!it) return NULL;
1255
1256    it->hash = hash;
1257    it->get_content = FUNC_ITERATOR_GET_CONTENT(_eina_hash_iterator_data_get_content);
1258
1259    it->iterator.version = EINA_ITERATOR_VERSION;
1260    it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1261    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1262        _eina_hash_iterator_get_container);
1263    it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1264
1265    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1266    EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1267
1268    return &it->iterator;
1269 }
1270
1271 EAPI Eina_Iterator *
1272 eina_hash_iterator_key_new(const Eina_Hash *hash)
1273 {
1274    Eina_Iterator_Hash *it;
1275
1276    if (!hash) return NULL;
1277    EINA_MAGIC_CHECK_HASH(hash);
1278
1279    it = calloc(1, sizeof (Eina_Iterator_Hash));
1280    if (!it) return NULL;
1281
1282    it->hash = hash;
1283    it->get_content = FUNC_ITERATOR_GET_CONTENT(
1284        _eina_hash_iterator_key_get_content);
1285
1286    it->iterator.version = EINA_ITERATOR_VERSION;
1287    it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1288    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1289        _eina_hash_iterator_get_container);
1290    it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1291
1292    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1293    EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1294
1295    return &it->iterator;
1296 }
1297
1298 EAPI Eina_Iterator *
1299 eina_hash_iterator_tuple_new(const Eina_Hash *hash)
1300 {
1301    Eina_Iterator_Hash *it;
1302
1303    if (!hash) return NULL;
1304    EINA_MAGIC_CHECK_HASH(hash);
1305
1306    it = calloc(1, sizeof (Eina_Iterator_Hash));
1307    if (!it) return NULL;
1308
1309    it->hash = hash;
1310    it->get_content = FUNC_ITERATOR_GET_CONTENT(
1311        _eina_hash_iterator_tuple_get_content);
1312
1313    it->iterator.version = EINA_ITERATOR_VERSION;
1314    it->iterator.next = FUNC_ITERATOR_NEXT(_eina_hash_iterator_next);
1315    it->iterator.get_container = FUNC_ITERATOR_GET_CONTAINER(
1316        _eina_hash_iterator_get_container);
1317    it->iterator.free = FUNC_ITERATOR_FREE(_eina_hash_iterator_free);
1318
1319    EINA_MAGIC_SET(&it->iterator, EINA_MAGIC_ITERATOR);
1320    EINA_MAGIC_SET(it, EINA_MAGIC_HASH_ITERATOR);
1321
1322    return &it->iterator;
1323 }
1324
1325 /* Common hash functions */
1326
1327 /* Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html)
1328    used by WebCore (http://webkit.org/blog/8/hashtables-part-2/) */
1329 EAPI int
1330 eina_hash_superfast(const char *key, int len)
1331 {
1332    int hash = len, tmp;
1333    int rem;
1334
1335    rem = len & 3;
1336    len >>= 2;
1337
1338    /* Main loop */
1339    for (; len > 0; len--)
1340      {
1341         hash += get16bits(key);
1342         tmp = (get16bits(key + 2) << 11) ^ hash;
1343         hash = (hash << 16) ^ tmp;
1344         key += 2 * sizeof (uint16_t);
1345         hash += hash >> 11;
1346      }
1347
1348    /* Handle end cases */
1349    switch (rem)
1350      {
1351       case 3:
1352         hash += get16bits(key);
1353         hash ^= hash << 16;
1354         hash ^= key[sizeof (uint16_t)] << 18;
1355         hash += hash >> 11;
1356         break;
1357
1358       case 2:
1359         hash += get16bits(key);
1360         hash ^= hash << 11;
1361         hash += hash >> 17;
1362         break;
1363
1364       case 1:
1365         hash += *key;
1366         hash ^= hash << 10;
1367         hash += hash >> 1;
1368      }
1369
1370    /* Force "avalanching" of final 127 bits */
1371    hash ^= hash << 3;
1372    hash += hash >> 5;
1373    hash ^= hash << 4;
1374    hash += hash >> 17;
1375    hash ^= hash << 25;
1376    hash += hash >> 6;
1377
1378    return hash;
1379 }
1380
1381 EAPI void
1382 eina_hash_list_append(Eina_Hash *hash, const void *key, const void *data)
1383 {
1384    Eina_Hash_Tuple tuple;
1385    Eina_Hash_Head *hash_head;
1386    Eina_Hash_Element *hash_element;
1387    int key_length;
1388    int key_hash;
1389
1390    EINA_SAFETY_ON_NULL_RETURN(hash);
1391    EINA_SAFETY_ON_NULL_RETURN(hash->key_hash_cb);
1392    EINA_SAFETY_ON_NULL_RETURN(key);
1393    EINA_SAFETY_ON_NULL_RETURN(data);
1394    EINA_MAGIC_CHECK_HASH(hash);
1395
1396    _eina_hash_compute(hash, key, &key_length, &key_hash);
1397
1398    tuple.key = key;
1399    tuple.key_length = key_length;
1400    tuple.data = NULL;
1401
1402    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1403    if (hash_element)
1404       hash_element->tuple.data = eina_list_append(hash_element->tuple.data, data);
1405    else
1406      eina_hash_add_alloc_by_hash(hash,
1407                             key,
1408                             key_length,
1409                             key_length,
1410                             key_hash,
1411                             eina_list_append(NULL, data));
1412 }
1413
1414 EAPI void
1415 eina_hash_list_direct_append(Eina_Hash *hash, const void *key, const void *data)
1416 {
1417    Eina_Hash_Tuple tuple;
1418    Eina_Hash_Head *hash_head;
1419    Eina_Hash_Element *hash_element;
1420    int key_length;
1421    int key_hash;
1422
1423    EINA_SAFETY_ON_NULL_RETURN(hash);
1424    EINA_SAFETY_ON_NULL_RETURN(hash->key_hash_cb);
1425    EINA_SAFETY_ON_NULL_RETURN(key);
1426    EINA_SAFETY_ON_NULL_RETURN(data);
1427    EINA_MAGIC_CHECK_HASH(hash);
1428
1429    _eina_hash_compute(hash, key, &key_length, &key_hash);
1430
1431    tuple.key = key;
1432    tuple.key_length = key_length;
1433    tuple.data = NULL;
1434
1435    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1436    if (hash_element)
1437       hash_element->tuple.data = eina_list_append(hash_element->tuple.data, data);
1438    else
1439      eina_hash_add_alloc_by_hash(hash,
1440                             key,
1441                             key_length,
1442                             0,
1443                             key_hash,
1444                             eina_list_append(NULL, data));
1445 }
1446
1447 EAPI void
1448 eina_hash_list_prepend(Eina_Hash *hash, const void *key, const void *data)
1449 {
1450    Eina_Hash_Tuple tuple;
1451    Eina_Hash_Head *hash_head;
1452    Eina_Hash_Element *hash_element;
1453    int key_length;
1454    int key_hash;
1455
1456    EINA_SAFETY_ON_NULL_RETURN(hash);
1457    EINA_SAFETY_ON_NULL_RETURN(hash->key_hash_cb);
1458    EINA_SAFETY_ON_NULL_RETURN(key);
1459    EINA_SAFETY_ON_NULL_RETURN(data);
1460    EINA_MAGIC_CHECK_HASH(hash);
1461
1462    _eina_hash_compute(hash, key, &key_length, &key_hash);
1463
1464    tuple.key = key;
1465    tuple.key_length = key_length;
1466    tuple.data = NULL;
1467
1468    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1469    if (hash_element)
1470       hash_element->tuple.data = eina_list_prepend(hash_element->tuple.data, data);
1471    else
1472      eina_hash_add_alloc_by_hash(hash,
1473                             key,
1474                             key_length,
1475                             key_length,
1476                             key_hash,
1477                             eina_list_append(NULL, data));
1478 }
1479
1480 EAPI void
1481 eina_hash_list_direct_prepend(Eina_Hash *hash, const void *key, const void *data)
1482 {
1483    Eina_Hash_Tuple tuple;
1484    Eina_Hash_Head *hash_head;
1485    Eina_Hash_Element *hash_element;
1486    int key_length;
1487    int key_hash;
1488
1489    EINA_SAFETY_ON_NULL_RETURN(hash);
1490    EINA_SAFETY_ON_NULL_RETURN(hash->key_hash_cb);
1491    EINA_SAFETY_ON_NULL_RETURN(key);
1492    EINA_SAFETY_ON_NULL_RETURN(data);
1493    EINA_MAGIC_CHECK_HASH(hash);
1494
1495    _eina_hash_compute(hash, key, &key_length, &key_hash);
1496
1497    tuple.key = key;
1498    tuple.key_length = key_length;
1499    tuple.data = NULL;
1500
1501    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1502    if (hash_element)
1503       hash_element->tuple.data = eina_list_prepend(hash_element->tuple.data, data);
1504    else
1505      eina_hash_add_alloc_by_hash(hash,
1506                             key,
1507                             key_length,
1508                             0,
1509                             key_hash,
1510                             eina_list_append(NULL, data));
1511 }
1512
1513 EAPI void
1514 eina_hash_list_remove(Eina_Hash *hash, const void *key, const void *data)
1515 {
1516    Eina_Hash_Tuple tuple;
1517    Eina_Hash_Head *hash_head;
1518    Eina_Hash_Element *hash_element;
1519    int key_length;
1520    int key_hash;
1521
1522    EINA_SAFETY_ON_NULL_RETURN(hash);
1523    EINA_SAFETY_ON_NULL_RETURN(hash->key_hash_cb);
1524    EINA_SAFETY_ON_NULL_RETURN(key);
1525    EINA_SAFETY_ON_NULL_RETURN(data);
1526    EINA_MAGIC_CHECK_HASH(hash);
1527
1528    _eina_hash_compute(hash, key, &key_length, &key_hash);
1529
1530    tuple.key = key;
1531    tuple.key_length = key_length;
1532    tuple.data = NULL;
1533
1534    hash_element = _eina_hash_find_by_hash(hash, &tuple, key_hash, &hash_head);
1535    if (!hash_element) return;
1536    hash_element->tuple.data = eina_list_remove(hash_element->tuple.data, data);
1537    if (!hash_element->tuple.data)
1538      _eina_hash_del_by_hash_el(hash, hash_element, hash_head, key_hash);
1539 }