summaryrefslogtreecommitdiff
path: root/src/hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/hashmap.c')
-rw-r--r--src/hashmap.c526
1 files changed, 262 insertions, 264 deletions
diff --git a/src/hashmap.c b/src/hashmap.c
index 15e5ffe..c060c60 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -1,4 +1,4 @@
-/* $Id: hashmap.c,v 1.16 2005-07-12 17:39:43 rjkaes Exp $
+/* $Id: hashmap.c,v 1.17 2005-08-15 03:54:31 rjkaes Exp $
*
* A hashmap implementation. The keys are case-insensitive NULL terminated
* strings, and the data is arbitrary lumps of data. Copies of both the
@@ -38,11 +38,11 @@
* with.
*/
struct hashentry_s {
- char *key;
- void *data;
- size_t len;
+ char *key;
+ void *data;
+ size_t len;
- struct hashentry_s *prev, *next;
+ struct hashentry_s *prev, *next;
};
struct hashbucket_s {
@@ -50,10 +50,10 @@ struct hashbucket_s {
};
struct hashmap_s {
- unsigned int size;
- hashmap_iter end_iterator;
+ unsigned int size;
+ hashmap_iter end_iterator;
- struct hashbucket_s *buckets;
+ struct hashbucket_s *buckets;
};
/*
@@ -68,23 +68,23 @@ struct hashmap_s {
static int
hashfunc(const char *key, unsigned int size)
{
- uint32_t hash;
-
- if (key == NULL)
- return -EINVAL;
- if (size == 0)
- return -ERANGE;
-
- for (hash = tolower(*key++); *key != '\0'; key++) {
- uint32_t bit =
- (hash & 1) ? (1 << (sizeof(uint32_t) - 1)) : 0;
- hash >>= 1;
-
- hash += tolower(*key) + bit;
- }
-
- /* Keep the hash within the table limits */
- return hash % size;
+ uint32_t hash;
+
+ if (key == NULL)
+ return -EINVAL;
+ if (size == 0)
+ return -ERANGE;
+
+ for (hash = tolower(*key++); *key != '\0'; key++) {
+ uint32_t bit = (hash & 1) ? (1 << (sizeof(uint32_t) - 1)) : 0;
+
+ hash >>= 1;
+
+ hash += tolower(*key) + bit;
+ }
+
+ /* Keep the hash within the table limits */
+ return hash % size;
}
/*
@@ -97,26 +97,26 @@ hashfunc(const char *key, unsigned int size)
hashmap_t
hashmap_create(unsigned int nbuckets)
{
- struct hashmap_s* ptr;
+ struct hashmap_s *ptr;
- if (nbuckets == 0)
- return NULL;
+ if (nbuckets == 0)
+ return NULL;
- ptr = safecalloc(1, sizeof(struct hashmap_s));
- if (!ptr)
- return NULL;
+ ptr = safecalloc(1, sizeof(struct hashmap_s));
+ if (!ptr)
+ return NULL;
- ptr->size = nbuckets;
- ptr->buckets = safecalloc(nbuckets, sizeof(struct hashbucket_s));
- if (!ptr->buckets) {
- safefree(ptr);
- return NULL;
- }
+ ptr->size = nbuckets;
+ ptr->buckets = safecalloc(nbuckets, sizeof(struct hashbucket_s));
+ if (!ptr->buckets) {
+ safefree(ptr);
+ return NULL;
+ }
- /* This points to "one" past the end of the hashmap. */
- ptr->end_iterator = 0;
+ /* This points to "one" past the end of the hashmap. */
+ ptr->end_iterator = 0;
- return ptr;
+ return ptr;
}
/*
@@ -127,26 +127,26 @@ hashmap_create(unsigned int nbuckets)
* negative number is returned if "entry" was NULL
*/
static inline int
-delete_hashbucket(struct hashbucket_s* bucket)
+delete_hashbucket(struct hashbucket_s *bucket)
{
- struct hashentry_s *nextptr;
- struct hashentry_s *ptr;
+ struct hashentry_s *nextptr;
+ struct hashentry_s *ptr;
+
+ if (bucket == NULL || bucket->head == NULL)
+ return -EINVAL;
- if (bucket == NULL || bucket->head == NULL)
- return -EINVAL;
+ ptr = bucket->head;
+ while (ptr) {
+ nextptr = ptr->next;
- ptr = bucket->head;
- while (ptr) {
- nextptr = ptr->next;
-
- safefree(ptr->key);
- safefree(ptr->data);
- safefree(ptr);
+ safefree(ptr->key);
+ safefree(ptr->data);
+ safefree(ptr);
- ptr = nextptr;
- }
+ ptr = nextptr;
+ }
- return 0;
+ return 0;
}
/*
@@ -158,21 +158,21 @@ delete_hashbucket(struct hashbucket_s* bucket)
int
hashmap_delete(hashmap_t map)
{
- unsigned int i;
-
- if (map == NULL)
- return -EINVAL;
+ unsigned int i;
+
+ if (map == NULL)
+ return -EINVAL;
- for (i = 0; i != map->size; i++) {
- if (map->buckets[i].head != NULL) {
- delete_hashbucket(&map->buckets[i]);
- }
- }
+ for (i = 0; i != map->size; i++) {
+ if (map->buckets[i].head != NULL) {
+ delete_hashbucket(&map->buckets[i]);
+ }
+ }
- safefree(map->buckets);
- safefree(map);
+ safefree(map->buckets);
+ safefree(map);
- return 0;
+ return 0;
}
/*
@@ -186,57 +186,56 @@ hashmap_delete(hashmap_t map)
* negative number if there are errors
*/
int
-hashmap_insert(hashmap_t map, const char *key,
- const void *data, size_t len)
+hashmap_insert(hashmap_t map, const char *key, const void *data, size_t len)
{
- struct hashentry_s *ptr;
- int hash;
- char *key_copy;
- void *data_copy;
-
- assert(map != NULL);
- assert(key != NULL);
- assert(data != NULL);
- assert(len > 0);
-
- if (map == NULL || key == NULL)
- return -EINVAL;
- if (!data || len < 1)
- return -ERANGE;
-
- hash = hashfunc(key, map->size);
- if (hash < 0)
- return hash;
-
- /*
- * First make copies of the key and data in case there is a memory
- * problem later.
- */
- key_copy = safestrdup(key);
- if (!key_copy)
- return -ENOMEM;
-
- if (data) {
- data_copy = safemalloc(len);
- if (!data_copy) {
- safefree(key_copy);
- return -ENOMEM;
- }
- memcpy(data_copy, data, len);
- } else {
- data_copy = NULL;
- }
-
- ptr = safemalloc(sizeof(struct hashentry_s));
- if (!ptr) {
- safefree(key_copy);
- safefree(data_copy);
- return -ENOMEM;
- }
-
- ptr->key = key_copy;
- ptr->data = data_copy;
- ptr->len = len;
+ struct hashentry_s *ptr;
+ int hash;
+ char *key_copy;
+ void *data_copy;
+
+ assert(map != NULL);
+ assert(key != NULL);
+ assert(data != NULL);
+ assert(len > 0);
+
+ if (map == NULL || key == NULL)
+ return -EINVAL;
+ if (!data || len < 1)
+ return -ERANGE;
+
+ hash = hashfunc(key, map->size);
+ if (hash < 0)
+ return hash;
+
+ /*
+ * First make copies of the key and data in case there is a memory
+ * problem later.
+ */
+ key_copy = safestrdup(key);
+ if (!key_copy)
+ return -ENOMEM;
+
+ if (data) {
+ data_copy = safemalloc(len);
+ if (!data_copy) {
+ safefree(key_copy);
+ return -ENOMEM;
+ }
+ memcpy(data_copy, data, len);
+ } else {
+ data_copy = NULL;
+ }
+
+ ptr = safemalloc(sizeof(struct hashentry_s));
+ if (!ptr) {
+ safefree(key_copy);
+ safefree(data_copy);
+ return -ENOMEM;
+ }
+
+ ptr->key = key_copy;
+ ptr->data = data_copy;
+ ptr->len = len;
/*
* Now add the entry to the end of the bucket chain.
@@ -245,13 +244,13 @@ hashmap_insert(hashmap_t map, const char *key,
ptr->prev = map->buckets[hash].tail;
if (map->buckets[hash].tail)
map->buckets[hash].tail->next = ptr;
-
+
map->buckets[hash].tail = ptr;
if (!map->buckets[hash].head)
map->buckets[hash].head = ptr;
- map->end_iterator++;
- return 0;
+ map->end_iterator++;
+ return 0;
}
/*
@@ -262,15 +261,15 @@ hashmap_insert(hashmap_t map, const char *key,
hashmap_iter
hashmap_first(hashmap_t map)
{
- assert(map != NULL);
+ assert(map != NULL);
- if (!map)
- return -EINVAL;
+ if (!map)
+ return -EINVAL;
- if (map->end_iterator == 0)
- return -1;
- else
- return 0;
+ if (map->end_iterator == 0)
+ return -1;
+ else
+ return 0;
}
/*
@@ -282,16 +281,16 @@ hashmap_first(hashmap_t map)
int
hashmap_is_end(hashmap_t map, hashmap_iter iter)
{
- assert(map != NULL);
- assert(iter >= 0);
+ assert(map != NULL);
+ assert(iter >= 0);
- if (!map || iter < 0)
- return -EINVAL;
+ if (!map || iter < 0)
+ return -EINVAL;
- if (iter == map->end_iterator)
- return 1;
- else
- return 0;
+ if (iter == map->end_iterator)
+ return 1;
+ else
+ return 0;
}
/*
@@ -303,37 +302,37 @@ hashmap_is_end(hashmap_t map, hashmap_iter iter)
* an "end-iterator" if the key wasn't found
*/
hashmap_iter
-hashmap_find(hashmap_t map, const char* key)
+hashmap_find(hashmap_t map, const char *key)
{
- unsigned int i;
- hashmap_iter iter = 0;
- struct hashentry_s* ptr;
-
- assert(map != NULL);
- assert(key != NULL);
-
- if (!map || !key)
- return -EINVAL;
-
- /*
- * Loop through all the keys and look for the first occurrence
- * of a particular key.
- */
- for (i = 0; i != map->size; i++) {
- ptr = map->buckets[i].head;
-
- while (ptr) {
- if (strcasecmp(ptr->key, key) == 0) {
- /* Found it, so return the current count */
- return iter;
- }
-
- iter++;
- ptr = ptr->next;
- }
- }
-
- return iter;
+ unsigned int i;
+ hashmap_iter iter = 0;
+ struct hashentry_s *ptr;
+
+ assert(map != NULL);
+ assert(key != NULL);
+
+ if (!map || !key)
+ return -EINVAL;
+
+ /*
+ * Loop through all the keys and look for the first occurrence
+ * of a particular key.
+ */
+ for (i = 0; i != map->size; i++) {
+ ptr = map->buckets[i].head;
+
+ while (ptr) {
+ if (strcasecmp(ptr->key, key) == 0) {
+ /* Found it, so return the current count */
+ return iter;
+ }
+
+ iter++;
+ ptr = ptr->next;
+ }
+ }
+
+ return iter;
}
/*
@@ -343,38 +342,37 @@ hashmap_find(hashmap_t map, const char* key)
* negative upon error
*/
ssize_t
-hashmap_return_entry(hashmap_t map, hashmap_iter iter,
- char** key, void** data)
+hashmap_return_entry(hashmap_t map, hashmap_iter iter, char **key, void **data)
{
- unsigned int i;
- struct hashentry_s* ptr;
- hashmap_iter count = 0;
-
- assert(map != NULL);
- assert(iter >= 0);
- assert(iter != map->end_iterator);
- assert(key != NULL);
- assert(data != NULL);
-
- if (!map || iter < 0 || !key || !data)
- return -EINVAL;
-
- for (i = 0; i != map->size; i++) {
- ptr = map->buckets[i].head;
- while (ptr) {
- if (count == iter) {
- /* This is the data so return it */
- *key = ptr->key;
- *data = ptr->data;
- return ptr->len;
- }
-
- ptr = ptr->next;
- count++;
- }
- }
-
- return -EFAULT;
+ unsigned int i;
+ struct hashentry_s *ptr;
+ hashmap_iter count = 0;
+
+ assert(map != NULL);
+ assert(iter >= 0);
+ assert(iter != map->end_iterator);
+ assert(key != NULL);
+ assert(data != NULL);
+
+ if (!map || iter < 0 || !key || !data)
+ return -EINVAL;
+
+ for (i = 0; i != map->size; i++) {
+ ptr = map->buckets[i].head;
+ while (ptr) {
+ if (count == iter) {
+ /* This is the data so return it */
+ *key = ptr->key;
+ *data = ptr->data;
+ return ptr->len;
+ }
+
+ ptr = ptr->next;
+ count++;
+ }
+ }
+
+ return -EFAULT;
}
/*
@@ -387,29 +385,29 @@ hashmap_return_entry(hashmap_t map, hashmap_iter iter,
ssize_t
hashmap_search(hashmap_t map, const char *key)
{
- int hash;
- struct hashentry_s* ptr;
- ssize_t count = 0;
+ int hash;
+ struct hashentry_s *ptr;
+ ssize_t count = 0;
- if (map == NULL || key == NULL)
- return -EINVAL;
+ if (map == NULL || key == NULL)
+ return -EINVAL;
- hash = hashfunc(key, map->size);
- if (hash < 0)
- return hash;
+ hash = hashfunc(key, map->size);
+ if (hash < 0)
+ return hash;
- ptr = map->buckets[hash].head;
+ ptr = map->buckets[hash].head;
- /* All right, there is an entry here, now see if it's the one we want */
- while (ptr) {
- if (strcasecmp(ptr->key, key) == 0)
- ++count;
+ /* All right, there is an entry here, now see if it's the one we want */
+ while (ptr) {
+ if (strcasecmp(ptr->key, key) == 0)
+ ++count;
- /* This entry didn't contain the key; move to the next one */
- ptr = ptr->next;
- }
+ /* This entry didn't contain the key; move to the next one */
+ ptr = ptr->next;
+ }
- return count;
+ return count;
}
/*
@@ -421,30 +419,30 @@ hashmap_search(hashmap_t map, const char *key)
* length of data for the entry
*/
ssize_t
-hashmap_entry_by_key(hashmap_t map, const char* key, void** data)
+hashmap_entry_by_key(hashmap_t map, const char *key, void **data)
{
- int hash;
- struct hashentry_s* ptr;
+ int hash;
+ struct hashentry_s *ptr;
+
+ if (!map || !key || !data)
+ return -EINVAL;
- if (!map || !key || !data)
- return -EINVAL;
-
- hash = hashfunc(key, map->size);
- if (hash < 0)
- return hash;
+ hash = hashfunc(key, map->size);
+ if (hash < 0)
+ return hash;
- ptr = map->buckets[hash].head;
+ ptr = map->buckets[hash].head;
- while (ptr) {
- if (strcasecmp(ptr->key, key) == 0) {
- *data = ptr->data;
- return ptr->len;
- }
+ while (ptr) {
+ if (strcasecmp(ptr->key, key) == 0) {
+ *data = ptr->data;
+ return ptr->len;
+ }
- ptr = ptr->next;
- }
+ ptr = ptr->next;
+ }
- return 0;
+ return 0;
}
/*
@@ -458,26 +456,26 @@ hashmap_entry_by_key(hashmap_t map, const char* key, void** data)
ssize_t
hashmap_remove(hashmap_t map, const char *key)
{
- int hash;
- struct hashentry_s *ptr, *next;
- short int deleted = 0;
-
- if (map == NULL || key == NULL)
- return -EINVAL;
-
- hash = hashfunc(key, map->size);
- if (hash < 0)
- return hash;
-
- ptr = map->buckets[hash].head;
- while (ptr) {
- if (strcasecmp(ptr->key, key) == 0) {
- /*
- * Found the data, now need to remove everything
- * and update the hashmap.
- */
+ int hash;
+ struct hashentry_s *ptr, *next;
+ short int deleted = 0;
+
+ if (map == NULL || key == NULL)
+ return -EINVAL;
+
+ hash = hashfunc(key, map->size);
+ if (hash < 0)
+ return hash;
+
+ ptr = map->buckets[hash].head;
+ while (ptr) {
+ if (strcasecmp(ptr->key, key) == 0) {
+ /*
+ * Found the data, now need to remove everything
+ * and update the hashmap.
+ */
next = ptr->next;
-
+
if (ptr->prev)
ptr->prev->next = ptr->next;
if (ptr->next)
@@ -487,22 +485,22 @@ hashmap_remove(hashmap_t map, const char *key)
map->buckets[hash].head = ptr->next;
if (map->buckets[hash].tail == ptr)
map->buckets[hash].tail = ptr->prev;
-
- safefree(ptr->key);
- safefree(ptr->data);
- safefree(ptr);
-
- ++deleted;
- --map->end_iterator;
+
+ safefree(ptr->key);
+ safefree(ptr->data);
+ safefree(ptr);
+
+ ++deleted;
+ --map->end_iterator;
ptr = next;
- continue;
- }
+ continue;
+ }
- /* This entry didn't contain the key; move to the next one */
- ptr = ptr->next;
- }
+ /* This entry didn't contain the key; move to the next one */
+ ptr = ptr->next;
+ }
- /* The key was not found, so return 0 */
- return deleted;
+ /* The key was not found, so return 0 */
+ return deleted;
}
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-22 15:22:07 +0000