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