Merge branch 'ubi'

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;
+}