From e0023883c6d2e6745a19e4b48e186ed156c1fca8 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Sun, 7 Apr 2024 17:19:27 +0200 Subject: Adding upstream version 2.11.2. Signed-off-by: Daniel Baumann --- gl/lib/gl_anyhash2.h | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 82 insertions(+) create mode 100644 gl/lib/gl_anyhash2.h (limited to 'gl/lib/gl_anyhash2.h') diff --git a/gl/lib/gl_anyhash2.h b/gl/lib/gl_anyhash2.h new file mode 100644 index 0000000..5ceba98 --- /dev/null +++ b/gl/lib/gl_anyhash2.h @@ -0,0 +1,82 @@ +/* Hash table for sequential list, set, and map data type. + Copyright (C) 2006, 2009-2022 Free Software Foundation, Inc. + Written by Bruno Haible , 2006. + + This file is free software: you can redistribute it and/or modify + it under the terms of the GNU Lesser General Public License as + published by the Free Software Foundation; either version 2.1 of the + License, or (at your option) any later version. + + This file 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 Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with this program. If not, see . */ + +/* 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_map.c, gl_hash_map.c. */ + +#include "gl_anyhash_primes.h" + +/* Resizes 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; +} + +/* Resizes 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); +} -- cgit v1.2.3