From: Gustavo Sverzut Barbieri <barbi...@profusion.mobi>
Using an ordered array will allow binary search, the code is also
reduced.
Bonus for less memory fragmentation due less memory allocations and
less cache trashing due using linear memory for lookups.
---
ell/hashmap.c | 159 ++++++++++++++++++++++++---------------------------------
1 file changed, 66 insertions(+), 93 deletions(-)
diff --git a/ell/hashmap.c b/ell/hashmap.c
index 93e3954..d142d10 100644
--- a/ell/hashmap.c
+++ b/ell/hashmap.c
@@ -24,6 +24,7 @@
#endif
#include "util.h"
+#include "array.h"
#include "hashmap.h"
#include "private.h"
@@ -45,7 +46,6 @@ typedef const void *(*key_user_func_t) (const void *p);
struct entry {
void *key;
void *value;
- struct entry *next;
};
/**
@@ -60,7 +60,7 @@ struct l_hashmap {
key_free_func_t key_free_func;
key_user_func_t key_user_func;
unsigned int entries;
- struct entry buckets[NBUCKETS];
+ struct l_array buckets[NBUCKETS];
};
static inline void *get_key_new(const struct l_hashmap *hashmap,
@@ -85,6 +85,13 @@ static inline const void *get_key_user(const struct
l_hashmap *hashmap,
return key;
}
+static int compare(const void *pa, const void *pb, void *user_data)
+{
+ const struct l_hashmap *hashmap = user_data;
+ const struct entry *a = pa, *b = pb;
+ return hashmap->compare_func(a->key, b->key);
+}
+
static inline unsigned int hash_superfast(const uint8_t *key, unsigned int len)
{
/*
@@ -184,13 +191,9 @@ static unsigned int string_hash_func(const void *p)
return hash_superfast((const uint8_t *)sk->str, sk->len);
}
-static int string_compare(const void *pa, const void *pb)
+static int string_compare(const void *a, const void *b)
{
- const struct strkey *a = pa, *b = pb;
- int r = a->len - b->len;
- if (r == 0)
- r = memcmp(a->str, b->str, a->len);
- return r;
+ return strcmp(a, b);
}
static void *string_key_new(const void *p)
@@ -254,20 +257,18 @@ LIB_EXPORT void l_hashmap_destroy(struct l_hashmap
*hashmap,
return;
for (i = 0; i < NBUCKETS; i++) {
- struct entry *entry, *head = &hashmap->buckets[i];
+ struct l_array *array = hashmap->buckets + i;
+ struct entry *entry;
- if (!head->next)
+ if (array->member_size == 0)
continue;
- for (entry = head;; entry = entry->next) {
+ L_ARRAY_FOREACH(array, entry) {
if (destroy)
destroy(entry->key, entry->value);
-
free_key(hashmap, entry->key);
-
- if (entry->next == head)
- break;
}
+ l_array_clear(array, NULL);
}
l_free(hashmap);
@@ -286,7 +287,8 @@ LIB_EXPORT void l_hashmap_destroy(struct l_hashmap *hashmap,
LIB_EXPORT bool l_hashmap_insert(struct l_hashmap *hashmap,
const void *key, void *value)
{
- struct entry *entry, *head;
+ struct l_array *array;
+ struct entry entry;
unsigned int hash;
void *key_new;
@@ -295,28 +297,19 @@ LIB_EXPORT bool l_hashmap_insert(struct l_hashmap
*hashmap,
key_new = get_key_new(hashmap, key);
hash = hashmap->hash_func(key_new) % NBUCKETS;
- head = &hashmap->buckets[hash];
-
- if (!head->next) {
- head->key = key_new;
- head->value = value;
- head->next = head;
- goto done;
- }
-
- entry = l_new(struct entry, 1);
- entry->key = key_new;
- entry->value = value;
- entry->next = head;
+ array = hashmap->buckets + hash;
- while (head->next != entry->next)
- head = head->next;
+ if (array->member_size == 0)
+ l_array_init(array, sizeof(struct entry), 0);
- head->next = entry;
+ entry.key = key_new;
+ entry.value = value;
+ if (l_array_insert_sorted(array, &entry, compare, hashmap) < 0) {
+ free_key(hashmap, key_new);
+ return false;
+ }
-done:
hashmap->entries++;
-
return true;
}
@@ -331,56 +324,38 @@ done:
**/
LIB_EXPORT void *l_hashmap_remove(struct l_hashmap *hashmap, const void *key)
{
- struct entry *entry, *head, *prev;
+ struct l_array *array;
+ struct entry search, *entry;
unsigned int hash;
- void *key_new;
+ void *key_new, *value = NULL;
+ int pos;
if (unlikely(!hashmap))
return NULL;
key_new = get_key_new(hashmap, key);
hash = hashmap->hash_func(key_new) % NBUCKETS;
- head = &hashmap->buckets[hash];
-
- if (!head->next) {
- free_key(hashmap, key_new);
- return NULL;
- }
+ array = hashmap->buckets + hash;
- for (entry = head, prev = NULL;; prev = entry, entry = entry->next) {
- void *value;
+ if (array->member_size == 0)
+ goto end;
- if (hashmap->compare_func(key_new, entry->key))
- continue;
+ search.key = key_new;
+ pos = l_array_lookup_sorted(array, &search, compare, hashmap);
+ if (pos < 0)
+ goto end;
+ entry = l_array_get_at(array, pos);
+ if (entry) {
+ free_key(hashmap, entry->key);
value = entry->value;
-
- if (entry == head) {
- if (entry->next == head) {
- free_key(hashmap, entry->key);
- head->key = NULL;
- head->value = NULL;
- head->next = NULL;
- } else {
- entry = entry->next;
- free_key(hashmap, head->key);
- head->key = entry->key;
- head->value = entry->value;
- head->next = entry->next;
- l_free(entry);
- }
- } else {
- prev->next = entry->next;
- free_key(hashmap, entry->key);
- l_free(entry);
- }
-
- hashmap->entries--;
- free_key(hashmap, key_new);
- return value;
}
+ l_array_remove_at(array, pos);
+ hashmap->entries--;
+
+end:
free_key(hashmap, key_new);
- return NULL;
+ return value;
}
/**
@@ -394,34 +369,34 @@ LIB_EXPORT void *l_hashmap_remove(struct l_hashmap
*hashmap, const void *key)
**/
LIB_EXPORT void *l_hashmap_lookup(struct l_hashmap *hashmap, const void *key)
{
- struct entry *entry, *head;
+ struct l_array *array;
+ struct entry search, *entry;
unsigned int hash;
- void *key_new;
+ void *key_new, *value = NULL;
+ int pos;
if (unlikely(!hashmap))
return NULL;
key_new = get_key_new(hashmap, key);
hash = hashmap->hash_func(key_new) % NBUCKETS;
- head = &hashmap->buckets[hash];
+ array = hashmap->buckets + hash;
- if (!head->next) {
- free_key(hashmap, key_new);
- return NULL;
- }
+ if (array->member_size == 0)
+ goto end;
- for (entry = head;; entry = entry->next) {
- if (!hashmap->compare_func(key_new, entry->key)) {
- free_key(hashmap, key_new);
- return entry->value;
- }
+ search.key = key_new;
+ pos = l_array_lookup_sorted(array, &search, compare, hashmap);
+ if (pos < 0)
+ goto end;
- if (entry->next == head)
- break;
- }
+ entry = l_array_get_at(array, pos);
+ if (entry)
+ value = entry->value;
+end:
free_key(hashmap, key_new);
- return NULL;
+ return value;
}
/**
@@ -441,17 +416,15 @@ LIB_EXPORT void l_hashmap_foreach(struct l_hashmap
*hashmap,
return;
for (i = 0; i < NBUCKETS; i++) {
- struct entry *entry, *head = &hashmap->buckets[i];
+ const struct l_array *array = hashmap->buckets + i;
+ const struct entry *entry;
- if (!head->next)
+ if (array->member_size == 0)
continue;
- for (entry = head;; entry = entry->next) {
+ L_ARRAY_FOREACH(array, entry) {
function(get_key_user(hashmap, entry->key),
entry->value, user_data);
-
- if (entry->next == head)
- break;
}
}
}
--
1.7.10.2
_______________________________________________
connman mailing list
connman@connman.net
http://lists.connman.net/listinfo/connman
