Mercurial > gnulib
changeset 39993:9f23dbd05922
linkedhash-set: New module.
* lib/gl_linkedhash_set.h: New file.
* lib/gl_linkedhash_set.c: New file.
* lib/gl_anyhash_set1.h: New file, based on lib/gl_anyhash_list1.h.
* lib/gl_anyhash_set2.h: New file, based on lib/gl_anyhash_list2.h.
* lib/gl_anyhash_primes.h: New file, extracted from
lib/gl_anyhash_list2.h.
* lib/gl_anyhash_list2.h: Include it.
(primes, next_prime): Remove definitions.
* modules/linkedhash-set: New file.
* modules/avltreehash-list (Files): Add lib/gl_anyhash_primes.h.
(Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
* modules/linkedhash-list (Files): Add lib/gl_anyhash_primes.h.
(Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
* modules/rbtreehash-list (Files): Add lib/gl_anyhash_primes.h.
(Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES.
| author | Bruno Haible <bruno@clisp.org> |
|---|---|
| date | Tue, 04 Dec 2018 00:53:12 +0100 |
| parents | ff9ae6bf581d |
| children | ca8fd061125a |
| files | ChangeLog lib/gl_anyhash_list2.h lib/gl_anyhash_primes.h lib/gl_anyhash_set1.h lib/gl_anyhash_set2.h lib/gl_linkedhash_set.c lib/gl_linkedhash_set.h modules/avltreehash-list modules/linkedhash-list modules/linkedhash-set modules/rbtreehash-list |
| diffstat | 11 files changed, 592 insertions(+), 73 deletions(-) [+] |
line wrap: on
line diff
--- a/ChangeLog Tue Dec 04 00:43:22 2018 +0100 +++ b/ChangeLog Tue Dec 04 00:53:12 2018 +0100 @@ -1,5 +1,22 @@ 2018-12-03 Bruno Haible <bruno@clisp.org> + linkedhash-set: New module. + * lib/gl_linkedhash_set.h: New file. + * lib/gl_linkedhash_set.c: New file. + * lib/gl_anyhash_set1.h: New file, based on lib/gl_anyhash_list1.h. + * lib/gl_anyhash_set2.h: New file, based on lib/gl_anyhash_list2.h. + * lib/gl_anyhash_primes.h: New file, extracted from + lib/gl_anyhash_list2.h. + * lib/gl_anyhash_list2.h: Include it. + (primes, next_prime): Remove definitions. + * modules/linkedhash-set: New file. + * modules/avltreehash-list (Files): Add lib/gl_anyhash_primes.h. + (Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES. + * modules/linkedhash-list (Files): Add lib/gl_anyhash_primes.h. + (Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES. + * modules/rbtreehash-list (Files): Add lib/gl_anyhash_primes.h. + (Makefile.am): Add gl_anyhash_primes.h to lib_SOURCES. + array-set: New module. * lib/gl_array_set.h: New file. * lib/gl_array_set.c: New file.
--- a/lib/gl_anyhash_list2.h Tue Dec 04 00:43:22 2018 +0100 +++ b/lib/gl_anyhash_list2.h Tue Dec 04 00:53:12 2018 +0100 @@ -18,76 +18,7 @@ /* Common code of gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */ -/* Array of primes, approximately in steps of factor 1.2. - This table was computed by executing the Common Lisp expression - (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i)))) - and feeding the result to PARI/gp. */ -static const size_t primes[] = - { - 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199, - 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543, - 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899, - 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849, - 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887, - 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277, - 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307, - 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233, - 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469, - 171731387, 206077643, 247293161, 296751781, 356102141, 427322587, - 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331, - 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL, - 3810050851UL, -#if SIZE_MAX > 4294967295UL - 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL, - 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL, - 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL, - 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL, - 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL, - 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL, - 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL, - 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL, - 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL, - 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL, - 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL, - 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL, - 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL, - 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL, - 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL, - 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL, - 923114351670013UL, 1107737222003791UL, 1329284666404567UL, - 1595141599685509UL, 1914169919622551UL, 2297003903547091UL, - 2756404684256459UL, 3307685621107757UL, 3969222745329323UL, - 4763067294395177UL, 5715680753274209UL, 6858816903929113UL, - 8230580284714831UL, 9876696341657791UL, 11852035609989371UL, - 14222442731987227UL, 17066931278384657UL, 20480317534061597UL, - 24576381040873903UL, 29491657249048679UL, 35389988698858471UL, - 42467986438630267UL, 50961583726356109UL, 61153900471627387UL, - 73384680565952851UL, 88061616679143347UL, 105673940014972061UL, - 126808728017966413UL, 152170473621559703UL, 182604568345871671UL, - 219125482015045997UL, 262950578418055169UL, 315540694101666193UL, - 378648832921999397UL, 454378599506399233UL, 545254319407679131UL, - 654305183289214771UL, 785166219947057701UL, 942199463936469157UL, - 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL, - 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL, - 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL, - 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL, - 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL, - 17419784962119465179UL, -#endif - SIZE_MAX /* sentinel, to ensure the search terminates */ - }; - -/* Return a suitable prime >= ESTIMATE. */ -static size_t -next_prime (size_t estimate) -{ - size_t i; - - for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++) - if (primes[i] >= estimate) - return primes[i]; - return SIZE_MAX; /* not a prime, but better than nothing */ -} +#include "gl_anyhash_primes.h" /* Resize the hash table with a new estimated size. */ static void
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_anyhash_primes.h Tue Dec 04 00:53:12 2018 +0100 @@ -0,0 +1,87 @@ +/* Table of primes, for use by hash tables. + Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 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 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 <https://www.gnu.org/licenses/>. */ + +/* Array of primes, approximately in steps of factor 1.2. + This table was computed by executing the Common Lisp expression + (dotimes (i 244) (format t "nextprime(~D)~%" (ceiling (expt 1.2d0 i)))) + and feeding the result to PARI/gp. */ +static const size_t primes[] = + { + 11, 13, 17, 19, 23, 29, 37, 41, 47, 59, 67, 83, 97, 127, 139, 167, 199, + 239, 293, 347, 419, 499, 593, 709, 853, 1021, 1229, 1471, 1777, 2129, 2543, + 3049, 3659, 4391, 5273, 6323, 7589, 9103, 10937, 13109, 15727, 18899, + 22651, 27179, 32609, 39133, 46957, 56359, 67619, 81157, 97369, 116849, + 140221, 168253, 201907, 242309, 290761, 348889, 418667, 502409, 602887, + 723467, 868151, 1041779, 1250141, 1500181, 1800191, 2160233, 2592277, + 3110741, 3732887, 4479463, 5375371, 6450413, 7740517, 9288589, 11146307, + 13375573, 16050689, 19260817, 23112977, 27735583, 33282701, 39939233, + 47927081, 57512503, 69014987, 82818011, 99381577, 119257891, 143109469, + 171731387, 206077643, 247293161, 296751781, 356102141, 427322587, + 512787097, 615344489, 738413383, 886096061, 1063315271, 1275978331, + 1531174013, 1837408799, 2204890543UL, 2645868653UL, 3175042391UL, + 3810050851UL, +#if SIZE_MAX > 4294967295UL + 4572061027UL, 5486473229UL, 6583767889UL, 7900521449UL, 9480625733UL, + 11376750877UL, 13652101063UL, 16382521261UL, 19659025513UL, 23590830631UL, + 28308996763UL, 33970796089UL, 40764955463UL, 48917946377UL, 58701535657UL, + 70441842749UL, 84530211301UL, 101436253561UL, 121723504277UL, + 146068205131UL, 175281846149UL, 210338215379UL, 252405858521UL, + 302887030151UL, 363464436191UL, 436157323417UL, 523388788231UL, + 628066545713UL, 753679854847UL, 904415825857UL, 1085298991109UL, + 1302358789181UL, 1562830547009UL, 1875396656429UL, 2250475987709UL, + 2700571185239UL, 3240685422287UL, 3888822506759UL, 4666587008147UL, + 5599904409713UL, 6719885291641UL, 8063862349969UL, 9676634819959UL, + 11611961783951UL, 13934354140769UL, 16721224968907UL, 20065469962669UL, + 24078563955191UL, 28894276746229UL, 34673132095507UL, 41607758514593UL, + 49929310217531UL, 59915172260971UL, 71898206713183UL, 86277848055823UL, + 103533417666967UL, 124240101200359UL, 149088121440451UL, 178905745728529UL, + 214686894874223UL, 257624273849081UL, 309149128618903UL, 370978954342639UL, + 445174745211143UL, 534209694253381UL, 641051633104063UL, 769261959724877UL, + 923114351670013UL, 1107737222003791UL, 1329284666404567UL, + 1595141599685509UL, 1914169919622551UL, 2297003903547091UL, + 2756404684256459UL, 3307685621107757UL, 3969222745329323UL, + 4763067294395177UL, 5715680753274209UL, 6858816903929113UL, + 8230580284714831UL, 9876696341657791UL, 11852035609989371UL, + 14222442731987227UL, 17066931278384657UL, 20480317534061597UL, + 24576381040873903UL, 29491657249048679UL, 35389988698858471UL, + 42467986438630267UL, 50961583726356109UL, 61153900471627387UL, + 73384680565952851UL, 88061616679143347UL, 105673940014972061UL, + 126808728017966413UL, 152170473621559703UL, 182604568345871671UL, + 219125482015045997UL, 262950578418055169UL, 315540694101666193UL, + 378648832921999397UL, 454378599506399233UL, 545254319407679131UL, + 654305183289214771UL, 785166219947057701UL, 942199463936469157UL, + 1130639356723763129UL, 1356767228068515623UL, 1628120673682218619UL, + 1953744808418662409UL, 2344493770102394881UL, 2813392524122873857UL, + 3376071028947448339UL, 4051285234736937517UL, 4861542281684325481UL, + 5833850738021191727UL, 7000620885625427969UL, 8400745062750513217UL, + 10080894075300616261UL, 12097072890360739951UL, 14516487468432885797UL, + 17419784962119465179UL, +#endif + SIZE_MAX /* sentinel, to ensure the search terminates */ + }; + +/* Return a suitable prime >= ESTIMATE. */ +static size_t +next_prime (size_t estimate) +{ + size_t i; + + for (i = 0; i < sizeof (primes) / sizeof (primes[0]); i++) + if (primes[i] >= estimate) + return primes[i]; + return SIZE_MAX; /* not a prime, but better than nothing */ +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_anyhash_set1.h Tue Dec 04 00:53:12 2018 +0100 @@ -0,0 +1,27 @@ +/* Set data type implemented by a hash table with another list. + Copyright (C) 2006-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 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 <https://www.gnu.org/licenses/>. */ + +/* Common code of + gl_linkedhash_set.c, gl_hash_set.c. */ + +/* Hash table entry. */ +struct gl_hash_entry +{ + struct gl_hash_entry *hash_next; /* chain of entries in same bucket */ + size_t hashcode; /* cache of the hash code of the value */ +}; +typedef struct gl_hash_entry * gl_hash_entry_t;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_anyhash_set2.h Tue Dec 04 00:53:12 2018 +0100 @@ -0,0 +1,79 @@ +/* Set data type implemented by a hash table with another list. + Copyright (C) 2006-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 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 <https://www.gnu.org/licenses/>. */ + +/* Common code of + gl_linkedhash_set.c, gl_hash_set.c. */ + +#include "gl_anyhash_primes.h" + +/* Resize the hash table with a new estimated size. */ +static void +hash_resize (gl_set_t set, size_t estimate) +{ + size_t new_size = next_prime (estimate); + + if (new_size > set->table_size) + { + gl_hash_entry_t *old_table = set->table; + /* Allocate the new table. */ + gl_hash_entry_t *new_table; + size_t i; + + if (size_overflow_p (xtimes (new_size, sizeof (gl_hash_entry_t)))) + goto fail; + new_table = + (gl_hash_entry_t *) calloc (new_size, sizeof (gl_hash_entry_t)); + if (new_table == NULL) + goto fail; + + /* Iterate through the entries of the old table. */ + for (i = set->table_size; i > 0; ) + { + gl_hash_entry_t node = old_table[--i]; + + while (node != NULL) + { + gl_hash_entry_t next = node->hash_next; + /* Add the entry to the new table. */ + size_t bucket = node->hashcode % new_size; + node->hash_next = new_table[bucket]; + new_table[bucket] = node; + + node = next; + } + } + + set->table = new_table; + set->table_size = new_size; + free (old_table); + } + return; + + fail: + /* Just continue without resizing the table. */ + return; +} + +/* Resize the hash table if needed, after set->count was incremented. */ +static void +hash_resize_after_add (gl_set_t set) +{ + size_t count = set->count; + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate > set->table_size) + hash_resize (set, estimate); +}
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_linkedhash_set.c Tue Dec 04 00:53:12 2018 +0100 @@ -0,0 +1,313 @@ +/* Set data type implemented by a hash table with a linked list. + Copyright (C) 2006, 2008-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 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 <https://www.gnu.org/licenses/>. */ + +#include <config.h> + +/* Specification. */ +#include "gl_linkedhash_set.h" + +#include <stdint.h> /* for SIZE_MAX */ +#include <stdlib.h> + +#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 */ + struct gl_list_node_impl *next; + struct gl_list_node_impl *prev; + 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; + /* 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; +}; + +#include "gl_anyhash_set2.h" + +/* If the symbol SIGNAL_SAFE_SET is defined, the code is compiled in such + a way that a gl_set_t data structure may be used from within a signal + handler. The operations allowed in the signal handler are: + gl_set_iterator, gl_set_iterator_next, gl_set_iterator_free. + The set and node fields that are therefore accessed from the signal handler + are: + set->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_SET +# define ASYNCSAFE(type) *(type volatile *)& +#else +# define ASYNCSAFE(type) +#endif + +/* --------------------------- gl_set_t Data Type --------------------------- */ + +static gl_set_t +gl_linkedhash_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->root.next = &set->root; + set->root.prev = &set->root; + set->count = 0; + + return set; + + fail: + free (set); + return NULL; +} + +static size_t _GL_ATTRIBUTE_PURE +gl_linkedhash_size (gl_set_t set) +{ + return set->count; +} + +static bool _GL_ATTRIBUTE_PURE +gl_linkedhash_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_linkedhash_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; + + ASYNCSAFE(const void *) 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. */ + ASYNCSAFE(gl_list_node_t) node->next = &set->root; + node->prev = set->root.prev; + ASYNCSAFE(gl_list_node_t) node->prev->next = node; + set->root.prev = node; + set->count++; + + hash_resize_after_add (set); + + return 1; +} + +static bool +gl_linkedhash_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 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; + } + set->count--; + + if (set->base.dispose_fn != NULL) + set->base.dispose_fn (node->value); + free (node); + return true; + } + } + + return false; +} + +static void +gl_linkedhash_free (gl_set_t set) +{ + gl_setelement_dispose_fn dispose = set->base.dispose_fn; + gl_list_node_t node; + + for (node = set->root.next; node != &set->root; ) + { + gl_list_node_t next = node->next; + if (dispose != NULL) + dispose (node->value); + free (node); + node = next; + } + free (set->table); + free (set); +} + +/* ---------------------- gl_set_iterator_t Data Type ---------------------- */ + +/* Iterate through the list, not through the hash buckets, so that the order + in which the elements are returned is predictable. */ + +static gl_set_iterator_t +gl_linkedhash_iterator (gl_set_t set) +{ + gl_set_iterator_t result; + + result.vtable = set->base.vtable; + result.set = set; + result.p = set->root.next; + result.q = &set->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_set_iterator_t *iterator, const void **eltp) +{ + if (iterator->p != iterator->q) + { + gl_list_node_t node = (gl_list_node_t) iterator->p; + *eltp = node->value; + iterator->p = node->next; + return true; + } + else + return false; +} + +static void +gl_linkedhash_iterator_free (gl_set_iterator_t *iterator) +{ +} + + +const struct gl_set_implementation gl_linkedhash_set_implementation = + { + gl_linkedhash_nx_create_empty, + gl_linkedhash_size, + gl_linkedhash_search, + gl_linkedhash_nx_add, + gl_linkedhash_remove, + gl_linkedhash_free, + gl_linkedhash_iterator, + gl_linkedhash_iterator_next, + gl_linkedhash_iterator_free + };
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/lib/gl_linkedhash_set.h Tue Dec 04 00:53:12 2018 +0100 @@ -0,0 +1,34 @@ +/* Set data type implemented by a hash table with a linked list. + Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <bruno@clisp.org>, 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 <https://www.gnu.org/licenses/>. */ + +#ifndef _GL_LINKEDHASH_SET_H +#define _GL_LINKEDHASH_SET_H + +#include "gl_set.h" + +#ifdef __cplusplus +extern "C" { +#endif + +extern const struct gl_set_implementation gl_linkedhash_set_implementation; +#define GL_LINKEDHASH_SET &gl_linkedhash_set_implementation + +#ifdef __cplusplus +} +#endif + +#endif /* _GL_LINKEDHASH_SET_H */
--- a/modules/avltreehash-list Tue Dec 04 00:43:22 2018 +0100 +++ b/modules/avltreehash-list Tue Dec 04 00:53:12 2018 +0100 @@ -6,6 +6,7 @@ lib/gl_avltreehash_list.c lib/gl_anyhash_list1.h lib/gl_anyhash_list2.h +lib/gl_anyhash_primes.h lib/gl_anyavltree_list1.h lib/gl_anyavltree_list2.h lib/gl_anytree_list1.h @@ -23,7 +24,7 @@ configure.ac: Makefile.am: -lib_SOURCES += gl_avltreehash_list.h gl_avltreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyavltree_list1.h gl_anyavltree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h +lib_SOURCES += gl_avltreehash_list.h gl_avltreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyhash_primes.h gl_anyavltree_list1.h gl_anyavltree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h Include: "gl_avltreehash_list.h"
--- a/modules/linkedhash-list Tue Dec 04 00:43:22 2018 +0100 +++ b/modules/linkedhash-list Tue Dec 04 00:53:12 2018 +0100 @@ -6,6 +6,7 @@ lib/gl_linkedhash_list.c lib/gl_anyhash_list1.h lib/gl_anyhash_list2.h +lib/gl_anyhash_primes.h lib/gl_anylinked_list1.h lib/gl_anylinked_list2.h @@ -17,7 +18,7 @@ configure.ac: Makefile.am: -lib_SOURCES += gl_linkedhash_list.h gl_linkedhash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anylinked_list1.h gl_anylinked_list2.h +lib_SOURCES += gl_linkedhash_list.h gl_linkedhash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyhash_primes.h gl_anylinked_list1.h gl_anylinked_list2.h Include: "gl_linkedhash_list.h"
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/modules/linkedhash-set Tue Dec 04 00:53:12 2018 +0100 @@ -0,0 +1,28 @@ +Description: +Set data type implemented by a hash table with a linked list. + +Files: +lib/gl_linkedhash_set.h +lib/gl_linkedhash_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_linkedhash_set.h gl_linkedhash_set.c gl_anyhash_set1.h gl_anyhash_set2.h gl_anyhash_primes.h + +Include: +"gl_linkedhash_set.h" + +License: +GPL + +Maintainer: +all
--- a/modules/rbtreehash-list Tue Dec 04 00:43:22 2018 +0100 +++ b/modules/rbtreehash-list Tue Dec 04 00:53:12 2018 +0100 @@ -6,6 +6,7 @@ lib/gl_rbtreehash_list.c lib/gl_anyhash_list1.h lib/gl_anyhash_list2.h +lib/gl_anyhash_primes.h lib/gl_anyrbtree_list1.h lib/gl_anyrbtree_list2.h lib/gl_anytree_list1.h @@ -23,7 +24,7 @@ configure.ac: Makefile.am: -lib_SOURCES += gl_rbtreehash_list.h gl_rbtreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h +lib_SOURCES += gl_rbtreehash_list.h gl_rbtreehash_list.c gl_anyhash_list1.h gl_anyhash_list2.h gl_anyhash_primes.h gl_anyrbtree_list1.h gl_anyrbtree_list2.h gl_anytree_list1.h gl_anytree_list2.h gl_anytreehash_list1.h gl_anytreehash_list2.h Include: "gl_rbtreehash_list.h"