>From 96499e27955e55b86d0dd13d36c33decf149aacd Mon Sep 17 00:00:00 2001 From: Bruno Haible Date: Tue, 4 Dec 2018 00:54:30 +0100 Subject: [PATCH 4/8] hash-set: New module. * lib/gl_hash_set.h: New file. * lib/gl_hash_set.c: New file. * modules/hash-set: New file. --- ChangeLog | 7 ++ lib/gl_hash_set.c | 315 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ lib/gl_hash_set.h | 34 ++++++ modules/hash-set | 28 +++++ 4 files changed, 384 insertions(+) create mode 100644 lib/gl_hash_set.c create mode 100644 lib/gl_hash_set.h create mode 100644 modules/hash-set diff --git a/ChangeLog b/ChangeLog index 5f0ae48..a8f2314 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,12 @@ 2018-12-03 Bruno Haible + hash-set: New module. + * lib/gl_hash_set.h: New file. + * lib/gl_hash_set.c: New file. + * modules/hash-set: New file. + +2018-12-03 Bruno Haible + linkedhash-set: New module. * lib/gl_linkedhash_set.h: New file. * lib/gl_linkedhash_set.c: New file. diff --git a/lib/gl_hash_set.c b/lib/gl_hash_set.c new file mode 100644 index 0000000..1f2f141 --- /dev/null +++ b/lib/gl_hash_set.c @@ -0,0 +1,315 @@ +/* Set 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_set.h" + +#include /* for SIZE_MAX */ +#include + +#include "xsize.h" + +#ifndef uintptr_t +# define uintptr_t unsigned long +#endif + +/* --------------------------- gl_set_t Data Type --------------------------- */ + +#include "gl_anyhash_set1.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 *value; +}; +typedef struct gl_list_node_impl * gl_list_node_t; + +/* Concrete gl_set_impl type, valid for this file only. */ +struct gl_set_impl +{ + struct gl_set_impl_base base; + gl_setelement_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; +}; + +#include "gl_anyhash_set2.h" + +/* --------------------------- gl_set_t Data Type --------------------------- */ + +static gl_set_t +gl_hash_nx_create_empty (gl_set_implementation_t implementation, + gl_setelement_equals_fn equals_fn, + gl_setelement_hashcode_fn hashcode_fn, + gl_setelement_dispose_fn dispose_fn) +{ + struct gl_set_impl *set = + (struct gl_set_impl *) malloc (sizeof (struct gl_set_impl)); + + if (set == NULL) + return NULL; + + set->base.vtable = implementation; + set->base.equals_fn = equals_fn; + set->base.dispose_fn = dispose_fn; + set->hashcode_fn = hashcode_fn; + set->table_size = 11; + set->table = + (gl_hash_entry_t *) calloc (set->table_size, sizeof (gl_hash_entry_t)); + if (set->table == NULL) + goto fail; + set->count = 0; + + return set; + + fail: + free (set); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_hash_size (gl_set_t set) +{ + return set->count; +} + +static bool _GL_ATTRIBUTE_PURE +gl_hash_search (gl_set_t set, const void *elt) +{ + size_t hashcode = + (set->hashcode_fn != NULL + ? set->hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % set->table_size; + gl_setelement_equals_fn equals = set->base.equals_fn; + + /* Look for a match in the hash bucket. */ + gl_list_node_t node; + + for (node = (gl_list_node_t) set->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->value)) + return true; + return false; +} + +static int +gl_hash_nx_add (gl_set_t set, const void *elt) +{ + size_t hashcode = + (set->hashcode_fn != NULL + ? set->hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % set->table_size; + gl_setelement_equals_fn equals = set->base.equals_fn; + + /* Look for a match in the hash bucket. */ + { + gl_list_node_t node; + + for (node = (gl_list_node_t) set->table[bucket]; + node != NULL; + node = (gl_list_node_t) node->h.hash_next) + if (node->h.hashcode == hashcode + && (equals != NULL + ? equals (elt, node->value) + : elt == node->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->value = elt; + node->h.hashcode = hashcode; + + /* Add node to the hash table. */ + node->h.hash_next = set->table[bucket]; + set->table[bucket] = &node->h; + + /* Add node to the set. */ + set->count++; + + hash_resize_after_add (set); + + return 1; +} + +static bool +gl_hash_remove (gl_set_t set, const void *elt) +{ + size_t hashcode = + (set->hashcode_fn != NULL + ? set->hashcode_fn (elt) + : (size_t)(uintptr_t) elt); + size_t bucket = hashcode % set->table_size; + gl_setelement_equals_fn equals = set->base.equals_fn; + + /* Look for the first match in the hash bucket. */ + gl_list_node_t *nodep; + + for (nodep = (gl_list_node_t *) &set->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 (elt, node->value) + : elt == node->value)) + { + /* Remove node from the hash table. */ + *nodep = (gl_list_node_t) node->h.hash_next; + + /* Remove node from the set. */ + set->count--; + + if (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); + free (node); + return true; + } + } + + return false; +} + +static void +gl_hash_free (gl_set_t set) +{ + if (set->count > 0) + { + gl_setelement_dispose_fn dispose = set->base.dispose_fn; + struct gl_hash_entry **table = set->table; + size_t i; + + for (i = set->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 (dispose != NULL) + dispose (((gl_list_node_t) node)->value); + free (node); + + node = next; + } + } + } + + free (set->table); + free (set); +} + +/* ---------------------- gl_set_iterator_t Data Type ---------------------- */ + +/* Here we iterate through the hash buckets. Therefore the order in which the + elements are returned is unpredictable. */ + +static gl_set_iterator_t +gl_hash_iterator (gl_set_t set) +{ + gl_set_iterator_t result; + + result.vtable = set->base.vtable; + result.set = set; + result.p = NULL; /* runs through the nodes of a bucket */ + result.i = 0; /* index of the bucket that p points into + 1 */ + result.j = set->table_size; +#if defined GCC_LINT || defined lint + result.q = NULL; + result.count = 0; +#endif + + return result; +} + +static bool +gl_hash_iterator_next (gl_set_iterator_t *iterator, const void **eltp) +{ + if (iterator->p != NULL) + { + /* We're traversing a bucket. */ + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = 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->set->table; + do + { + gl_list_node_t node = (gl_list_node_t) table[i++]; + if (node != NULL) + { + *eltp = 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_set_iterator_t *iterator) +{ +} + + +const struct gl_set_implementation gl_hash_set_implementation = + { + gl_hash_nx_create_empty, + gl_hash_size, + gl_hash_search, + gl_hash_nx_add, + gl_hash_remove, + gl_hash_free, + gl_hash_iterator, + gl_hash_iterator_next, + gl_hash_iterator_free + }; diff --git a/lib/gl_hash_set.h b/lib/gl_hash_set.h new file mode 100644 index 0000000..7d3d500 --- /dev/null +++ b/lib/gl_hash_set.h @@ -0,0 +1,34 @@ +/* Set 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_SET_H +#define _GL_HASH_SET_H + +#include "gl_set.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_set_implementation gl_hash_set_implementation; +#define GL_HASH_SET &gl_hash_set_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_HASH_SET_H */ diff --git a/modules/hash-set b/modules/hash-set new file mode 100644 index 0000000..cd8ac8b --- /dev/null +++ b/modules/hash-set @@ -0,0 +1,28 @@ +Description: +Set data type implemented by a hash table. + +Files: +lib/gl_hash_set.h +lib/gl_hash_set.c +lib/gl_anyhash_set1.h +lib/gl_anyhash_set2.h +lib/gl_anyhash_primes.h + +Depends-on: +set +stdint +xsize + +configure.ac: + +Makefile.am: +lib_SOURCES += gl_hash_set.h gl_hash_set.c gl_anyhash_set1.h gl_anyhash_set2.h gl_anyhash_primes.h + +Include: +"gl_hash_set.h" + +License: +GPL + +Maintainer: +all -- 2.7.4