>From 4d2c4598b2c8d1a726dd2480f6ee06c1f32ddd92 Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Wed, 12 Dec 2018 01:27:08 +0100 Subject: [PATCH 3/8] linkedhash-map: New module. * lib/gl_linkedhash_map.h: New file. * lib/gl_linkedhash_map.c: New file. * lib/gl_anyhash1.h: Update comments. * lib/gl_anyhash2.h: Likewise. * modules/linkedhash-map: New file. --- ChangeLog | 7 + lib/gl_anyhash1.h | 3 +- lib/gl_anyhash2.h | 3 +- lib/gl_linkedhash_map.c | 334 ++++++++++++++++++++++++++++++++++++++++++++++++ lib/gl_linkedhash_map.h | 34 +++++ modules/linkedhash-map | 28 ++++ 6 files changed, 407 insertions(+), 2 deletions(-) create mode 100644 lib/gl_linkedhash_map.c create mode 100644 lib/gl_linkedhash_map.h create mode 100644 modules/linkedhash-map diff --git a/ChangeLog b/ChangeLog index a24e5c1..4b7407e 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,12 @@ 2018-12-11 Bruno Haible + linkedhash-map: New module. + * lib/gl_linkedhash_map.h: New file. + * lib/gl_linkedhash_map.c: New file. + * lib/gl_anyhash1.h: Update comments. + * lib/gl_anyhash2.h: Likewise. + * modules/linkedhash-map: New file. + array-map: New module. * lib/gl_array_map.h: New file. * lib/gl_array_map.c: New file. diff --git a/lib/gl_anyhash1.h b/lib/gl_anyhash1.h index 86bdee3..dda29fe 100644 --- a/lib/gl_anyhash1.h +++ b/lib/gl_anyhash1.h @@ -17,7 +17,8 @@ /* Common code of gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c, - gl_linkedhash_set.c, gl_hash_set.c. */ + gl_linkedhash_set.c, gl_hash_set.c, + gl_linkedhash_map.c, gl_hash_map.c. */ /* Hash table entry. */ struct gl_hash_entry diff --git a/lib/gl_anyhash2.h b/lib/gl_anyhash2.h index d4c5430..c7ece04 100644 --- a/lib/gl_anyhash2.h +++ b/lib/gl_anyhash2.h @@ -17,7 +17,8 @@ /* Common code of gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c, - gl_linkedhash_set.c, gl_hash_set.c. */ + gl_linkedhash_set.c, gl_hash_set.c, + gl_linkedhash_map.c, gl_hash_map.c. */ #include "gl_anyhash_primes.h" diff --git a/lib/gl_linkedhash_map.c b/lib/gl_linkedhash_map.c new file mode 100644 index 0000000..2cf3199 --- /dev/null +++ b/lib/gl_linkedhash_map.c @@ -0,0 +1,334 @@ +/* Map data type implemented by a hash table with a linked list. + 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_linkedhash_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 */ + struct gl_list_node_impl *next; + struct gl_list_node_impl *prev; + 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; + /* A circular list anchored at root. + The first node is = root.next, the last node is = root.prev. + The root's value is unused. */ + struct gl_list_node_impl root; + /* Number of list nodes, excluding the root. */ + size_t count; +}; + +#define CONTAINER_T gl_map_t +#define CONTAINER_COUNT(map) (map)->count +#include "gl_anyhash2.h" + +/* If the symbol SIGNAL_SAFE_MAP is defined, the code is compiled in such + a way that a gl_map_t data structure may be used from within a signal + handler. The operations allowed in the signal handler are: + gl_map_iterator, gl_map_iterator_next, gl_map_iterator_free. + The map and node fields that are therefore accessed from the signal handler + are: + map->root, node->next, node->value. + We are careful to make modifications to these fields only in an order + that maintains the consistency of the list data structure at any moment, + and we use 'volatile' assignments to prevent the compiler from reordering + such assignments. */ +#ifdef SIGNAL_SAFE_MAP +# define ASYNCSAFE(type) *(type volatile *)& +#else +# define ASYNCSAFE(type) +#endif + +/* --------------------------- gl_map_t Data Type --------------------------- */ + +static gl_map_t +gl_linkedhash_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->root.next = &map->root; + map->root.prev = &map->root; + map->count = 0; + + return map; + + fail: + free (map); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_linkedhash_size (gl_map_t map) +{ + return map->count; +} + +static bool _GL_ATTRIBUTE_PURE +gl_linkedhash_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_linkedhash_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; + + ASYNCSAFE(const void *) node->key = key; + ASYNCSAFE(const void *) 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. */ + ASYNCSAFE(gl_list_node_t) node->next = &map->root; + node->prev = map->root.prev; + ASYNCSAFE(gl_list_node_t) node->prev->next = node; + map->root.prev = node; + map->count++; + + hash_resize_after_add (map); + + return 1; +} + +static bool +gl_linkedhash_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 list. */ + { + gl_list_node_t prev = node->prev; + gl_list_node_t next = node->next; + + ASYNCSAFE(gl_list_node_t) prev->next = next; + next->prev = prev; + } + map->count--; + + if (map->base.kdispose_fn != NULL) + map->base.kdispose_fn (node->key); + free (node); + return true; + } + } + + return false; +} + +static void +gl_linkedhash_free (gl_map_t map) +{ + gl_mapkey_dispose_fn kdispose = map->base.kdispose_fn; + gl_mapvalue_dispose_fn vdispose = map->base.vdispose_fn; + gl_list_node_t node; + + for (node = map->root.next; node != &map->root; ) + { + gl_list_node_t next = node->next; + if (vdispose != NULL) + vdispose (node->value); + if (kdispose != NULL) + kdispose (node->key); + free (node); + node = next; + } + free (map->table); + free (map); +} + +/* ---------------------- gl_map_iterator_t Data Type ---------------------- */ + +/* Iterate through the list, not through the hash buckets, so that the order + in which the pairs are returned is predictable. */ + +static gl_map_iterator_t +gl_linkedhash_iterator (gl_map_t map) +{ + gl_map_iterator_t result; + + result.vtable = map->base.vtable; + result.map = map; + result.p = map->root.next; + result.q = &map->root; +#if defined GCC_LINT || defined lint + result.i = 0; + result.j = 0; + result.count = 0; +#endif + + return result; +} + +static bool +gl_linkedhash_iterator_next (gl_map_iterator_t *iterator, + const void **keyp, const void **valuep) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *keyp = node->key; + *valuep = node->value; + iterator->p = node->next; + return true; + } + else + return false; +} + +static void +gl_linkedhash_iterator_free (gl_map_iterator_t *iterator) +{ +} + + +const struct gl_map_implementation gl_linkedhash_map_implementation = + { + gl_linkedhash_nx_create_empty, + gl_linkedhash_size, + gl_linkedhash_search, + gl_linkedhash_nx_getput, + gl_linkedhash_getremove, + gl_linkedhash_free, + gl_linkedhash_iterator, + gl_linkedhash_iterator_next, + gl_linkedhash_iterator_free + }; diff --git a/lib/gl_linkedhash_map.h b/lib/gl_linkedhash_map.h new file mode 100644 index 0000000..4ea98ba --- /dev/null +++ b/lib/gl_linkedhash_map.h @@ -0,0 +1,34 @@ +/* Map data type implemented by a hash table with a linked list. + 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_LINKEDHASH_MAP_H +#define _GL_LINKEDHASH_MAP_H + +#include "gl_map.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_map_implementation gl_linkedhash_map_implementation; +#define GL_LINKEDHASH_MAP &gl_linkedhash_map_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_LINKEDHASH_MAP_H */ diff --git a/modules/linkedhash-map b/modules/linkedhash-map new file mode 100644 index 0000000..3424660 --- /dev/null +++ b/modules/linkedhash-map @@ -0,0 +1,28 @@ +Description: +Set data type implemented by a hash table with a linked list. + +Files: +lib/gl_linkedhash_map.h +lib/gl_linkedhash_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_linkedhash_map.h gl_linkedhash_map.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h + +Include: +"gl_linkedhash_map.h" + +License: +GPL + +Maintainer: +all -- 2.7.4