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 #ifndef EINA_HASH_H_ 21 #define EINA_HASH_H_ 22 23 #include "eina_types.h" 24 #include "eina_iterator.h" 25 26 /** 27 * @page hash_01_example_page Eina_Hash in action 28 * @dontinclude eina_hash_01.c 29 * 30 * We are going to store some tuples into our table, that will map each @a name 31 * to a @a number. The cost to access a given number from the name should be 32 * very small, even with many entries in our table. This is the initial data: 33 * @skip _Phone_Entry 34 * @until // _start_entries 35 * 36 * Before starting to play with the hash, let's write a callback that will be 37 * used to free the elements from it. Since we are just storing strduped 38 * strings, we just need to free them: 39 * 40 * @skip static 41 * @until } 42 * 43 * We also need a callback to iterate over the elements of the list later, so 44 * we are defining it now: 45 * 46 * @skip Eina_Bool 47 * @until } 48 * 49 * Now let's create our @ref Eina_Hash using @ref 50 * eina_hash_string_superfast_new : 51 * 52 * @skip eina_init 53 * @until phone_book 54 * 55 * Now we add the keys and data to the hash using @ref eina_hash_add . This 56 * means that the key is copied inside the table, together with the pointer to 57 * the data (phone numbers). 58 * 59 * @skip for 60 * @until } 61 * 62 * Some basic manipulations with the hash, like finding a value given a key, 63 * deleting an entry, modifying an entry are exemplified in the following lines. 64 * Notice that the @ref eina_hash_modify function returns the old value stored 65 * in that entry, and it needs to be freed, while the @ref eina_hash_del 66 * function already calls our free callback: 67 * 68 * @skip Look for 69 * @until free( 70 * 71 * The @ref eina_hash_set function can be used to set a key-value entry to the 72 * table if it doesn't exist, or to modify an existent entry. It returns the old 73 * entry if it was already set, and NULL otherwise. But since it will 74 * return NULL on error too, we need to check if an error has occurred: 75 * 76 * @skip Modify 77 * @until printf("\n"); 78 * 79 * There are different ways of iterate over the entries of a hash. Here we show 80 * two of them: using @ref eina_hash_foreach and @ref Eina_Iterator. 81 * 82 * @skip List of phones 83 * @until eina_iterator_free(it); 84 * 85 * It's also possible to change the key for a specific entry, without having to 86 * remove the entry from the table and adding it again: 87 * 88 * @skipline eina_hash_move 89 * 90 * We can remove all the elements from the table without free the table itself: 91 * 92 * @skip Empty the phone book 93 * @until eina_hash_population 94 * 95 * Or free the the entire table with its content: 96 * 97 * @skipline eina_hash_free 98 * 99 * 100 * The full code for this example can be seen here: @ref eina_hash_01_c 101 */ 102 103 /** 104 * @page eina_hash_01_c Hash table in action 105 * 106 * @include eina_hash_01.c 107 * @example eina_hash_01.c 108 */ 109 110 /** 111 * @page hash_02_example_page Different types of tables 112 * 113 * This example shows two more types of hash tables that can be created using 114 * @ref Eina_Hash . For more types, consult the reference documentation of @ref 115 * eina_hash_new. 116 * @include eina_hash_02.c 117 * @example eina_hash_02.c 118 */ 119 120 /** 121 * @example eina_hash_03.c 122 * Same example as @ref hash_01_example_page but using a "string small" hash 123 * table instead of "string superfast". 124 */ 125 126 /** 127 * @example eina_hash_04.c 128 * Same example as @ref hash_01_example_page but using a "string djb2" hash 129 * table instead of "string superfast". 130 */ 131 132 /** 133 * @example eina_hash_05.c 134 * Same example as @ref hash_01_example_page but using a "int32" hash 135 * table instead of "string superfast". 136 */ 137 138 /** 139 * @example eina_hash_06.c 140 * Same example as @ref hash_01_example_page but using a "int64" hash 141 * table instead of "string superfast". 142 */ 143 144 /** 145 * @example eina_hash_07.c 146 * Same example as @ref hash_01_example_page but using a "pointer" hash 147 * table instead of "string superfast". 148 */ 149 150 /** 151 * @example eina_hash_08.c 152 * This example shows the the usage of eina_hash_add(), eina_hash_add_by_hash(), 153 * eina_hash_direct_add_by_hash(), eina_hash_del(), eina_hash_del_by_key_hash(), 154 * eina_hash_del_by_key(), eina_hash_del_by_data(), eina_hash_find_by_hash() and 155 * eina_hash_modify_by_hash(). 156 */ 157 158 /** 159 * @addtogroup Eina_Hash_Group Hash Table 160 * 161 * @brief Hash table management. Maps keys to values. 162 * 163 * The hash table associates keys (e.g. strings) to data, with 164 * relatively fast access time. The performance is proportional to the 165 * load factor of the table (number of elements / number of 166 * buckets). See @ref hashtable_algo for implementation details. 167 * 168 * There are optimized implementations for some common key types, such 169 * as strings, integers, pointers, and stringshared; custom optimizations 170 * are also permitted. 171 * 172 * The hash table keys can be either copied or non-copied, using 173 * eina_hash_add() or eina_hash_direct_add(), respectively. 174 * 175 * @section hashtable_algo Algorithm 176 * 177 * The Eina_Hash is implemented using an array of N "buckets", where each 178 * bucket is a pointer to a structure that is the head of a <a 179 * href="http://en.wikipedia.org/wiki/Red-black_tree">red-black tree</a>. The 180 * array can then be indexed by the [hash_of_element mod N]. The 181 * hash_of_element is calculated using the hashing function, passed as a 182 * parameter to the @ref eina_hash_new function. N is the number of buckets 183 * (array positions), and is calculated based on the buckets_power_size 184 * (argument of @ref eina_hash_new too). The following picture illustrates the 185 * basic idea: 186 * 187 * @image latex 01_hash-table.eps 188 * @image html 01_hash-table.png 189 * 190 * Adding an element to the hash table involves the following steps: 191 * @li calculate the hash for that key (using the specified hash function); 192 * @li calculate the array position [hash mod N]; 193 * @li add the element to the rbtree on that position. 194 * 195 * The first two steps have constant time, proportional to the hash function 196 * being used. Adding the key to the rbtree will be proportional to the number 197 * of keys in that bucket. 198 * 199 * The average lookup cost depends on the number of keys per bucket 200 * (load factor) of the table, assuming the distribution of keys is 201 * sufficiently uniform. 202 * 203 * @section hashtable_perf Performance 204 * 205 * Keeping the load factor small will improve the hash table performance. But 206 * increasing the buckets_power_size will also increase the memory consumption. 207 * The default hash table creation functions provides enough 208 * buckets for most cases. If just a few string keys 209 * (less than 30) will be added to the hash table, @ref 210 * eina_hash_string_small_new should be used, since it reduces the memory 211 * consumption for the buckets without causing too many collisions. 212 * However, @ref eina_hash_string_small_new still uses the same hash calculation 213 * function that @ref eina_hash_string_superfast_new, which is more complex than 214 * @ref eina_hash_string_djb2_new. The latter has a faster hash computation 215 * function, but that will imply a not so good distribution. But if just a 216 * few keys are being added, this is not a problem, it will still have not many 217 * collisions and be faster to calculate the hash than in a hash created with 218 * @ref eina_hash_string_small_new and @ref eina_hash_string_superfast_new. 219 * 220 * A simple comparison between them would be: 221 * 222 * @li @c djb2 - faster hash function - 256 buckets (higher memory consumption) 223 * @li @c string_small - slower hash function but less collisions - 32 buckets 224 * (lower memory consumption) 225 * @li @c string_superfast - slower hash function but less collisions - 256 buckets 226 * (higher memory consumption) - not randomized, avoid it on public remote interface. 227 * 228 * Basically for a very small number of keys (10 or less), @c djb2 should be 229 * used, or @c string_small if you have a restriction on memory usage. And for a 230 * higher number of keys, @c string_superfast should be preferred if not used on a 231 * public remote interface. 232 * 233 * If just stringshared keys are being added, use @ref 234 * eina_hash_stringshared_new. If a lot of keys will be added to the hash table 235 * (e.g. more than 1000), then it's better to increase the buckets_power_size. 236 * See @ref eina_hash_new for more details. 237 * 238 * When adding a new key to a hash table, use @ref eina_hash_add or @ref 239 * eina_hash_direct_add (the latter if this key is already stored elsewhere). If 240 * the key may be already inside the hash table, rather than checking with 241 * @ref eina_hash_find followed by @ref eina_hash_add, one can use just @ref 242 * eina_hash_set (this will change the data pointed by this key if it was 243 * already present in the table). 244 * 245 * @section hashtable_tutorial Tutorial 246 * 247 * These examples show many Eina_Hash functions in action: 248 * <ul> 249 * <li> @ref hash_01_example_page 250 * <li> @ref hash_02_example_page 251 * <li> Different types of hash in use: 252 * <ul> 253 * <li> @ref eina_hash_03.c "string small" 254 * <li> @ref eina_hash_04.c "string djb2" 255 * <li> @ref eina_hash_05.c "int32" 256 * <li> @ref eina_hash_06.c "int64" 257 * <li> @ref eina_hash_07.c "pointer" 258 * </ul> 259 * <li> @ref eina_hash_08.c "Different add and delete functions" 260 * </ul> 261 */ 262 263 /** 264 * @addtogroup Eina_Data_Types_Group Data Types 265 * 266 * @{ 267 */ 268 269 /** 270 * @addtogroup Eina_Containers_Group Containers 271 * 272 * @{ 273 */ 274 275 /** 276 * @defgroup Eina_Hash_Group Hash Table 277 * 278 * @{ 279 */ 280 281 /** 282 * @typedef Eina_Hash 283 * Type for a generic hash table. 284 */ 285 typedef struct _Eina_Hash Eina_Hash; 286 287 /** 288 * @typedef Eina_Hash_Tuple 289 * Type for a hash table of key/value pairs. 290 */ 291 typedef struct _Eina_Hash_Tuple Eina_Hash_Tuple; 292 293 /** 294 * @struct _Eina_Hash_Tuple 295 * Data for a hash table of key/value pairs. 296 */ 297 struct _Eina_Hash_Tuple 298 { 299 const void *key; /**< The key */ 300 void *data; /**< The data associated to the key */ 301 unsigned int key_length; /**< The length of the key */ 302 }; 303 304 /** 305 * @typedef Eina_Key_Length 306 * Type for a function to determine the length of a hash key. 307 */ 308 typedef unsigned int (*Eina_Key_Length)(const void *key); 309 310 /** 311 * @def EINA_KEY_LENGTH 312 * @param[in] Function The function used to calculate length of hash key. 313 */ 314 #define EINA_KEY_LENGTH(Function) ((Eina_Key_Length)Function) 315 316 /** 317 * @typedef Eina_Key_Cmp 318 * Type for a function to compare two hash keys. 319 */ 320 typedef int (*Eina_Key_Cmp)(const void *key1, int key1_length, const void *key2, int key2_length); 321 /** 322 * @def EINA_KEY_CMP 323 * @param[in] Function The function used to compare hash key. 324 */ 325 #define EINA_KEY_CMP(Function) ((Eina_Key_Cmp)Function) 326 327 /** 328 * @typedef Eina_Key_Hash 329 * Type for a function to create a hash key. 330 */ 331 typedef int (*Eina_Key_Hash)(const void *key, int key_length); 332 /** 333 * @def EINA_KEY_HASH 334 * @param[in] Function The function used to hash key. 335 */ 336 #define EINA_KEY_HASH(Function) ((Eina_Key_Hash)Function) 337 338 /** 339 * @typedef Eina_Hash_Foreach 340 * Type for a function to iterate over a hash table. 341 */ 342 typedef Eina_Bool (*Eina_Hash_Foreach)(const Eina_Hash *hash, const void *key, void *data, void *fdata); 343 344 345 /** 346 * @brief Creates a new hash table. 347 * 348 * @param[in] key_length_cb The function called when getting the size of the key. 349 * @param[in] key_cmp_cb The function called when comparing the keys. 350 * @param[in] key_hash_cb The function called when getting the values. 351 * @param[in] data_free_cb The function called on each value when the hash table is 352 * freed, or when an item is deleted from it. @c NULL can be passed as a 353 * callback. 354 * @param[in] buckets_power_size The size of the buckets. 355 * @return The new hash table, or @c NULL on failure. 356 * 357 * This function creates a new hash table using user-defined callbacks 358 * to manage the hash table. 359 * If @p key_cmp_cb or @p key_hash_cb 360 * are @c NULL, @c NULL is returned. If @p buckets_power_size is 361 * smaller or equal than 2, or if it is greater or equal than 17, 362 * @c NULL is returned. 363 * 364 * The number of buckets created will be 2 ^ @p buckets_power_size. This means 365 * that if @p buckets_power_size is 5, there will be created 32 buckets, whereas for a 366 * @p buckets_power_size of 8, there will be 256 buckets. 367 * 368 * Pre-defined functions are available to create a hash table. See 369 * eina_hash_string_djb2_new(), eina_hash_string_superfast_new(), 370 * eina_hash_string_small_new(), eina_hash_int32_new(), 371 * eina_hash_int64_new(), eina_hash_pointer_new() and 372 * eina_hash_stringshared_new(). 373 */ 374 EAPI Eina_Hash *eina_hash_new(Eina_Key_Length key_length_cb, 375 Eina_Key_Cmp key_cmp_cb, 376 Eina_Key_Hash key_hash_cb, 377 Eina_Free_Cb data_free_cb, 378 int buckets_power_size) EINA_MALLOC EINA_WARN_UNUSED_RESULT EINA_ARG_NONNULL(2, 3); 379 380 /** 381 * @brief Sets the data cleanup callback for a hash. 382 * 383 * @param[in,out] hash The given hash table. 384 * @param[in] data_free_cb The function called on each value when the hash 385 * table is freed, or when an item is deleted from it. @c NULL can be passed as 386 * callback to remove an existing callback. 387 * 388 * The argument received by @p data_free_cb will be the data of the item being 389 * removed. 390 * 391 * @since 1.1 392 * @see eina_hash_new. 393 */ 394 EAPI void eina_hash_free_cb_set(Eina_Hash *hash, Eina_Free_Cb data_free_cb) EINA_ARG_NONNULL(1); 395 396 /** 397 * @brief Creates a new hash table using the djb2 algorithm. 398 * 399 * @param[in] data_free_cb The function called on each value when the hash table 400 * is freed, or when an item is deleted from it. @c NULL can be passed as 401 * callback. 402 * @return The new hash table, or @c NULL on failure. 403 * 404 * This function creates a new hash table using the djb2 algorithm for 405 * table management and strcmp() to compare the keys. Values can then 406 * be looked up with pointers other than the original key pointer that 407 * was used to add values. 408 */ 409 EAPI Eina_Hash *eina_hash_string_djb2_new(Eina_Free_Cb data_free_cb); 410 411 /** 412 * @brief Creates a new hash table for use with strings. 413 * 414 * @param[in] data_free_cb The function called on each value when the hash table 415 * is freed, or when an item is deleted from it. @c NULL can be passed as 416 * callback. 417 * @return The new hash table, or @c NULL on failure. 418 * 419 * This function creates a new hash table using the superfast algorithm 420 * for table management and strcmp() to compare the keys. Values can 421 * then be looked up with pointers other than the original key pointer 422 * that was used to add values. 423 * 424 * @warning Don't use this kind of hash when there is a possibility to 425 * remotely request and push data in it. This hash is subject to denial 426 * of service. 427 */ 428 EAPI Eina_Hash *eina_hash_string_superfast_new(Eina_Free_Cb data_free_cb); 429 430 /** 431 * @brief Creates a new hash table for use with strings with small bucket size. 432 * 433 * @param[in] data_free_cb The function called on each value when the hash table 434 * is freed, or when an item is deleted from it. @c NULL can be passed as 435 * callback. 436 * @return The new hash table, or @c NULL on failure. 437 * 438 * This function creates a new hash table using the superfast algorithm 439 * for table management and strcmp() to compare the keys, but with a 440 * smaller bucket size (compared to eina_hash_string_superfast_new()) 441 * which will minimize the memory used by the returned hash 442 * table. Values can then be looked up with pointers other than the 443 * original key pointer that was used to add values. 444 */ 445 EAPI Eina_Hash *eina_hash_string_small_new(Eina_Free_Cb data_free_cb); 446 447 /** 448 * @brief Creates a new hash table for use with 32bit integers. 449 * 450 * @param[in] data_free_cb The function called on each value when the hash table 451 * is freed, or when an item is deleted from it. @c NULL can be passed as 452 * callback. 453 * @return The new hash table, or @c NULL on failure. 454 * 455 * This function creates a new hash table where keys are 32bit integers. 456 * When adding or looking up in the hash table, pointers to 32bit integers 457 * must be passed. They can be addresses on the stack if you let the 458 * eina_hash copy the key. Values can then 459 * be looked up with pointers other than the original key pointer that was 460 * used to add values. This method is not suitable to match string keys as 461 * it would only match the first character. 462 */ 463 EAPI Eina_Hash *eina_hash_int32_new(Eina_Free_Cb data_free_cb); 464 465 /** 466 * @brief Creates a new hash table for use with 64bit integers. 467 * 468 * @param[in] data_free_cb The function called on each value when the hash table 469 * is freed, or when an item is deleted from it. @c NULL can be passed as 470 * callback. 471 * @return The new hash table, or @c NULL on failure. 472 * 473 * This function creates a new hash table where keys are 64bit integers. 474 * When adding or looking up in the hash table, pointers to 64bit integers 475 * must be passed. They can be addresses on the stack. Values can then 476 * be looked up with pointers other than the original key pointer that was 477 * used to add values. This method is not suitable to match string keys as 478 * it would only match the first character. 479 */ 480 EAPI Eina_Hash *eina_hash_int64_new(Eina_Free_Cb data_free_cb); 481 482 /** 483 * @brief Creates a new hash table for use with pointers. 484 * 485 * @param[in] data_free_cb The function called on each value when the hash table 486 * is freed, or when an item is deleted from it. @c NULL can be passed as 487 * callback. 488 * @return The new hash table, or @c NULL on failure. 489 * 490 * This function creates a new hash table using the int64/int32 algorithm for 491 * table management and dereferenced pointers to compare the 492 * keys. Values can then be looked up with pointers other than the 493 * original key pointer that was used to add values. This method may 494 * appear to be able to match string keys, but actually it only matches 495 * the first character. 496 * 497 * @code 498 * // For a hash that will have only one pointer to each structure 499 * extern Eina_Hash *hash; 500 * extern void *data; 501 * 502 * if (!eina_hash_find(hash, &data)) 503 * eina_hash_add(hash, &data, data); 504 * @endcode 505 */ 506 EAPI Eina_Hash *eina_hash_pointer_new(Eina_Free_Cb data_free_cb); 507 508 /** 509 * @brief Creates a new hash table optimized for stringshared values. 510 * 511 * @param[in] data_free_cb The function called on each value when the hash table 512 * is freed, or when an item is deleted from it. @c NULL can be passed as 513 * callback. 514 * @return The new hash table, or @c NULL on failure. 515 * 516 * This function creates a new hash table optimized for stringshared 517 * values. Values CANNOT be looked up with pointers not 518 * equal to the original key pointer that was used to add a value. 519 * 520 * Excerpt of code that will NOT work with this type of hash: 521 * 522 * @code 523 * extern Eina_Hash *hash; 524 * extern const char *value; 525 * const char *a = eina_stringshare_add("key"); 526 * 527 * eina_hash_add(hash, a, value); 528 * eina_hash_find(hash, "key"); 529 * @endcode 530 */ 531 EAPI Eina_Hash *eina_hash_stringshared_new(Eina_Free_Cb data_free_cb); 532 533 /** 534 * @brief Adds an entry to the given hash table. 535 * 536 * @param[in,out] hash The given hash table. Cannot be @c NULL. 537 * @param[in] key A unique key. Cannot be @c NULL. 538 * @param[in] data The data to associate with the string given by @p key. Cannot be @c 539 * NULL. 540 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 541 * 542 * This function adds @p key to @p hash. @p key must be unique within 543 * the hash table so that @ref eina_hash_find() and @ref eina_hash_del() 544 * operate on the correct data item. 545 * 546 * Key uniqueness varies depending on the type of @p hash: a 547 * stringshared @ref Eina_Hash needs unique pointers (which implies 548 * unique strings). All other string hash types require that the 549 * strings themselves are unique. Pointer, int32 and int64 hashes need 550 * to have unique values. Failure to use sufficient uniqueness will 551 * result in unexpected results when inserting data pointers accessed 552 * with @ref eina_hash_find(), and removed with @ref eina_hash_del(). 553 * 554 * Key strings are case sensitive. 555 */ 556 EAPI Eina_Bool eina_hash_add(Eina_Hash *hash, 557 const void *key, 558 const void *data) EINA_ARG_NONNULL(1, 2, 3); 559 560 /** 561 * @brief Adds an entry to the given hash table without duplicating the string. 562 * 563 * @param[in,out] hash The given hash table. Cannot be @c NULL. 564 * @param[in] key A unique key. Cannot be @c NULL. 565 * @param[in] data The data to associate with the string given by @p 566 * key. Cannot be @c NULL 567 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 568 * 569 * This function adds @p key to @p hash. @p key must be unique within 570 * the hash table so that @ref eina_hash_find() and @ref eina_hash_del() 571 * operate on the correct data item. 572 * 573 * Key uniqueness varies depending on the type of @p hash: a 574 * stringshared @ref Eina_Hash needs unique pointers (which implies 575 * unique strings). All other string hash types require that the 576 * strings themselves are unique. Pointer, int32 and int64 hashes need 577 * to have unique values. Failure to use sufficient uniqueness will 578 * result in unexpected results when inserting data pointers accessed 579 * with @ref eina_hash_find(), and removed with @ref eina_hash_del(). 580 * 581 * Unlike @ref eina_hash_add(), this function does not make a copy of 582 * @p key, so it must be a string constant or stored elsewhere (such as 583 * in the object being added). Key strings are case sensitive. 584 */ 585 EAPI Eina_Bool eina_hash_direct_add(Eina_Hash *hash, 586 const void *key, 587 const void *data) EINA_ARG_NONNULL(1, 2, 3); 588 589 /** 590 * @brief Removes the entry identified by a key or a data from the given 591 * hash table. 592 * 593 * @param[in,out] hash The given hash table. 594 * @param[in] key The key. 595 * @param[in] data The data pointer to remove if the key is @c NULL. 596 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 597 * 598 * This function removes the entry identified by @p key or @p data 599 * from @p hash. If a free function was given to the 600 * callback on creation, it will be called for the data being 601 * deleted. If @p hash is @c NULL, the function returns immediately #EINA_FALSE. 602 * If @p key is @c NULL, then @p data is used to find the a 603 * match to remove, otherwise @p key is used and @p data is not 604 * required and can be @c NULL. 605 * 606 * @note If you already have the key, use eina_hash_del_by_key() or 607 * eina_hash_del_by_key_hash(). If you don't have the key, use 608 * eina_hash_del_by_data() directly. 609 */ 610 EAPI Eina_Bool eina_hash_del(Eina_Hash *hash, 611 const void *key, 612 const void *data) EINA_ARG_NONNULL(1); 613 614 /** 615 * @brief Retrieves a specific entry in the given hash table. 616 * 617 * @param[in] hash The given hash table. 618 * @param[in] key The key of the entry to find. 619 * @return The data pointer for the stored entry on success, or @c NULL 620 * otherwise. 621 * 622 * This function retrieves the entry associated with @p key in 623 * @p hash. If @p hash is @c NULL, this function returns @c NULL. 624 */ 625 EAPI void *eina_hash_find(const Eina_Hash *hash, 626 const void *key) EINA_ARG_NONNULL(2); 627 628 /** 629 * @brief Modifies the entry pointer at the specified key and returns 630 * the previous entry. 631 * @param[in,out] hash The given hash table. 632 * @param[in] key The key of the entry to modify. 633 * @param[in] data The new data. 634 * @return The data pointer for the previously stored entry on success, 635 * or @c NULL otherwise. 636 * 637 * This function modifies the data of @p key with @p data in @p 638 * hash. If no entry is found, nothing is added to @p hash. 639 */ 640 EAPI void *eina_hash_modify(Eina_Hash *hash, 641 const void *key, 642 const void *data) EINA_ARG_NONNULL(1, 2, 3); 643 644 /** 645 * @brief Modifies the entry pointer at the specified key and returns the 646 * previous entry or adds the entry if not found. 647 * 648 * @param[in,out] hash The given hash table. 649 * @param[in] key The key of the entry to modify. 650 * @param[in] data The data to replace the previous entry. 651 * @return The data pointer for the previous stored entry, or @c NULL 652 * otherwise. 653 * 654 * This function modifies the value of @p key to @p data in @p 655 * hash. If no entry is found, @p data is added to @p hash with the 656 * key @p key. 657 */ 658 EAPI void *eina_hash_set(Eina_Hash *hash, 659 const void *key, 660 const void *data) EINA_ARG_NONNULL(1, 2); 661 662 /** 663 * @brief Changes the key of an entry in a hash without triggering the 664 * free callback. 665 * 666 * @param[in,out] hash The given hash table. 667 * @param[in] old_key The current key associated with the data. 668 * @param[in] new_key The new key to associate data with. 669 * @return #EINA_FALSE in any case but success, #EINA_TRUE on success. 670 * 671 * This function moves data from one key to another, 672 * but does not call the Eina_Free_Cb associated with the hash table 673 * when destroying the old key. 674 */ 675 EAPI Eina_Bool eina_hash_move(Eina_Hash *hash, 676 const void *old_key, 677 const void *new_key) EINA_ARG_NONNULL(1, 2, 3); 678 679 /** 680 * @brief Frees the given hash table's resources. 681 * 682 * @param[in] hash The hash table to be freed. 683 * 684 * This function frees memory allocated for the @p hash and to its 685 * internal buckets. 686 * 687 * If @p data_free_cb was specified at creation time in 688 * @ref eina_hash_new, it will be called for each element as it gets 689 * freed. If the callback was not specified, then any data in these 690 * elements may now be lost, if not stored or freed elsewhere. 691 * 692 * If @p hash is @c NULL, the function returns immediately. 693 * 694 * Example: 695 * @code 696 * extern Eina_Hash *hash; 697 * 698 * eina_hash_free(hash); 699 * hash = NULL; 700 * @endcode 701 */ 702 EAPI void eina_hash_free(Eina_Hash *hash) EINA_ARG_NONNULL(1); 703 704 /** 705 * @brief Frees the given hash table buckets resources. 706 * 707 * @param[in] hash The hash table whose buckets have to be freed. 708 * 709 * This function frees memory allocated to internal buckets for @p hash. 710 * 711 * If @p data_free_cb was specified at creation time in 712 * @ref eina_hash_new(), it will be called for each element as it gets 713 * freed. If the callback was not specified, then any data in these 714 * elements may now be lost, if not stored or freed elsewhere. 715 * 716 * If @p hash is @c NULL, the function returns immediately. 717 */ 718 EAPI void eina_hash_free_buckets(Eina_Hash *hash) EINA_ARG_NONNULL(1); 719 720 /** 721 * @brief Returns the number of entries in the given hash table. 722 * 723 * @param[in] hash The given hash table. 724 * @return The number of entries in the hash table, or @c 0 on error or 725 * if @p hash is @c NULL. 726 */ 727 EAPI int eina_hash_population(const Eina_Hash *hash) EINA_ARG_NONNULL(1); 728 729 /** 730 * @brief Adds an entry to the given hash table by its key hash. 731 * 732 * @param[in,out] hash The given hash table. Cannot be @c NULL. 733 * @param[in] key A unique key. Cannot be @c NULL. 734 * @param[in] key_length The length of @p key (including terminating '\\0'). 735 * @param[in] key_hash The hash of @p key. 736 * @param[in] data The data to associate with the string given by the key. Cannot be 737 * @c NULL. 738 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 739 * 740 * This function adds @p key to @p hash. 741 * 742 * @p key must be unique within the hash table so that 743 * @ref eina_hash_find() and @ref eina_hash_del() operate on the correct 744 * data item. @p key_hash must match @p key so that the correct item can 745 * be found by @ref eina_hash_find_by_hash(). Key strings are case 746 * sensitive. 747 * 748 * @see eina_hash_add() 749 */ 750 EAPI Eina_Bool eina_hash_add_by_hash(Eina_Hash *hash, 751 const void *key, 752 int key_length, 753 int key_hash, 754 const void *data) EINA_ARG_NONNULL(1, 2, 5); 755 756 /** 757 * @brief Adds an entry to a hash table by its key hash without duplicating the string key. 758 * 759 * @param[in,out] hash The given hash table. Cannot be @c NULL. 760 * @param[in] key A unique key. Cannot be @c NULL. 761 * @param[in] key_length The length of @p key (including terminating '\\0'). 762 * @param[in] key_hash The hash of @p key. 763 * @param[in] data The data to associate with the string given by @p key. Cannot be @c 764 * NULL. 765 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 766 * 767 * This function adds @p key to @p hash. 768 * 769 * @p key must be unique within the hash table so that 770 * @ref eina_hash_find() and @ref eina_hash_del() operate on the correct 771 * data item. @p key_hash must match @p key so that the correct item can 772 * be found by @ref eina_hash_find_by_hash(). Key strings are case 773 * sensitive. 774 * 775 * Unlike @ref eina_hash_add_by_hash(), this function does not make a 776 * copy of @p key, so it must be a string constant or stored elsewhere 777 * (such as inside the object being added). 778 * 779 * @see eina_hash_direct_add() 780 */ 781 EAPI Eina_Bool eina_hash_direct_add_by_hash(Eina_Hash *hash, 782 const void *key, 783 int key_length, 784 int key_hash, 785 const void *data) EINA_ARG_NONNULL(1, 2, 5); 786 787 /** 788 * @brief Removes the entry identified by a key and a key hash from the given 789 * hash table. 790 * 791 * @param[in,out] hash The given hash table. Cannot be @c NULL. 792 * @param[in] key The key. Cannot be @c NULL. 793 * @param[in] key_length The length of the key (including terminating '\\0'). 794 * @param[in] key_hash The hash that always matches the key. 795 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 796 * 797 * This function removes the entry identified by @p key and 798 * @p key_hash from @p hash. If a free function was given to the 799 * callback on creation, it will be called for the data being 800 * deleted. If @p hash or @p key are @c NULL, the 801 * function returns #EINA_FALSE immediately. 802 * 803 * @note If you don't have the key_hash, use eina_hash_del_by_key() 804 * instead. If you don't have the key, use eina_hash_del_by_data(). 805 */ 806 EAPI Eina_Bool eina_hash_del_by_key_hash(Eina_Hash *hash, 807 const void *key, 808 int key_length, 809 int key_hash) EINA_ARG_NONNULL(1, 2); 810 811 /** 812 * @brief Removes the entry identified by a key from the given hash table. 813 * 814 * This version will calculate key length and hash by using functions 815 * provided to the hash creation function. 816 * 817 * @param[in,out] hash The given hash table. Cannot be @c NULL. 818 * @param[in] key The key. Cannot be @c NULL. 819 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 820 * 821 * This function removes the entry identified by @p key from @p 822 * hash. The key length and hash will be calculated automatically via 823 * a function provided to the hash creation function. If a free 824 * function was given to the callback on creation, it will be called 825 * for the data being deleted. If @p hash or @p key are @c NULL, the 826 * function returns #EINA_FALSE immediately. 827 * 828 * @note If you already have the key_hash, use eina_hash_del_by_key_hash(). 829 * If you don't have the key, use eina_hash_del_by_data() instead. 830 */ 831 EAPI Eina_Bool eina_hash_del_by_key(Eina_Hash *hash, 832 const void *key) EINA_ARG_NONNULL(1, 2); 833 834 /** 835 * @brief Removes an entry from a hash table identified by its data value. 836 * 837 * @param[in,out] hash The given hash table. Cannot be @c NULL. 838 * @param[in] data The data value to search and remove. Cannot be @c NULL. 839 * @return #EINA_FALSE if an error occurred or if @p hash or @p data are 840 * @c NULL, #EINA_TRUE otherwise. 841 * thing goes fine. 842 * 843 * This function removes the entry identified by @p data from @p 844 * hash. If a free function was given to the callback on creation, it 845 * will be called for the data being deleted. 846 * 847 * @note This version is slow since there is no quick access to nodes 848 * based on data. 849 * 850 * @note If you already have the key, use eina_hash_del_by_key() 851 * or eina_hash_del_by_key_hash() instead. 852 */ 853 EAPI Eina_Bool eina_hash_del_by_data(Eina_Hash *hash, 854 const void *data) EINA_ARG_NONNULL(1, 2); 855 856 /** 857 * @brief Removes the entry identified by a key and a key hash, or a 858 * data value from the given hash table. 859 * 860 * If @p key is @c NULL, then @p data is used to find a match to 861 * remove. 862 * 863 * @param[in,out] hash The given hash table. Cannot be @c NULL. 864 * @param[in] key The key. 865 * @param[in] key_length The length of the key. 866 * @param[in] key_hash The hash that always match the key. 867 * @param[in] data The data pointer to remove if the key is @c NULL. 868 * @return #EINA_FALSE if an error occurred, #EINA_TRUE otherwise. 869 * 870 * This function removes the entry identified by @p key and @p key_hash, 871 * or @p data, from @p hash. If a free function was given to the 872 * callback on creation, it will be called for the data being 873 * deleted. If @p hash is @c NULL, the function returns #EINA_FALSE 874 * immediately. If @p key is @c NULL, then @p key_length and @p 875 * key_hash are ignored and @p data is used to find a match to remove, 876 * otherwise @p key and @p key_hash are used and @p data is not required 877 * and can be @c NULL. Do not forget to count '\\0' for string when 878 * setting the value of @p key_length. 879 * 880 * @note If you already have the key, use eina_hash_del_by_key_hash(). 881 * If you don't have the key, use eina_hash_del_by_data() directly. 882 */ 883 EAPI Eina_Bool eina_hash_del_by_hash(Eina_Hash *hash, 884 const void *key, 885 int key_length, 886 int key_hash, 887 const void *data) EINA_ARG_NONNULL(1); 888 889 /** 890 * @brief Retrieves a specific entry from the given hash table. 891 * 892 * @param[in] hash The given hash table. Cannot be @c NULL. 893 * @param[in] key The key of the entry to find. 894 * @param[in] key_length The length of the key. 895 * @param[in] key_hash The hash that always matches the key 896 * @return The data pointer for the stored entry on success, or @c NULL 897 * if @p hash is @c NULL or if the data pointer could not be retrieved. 898 * 899 * This function retrieves the entry associated with @p key of length 900 * @p key_length in @p hash. @p key_hash is the hash that always matches 901 * @p key. It is ignored if @p key is @c NULL. Do not forget to count 902 * '\\0' for string when setting the value of @p key_length. 903 */ 904 EAPI void *eina_hash_find_by_hash(const Eina_Hash *hash, 905 const void *key, 906 int key_length, 907 int key_hash) EINA_ARG_NONNULL(1, 2); 908 909 /** 910 * @brief Modifies the entry pointer at the specified key and returns 911 * the previous entry. 912 * 913 * @param[in,out] hash The given hash table. 914 * @param[in] key The key of the entry to modify. 915 * @param[in] key_length Should be the length of @p key (don't forget to count 916 * '\\0' for string). 917 * @param[in] key_hash The hash that always matches the key. Ignored if @p 918 * key is @c NULL. 919 * @param[in] data The data to replace the current entry, if it exists. 920 * @return The data pointer for the previously stored entry, or @c NULL 921 * if not found. If an existing entry is not found, nothing is added to 922 * the hash. 923 */ 924 EAPI void *eina_hash_modify_by_hash(Eina_Hash *hash, 925 const void *key, 926 int key_length, 927 int key_hash, 928 const void *data) EINA_ARG_NONNULL(1, 2, 5); 929 930 /** 931 * @brief Returns a new iterator associated with hash keys. 932 * 933 * @param[in] hash The hash. 934 * @return A new iterator, or @c NULL if memory could not be allocated. 935 * 936 * This function returns a newly allocated iterator associated with @p 937 * hash. If @p hash is not populated, this function still returns a 938 * valid iterator that will always return false on 939 * eina_iterator_next(). 940 * 941 * @warning If the hash structure changes then the iterator becomes 942 * invalid; adding or removing items may lead to program crash. 943 */ 944 EAPI Eina_Iterator *eina_hash_iterator_key_new(const Eina_Hash *hash) EINA_MALLOC EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 945 946 /** 947 * @brief Returns a new iterator associated with a hash. 948 * 949 * @param[in] hash The hash. 950 * @return A new iterator, or @c NULL if memory could not be allocated. 951 * 952 * This function returns a newly allocated iterator associated with 953 * @p hash. If @p hash is not populated, this function still returns a 954 * valid iterator that will always return false on 955 * eina_iterator_next(). 956 * 957 * @warning If the hash structure changes then the iterator becomes 958 * invalid; adding or removing items may lead to program crash. 959 */ 960 EAPI Eina_Iterator *eina_hash_iterator_data_new(const Eina_Hash *hash) EINA_MALLOC EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 961 962 /** 963 * @brief Returned a new iterator associated with hash keys and data. 964 * 965 * @param[in] hash The hash. 966 * @return A new iterator, or @c NULL if memory could not be allocated. 967 * 968 * This function returns a newly allocated iterator associated with @p 969 * hash. If @p hash is not populated, this function still returns a 970 * valid iterator that will always return false on 971 * eina_iterator_next(). 972 * 973 * @note Iterator data will provide values as Eina_Hash_Tuple that 974 * should not be modified! 975 * 976 * @warning If the hash structure changes then the iterator becomes 977 * invalid; adding or removing items may lead to program crash. 978 */ 979 EAPI Eina_Iterator *eina_hash_iterator_tuple_new(const Eina_Hash *hash) EINA_MALLOC EINA_ARG_NONNULL(1) EINA_WARN_UNUSED_RESULT; 980 981 /** 982 * @brief Calls a function on every member stored in the hash table. 983 * 984 * @param[in] hash The hash table whose members will be walked. 985 * @param[in] func The function to call on each parameter. 986 * @param[in] fdata The data pointer to pass to the function being called. 987 * 988 * This function iterates over the hash table @p hash, calling the 989 * function @p func on each member. If @p func modifies the contents 990 * of the hash table, or wishes to stop processing it should return 991 * #EINA_FALSE. If @p func returns #EINA_TRUE the foreach loop will 992 * keep processing. 993 * 994 * Example: 995 * @code 996 * extern Eina_Hash *hash; 997 * 998 * Eina_Bool hash_fn(const Eina_Hash *hash, const void *key, 999 * void *data, void *fdata) 1000 * { 1001 * printf("Func data: %s, Hash entry: %s / %p\n", 1002 * fdata, (const char *)key, data); 1003 * return EINA_TRUE; 1004 * } 1005 * 1006 * int main(int argc, char **argv) 1007 * { 1008 * char *hash_fn_data; 1009 * 1010 * hash_fn_data = strdup("Hello World"); 1011 * eina_hash_foreach(hash, hash_fn, hash_fn_data); 1012 * free(hash_fn_data); 1013 * } 1014 * @endcode 1015 */ 1016 EAPI void eina_hash_foreach(const Eina_Hash *hash, 1017 Eina_Hash_Foreach func, 1018 const void *fdata) EINA_ARG_NONNULL(1, 2); 1019 1020 1021 /** 1022 * @brief Appends data to an #Eina_List inside a hash. 1023 * 1024 * This function is identical to the sequence of calling 1025 * eina_hash_find(), eina_list_append(), eina_hash_set(), 1026 * but with one fewer required hash lookup. 1027 * 1028 * @param[in,out] hash The hash table. 1029 * @param[in] key The key associated with the data. 1030 * @param[in] data The data to append to the list. 1031 * 1032 * @since 1.10 1033 */ 1034 EAPI void eina_hash_list_append(Eina_Hash *hash, const void *key, const void *data) EINA_ARG_NONNULL(1, 2, 3); 1035 1036 /** 1037 * @brief Appends data to an #Eina_List inside a hash using eina_hash_direct_add(). 1038 * 1039 * This function is identical to the sequence of calling 1040 * eina_hash_find(), eina_list_append(), eina_hash_set(), 1041 * but with one fewer required hash lookup. 1042 * 1043 * @param[in,out] hash The hash table. 1044 * @param[in] key The key associated with the data. 1045 * @param[in] data The data to append to the list. 1046 * 1047 * @since 1.23 1048 */ 1049 EAPI void eina_hash_list_direct_append(Eina_Hash *hash, const void *key, const void *data) EINA_ARG_NONNULL(1, 2, 3); 1050 1051 /** 1052 * @brief Prepends data to an #Eina_List inside a hash. 1053 * 1054 * This function is identical to the sequence of calling 1055 * eina_hash_find(), eina_list_prepend(), eina_hash_set(), 1056 * but with one fewer required hash lookup. 1057 * 1058 * @param[in,out] hash The hash table. 1059 * @param[in] key The key associated with the data. 1060 * @param[in] data The data to prepend to the list. 1061 * 1062 * @since 1.10 1063 */ 1064 EAPI void eina_hash_list_prepend(Eina_Hash *hash, const void *key, const void *data) EINA_ARG_NONNULL(1, 2, 3); 1065 1066 /** 1067 * @brief Prepends data to an #Eina_List inside a hash using eina_hash_direct_add(). 1068 * 1069 * This function is identical to the sequence of calling 1070 * eina_hash_find(), eina_list_prepend(), eina_hash_set(), 1071 * but with one fewer required hash lookup. 1072 * 1073 * @param[in,out] hash The hash table. 1074 * @param[in] key The key associated with the data. 1075 * @param[in] data The data to prepend to the list. 1076 * 1077 * @since 1.23 1078 */ 1079 EAPI void eina_hash_list_direct_prepend(Eina_Hash *hash, const void *key, const void *data) EINA_ARG_NONNULL(1, 2, 3); 1080 1081 /** 1082 * @brief Removes data from an #Eina_List inside a hash. 1083 * 1084 * This function is identical to the sequence of calling 1085 * eina_hash_find(), eina_list_remove(), eina_hash_set(), 1086 * but with one fewer required hash lookup. 1087 * 1088 * @param[in,out] hash The hash table. 1089 * @param[in] key The key associated with the data. 1090 * @param[in] data The data to remove from the list. 1091 * 1092 * @since 1.10 1093 */ 1094 EAPI void eina_hash_list_remove(Eina_Hash *hash, const void *key, const void *data) EINA_ARG_NONNULL(1, 2, 3); 1095 1096 /** 1097 * @brief 1098 * Paul Hsieh (http://www.azillionmonkeys.com/qed/hash.html) hash function used by WebCore (http://webkit.org/blog/8/hashtables-part-2/) 1099 * 1100 * @param[in] key The key to hash. 1101 * @param[in] len The length of the key. 1102 * @return The hash value. 1103 */ 1104 EAPI int eina_hash_superfast(const char *key, 1105 int len) EINA_ARG_NONNULL(1); 1106 1107 /** 1108 * @brief 1109 * Hash function first reported by Dan Bernstein many years ago in comp.lang.c 1110 * 1111 * @param[in] key The key to hash. 1112 * @param[in] len The length of the key. 1113 * @return The hash value. 1114 */ 1115 static inline int eina_hash_djb2(const char *key, 1116 int len) EINA_ARG_NONNULL(1); 1117 1118 /** 1119 * @brief 1120 * Hash function first reported by Dan Bernstein many years ago in comp.lang.c 1121 * 1122 * @param[in] key The key to hash. 1123 * @param[in] plen The length of the key. 1124 * @return The hash value. 1125 */ 1126 static inline int eina_hash_djb2_len(const char *key, 1127 int *plen) EINA_ARG_NONNULL(1, 2); 1128 1129 /** 1130 * @brief 1131 * Hash function from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm 1132 * 1133 * @param[in] pkey The key to hash. 1134 * @param[in] len The length of the key. 1135 * @return The hash value. 1136 */ 1137 static inline int eina_hash_int32(const unsigned int *pkey, 1138 int len) EINA_ARG_NONNULL(1); 1139 1140 /** 1141 * @brief 1142 * Hash function from http://web.archive.org/web/20071223173210/http://www.concentric.net/~Ttwang/tech/inthash.htm 1143 * 1144 * @param[in] pkey The key to hash. 1145 * @param[in] len The length of the key. 1146 * @return The hash value. 1147 */ 1148 static inline int eina_hash_int64(const unsigned long long int *pkey, 1149 int len) EINA_ARG_NONNULL(1); 1150 1151 /** 1152 * @brief 1153 * Hash function from http://sites.google.com/site/murmurhash/ 1154 * 1155 * @param[in] key The key to hash. 1156 * @param[in] len The length of the key. 1157 * @return The hash value. 1158 */ 1159 static inline int eina_hash_murmur3(const char *key, 1160 int len) EINA_ARG_NONNULL(1); 1161 1162 /** 1163 * @brief 1164 * Hash function using crc-32 algorithm and and 0xEDB88320 polynomial 1165 * 1166 * @param[in] key The key to hash. 1167 * @param[in] len The length of the key. 1168 * @return The hash value. 1169 */ 1170 static inline int eina_hash_crc(const char *key, 1171 int len) EINA_ARG_NONNULL(1); 1172 1173 #include "eina_inline_hash.x" 1174 1175 /** 1176 * @} 1177 */ 1178 1179 /** 1180 * @} 1181 */ 1182 1183 /** 1184 * @} 1185 */ 1186 1187 #endif /*EINA_HASH_H_*/ 1188