Mercurial > gnulib
view lib/gl_anyhash2.h @ 40214:452ab00796c7
Fix undefined behaviour.
* lib/bitrotate.h (rotl16, rotr16, rotl8, rotr8): Case x to
'unsigned int', to avoid shift operations on 'int'.
* lib/xmemdup0.c (xmemdup0): Don't invoke memcpy with a zero size.
* tests/test-count-leading-zeros.c (main): Use a random number that has
as many bits as TYPE, not only 2*15 or 2*31 bits.
* tests/test-count-trailing-zeros.c (main): Likewise.
* tests/test-count-one-bits.c (main): Likewise.
* tests/test-memmem.c: Don't include "null-ptr.h".
(main): Use zerosize_ptr() instead of null_ptr().
* modules/memmem-tests (Files): Remove tests/null-ptr.h.
author | Bruno Haible <bruno@clisp.org> |
---|---|
date | Sat, 09 Mar 2019 20:32:25 +0100 |
parents | b06060465f09 |
children |
line wrap: on
line source
/* Hash table for sequential list, set, and map data type. Copyright (C) 2006, 2009-2019 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, gl_linkedhash_map.c, gl_hash_map.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); }