These *-set patches introduced a bit of code duplication. This patch here reduces the code duplication again.
2018-12-11 Bruno Haible <br...@clisp.org> hash-set, linkedhash-set: Reduce code duplication. * lib/gl_anyhash1.h: Rename from lib/gl_anyhash_list1.h and lib/gl_anyhash_set1.h. * lib/gl_anyhash2.h: Rename from lib/gl_anyhash_list2.h and lib/gl_anyhash_set2.h. Parameterize. (hash_resize_after_add): New function, from lib/gl_anyhash_set2.h. * lib/gl_anytreehash_list1.h (hash_resize_after_add): Remove function. * lib/gl_avltreehash_list.c: Include gl_anyhash1.h instead of gl_anyhash_list1.h. Include gl_anyhash2.h instead of gl_anyhash_list2.h. * lib/gl_rbtreehash_list.c: Likewise. * lib/gl_linkedhash_list.c: Likewise. (hash_resize_after_add): Remove function. * lib/gl_linkedhash_set.c: Include gl_anyhash1.h instead of gl_anyhash_set1.h. Include gl_anyhash2.h instead of gl_anyhash_set2.h. * gl_hash_set.c: Likewise. * modules/avltreehash-list (Files, Makefile.am): Update file list. * modules/rbtreehash-list (Files, Makefile.am): Likewise. * modules/linkedhash-list (Files, Makefile.am): Likewise. * modules/linkedhash-set (Files, Makefile.am): Likewise. * modules/hash-set (Files, Makefile.am): Likewise. diff --git a/lib/gl_anyhash1.h b/lib/gl_anyhash1.h new file mode 100644 index 0000000..86bdee3 --- /dev/null +++ b/lib/gl_anyhash1.h @@ -0,0 +1,30 @@ +/* Hash table for sequential list, set, and map data type. + Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <br...@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/>. */ + +/* Common code of + gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c, + 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 key (for map data type) or + - the value (for list, set data types) */ +}; +typedef struct gl_hash_entry * gl_hash_entry_t; diff --git a/lib/gl_anyhash2.h b/lib/gl_anyhash2.h new file mode 100644 index 0000000..d4c5430 --- /dev/null +++ b/lib/gl_anyhash2.h @@ -0,0 +1,81 @@ +/* Hash table for sequential list, set, and map data type. + Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. + Written by Bruno Haible <br...@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/>. */ + +/* Common code of + gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c, + 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 (CONTAINER_T container, size_t estimate) +{ + size_t new_size = next_prime (estimate); + + if (new_size > container->table_size) + { + gl_hash_entry_t *old_table = container->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 = container->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; + } + } + + container->table = new_table; + container->table_size = new_size; + free (old_table); + } + return; + + fail: + /* Just continue without resizing the table. */ + return; +} + +/* Resize the hash table if needed, after CONTAINER_COUNT (container) was + incremented. */ +static void +hash_resize_after_add (CONTAINER_T container) +{ + size_t count = CONTAINER_COUNT (container); + size_t estimate = xsum (count, count / 2); /* 1.5 * count */ + if (estimate > container->table_size) + hash_resize (container, estimate); +} diff --git a/lib/gl_anyhash_list1.h b/lib/gl_anyhash_list1.h deleted file mode 100644 index ab2c083..0000000 --- a/lib/gl_anyhash_list1.h +++ /dev/null @@ -1,27 +0,0 @@ -/* Sequential list data type implemented by a hash table with another list. - Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. - Written by Bruno Haible <br...@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/>. */ - -/* Common code of - gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.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 values' common hash code */ -}; -typedef struct gl_hash_entry * gl_hash_entry_t; diff --git a/lib/gl_anyhash_list2.h b/lib/gl_anyhash_list2.h deleted file mode 100644 index d1a5dfb..0000000 --- a/lib/gl_anyhash_list2.h +++ /dev/null @@ -1,69 +0,0 @@ -/* Sequential list data type implemented by a hash table with another list. - Copyright (C) 2006, 2009-2018 Free Software Foundation, Inc. - Written by Bruno Haible <br...@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/>. */ - -/* Common code of - gl_linkedhash_list.c, gl_avltreehash_list.c, gl_rbtreehash_list.c. */ - -#include "gl_anyhash_primes.h" - -/* Resize the hash table with a new estimated size. */ -static void -hash_resize (gl_list_t list, size_t estimate) -{ - size_t new_size = next_prime (estimate); - - if (new_size > list->table_size) - { - gl_hash_entry_t *old_table = list->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 = list->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; - } - } - - list->table = new_table; - list->table_size = new_size; - free (old_table); - } - return; - - fail: - /* Just continue without resizing the table. */ - return; -} diff --git a/lib/gl_anyhash_set1.h b/lib/gl_anyhash_set1.h deleted file mode 100644 index 0816a45..0000000 --- a/lib/gl_anyhash_set1.h +++ /dev/null @@ -1,27 +0,0 @@ -/* Set data type implemented by a hash table with another list. - Copyright (C) 2006-2018 Free Software Foundation, Inc. - Written by Bruno Haible <br...@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; diff --git a/lib/gl_anyhash_set2.h b/lib/gl_anyhash_set2.h deleted file mode 100644 index 98dc0cb..0000000 --- a/lib/gl_anyhash_set2.h +++ /dev/null @@ -1,79 +0,0 @@ -/* Set data type implemented by a hash table with another list. - Copyright (C) 2006-2018 Free Software Foundation, Inc. - Written by Bruno Haible <br...@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); -} diff --git a/lib/gl_anytreehash_list1.h b/lib/gl_anytreehash_list1.h index 6339ca0..6ee1630 100644 --- a/lib/gl_anytreehash_list1.h +++ b/lib/gl_anytreehash_list1.h @@ -28,16 +28,6 @@ struct gl_multiple_nodes gl_list_node_impl. */ #define MULTIPLE_NODES_MAGIC (void *) -1 -/* Resize the hash table if needed, after list->count was incremented. */ -static void -hash_resize_after_add (gl_list_t list) -{ - size_t count = (list->root != 0 ? list->root->branch_size : 0); - size_t estimate = xsum (count, count / 2); /* 1.5 * count */ - if (estimate > list->table_size) - hash_resize (list, estimate); -} - /* Return the position of the given node in the tree. */ static size_t node_position (gl_list_node_t node) diff --git a/lib/gl_avltreehash_list.c b/lib/gl_avltreehash_list.c index 6917e05..305d640 100644 --- a/lib/gl_avltreehash_list.c +++ b/lib/gl_avltreehash_list.c @@ -38,13 +38,16 @@ /* -------------------------- gl_list_t Data Type -------------------------- */ /* Generic hash-table code: Type definitions. */ -#include "gl_anyhash_list1.h" +#include "gl_anyhash1.h" /* Generic AVL tree code: Type definitions. */ #include "gl_anyavltree_list1.h" /* Generic hash-table code: Low-level code. */ -#include "gl_anyhash_list2.h" +#define CONTAINER_T gl_list_t +#define CONTAINER_COUNT(list) \ + ((list)->root != NULL ? (list)->root->branch_size : 0) +#include "gl_anyhash2.h" /* Generic binary tree code: Type definitions. */ #include "gl_anytree_list1.h" diff --git a/lib/gl_hash_set.c b/lib/gl_hash_set.c index 1f2f141..660ae1a 100644 --- a/lib/gl_hash_set.c +++ b/lib/gl_hash_set.c @@ -31,7 +31,7 @@ /* --------------------------- gl_set_t Data Type --------------------------- */ -#include "gl_anyhash_set1.h" +#include "gl_anyhash1.h" /* Concrete list node implementation, valid for this file only. */ struct gl_list_node_impl @@ -53,7 +53,9 @@ struct gl_set_impl size_t count; }; -#include "gl_anyhash_set2.h" +#define CONTAINER_T gl_set_t +#define CONTAINER_COUNT(set) (set)->count +#include "gl_anyhash2.h" /* --------------------------- gl_set_t Data Type --------------------------- */ diff --git a/lib/gl_linkedhash_list.c b/lib/gl_linkedhash_list.c index b978d39..690468f 100644 --- a/lib/gl_linkedhash_list.c +++ b/lib/gl_linkedhash_list.c @@ -34,23 +34,15 @@ /* -------------------------- gl_list_t Data Type -------------------------- */ /* Generic hash-table code. */ -#include "gl_anyhash_list1.h" +#include "gl_anyhash1.h" /* Generic linked list code. */ #include "gl_anylinked_list1.h" /* Generic hash-table code. */ -#include "gl_anyhash_list2.h" - -/* Resize the hash table if needed, after list->count was incremented. */ -static void -hash_resize_after_add (gl_list_t list) -{ - size_t count = list->count; - size_t estimate = xsum (count, count / 2); /* 1.5 * count */ - if (estimate > list->table_size) - hash_resize (list, estimate); -} +#define CONTAINER_T gl_list_t +#define CONTAINER_COUNT(list) (list)->count +#include "gl_anyhash2.h" /* Add a node to the hash table structure. */ static void diff --git a/lib/gl_linkedhash_set.c b/lib/gl_linkedhash_set.c index 9f2d730..021eed3 100644 --- a/lib/gl_linkedhash_set.c +++ b/lib/gl_linkedhash_set.c @@ -31,7 +31,7 @@ /* --------------------------- gl_set_t Data Type --------------------------- */ -#include "gl_anyhash_set1.h" +#include "gl_anyhash1.h" /* Concrete list node implementation, valid for this file only. */ struct gl_list_node_impl @@ -59,7 +59,9 @@ struct gl_set_impl size_t count; }; -#include "gl_anyhash_set2.h" +#define CONTAINER_T gl_set_t +#define CONTAINER_COUNT(set) (set)->count +#include "gl_anyhash2.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 diff --git a/lib/gl_rbtreehash_list.c b/lib/gl_rbtreehash_list.c index 9f16cf2..36ddc5c 100644 --- a/lib/gl_rbtreehash_list.c +++ b/lib/gl_rbtreehash_list.c @@ -38,13 +38,16 @@ /* -------------------------- gl_list_t Data Type -------------------------- */ /* Generic hash-table code: Type definitions. */ -#include "gl_anyhash_list1.h" +#include "gl_anyhash1.h" /* Generic red-black tree code: Type definitions. */ #include "gl_anyrbtree_list1.h" /* Generic hash-table code: Low-level code. */ -#include "gl_anyhash_list2.h" +#define CONTAINER_T gl_list_t +#define CONTAINER_COUNT(list) \ + ((list)->root != NULL ? (list)->root->branch_size : 0) +#include "gl_anyhash2.h" /* Generic binary tree code: Type definitions. */ #include "gl_anytree_list1.h" diff --git a/modules/avltreehash-list b/modules/avltreehash-list index afd4b25..2873c8f 100644 --- a/modules/avltreehash-list +++ b/modules/avltreehash-list @@ -4,8 +4,8 @@ Sequential list data type implemented by a hash table with a binary tree. Files: lib/gl_avltreehash_list.h lib/gl_avltreehash_list.c -lib/gl_anyhash_list1.h -lib/gl_anyhash_list2.h +lib/gl_anyhash1.h +lib/gl_anyhash2.h lib/gl_anyhash_primes.h lib/gl_anyavltree_list1.h lib/gl_anyavltree_list2.h @@ -24,7 +24,7 @@ xsize configure.ac: Makefile.am: -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 +lib_SOURCES += gl_avltreehash_list.h gl_avltreehash_list.c gl_anyhash1.h gl_anyhash2.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" diff --git a/modules/hash-set b/modules/hash-set index cd8ac8b..4d95e74 100644 --- a/modules/hash-set +++ b/modules/hash-set @@ -4,8 +4,8 @@ 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_anyhash1.h +lib/gl_anyhash2.h lib/gl_anyhash_primes.h Depends-on: @@ -16,7 +16,7 @@ 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 +lib_SOURCES += gl_hash_set.h gl_hash_set.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h Include: "gl_hash_set.h" diff --git a/modules/linkedhash-list b/modules/linkedhash-list index 35de8c4..0db6eb9 100644 --- a/modules/linkedhash-list +++ b/modules/linkedhash-list @@ -4,8 +4,8 @@ Sequential list data type implemented by a hash table with a linked list. Files: lib/gl_linkedhash_list.h lib/gl_linkedhash_list.c -lib/gl_anyhash_list1.h -lib/gl_anyhash_list2.h +lib/gl_anyhash1.h +lib/gl_anyhash2.h lib/gl_anyhash_primes.h lib/gl_anylinked_list1.h lib/gl_anylinked_list2.h @@ -18,7 +18,7 @@ xsize configure.ac: Makefile.am: -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 +lib_SOURCES += gl_linkedhash_list.h gl_linkedhash_list.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h gl_anylinked_list1.h gl_anylinked_list2.h Include: "gl_linkedhash_list.h" diff --git a/modules/linkedhash-set b/modules/linkedhash-set index 5ca2544..2ee88c3 100644 --- a/modules/linkedhash-set +++ b/modules/linkedhash-set @@ -4,8 +4,8 @@ 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_anyhash1.h +lib/gl_anyhash2.h lib/gl_anyhash_primes.h Depends-on: @@ -16,7 +16,7 @@ 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 +lib_SOURCES += gl_linkedhash_set.h gl_linkedhash_set.c gl_anyhash1.h gl_anyhash2.h gl_anyhash_primes.h Include: "gl_linkedhash_set.h" diff --git a/modules/rbtreehash-list b/modules/rbtreehash-list index 7957d51..574eabe 100644 --- a/modules/rbtreehash-list +++ b/modules/rbtreehash-list @@ -4,8 +4,8 @@ Sequential list data type implemented by a hash table with a binary tree. Files: lib/gl_rbtreehash_list.h lib/gl_rbtreehash_list.c -lib/gl_anyhash_list1.h -lib/gl_anyhash_list2.h +lib/gl_anyhash1.h +lib/gl_anyhash2.h lib/gl_anyhash_primes.h lib/gl_anyrbtree_list1.h lib/gl_anyrbtree_list2.h @@ -24,7 +24,7 @@ xsize configure.ac: Makefile.am: -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 +lib_SOURCES += gl_rbtreehash_list.h gl_rbtreehash_list.c gl_anyhash1.h gl_anyhash2.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"