From 606f38a2221648ca5c5fa292c9f71d2ddd59fa66 Mon Sep 17 00:00:00 2001 From: Artem Bityutskiy Date: Tue, 17 Mar 2009 10:14:54 +0200 Subject: ubi-utils: re-arrange directory layout Move new-utils to ubi-utils and old ones to ubi-utils/old-utils. Signed-off-by: Artem Bityutskiy --- ubi-utils/src/hashmap.c | 412 ------------------------------------------------ 1 file changed, 412 deletions(-) delete mode 100644 ubi-utils/src/hashmap.c (limited to 'ubi-utils/src/hashmap.c') diff --git a/ubi-utils/src/hashmap.c b/ubi-utils/src/hashmap.c deleted file mode 100644 index 3511d56..0000000 --- a/ubi-utils/src/hashmap.c +++ /dev/null @@ -1,412 +0,0 @@ -/* - * 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 -#include -#include -#include -#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; -} -- cgit v1.2.3