summaryrefslogtreecommitdiff
path: root/ubi-utils/src/hashmap.c
diff options
context:
space:
mode:
Diffstat (limited to 'ubi-utils/src/hashmap.c')
-rw-r--r--ubi-utils/src/hashmap.c412
1 files changed, 0 insertions, 412 deletions
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 <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;
-}
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-08 21:22:00 +0000