>From b23673c63782f8468fb8261fbab9f7bab3758609 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Wed, 12 Dec 2018 01:27:47 +0100 Subject: [PATCH 4/8] hash-map: New module. * lib/gl_hash_map.h: New file. * lib/gl_hash_map.c: New file. * modules/hash-map: New file. --- ChangeLog | 5 + lib/gl_hash_map.c | 337 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/gl_hash_map.h | 34 ++++++ modules/hash-map | 28 +++++ 4 files changed, 404 insertions(+) create mode 100644 lib/gl_hash_map.c create mode 100644 lib/gl_hash_map.h create mode 100644 modules/hash-map diff --git a/ChangeLog b/ChangeLog index 4b7407e..817998e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,10 @@ 2018-12-11 Bruno Haible + hash-map: New module. + * lib/gl_hash_map.h: New file. + * lib/gl_hash_map.c: New file. + * modules/hash-map: New file. + linkedhash-map: New module. * lib/gl_linkedhash_map.h: New file. * lib/gl_linkedhash_map.c: New file. diff --git a/lib/gl_hash_map.c b/lib/gl_hash_map.c new file mode 100644 index 0000000..7d68e7b --- /dev/null +++ b/lib/gl_hash_map.c @@ -0,0 +1,337 @@ +/* Map data type implemented by a hash table. + Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc. + Written by Bruno Haible , 2018. + + 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 3 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, see . */ + +#include + +/* Specification. */ +#include "gl_hash_map.h" + +#include /* for SIZE_MAX */ +#include + +#include "xsize.h" + +#ifndef uintptr_t +# define uintptr_t unsigned long +#endif + +/* --------------------------- gl_map_t Data Type --------------------------- */ + +#include "gl_anyhash1.h" + +/* Concrete list node implementation, valid for this file only. */ +struct gl_list_node_impl +{ + struct gl_hash_entry h; /* hash table entry fields; must be first */ + const void *key; + const void *value; +}; +typedef struct gl_list_node_impl * gl_list_node_t; + +/* Concrete gl_map_impl type, valid for this file only. */ +struct gl_map_impl +{ + struct gl_map_impl_base base; + gl_mapkey_hashcode_fn hashcode_fn; + /* A hash table: managed as an array of collision lists. */ + struct gl_hash_entry **table; + size_t table_size; + /* Number of hash table entries. */ + size_t count; +}; + +#define CONTAINER_T gl_map_t +#define CONTAINER_COUNT(map) (map)->count +#include "gl_anyhash2.h" + +/* --------------------------- gl_map_t Data Type --------------------------- */ + +static gl_map_t +gl_hash_nx_create_empty (gl_map_implementation_t implementation, + gl_mapkey_equals_fn equals_fn, + gl_mapkey_hashcode_fn hashcode_fn, + gl_mapkey_dispose_fn kdispose_fn, + gl_mapvalue_dispose_fn vdispose_fn) +{ + struct gl_map_impl *map = + (struct gl_map_impl *) malloc (sizeof (struct gl_map_impl)); + + if (map == NULL) + return NULL; + + map->base.vtable = implementation; + map->base.equals_fn = equals_fn; + map->base.kdispose_fn = kdispose_fn; + map->base.vdispose_fn = vdispose_fn; + map->hashcode_fn = hashcode_fn; + map->table_size = 11; + map->table = + (gl_hash_entry_t *) calloc (map->table_size, sizeof (gl_hash_entry_t)); + if (map->table == NULL) + goto fail; + map->count = 0; + + return map; + + fail: + free (map); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_hash_size (gl_map_t map) +{ + return map->count; +} + +static bool _GL_ATTRIBUTE_PURE +gl_hash_search (gl_map_t map, const void *key, const void **valuep) +{ + size_t hashcode = + (map->hashcode_fn != NULL + ? map->hashcode_fn (key) + : (size_t)(uintptr_t) key); + size_t bucket = hashcode % map->table_size; + gl_mapkey_equals_fn equals = map->base.equals_fn; + + /* Look for a match in the hash bucket. */ + gl_list_node_t node; + + for (node = (gl_list_node_t) map->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (key, node->key) + : key == node->key)) + { + *valuep = node->value; + return true; + } + return false; +} + +static int +gl_hash_nx_getput (gl_map_t map, const void *key, const void *value, + const void **oldvaluep) +{ + size_t hashcode = + (map->hashcode_fn != NULL + ? map->hashcode_fn (key) + : (size_t)(uintptr_t) key); + size_t bucket = hashcode % map->table_size; + gl_mapkey_equals_fn equals = map->base.equals_fn; + + /* Look for a match in the hash bucket. */ + { + gl_list_node_t node; + + for (node = (gl_list_node_t) map->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (key, node->key) + : key == node->key)) + { + *oldvaluep = node->value; + node->value = value; + return 0; + } + } + + /* Allocate a new node. */ + gl_list_node_t node = + (struct gl_list_node_impl *) malloc (sizeof (struct gl_list_node_impl)); + + if (node == NULL) + return -1; + + node->key = key; + node->value = value; + node->h.hashcode = hashcode; + + /* Add node to the hash table. */ + node->h.hash_next = map->table[bucket]; + map->table[bucket] = &node->h; + + /* Add node to the map. */ + map->count++; + + hash_resize_after_add (map); + + return 1; +} + +static bool +gl_hash_getremove (gl_map_t map, const void *key, const void **oldvaluep) +{ + size_t hashcode = + (map->hashcode_fn != NULL + ? map->hashcode_fn (key) + : (size_t)(uintptr_t) key); + size_t bucket = hashcode % map->table_size; + gl_mapkey_equals_fn equals = map->base.equals_fn; + + /* Look for the first match in the hash bucket. */ + gl_list_node_t *nodep; + + for (nodep = (gl_list_node_t *) &map->table[bucket]; + *nodep != NULL; + nodep = (gl_list_node_t *) &(*nodep)->h.hash_next) + { + gl_list_node_t node = *nodep; + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (key, node->key) + : key == node->key)) + { + *oldvaluep = node->value; + + /* Remove node from the hash table. */ + *nodep = (gl_list_node_t) node->h.hash_next; + + /* Remove node from the map. */ + map->count--; + + if (map->base.kdispose_fn != NULL) + map->base.kdispose_fn (node->key); + free (node); + return true; + } + } + + return false; +} + +static void +gl_hash_free (gl_map_t map) +{ + if (map->count > 0) + { + gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn; + gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn; + struct gl_hash_entry **table = map->table; + size_t i; + + for (i = map->table_size; i > 0; ) + { + gl_hash_entry_t node = table[--i]; + + while (node != NULL) + { + gl_hash_entry_t next = node->hash_next; + + /* Free the entry. */ + if (vdispose != NULL) + vdispose (((gl_list_node_t) node)->value); + if (kdispose != NULL) + kdispose (((gl_list_node_t) node)->key); + free (node); + + node = next; + } + } + } + + free (map->table); + free (map); +} + +/* ---------------------- gl_map_iterator_t Data Type ---------------------- */ + +/* Here we iterate through the hash buckets. Therefore the order in which the + pairs are returned is unpredictable. */ + +static gl_map_iterator_t +gl_hash_iterator (gl_map_t map) +{ + gl_map_iterator_t result; + + result.vtable = map->base.vtable; + result.map = map; + result.p = NULL; /* runs through the nodes of a bucket */ + result.i = 0; /* index of the bucket that p points into + 1 */ + result.j = map->table_size; +#if defined GCC_LINT || defined lint + result.q = NULL; + result.count = 0; +#endif + + return result; +} + +static bool +gl_hash_iterator_next (gl_map_iterator_t *iterator, + const void **keyp, const void **valuep) +{ + if (iterator->p != NULL) + { + /* We're traversing a bucket. */ + gl_list_node_t node = (gl_list_node_t) iterator->p; + *keyp = node->key; + *valuep = node->value; + iterator->p = (gl_list_node_t) node->h.hash_next; + return true; + } + else + { + /* Find the next bucket that is not empty. */ + size_t j = iterator->j; + size_t i = iterator->i; + + if (i < j) + { + gl_hash_entry_t *table = iterator->map->table; + do + { + gl_list_node_t node = (gl_list_node_t) table[i++]; + if (node != NULL) + { + *keyp = node->key; + *valuep = node->value; + iterator->p = (gl_list_node_t) node->h.hash_next; + iterator->i = i; + return true; + } + } + while (i < j); + } + /* Here iterator->p is still NULL, and i == j. */ + iterator->i = j; + return false; + } +} + +static void +gl_hash_iterator_free (gl_map_iterator_t *iterator) +{ +} + + +const struct gl_map_implementation gl_hash_map_implementation = + { + gl_hash_nx_create_empty, + gl_hash_size, + gl_hash_search, + gl_hash_nx_getput, + gl_hash_getremove, + gl_hash_free, + gl_hash_iterator, + gl_hash_iterator_next, + gl_hash_iterator_free + }; diff --git a/lib/gl_hash_map.h b/lib/gl_hash_map.h new file mode 100644 index 0000000..1ae8085 --- /dev/null +++ b/lib/gl_hash_map.h @@ -0,0 +1,34 @@ +/* Map data type implemented by a hash table. + Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible , 2018. + + 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 3 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, see . */ + +#ifndef _GL_HASH_MAP_H +#define _GL_HASH_MAP_H + +#include "gl_map.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_map_implementation gl_hash_map_implementation; +#define GL_HASH_MAP &gl_hash_map_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_HASH_MAP_H */ diff --git a/modules/hash-map b/modules/hash-map new file mode 100644 index 0000000..5cc5c68 --- /dev/null +++ b/modules/hash-map @@ -0,0 +1,28 @@ +Description: +Set data type implemented by a hash table. + +Files: +lib/gl_hash_map.h +lib/gl_hash_map.c +lib/gl_anyhash1.h +lib/gl_anyhash2.h +lib/gl_anyhash_primes.h + +Depends-on: +map +stdint +xsize + +configure.ac: + +Makefile.am: +lib_SOURCES += gl_hash_map.h gl_hash_map.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h + +Include: +"gl_hash_map.h" + +License: +GPL + +Maintainer: +all -- 2.7.4