From dde440ad22e2395253d84694ca5c22356bfaff11 Mon Sep 17 00:00:00 2001 From: antognolli Date: Thu, 9 Jun 2011 18:52:45 +0000 Subject: [PATCH] [eina] Add high-level documentation and examples for Eina_Hash. git-svn-id: svn+ssh://svn.enlightenment.org/var/svn/e/trunk/eina@60149 7cbeb6ba-43b4-40fd-8cce-4c39aea84d33 --- src/examples/eina_hash_01.c | 195 ++++++++++++++++++++++++++++++++++++++++++++ src/examples/eina_hash_02.c | 144 ++++++++++++++++++++++++++++++++ src/include/eina_hash.h | 160 +++++++++++++++++++++++++++++++++--- 3 files changed, 488 insertions(+), 11 deletions(-) create mode 100644 src/examples/eina_hash_01.c create mode 100644 src/examples/eina_hash_02.c diff --git a/src/examples/eina_hash_01.c b/src/examples/eina_hash_01.c new file mode 100644 index 0000000..fa5470a --- /dev/null +++ b/src/examples/eina_hash_01.c @@ -0,0 +1,195 @@ +#include +#include +#include + +/* + * Eina Hash - phonebook + * + * This example demonstrate the use of Eina Hash by implementing a phonebook + * that stores its contact data into the hash. + * + * It indexes the phone numbers by Contact Full Name, so it's a hash with + * string keys. + */ + +struct _Phone_Entry { + const char *name; // Full name. + const char *number; // Phone number. +}; + +typedef struct _Phone_Entry Phone_Entry; + +static Phone_Entry _start_entries[] = { + { "Wolfgang Amadeus Mozart", "+01 23 456-78910" }, + { "Ludwig van Beethoven", "+12 34 567-89101" }, + { "Richard Georg Strauss", "+23 45 678-91012" }, + { "Heitor Villa-Lobos", "+34 56 789-10123" }, + { NULL, NULL } +}; // _start_entries + +static void +_phone_entry_free_cb(void *data) +{ + free(data); +} + +static Eina_Bool +_phone_book_foreach_cb(const Eina_Hash *phone_book, const void *key, + void *data, void *fdata) +{ + const char *name = key; + const char *number = data; + printf("%s: %s\n", name, number); + + // Return EINA_FALSE to stop this callback from being called + return EINA_TRUE; +} + +int +main(int argc, const char *argv[]) +{ + Eina_Hash *phone_book = NULL; + int i; + const char *entry_name = "Heitor Villa-Lobos"; + char *phone = NULL; + Eina_Bool r; + Eina_Iterator *it; + void *data; + + eina_init(); + + phone_book = eina_hash_string_superfast_new(_phone_entry_free_cb); + + // Add initial entries to our hash + for (i = 0; _start_entries[i].name != NULL; i++) + { + eina_hash_add(phone_book, _start_entries[i].name, + strdup(_start_entries[i].number)); + } + + // Look for a specific entry and get its phone number + phone = eina_hash_find(phone_book, entry_name); + if (phone) + { + printf("Printing entry.\n"); + printf("Name: %s\n", entry_name); + printf("Number: %s\n\n", phone); + } + + // Delete this entry + r = eina_hash_del(phone_book, entry_name, NULL); + printf("Hash entry successfully deleted? %d\n\n", r); + + // Modify the pointer data of an entry and free the old one + phone = eina_hash_modify(phone_book, "Richard Georg Strauss", + strdup("+23 45 111-11111")); + free(phone); + + // Modify or add an entry to the hash with eina_hash_set + // Let's first add a new entry + eina_error_set(0); + phone = eina_hash_set(phone_book, "Raul Seixas", + strdup("+55 01 234-56789")); + if (!phone) + { + Eina_Error err = eina_error_get(); + if (!err) + { + printf("No previous phone found for Raul Seixas. "); + printf("Creating new entry.\n"); + } + else + printf("Error when setting phone for Raul Seixas\n"); + } + else + { + printf("Old phone for Raul Seixas was %s\n", phone); + free(phone); + } + + printf("\n"); + + // Now change the phone number + eina_error_set(0); + phone = eina_hash_set(phone_book, "Raul Seixas", + strdup("+55 02 234-56789")); + if (phone) + { + printf("Changing phone for Raul Seixas to +55 02 234-56789. "); + printf("Old phone was %s\n", phone); + free(phone); + } + else + { + Eina_Error err = eina_error_get(); + if (err) + printf("Error when changing phone for Raul Seixas\n"); + else + { + printf("No previous phone found for Raul Seixas. "); + printf("Creating new entry.\n"); + } + } + + // There are many ways to iterate over our Phone book. + // First, iterate showing the names and associated numbers. + printf("List of phones:\n"); + eina_hash_foreach(phone_book, _phone_book_foreach_cb, NULL); + printf("\n"); + + // Now iterate using an iterator + printf("List of phones:\n"); + it = eina_hash_iterator_tuple_new(phone_book); + while (eina_iterator_next(it, &data)) + { + Eina_Hash_Tuple *t = data; + const char *name = t->key; + const char *number = t->data; + printf("%s: %s\n", name, number); + } + eina_iterator_free(it); // Always free the iterator after its use + printf("\n"); + + // Just iterate over the keys (names) + printf("List of names in the phone book:\n"); + it = eina_hash_iterator_key_new(phone_book); + while (eina_iterator_next(it, &data)) + { + const char *name = data; + printf("%s\n", name); + } + eina_iterator_free(it); + printf("\n"); + + // Just iterate over the data (numbers) + printf("List of numbers in the phone book:\n"); + it = eina_hash_iterator_data_new(phone_book); + while (eina_iterator_next(it, &data)) + { + const char *number = data; + printf("%s\n", number); + } + eina_iterator_free(it); + printf("\n"); + + // Check how many items are in the phone book + printf("There are %d items in the hash.\n\n", + eina_hash_population(phone_book)); + + // Change the name (key) on an entry + eina_hash_move(phone_book, "Raul Seixas", "Alceu Valenca"); + printf("List of phones after change:\n"); + eina_hash_foreach(phone_book, _phone_book_foreach_cb, NULL); + printf("\n"); + + // Empty the phone book, but don't destroy it + eina_hash_free_buckets(phone_book); + printf("There are %d items in the hash.\n\n", + eina_hash_population(phone_book)); + + // Phone book could still be used, but we are freeing it since we are + // done for now + eina_hash_free(phone_book); + + eina_shutdown(); +} diff --git a/src/examples/eina_hash_02.c b/src/examples/eina_hash_02.c new file mode 100644 index 0000000..d43d7a3 --- /dev/null +++ b/src/examples/eina_hash_02.c @@ -0,0 +1,144 @@ +#include +#include +#include + +/* + * Eina Hash - Two more types of hash + * + * This example demonstrate two other types of hash in action - using + * eina_hash_stringshared_new and eina_hash_new. + * + * It indexes the phone numbers by Contact Full Name, so it's a hash with string + * keys, exactly the same as the other example. + */ + +struct _Phone_Entry { + const char *name; // Full name. + const char *number; // Phone number. +}; + +typedef struct _Phone_Entry Phone_Entry; + +static Phone_Entry _start_entries[] = { + { "Wolfgang Amadeus Mozart", "+01 23 456-78910" }, + { "Ludwig van Beethoven", "+12 34 567-89101" }, + { "Richard Georg Strauss", "+23 45 678-91012" }, + { "Heitor Villa-Lobos", "+34 56 789-10123" }, + { NULL, NULL } +}; + +static void +_phone_entry_free_cb(void *data) +{ + free(data); +} + +static void +_phone_book_stringshared_free_cb(void *data) +{ + Phone_Entry *e = data; + eina_stringshare_del(e->name); + eina_stringshare_del(e->number); + free(e); +} + +static Eina_Bool +_phone_book_stringshared_foreach_cb(const Eina_Hash *phone_book, + const void *key, void *data, void *fdata) +{ + Phone_Entry *e = data; + const char *name = e->name; // e->name == key + const char *number = e->number; + printf("%s: %s\n", name, number); + + return EINA_TRUE; +} + +static void +example_hash_stringshared(void) +{ + Eina_Hash *phone_book = NULL; + int i; + + // Create the hash as before + phone_book = eina_hash_stringshared_new(_phone_book_stringshared_free_cb); + + // Add initial entries to our hash, using direct_add + for (i = 0; _start_entries[i].name != NULL; i++) + { + Phone_Entry *e = malloc(sizeof(Phone_Entry)); + e->name = eina_stringshare_add(_start_entries[i].name); + e->number = eina_stringshare_add(_start_entries[i].number); + // Since we are storing the key (name) in our struct, we can use + // eina_hash_direct_add. It could be used in the previous example + // too, since each key is already stored in the _start_entries + // static array, but we started it with the default add function. + eina_hash_direct_add(phone_book, e->name, e); + } + + // Iterate over the elements + printf("List of phones:\n"); + eina_hash_foreach(phone_book, _phone_book_stringshared_foreach_cb, NULL); + printf("\n"); + + eina_hash_free(phone_book); +} + +static unsigned int +_phone_book_string_key_length(const char *key) +{ + if (!key) + return 0; + + return (int)strlen(key) + 1; +} + +static int +_phone_book_string_key_cmp(const char *key1, int key1_length, + const char *key2, int key2_length) +{ + return strcmp(key1, key2); +} + +static void +example_hash_big(void) +{ + Eina_Hash *phone_book = NULL; + int i; + const char *phone; + + // Create the same hash as used in eina_hash_01.c, but + // use 1024 (2 ^ 10) buckets. + phone_book = eina_hash_new(EINA_KEY_LENGTH(_phone_book_string_key_length), + EINA_KEY_CMP(_phone_book_string_key_cmp), + EINA_KEY_HASH(eina_hash_superfast), + _phone_entry_free_cb, + 10); + for (i = 0; _start_entries[i].name != NULL; i++) + { + eina_hash_add(phone_book, _start_entries[i].name, + strdup(_start_entries[i].number)); + } + + // Look for a specific entry and get its phone number + phone = eina_hash_find(phone_book, "Heitor Villa-Lobos"); + if (phone) + { + printf("Printing entry.\n"); + printf("Name: Heitor Villa-Lobos\n"); + printf("Number: %s\n\n", phone); + } + + eina_hash_free(phone_book); +} + +int +main(int argc, const char *argv[]) +{ + eina_init(); + + example_hash_stringshared(); + example_hash_big(); + + eina_shutdown(); +} diff --git a/src/include/eina_hash.h b/src/include/eina_hash.h index 3abd363..f986ab7 100644 --- a/src/include/eina_hash.h +++ b/src/include/eina_hash.h @@ -24,30 +24,168 @@ #include "eina_iterator.h" /** + * @page hash_01_example_page Eina_Hash in action + * @dontinclude eina_hash_01.c + * + * We are going to store some tuples into our table, that will map each @a name + * to a @a number. The cost to access a given number from the name should be + * very small, even with many entries in our table. This is the initial data: + * @skip _Phone_Entry + * @until // _start_entries + * + * Before starting to play with the hash, let's write a callback that will be + * used to free the elements from it. Since we are just storing strduped + * strings, we just need to free them: + * + * @skip static + * @until } + * + * We also need a callback to iterate over the elements of the list later, so + * we are defining it now: + * + * @skip Eina_Bool + * @until } + * + * Now let's create our @ref Eina_Hash using @ref + * eina_hash_string_superfast_new : + * + * @skip eina_init + * @until phone_book + * + * Now we add the keys and data to the hash using @ref eina_hash_add . This + * means that the key is copied inside the table, together with the pointer to + * the data (phone numbers). + * + * @skip for + * @until } + * + * Some basic manipulations with the hash, like finding a value given a key, + * deleting an entry, modifying an entry are exemplified in the following lines. + * Notice that the @ref eina_hash_modify function returns the old value stored + * in that entry, and it needs to be freed, while the @ref eina_hash_del + * function already calls our free callback: + * + * @skip Look for + * @until free( + * + * The @ref eina_hash_set function can be used to set a key-value entry to the + * table if it doesn't exist, or to modify an existent entry. It returns the old + * entry if it was already set, and NULL otherwise. But since it will + * return NULL on error too, we need to check if an error has occurred: + * + * @skip Modify + * @until printf("\n"); + * + * There are different ways of iterate over the entries of a hash. Here we show + * two of them: using @ref eina_hash_foreach and @ref Eina_Iterator . + * + * @skip List of phones + * @until eina_iterator_free(it); + * + * It's also possible to change the key for a specific entry, without having to + * remove the entry from the table and adding it again: + * + * @skipline eina_hash_move + * + * We can remove all the elements from the table without free the table itself: + * + * @skip Empty the phone book + * @until eina_hash_population + * + * Or free the the entire table with its content: + * + * @skipline eina_hash_free + * + * + * The full code for this example can be seen here: @ref eina_hash_01_c + */ + +/** + * @page eina_hash_01_c Hash table in action + * + * @include eina_hash_01.c + * @example eina_hash_01.c + */ + +/** + * @page hash_02_example_page Different types of tables + * + * This example shows two more types of hash tables that can be created using + * @ref Eina_Hash . For more types, consult the reference documentation of @ref + * eina_hash_new. + * @include eina_hash_02.c + * @example eina_hash_02.c + */ + +/** * @addtogroup Eina_Hash_Group Hash Table * - * @brief give a small description here : what it is for, what it does - * , etc... - * Different implementations exists depending on what to store: strings, - * integers, pointers, stringshared or your own... + * @brief Hash table management. Useful for mapping keys to values. + * + * The hash table is useful for when one wants to implement a table that maps + * keys (usually strings) to data, and have relatively fast access time. The + * performance is proportional to the load factor of the table (number of + * elements / number of buckets). See @ref hashtable_algo for implementation + * details. + * + * Different implementations exists depending on what kind of key will be used + * to access the data: strings, integers, pointers, stringshared or your own. + * * Eina hash tables can copy the keys when using eina_hash_add() or not when * using eina_hash_direct_add(). * - * Hash API. Give some hints about the use (functions that must be - * used like init / shutdown), general use, etc... Give also a link to - * tutorial below. - * * @section hashtable_algo Algorithm * - * Give here the algorithm used in the implementation + * The Eina_Hash is implemented using an array of N "buckets", where each + * bucket is a pointer to a structure that is the head of a red-black tree. The + * array can then be indexed by the [hash_of_element mod N]. The + * hash_of_element is calculated using the hashing function, passed as + * parameter to the @ref eina_hash_new function. N is the number of buckets + * (array positions), and is calculated based on the buckets_power_size + * (argument of @ref eina_hash_new too). The following picture ilustrates the + * basic idea: + * + * @image html 01_hash-table.jpg + * + * Adding an element to the hash table is made of: + * @li calculating the hash for that key (using the specified hash function); + * @li calculate the array position [hash mod N]; + * @li add the element to the rbtree on that position. + * + * The two first steps have constant time, proportional to the hash function + * being used. Adding the key to the rbtree will be proportional on the number + * of keys on that bucket. + * + * The average cost of lookup depends on the number of keys per + * bucket (load factor) of the table, if the distribution of keys is + * sufficiently uniform. * * @section hashtable_perf Performance * - * Give some hints about performance if it is possible, and an image ! + * As said before, the performance depends on the load factor. So trying to keep + * it as small as possible will improve the hash table performance. But + * increasing the buckets_power_size will also increase the memory consumption. + * The default hash table creation functions already have a good number of + * buckets, enough for most cases. Particularly for strings, if just a few keys + * (less than 30) will be added to the hash table, @ref + * eina_hash_string_small_new should be used. If just stringshared keys are + * being added, use @ref eina_hash_stringshared_new. If a lot of keys will be + * added to the hash table (e.g. more than 1000), then it's better to increase + * the buckets_power_size. See @ref eina_hash_new for more details. + * + * When adding a new key to a hash table, use @ref eina_hash_add or @ref + * eina_hash_direct_add (the latter if this key is already stored elsewhere). If + * the key may be already inside the hash table, instead of checking with + * @ref eina_hash_find and then doing @ref eina_hash_add, one can use just @ref + * eina_hash_set (this will change the data pointed by this key if it was + * already present in the table). * * @section hashtable_tutorial Tutorial * - * Here is a fantastic tutorial about our hash table + * These examples show many Eina_Hash functions in action: + * @li @ref hash_01_example_page + * @li @ref hash_02_example_page * * @{ */ -- 2.7.4