summaryrefslogtreecommitdiff
path: root/ubi-utils/src/hashmap.c
diff options
context:
space:
mode:
authorArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2007-05-04 21:00:46 +0300
committerArtem Bityutskiy <Artem.Bityutskiy@nokia.com>2007-05-04 21:00:46 +0300
commit80cecea79cf13075d136e73067aa40439539bb0f (patch)
treef28acc5b3a124c3a7355f77ccdbad48753f55872 /ubi-utils/src/hashmap.c
parent726ac243f051f0daee6149db66ac21ba621fb454 (diff)
parent22f90673165489fd50c893a91051a79c1b143d2a (diff)
Merge branch 'ubi'
Diffstat (limited to 'ubi-utils/src/hashmap.c')
-rw-r--r--ubi-utils/src/hashmap.c412
1 files changed, 412 insertions, 0 deletions
diff --git a/ubi-utils/src/hashmap.c b/ubi-utils/src/hashmap.c
new file mode 100644
index 0000000..3511d56
--- /dev/null
+++ b/ubi-utils/src/hashmap.c
@@ -0,0 +1,412 @@
+/*
+ * Copyright (c) International Business Machines Corp., 2006
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See
+ * the GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ *
+ * Author: Oliver Lohmann
+ */
+
+#include <errno.h>
+#include <string.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include "error.h"
+#include "hashmap.h"
+#define DEFAULT_BUCKETS 4096
+
+#if 0
+#define INFO_MSG(fmt...) do { \
+ info_msg(fmt); \
+} while (0)
+#else
+#define INFO_MSG(fmt...)
+#endif
+
+struct hashentry {
+ char* key; /* key '0' term. str */
+ char* value; /* payload '0' term. str */
+
+ hashentry_t next;
+};
+
+struct hashmap {
+ size_t entries; /* current #entries */
+ size_t maxsize; /* no. of hash buckets */
+ hashentry_t* data; /* array of buckets */
+};
+
+static int
+is_empty(hashentry_t l)
+{
+ return l == NULL ? 1 : 0;
+}
+
+hashmap_t
+hashmap_new(void)
+{
+ hashmap_t res;
+ res = (hashmap_t) calloc(1, sizeof(struct hashmap));
+
+ if (res == NULL)
+ return NULL;
+
+ res->maxsize = DEFAULT_BUCKETS;
+ res->entries = 0;
+
+ res->data = (hashentry_t*)
+ calloc(1, res->maxsize * sizeof(struct hashentry));
+
+ if (res->data == NULL)
+ return NULL;
+
+ return res;
+}
+
+static hashentry_t
+new_entry(const char* key, const char* value)
+{
+ hashentry_t res;
+
+ res = (hashentry_t) calloc(1, sizeof(struct hashentry));
+
+ if (res == NULL)
+ return NULL;
+
+ /* allocate key and value and copy them */
+ res->key = strdup(key);
+ if (res->key == NULL) {
+ free(res);
+ return NULL;
+ }
+
+ res->value = strdup(value);
+ if (res->value == NULL) {
+ free(res->key);
+ free(res);
+ return NULL;
+ }
+
+ res->next = NULL;
+
+ return res;
+}
+
+static hashentry_t
+free_entry(hashentry_t e)
+{
+ if (!is_empty(e)) {
+ if(e->key != NULL) {
+ free(e->key);
+ }
+ if(e->value != NULL)
+ free(e->value);
+ free(e);
+ }
+
+ return NULL;
+}
+
+static hashentry_t
+remove_entry(hashentry_t l, const char* key, size_t* entries)
+{
+ hashentry_t lnext;
+ if (is_empty(l))
+ return NULL;
+
+ if(strcmp(l->key,key) == 0) {
+ lnext = l->next;
+ l = free_entry(l);
+ (*entries)--;
+ return lnext;
+ }
+
+ l->next = remove_entry(l->next, key, entries);
+
+ return l;
+}
+
+static hashentry_t
+insert_entry(hashentry_t l, hashentry_t e, size_t* entries)
+{
+ if (is_empty(l)) {
+ (*entries)++;
+ return e;
+ }
+
+ /* check for update */
+ if (strcmp(l->key, e->key) == 0) {
+ e->next = l->next;
+ l = free_entry(l);
+ return e;
+ }
+
+ l->next = insert_entry(l->next, e, entries);
+ return l;
+}
+
+static hashentry_t
+remove_all(hashentry_t l, size_t* entries)
+{
+ hashentry_t lnext;
+ if (is_empty(l))
+ return NULL;
+
+ lnext = l->next;
+ free_entry(l);
+ (*entries)--;
+
+ return remove_all(lnext, entries);
+}
+
+static const char*
+value_lookup(hashentry_t l, const char* key)
+{
+ if (is_empty(l))
+ return NULL;
+
+ if (strcmp(l->key, key) == 0)
+ return l->value;
+
+ return value_lookup(l->next, key);
+}
+
+static void
+print_all(hashentry_t l)
+{
+ if (is_empty(l)) {
+ printf("\n");
+ return;
+ }
+
+ printf("%s=%s", l->key, l->value);
+ if (!is_empty(l->next)) {
+ printf(",");
+ }
+
+ print_all(l->next);
+}
+
+static void
+keys_to_array(hashentry_t l, const char** a, size_t* i)
+{
+ if (is_empty(l))
+ return;
+
+ a[*i] = l->key;
+ (*i)++;
+
+ keys_to_array(l->next, a, i);
+}
+
+uint32_t
+hash_str(const char* str, uint32_t mapsize)
+{
+ uint32_t hash = 0;
+ uint32_t x = 0;
+ uint32_t i = 0;
+ size_t len = strlen(str);
+
+ for(i = 0; i < len; str++, i++) {
+ hash = (hash << 4) + (*str);
+ if((x = hash & 0xF0000000L) != 0) {
+ hash ^= (x >> 24);
+ hash &= ~x;
+ }
+ }
+
+ return (hash & 0x7FFFFFFF) % mapsize;
+}
+
+
+int
+hashmap_is_empty(hashmap_t map)
+{
+ if (map == NULL)
+ return -EINVAL;
+
+ return map->entries > 0 ? 1 : 0;
+}
+
+const char*
+hashmap_lookup(hashmap_t map, const char* key)
+{
+ uint32_t i;
+
+ if ((map == NULL) || (key == NULL))
+ return NULL;
+
+ i = hash_str(key, map->maxsize);
+
+ return value_lookup(map->data[i], key);
+}
+
+int
+hashmap_add(hashmap_t map, const char* key, const char* value)
+{
+ uint32_t i;
+ hashentry_t entry;
+
+ if ((map == NULL) || (key == NULL) || (value == NULL))
+ return -EINVAL;
+
+ i = hash_str(key, map->maxsize);
+ entry = new_entry(key, value);
+ if (entry == NULL)
+ return -ENOMEM;
+
+ map->data[i] = insert_entry(map->data[i],
+ entry, &map->entries);
+
+ INFO_MSG("HASH_ADD: chain[%d] key:%s val:%s",i, key, value);
+ return 0;
+}
+
+int
+hashmap_remove(hashmap_t map, const char* key)
+{
+ uint32_t i;
+
+ if ((map == NULL) || (key == NULL))
+ return -EINVAL;
+
+ i = hash_str(key, map->maxsize);
+ map->data[i] = remove_entry(map->data[i], key, &map->entries);
+
+ return 0;
+}
+
+size_t
+hashmap_size(hashmap_t map)
+{
+ if (map != NULL)
+ return map->entries;
+ else
+ return 0;
+}
+
+int
+hashmap_free(hashmap_t map)
+{
+ size_t i;
+
+ if (map == NULL)
+ return -EINVAL;
+
+ /* "children" first */
+ for(i = 0; i < map->maxsize; i++) {
+ map->data[i] = remove_all(map->data[i], &map->entries);
+ }
+ free(map->data);
+ free(map);
+
+ return 0;
+}
+
+int
+hashmap_dump(hashmap_t map)
+{
+ size_t i;
+ if (map == NULL)
+ return -EINVAL;
+
+ for(i = 0; i < map->maxsize; i++) {
+ if (map->data[i] != NULL) {
+ printf("[%zd]: ", i);
+ print_all(map->data[i]);
+ }
+ }
+
+ return 0;
+}
+
+static const char**
+sort_key_vector(const char** a, size_t size)
+{
+ /* uses bubblesort */
+ size_t i, j;
+ const char* tmp;
+
+ if (size <= 0)
+ return a;
+
+ for (i = size - 1; i > 0; i--) {
+ for (j = 0; j < i; j++) {
+ if (strcmp(a[j], a[j+1]) > 0) {
+ tmp = a[j];
+ a[j] = a[j+1];
+ a[j+1] = tmp;
+ }
+ }
+ }
+ return a;
+}
+
+const char**
+hashmap_get_key_vector(hashmap_t map, size_t* size, int sort)
+{
+ const char** res;
+ size_t i, j;
+ *size = map->entries;
+
+ res = (const char**) malloc(*size * sizeof(char*));
+ if (res == NULL)
+ return NULL;
+
+ j = 0;
+ for(i=0; i < map->maxsize; i++) {
+ keys_to_array(map->data[i], res, &j);
+ }
+
+ if (sort)
+ res = sort_key_vector(res, *size);
+
+ return res;
+}
+
+int
+hashmap_key_is_in_vector(const char** vec, size_t size, const char* key)
+{
+ size_t i;
+ for (i = 0; i < size; i++) {
+ if (strcmp(vec[i], key) == 0) /* found */
+ return 1;
+ }
+
+ return 0;
+}
+
+const char**
+hashmap_get_update_key_vector(const char** vec1, size_t vec1_size,
+ const char** vec2, size_t vec2_size, size_t* res_size)
+{
+ const char** res;
+ size_t i, j;
+
+ *res_size = vec2_size;
+
+ res = (const char**) malloc(*res_size * sizeof(char*));
+ if (res == NULL)
+ return NULL;
+
+ /* get all keys from vec2 which are not set in vec1 */
+ j = 0;
+ for (i = 0; i < vec2_size; i++) {
+ if (!hashmap_key_is_in_vector(vec1, vec1_size, vec2[i]))
+ res[j++] = vec2[i];
+ }
+
+ *res_size = j;
+ return res;
+}