mtd-utils-1.3.1/ubi-utils/old-utils/src/hashmap.c

/*
 * 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;
}