User is able to set a function to free the value of the hashmap entry. --- ell/hashmap.c | 37 +++++++++++++++++++++++++++++++++++++ ell/hashmap.h | 6 ++++++ 2 files changed, 43 insertions(+) diff --git a/ell/hashmap.c b/ell/hashmap.c index b60cc62..f707d64 100644 --- a/ell/hashmap.c +++ b/ell/hashmap.c @@ -54,6 +54,8 @@ struct l_hashmap { l_hashmap_compare_func_t compare_func; l_hashmap_key_new_func_t key_new_func; l_hashmap_key_free_func_t key_free_func; + l_hashmap_value_free_func_t value_free_func; + void *user_data; unsigned int entries; struct entry buckets[NBUCKETS]; }; @@ -73,6 +75,12 @@ static inline void free_key(const struct l_hashmap *hashmap, void *key) hashmap->key_free_func(key); } +static inline void free_value(const struct l_hashmap *hashmap, void *value) +{ + if (hashmap->value_free_func) + hashmap->value_free_func(hashmap, value, hashmap->user_data); +} + static inline unsigned int hash_superfast(const uint8_t *key, unsigned int len) { /* @@ -307,6 +315,35 @@ LIB_EXPORT bool l_hashmap_set_key_free_function(struct l_hashmap *hashmap, } /** + * l_hashmap_set_value_free_function: + * @hashmap: hash table object + * @func: Value destructor function + * + * Sets the value destructor function to be used by this object. + * This function can be NULL, in which case no destructor is called. + * + * This function can only be called when the @hashmap is empty. + * + * Returns: #true when the value free function could be updated successfully, + * and #false otherwise. + **/ +LIB_EXPORT bool l_hashmap_set_value_free_function(struct l_hashmap *hashmap, + l_hashmap_value_free_func_t func, + void *user_data) +{ + if (unlikely(!hashmap)) + return false; + + if (hashmap->entries != 0) + return false; + + hashmap->value_free_func = func; + hashmap->user_data = user_data; + + return true; +} + +/** * l_hashmap_destroy: * @hashmap: hash table object * @destroy: destroy function diff --git a/ell/hashmap.h b/ell/hashmap.h index 9f4f5fa..a904109 100644 --- a/ell/hashmap.h +++ b/ell/hashmap.h @@ -39,6 +39,9 @@ typedef void (*l_hashmap_key_free_func_t) (void *p); struct l_hashmap; +typedef void (*l_hashmap_value_free_func_t) (const struct l_hashmap *hashmap, + void *p, void *user_data); + unsigned int l_str_hash(const void *p); struct l_hashmap *l_hashmap_new(void); @@ -52,6 +55,9 @@ bool l_hashmap_set_key_copy_function(struct l_hashmap *hashmap, l_hashmap_key_new_func_t func); bool l_hashmap_set_key_free_function(struct l_hashmap *hashmap, l_hashmap_key_free_func_t func); +bool l_hashmap_set_value_free_function(struct l_hashmap *hashmap, + l_hashmap_value_free_func_t func, + void *user_data); void l_hashmap_destroy(struct l_hashmap *hashmap, l_hashmap_destroy_func_t destroy); -- 1.8.3.1

Hi Jukka, On 02/10/2015 08:42 AM, Jukka Rissanen wrote: So this is not the way hashmap has been designed. The destroy function (which is the last argument to this call) is being called already to cleanup memory, etc. In effect, you're now duplicating this functionality. Regards, -Denis

Hi Jukka, On 02/10/2015 08:42 AM, Jukka Rissanen wrote: So the current implementation allows duplicates to be added. However, it is implementation dependent what happens if you lookup a duplicate key. With the current implementation, the item inserted first is returned. I don't think enforcement of unique keys is required at the hashmap_insert level. The user should not be always made to pay the cost of duplicate detection (e.g. if he knows no duplicates will ever be present). If duplicates are an issue, the way to handle this in the client code would be to - Call l_hashmap_remove first - Insert the new element Alternatively, you could add an l_hashmap_replace() method call, e.g.: bool l_hashmap_replace(struct l_hashmap *hashmap, const void *key, void *value, l_hashmap_destroy_func_t destroy); So this part doesn't really match the comment above. You're also freeing the key, which is an unnecessary step. If the keys are the same, just reuse them. Regards, -Denis

Use the value free function to test that we can replace an existing value in the hash. --- unit/test-hashmap.c | 17 +++++++++++++++++ 1 file changed, 17 insertions(+) diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c index a606099..836ed1c 100644 --- a/unit/test-hashmap.c +++ b/unit/test-hashmap.c @@ -86,6 +86,14 @@ static void test_ptr(const void *test_data) l_hashmap_destroy(hashmap, NULL); } +static void free_value(const struct l_hashmap *hashmap, + void *value, void *user_data) +{ + assert(hashmap == user_data); + + l_free(value); +} + static void test_str(const void *test_data) { struct l_hashmap *hashmap; @@ -97,6 +105,8 @@ static void test_str(const void *test_data) "a long key here, bla bla bla bla bla hey! enough?", NULL }; + const char *duplicate = "hello"; + unsigned int entries; hashmap = l_hashmap_string_new(); assert(hashmap); @@ -154,6 +164,13 @@ static void test_str(const void *test_data) assert(ptr == itr); } + /* check that value free function works */ + hashmap = l_hashmap_string_new(); + assert(l_hashmap_set_value_free_function(hashmap, free_value, + hashmap)); + assert(l_hashmap_insert(hashmap, strings[0], l_strdup(strings[0]))); + assert(l_hashmap_insert(hashmap, strings[0], l_strdup(strings[0]))); + assert(l_hashmap_lookup(hashmap, "not in hash") == NULL); l_hashmap_destroy(hashmap, NULL); -- 1.8.3.1

Allow user to remove and add values while inside a callback from foreach function. This is very much needed as it is easy to get things wrong here and it helps to avoid complicated call flows in calling applications. So foreach logic is changed so that if user tries to remove an entry from the hash while inside foreach callback, the entry is not yet removed from hash but marked as removable. After foreach has finished calling the callback function, it checks what elements it needs to remove from the hash. This valgrind report was seen and it relates to this issue. Here a DBus message was received and its callback function eventually called l_dbus_unregister() because of application logic. This then caused the signal_list hash to get corrupted because the unregister removed an entry from hash while traversing it. ==28077== Invalid read of size 1 ==28077== at 0x4044A9: l_hashmap_foreach (hashmap.c:606) ==28077== by 0x4071D9: message_read_handler (dbus.c:244) ==28077== by 0x410D94: io_callback (io.c:120) ==28077== by 0x404C42: l_main_run (main.c:346) ==28077== by 0x401D08: main (test-agent.c:460) ==28077== Address 0x1c is not stack'd, malloc'd or (recently) free'd ==28077== ==28077== ==28077== Process terminating with default action of signal 11 (SIGSEGV) ==28077== Access not within mapped region at address 0x1C ==28077== at 0x4044A9: l_hashmap_foreach (hashmap.c:606) ==28077== by 0x4071D9: message_read_handler (dbus.c:244) ==28077== by 0x410D94: io_callback (io.c:120) ==28077== by 0x404C42: l_main_run (main.c:346) ==28077== by 0x401D08: main (test-agent.c:460) ==28077== If you believe this happened as a result of a stack ==28077== overflow in your program's main thread (unlikely but ==28077== possible), you can try to increase the size of the ==28077== main thread stack using the --main-stacksize= flag. ==28077== The main thread stack size used in this run was 8388608. --- ell/hashmap.c | 69 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- 1 file changed, 67 insertions(+), 2 deletions(-) diff --git a/ell/hashmap.c b/ell/hashmap.c index a204726..6c7c10f 100644 --- a/ell/hashmap.c +++ b/ell/hashmap.c @@ -42,6 +42,7 @@ struct entry { void *value; struct entry *next; unsigned int hash; + bool removed; }; /** @@ -50,6 +51,8 @@ struct entry { * Opague object representing the hash table. */ struct l_hashmap { + bool dirty; + bool traversing; l_hashmap_hash_func_t hash_func; l_hashmap_compare_func_t compare_func; l_hashmap_key_new_func_t key_new_func; @@ -431,6 +434,7 @@ LIB_EXPORT bool l_hashmap_insert(struct l_hashmap *hashmap, free_key(hashmap, entry->key); entry->key = key_new; } + entry->removed = false; if (entry->value != value) { free_value(hashmap, entry->value); @@ -490,11 +494,20 @@ LIB_EXPORT void *l_hashmap_remove(struct l_hashmap *hashmap, const void *key) if (entry->hash != hash) goto next; + if (entry->removed) + goto next; + if (hashmap->compare_func(key, entry->key)) goto next; value = entry->value; + if (hashmap->traversing) { + entry->removed = true; + hashmap->dirty = true; + goto skip; + } + if (entry == head) { if (entry->next == head) { free_key(hashmap, entry->key); @@ -517,6 +530,7 @@ LIB_EXPORT void *l_hashmap_remove(struct l_hashmap *hashmap, const void *key) l_free(entry); } + skip: hashmap->entries--; return value; @@ -553,7 +567,7 @@ LIB_EXPORT void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key) return NULL; for (entry = head;; entry = entry->next) { - if (entry->hash == hash && + if (entry->hash == hash && !entry->removed && !hashmap->compare_func(key, entry->key)) return entry->value; @@ -580,6 +594,8 @@ LIB_EXPORT void l_hashmap_foreach(struct l_hashmap *hashmap, if (unlikely(!hashmap || !function)) return; + hashmap->traversing = true; + for (i = 0; i < NBUCKETS; i++) { struct entry *entry, *head = &hashmap->buckets[i]; @@ -587,12 +603,61 @@ LIB_EXPORT void l_hashmap_foreach(struct l_hashmap *hashmap, continue; for (entry = head;; entry = entry->next) { - function(entry->key, entry->value, user_data); + if (!entry->removed) + function(entry->key, entry->value, user_data); if (entry->next == head) break; } } + + hashmap->traversing = false; + + if (!hashmap->dirty) + return; + + /* Remove the entries that were marked removed. */ + for (i = 0; i < NBUCKETS; i++) { + struct entry *entry, *prev, *head = &hashmap->buckets[i]; + + if (!head->next) + continue; + + for (entry = head, prev = NULL; entry; + prev = entry, entry = entry->next) { + + if (!entry->removed) + goto next; + + if (entry == head) { + if (entry->next == head) { + free_key(hashmap, entry->key); + head->key = NULL; + head->value = NULL; + head->hash = 0; + head->next = NULL; + } else { + entry = entry->next; + free_key(hashmap, head->key); + head->key = entry->key; + head->value = entry->value; + head->hash = entry->hash; + head->next = entry->next; + l_free(entry); + } + } else { + prev->next = entry->next; + free_key(hashmap, entry->key); + l_free(entry); + } + + next: + if (entry->next == head) + break; + } + } + + hashmap->dirty = false; } /** -- 1.8.3.1

Check that we can add and remove items from hash while inside foreach callback. --- unit/test-hashmap.c | 81 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 81 insertions(+) diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c index 75c249c..51d03ba 100644 --- a/unit/test-hashmap.c +++ b/unit/test-hashmap.c @@ -184,11 +184,92 @@ static void test_str(const void *test_data) l_hashmap_destroy(hashmap, NULL); } +static void foreach_cb(const void *key, void *value, void *user_data) +{ + struct l_hashmap *hashmap = user_data; + static bool removed, insert, conflict; + unsigned int entries; + char *str, *mykey = "b"; + bool ret; + + if (!removed) { + printf("Removing entry in foreach\n"); + + entries = l_hashmap_size(hashmap); + + str = l_hashmap_remove(hashmap, "a"); + assert(str); + + assert(!l_hashmap_lookup(hashmap, "a")); + + assert(entries == (l_hashmap_size(hashmap) + 1)); + + removed = true; + } + + if (!insert) { + printf("Adding entry in foreach\n"); + + entries = l_hashmap_size(hashmap); + + ret = l_hashmap_insert(hashmap, mykey, mykey); + assert(ret); + + assert(entries == (l_hashmap_size(hashmap) - 1)); + + insert = true; + } + + if (!conflict) { + printf("Adding conflicting entry in foreach\n"); + + entries = l_hashmap_size(hashmap); + + assert(l_hashmap_lookup(hashmap, mykey)); + + ret = l_hashmap_insert(hashmap, mykey, mykey); + assert(ret); + + assert(entries == l_hashmap_size(hashmap)); + + conflict = true; + } +} + +static void test_reentrant(const void *test_data) +{ + struct l_hashmap *hashmap; + const void *ptr; + const char **itr, *strings[] = { + "hello", + "world", + "a", + "a longer key here", + NULL + }; + + hashmap = l_hashmap_string_new(); + assert(hashmap); + assert(l_hashmap_size(hashmap) == 0); + assert(l_hashmap_isempty(hashmap)); + + for (itr = strings; *itr != NULL; itr++) { + assert(l_hashmap_insert(hashmap, *itr, itr)); + ptr = l_hashmap_lookup(hashmap, *itr); + assert(ptr == itr); + } + + l_hashmap_foreach(hashmap, foreach_cb, hashmap); + + l_hashmap_destroy(hashmap, NULL); +} + int main(int argc, char *argv[]) { l_test_init(&argc, &argv); l_test_add("Pointer Test", test_ptr, NULL); l_test_add("String Test", test_str, NULL); + l_test_add("Re-entrant Test", test_reentrant, NULL); return l_test_run(); } -- 1.8.3.1

Hi Denis, On ti, 2015-02-10 at 16:42 +0200, Jukka Rissanen wrote: Just wanted to ask are you ok with func? At the moment there is no function to traverse the hash, other than the foreach variant and it is very sub-optimal as it will traverse the whole hash even if such a thing is not needed by the caller. Even better option would be to change the return parameter of foreach callback to return bool so we could do with only one traversing function. Jukka

--- unit/test-hashmap.c | 36 ++++++++++++++++++++++++++++++++++++ 1 file changed, 36 insertions(+) diff --git a/unit/test-hashmap.c b/unit/test-hashmap.c index 51d03ba..e9c4541 100644 --- a/unit/test-hashmap.c +++ b/unit/test-hashmap.c @@ -236,6 +236,39 @@ static void foreach_cb(const void *key, void *value, void *user_data) } } +static unsigned int find_called = 0; + +static bool find_cb(const void *key, void *value, void *user_data) +{ + struct l_hashmap *hashmap = user_data; + static bool removed; + static unsigned int entries; + char *str, *mykey = "b"; + bool ret; + + if (!removed) { + printf("Removing entry in find\n"); + + str = l_hashmap_remove(hashmap, "world"); + assert(str); + + assert(!l_hashmap_lookup(hashmap, "world")); + + entries = l_hashmap_size(hashmap); + + removed = true; + } + + find_called++; + + if (!(find_called % 2)) { + assert(entries == 3); + return true; + } + + return false; +} + static void test_reentrant(const void *test_data) { struct l_hashmap *hashmap; @@ -261,6 +294,9 @@ static void test_reentrant(const void *test_data) l_hashmap_foreach(hashmap, foreach_cb, hashmap); + l_hashmap_find(hashmap, find_cb, hashmap); + assert(find_called == 2); + l_hashmap_destroy(hashmap, NULL); } -- 1.8.3.1