diff options
author | Bruno Haible <bruno@clisp.org> | 2018-12-11 20:44:55 +0100 |
---|---|---|
committer | Bruno Haible <bruno@clisp.org> | 2018-12-11 20:44:55 +0100 |
commit | e18426e6b362b48fe66e6e58246485a06b288757 (patch) | |
tree | d32f871df0ef32f656325644f79a3250f514f165 /lib/gl_anyhash2.h | |
parent | 353348a7e26212d596c846461cef49670b8b225d (diff) | |
download | gnulib-e18426e6b362b48fe66e6e58246485a06b288757.tar.gz |
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.
Diffstat (limited to 'lib/gl_anyhash2.h')
-rw-r--r-- | lib/gl_anyhash2.h | 81 |
1 files changed, 81 insertions, 0 deletions
diff --git a/lib/gl_anyhash2.h b/lib/gl_anyhash2.h new file mode 100644 index 0000000000..d4c5430025 --- /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 <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/>. */ + +/* 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); +} |