octave-kai/gnulib-hg: lib/hash.c annotate

annotate lib/hash.c @ 17323:a56636d89038

secure_getenv: fix include typo * lib/secure_getenv.c: Include config.h. Somehow I forgot!

author	Paul Eggert <eggert@cs.ucla.edu>
date	Thu, 07 Feb 2013 21:58:09 -0800
parents	e542fd46ad6f
children

rev	line source
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1 /* hash - hashing table processing.
4251 3e9d34851e81 Include <stdbool.h> unconditionally. Paul Eggert <eggert@cs.ucla.edu> parents: 4040 diff changeset	2
17249 e542fd46ad6f maint: update all copyright year number ranges Eric Blake <eblake@redhat.com> parents: 16235 diff changeset	3 Copyright (C) 1998-2004, 2006-2007, 2009-2013 Free Software Foundation, Inc.
4251 3e9d34851e81 Include <stdbool.h> unconditionally. Paul Eggert <eggert@cs.ucla.edu> parents: 4040 diff changeset	4
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	5 Written by Jim Meyering, 1992.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	6
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9200 diff changeset	7 This program is free software: you can redistribute it and/or modify
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	8 it under the terms of the GNU General Public License as published by
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9200 diff changeset	9 the Free Software Foundation; either version 3 of the License, or
bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9200 diff changeset	10 (at your option) any later version.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	11
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	12 This program is distributed in the hope that it will be useful,
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	13 but WITHOUT ANY WARRANTY; without even the implied warranty of
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	15 GNU General Public License for more details.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	16
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	17 You should have received a copy of the GNU General Public License
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9200 diff changeset	18 along with this program. If not, see <http://www.gnu.org/licenses/>. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	19
1038 b12d8086ca7a (ZALLOC): Take Ht parameter instead of relying on one being in scope. Jim Meyering <jim@meyering.net> parents: 1037 diff changeset	20 /* A generic hash table package. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	21
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	22 /* Define USE_OBSTACK to 1 if you want the allocator to use obstacks instead
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	23 of malloc. If you change USE_OBSTACK, you have to recompile! */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	24
7302 8a1a9361108c * _fpending.c: Include <config.h> unconditionally, since we no Paul Eggert <eggert@cs.ucla.edu> parents: 6259 diff changeset	25 #include <config.h>
4251 3e9d34851e81 Include <stdbool.h> unconditionally. Paul Eggert <eggert@cs.ucla.edu> parents: 4040 diff changeset	26
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	27 #include "hash.h"
11640 66e1eeffb344 hash: make rotation more obvious Eric Blake <ebb9@byu.net> parents: 11639 diff changeset	28
66e1eeffb344 hash: make rotation more obvious Eric Blake <ebb9@byu.net> parents: 11639 diff changeset	29 #include "bitrotate.h"
14644 157bb0cdd13a hash, mgetgroups: drop xalloc dependency Eric Blake <eblake@redhat.com> parents: 14612 diff changeset	30 #include "xalloc-oversized.h"
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	31
11640 66e1eeffb344 hash: make rotation more obvious Eric Blake <ebb9@byu.net> parents: 11639 diff changeset	32 #include <stdint.h>
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	33 #include <stdio.h>
4658 6ef2ff78cbad Remove K&R cruft. Paul Eggert <eggert@cs.ucla.edu> parents: 4333 diff changeset	34 #include <stdlib.h>
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	35
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	36 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	37 # include "obstack.h"
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	38 # ifndef obstack_chunk_alloc
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	39 # define obstack_chunk_alloc malloc
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	40 # endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	41 # ifndef obstack_chunk_free
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	42 # define obstack_chunk_free free
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	43 # endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	44 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	45
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	46 struct hash_entry
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	47 {
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	48 void *data;
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	49 struct hash_entry *next;
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	50 };
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	51
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	52 struct hash_table
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	53 {
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	54 /* The array of buckets starts at BUCKET and extends to BUCKET_LIMIT-1,
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	55 for a possibility of N_BUCKETS. Among those, N_BUCKETS_USED buckets
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	56 are not empty, there are N_ENTRIES active entries in the table. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	57 struct hash_entry *bucket;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	58 struct hash_entry const *bucket_limit;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	59 size_t n_buckets;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	60 size_t n_buckets_used;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	61 size_t n_entries;
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	62
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	63 /* Tuning arguments, kept in a physically separate structure. */
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	64 const Hash_tuning *tuning;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	65
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	66 /* Three functions are given to 'hash_initialize', see the documentation
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	67 block for this function. In a word, HASHER randomizes a user entry
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	68 into a number up from 0 up to some maximum minus 1; COMPARATOR returns
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	69 true if two user entries compare equally; and DATA_FREER is the cleanup
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	70 function for a user entry. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	71 Hash_hasher hasher;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	72 Hash_comparator comparator;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	73 Hash_data_freer data_freer;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	74
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	75 /* A linked list of freed struct hash_entry structs. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	76 struct hash_entry *free_entry_list;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	77
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	78 #if USE_OBSTACK
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	79 /* Whenever obstacks are used, it is possible to allocate all overflowed
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	80 entries into a single stack, so they all can be freed in a single
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	81 operation. It is not clear if the speedup is worth the trouble. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	82 struct obstack entry_stack;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	83 #endif
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	84 };
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	85
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	86 /* A hash table contains many internal entries, each holding a pointer to
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	87 some user-provided data (also called a user entry). An entry indistinctly
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	88 refers to both the internal entry and its associated user entry. A user
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	89 entry contents may be hashed by a randomization function (the hashing
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	90 function, or just "hasher" for short) into a number (or "slot") between 0
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	91 and the current table size. At each slot position in the hash table,
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	92 starts a linked chain of entries for which the user data all hash to this
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	93 slot. A bucket is the collection of all entries hashing to the same slot.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	94
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	95 A good "hasher" function will distribute entries rather evenly in buckets.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	96 In the ideal case, the length of each bucket is roughly the number of
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	97 entries divided by the table size. Finding the slot for a data is usually
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	98 done in constant time by the "hasher", and the later finding of a precise
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	99 entry is linear in time with the size of the bucket. Consequently, a
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	100 larger hash table size (that is, a larger number of buckets) is prone to
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	101 yielding shorter chains, given the "hasher" function behaves properly.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	102
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	103 Long buckets slow down the lookup algorithm. One might use big hash table
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	104 sizes in hope to reduce the average length of buckets, but this might
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	105 become inordinate, as unused slots in the hash table take some space. The
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	106 best bet is to make sure you are using a good "hasher" function (beware
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	107 that those are not that easy to write! :-), and to use a table size
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	108 larger than the actual number of entries. */
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	109
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	110 /* If an insertion makes the ratio of nonempty buckets to table size larger
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	111 than the growth threshold (a number between 0.0 and 1.0), then increase
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	112 the table size by multiplying by the growth factor (a number greater than
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	113 1.0). The growth threshold defaults to 0.8, and the growth factor
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	114 defaults to 1.414, meaning that the table will have doubled its size
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	115 every second time 80% of the buckets get used. */
16137 d9f87d8f2228 hash: mark a few floating point constants with "f" suffix Jim Meyering <meyering@redhat.com> parents: 16132 diff changeset	116 #define DEFAULT_GROWTH_THRESHOLD 0.8f
d9f87d8f2228 hash: mark a few floating point constants with "f" suffix Jim Meyering <meyering@redhat.com> parents: 16132 diff changeset	117 #define DEFAULT_GROWTH_FACTOR 1.414f
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	118
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	119 /* If a deletion empties a bucket and causes the ratio of used buckets to
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	120 table size to become smaller than the shrink threshold (a number between
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	121 0.0 and 1.0), then shrink the table by multiplying by the shrink factor (a
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	122 number greater than the shrink threshold but smaller than 1.0). The shrink
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	123 threshold and factor default to 0.0 and 1.0, meaning that the table never
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	124 shrinks. */
16137 d9f87d8f2228 hash: mark a few floating point constants with "f" suffix Jim Meyering <meyering@redhat.com> parents: 16132 diff changeset	125 #define DEFAULT_SHRINK_THRESHOLD 0.0f
d9f87d8f2228 hash: mark a few floating point constants with "f" suffix Jim Meyering <meyering@redhat.com> parents: 16132 diff changeset	126 #define DEFAULT_SHRINK_FACTOR 1.0f
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	127
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	128 /* Use this to initialize or reset a TUNING structure to
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	129 some sensible values. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	130 static const Hash_tuning default_tuning =
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	131 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	132 DEFAULT_SHRINK_THRESHOLD,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	133 DEFAULT_SHRINK_FACTOR,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	134 DEFAULT_GROWTH_THRESHOLD,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	135 DEFAULT_GROWTH_FACTOR,
3114 475265eee049 whoops. revert last change Jim Meyering <jim@meyering.net> parents: 3112 diff changeset	136 false
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	137 };
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	138
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	139 /* Information and lookup. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	140
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	141 /* The following few functions provide information about the overall hash
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	142 table organization: the number of entries, number of buckets and maximum
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	143 length of buckets. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	144
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	145 /* Return the number of buckets in the hash table. The table size, the total
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	146 number of buckets (used plus unused), or the maximum number of slots, are
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	147 the same quantity. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	148
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	149 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	150 hash_get_n_buckets (const Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	151 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	152 return table->n_buckets;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	153 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	154
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	155 /* Return the number of slots in use (non-empty buckets). */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	156
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	157 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	158 hash_get_n_buckets_used (const Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	159 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	160 return table->n_buckets_used;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	161 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	162
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	163 /* Return the number of active entries. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	164
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	165 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	166 hash_get_n_entries (const Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	167 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	168 return table->n_entries;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	169 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	170
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	171 /* Return the length of the longest chain (bucket). */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	172
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	173 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	174 hash_get_max_bucket_length (const Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	175 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	176 struct hash_entry const *bucket;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	177 size_t max_bucket_length = 0;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	178
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	179 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	180 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	181 if (bucket->data)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	182 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	183 struct hash_entry const *cursor = bucket;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	184 size_t bucket_length = 1;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	185
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	186 while (cursor = cursor->next, cursor)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	187 bucket_length++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	188
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	189 if (bucket_length > max_bucket_length)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	190 max_bucket_length = bucket_length;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	191 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	192 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	193
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	194 return max_bucket_length;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	195 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	196
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	197 /* Do a mild validation of a hash table, by traversing it and checking two
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	198 statistics. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	199
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	200 bool
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	201 hash_table_ok (const Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	202 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	203 struct hash_entry const *bucket;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	204 size_t n_buckets_used = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	205 size_t n_entries = 0;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	206
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	207 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	208 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	209 if (bucket->data)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	210 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	211 struct hash_entry const *cursor = bucket;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	212
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	213 /* Count bucket head. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	214 n_buckets_used++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	215 n_entries++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	216
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	217 /* Count bucket overflow. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	218 while (cursor = cursor->next, cursor)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	219 n_entries++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	220 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	221 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	222
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	223 if (n_buckets_used == table->n_buckets_used && n_entries == table->n_entries)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	224 return true;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	225
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	226 return false;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	227 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	228
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	229 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	230 hash_print_statistics (const Hash_table table, FILE stream)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	231 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	232 size_t n_entries = hash_get_n_entries (table);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	233 size_t n_buckets = hash_get_n_buckets (table);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	234 size_t n_buckets_used = hash_get_n_buckets_used (table);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	235 size_t max_bucket_length = hash_get_max_bucket_length (table);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	236
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	237 fprintf (stream, "# entries: %lu\n", (unsigned long int) n_entries);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	238 fprintf (stream, "# buckets: %lu\n", (unsigned long int) n_buckets);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	239 fprintf (stream, "# buckets used: %lu (%.2f%%)\n",
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	240 (unsigned long int) n_buckets_used,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	241 (100.0 * n_buckets_used) / n_buckets);
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	242 fprintf (stream, "max bucket length: %lu\n",
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	243 (unsigned long int) max_bucket_length);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	244 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	245
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	246 /* Hash KEY and return a pointer to the selected bucket.
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	247 If TABLE->hasher misbehaves, abort. */
13622 fcda011710d9 hash: fix safe_hasher const typo Paul Eggert <eggert@cs.ucla.edu> parents: 13613 diff changeset	248 static struct hash_entry *
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	249 safe_hasher (const Hash_table table, const void key)
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	250 {
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	251 size_t n = table->hasher (key, table->n_buckets);
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	252 if (! (n < table->n_buckets))
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	253 abort ();
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	254 return table->bucket + n;
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	255 }
7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	256
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	257 /* If ENTRY matches an entry already in the hash table, return the
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	258 entry from the table. Otherwise, return NULL. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	259
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	260 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	261 hash_lookup (const Hash_table table, const void entry)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	262 {
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	263 struct hash_entry const *bucket = safe_hasher (table, entry);
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	264 struct hash_entry const *cursor;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	265
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	266 if (bucket->data == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	267 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	268
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	269 for (cursor = bucket; cursor; cursor = cursor->next)
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	270 if (entry == cursor->data \|\| table->comparator (entry, cursor->data))
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	271 return cursor->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	272
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	273 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	274 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	275
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	276 /* Walking. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	277
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	278 /* The functions in this page traverse the hash table and process the
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	279 contained entries. For the traversal to work properly, the hash table
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	280 should not be resized nor modified while any particular entry is being
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	281 processed. In particular, entries should not be added, and an entry
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	282 may be removed only if there is no shrink threshold and the entry being
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	283 removed has already been passed to hash_get_next. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	284
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	285 /* Return the first data in the table, or NULL if the table is empty. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	286
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	287 void *
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	288 hash_get_first (const Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	289 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	290 struct hash_entry const *bucket;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	291
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	292 if (table->n_entries == 0)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	293 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	294
4006 608641351e57 Avoid use of <assert.h>, as the GNU Coding Standards hint that one Paul Eggert <eggert@cs.ucla.edu> parents: 3645 diff changeset	295 for (bucket = table->bucket; ; bucket++)
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	296 if (! (bucket < table->bucket_limit))
4006 608641351e57 Avoid use of <assert.h>, as the GNU Coding Standards hint that one Paul Eggert <eggert@cs.ucla.edu> parents: 3645 diff changeset	297 abort ();
608641351e57 Avoid use of <assert.h>, as the GNU Coding Standards hint that one Paul Eggert <eggert@cs.ucla.edu> parents: 3645 diff changeset	298 else if (bucket->data)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	299 return bucket->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	300 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	301
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	302 /* Return the user data for the entry following ENTRY, where ENTRY has been
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	303 returned by a previous call to either 'hash_get_first' or 'hash_get_next'.
2956 4fb873832246 (hash_get_next): Fix a thinko: when ENTRY is the Jim Meyering <jim@meyering.net> parents: 2524 diff changeset	304 Return NULL if there are no more entries. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	305
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	306 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	307 hash_get_next (const Hash_table table, const void entry)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	308 {
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	309 struct hash_entry const *bucket = safe_hasher (table, entry);
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	310 struct hash_entry const *cursor;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	311
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	312 /* Find next entry in the same bucket. */
13612 37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	313 cursor = bucket;
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	314 do
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	315 {
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	316 if (cursor->data == entry && cursor->next)
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	317 return cursor->next->data;
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	318 cursor = cursor->next;
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	319 }
37d5b2cb63ba hash: silence spurious clang warning Bruno Haible <bruno@clisp.org> parents: 13448 diff changeset	320 while (cursor != NULL);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	321
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	322 /* Find first entry in any subsequent bucket. */
2956 4fb873832246 (hash_get_next): Fix a thinko: when ENTRY is the Jim Meyering <jim@meyering.net> parents: 2524 diff changeset	323 while (++bucket < table->bucket_limit)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	324 if (bucket->data)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	325 return bucket->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	326
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	327 /* None found. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	328 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	329 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	330
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	331 /* Fill BUFFER with pointers to active user entries in the hash table, then
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	332 return the number of pointers copied. Do not copy more than BUFFER_SIZE
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	333 pointers. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	334
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	335 size_t
1318 4e3526f71a49 split a couple long lines Jim Meyering <jim@meyering.net> parents: 1317 diff changeset	336 hash_get_entries (const Hash_table table, void *buffer,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	337 size_t buffer_size)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	338 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	339 size_t counter = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	340 struct hash_entry const *bucket;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	341 struct hash_entry const *cursor;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	342
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	343 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	344 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	345 if (bucket->data)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	346 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	347 for (cursor = bucket; cursor; cursor = cursor->next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	348 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	349 if (counter >= buffer_size)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	350 return counter;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	351 buffer[counter++] = cursor->data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	352 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	353 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	354 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	355
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	356 return counter;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	357 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	358
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	359 /* Call a PROCESSOR function for each entry of a hash table, and return the
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	360 number of entries for which the processor function returned success. A
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	361 pointer to some PROCESSOR_DATA which will be made available to each call to
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	362 the processor function. The PROCESSOR accepts two arguments: the first is
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	363 the user entry being walked into, the second is the value of PROCESSOR_DATA
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	364 as received. The walking continue for as long as the PROCESSOR function
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	365 returns nonzero. When it returns zero, the walking is interrupted. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	366
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	367 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	368 hash_do_for_each (const Hash_table *table, Hash_processor processor,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	369 void *processor_data)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	370 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	371 size_t counter = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	372 struct hash_entry const *bucket;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	373 struct hash_entry const *cursor;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	374
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	375 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	376 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	377 if (bucket->data)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	378 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	379 for (cursor = bucket; cursor; cursor = cursor->next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	380 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	381 if (! processor (cursor->data, processor_data))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	382 return counter;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	383 counter++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	384 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	385 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	386 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	387
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	388 return counter;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	389 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	390
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	391 /* Allocation and clean-up. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	392
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	393 /* Return a hash index for a NUL-terminated STRING between 0 and N_BUCKETS-1.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	394 This is a convenience routine for constructing other hashing functions. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	395
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	396 #if USE_DIFF_HASH
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	397
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	398 /* About hashings, Paul Eggert writes to me (FP), on 1994-01-01: "Please see
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	399 B. J. McKenzie, R. Harries & T. Bell, Selecting a hashing algorithm,
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	400 Software--practice & experience 20, 2 (Feb 1990), 209-224. Good hash
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	401 algorithms tend to be domain-specific, so what's good for [diffutils'] io.c
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	402 may not be good for your application." */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	403
14612 6ef4f1f39105 Revert "use _GL_ATTRIBUTE_CONST and _GL_ATTRIBUTE_PURE" Jim Meyering <meyering@redhat.com> parents: 14610 diff changeset	404 size_t
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	405 hash_string (const char *string, size_t n_buckets)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	406 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	407 # define HASH_ONE_CHAR(Value, Byte) \
11640 66e1eeffb344 hash: make rotation more obvious Eric Blake <ebb9@byu.net> parents: 11639 diff changeset	408 ((Byte) + rotl_sz (Value, 7))
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	409
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	410 size_t value = 0;
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	411 unsigned char ch;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	412
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	413 for (; (ch = *string); string++)
a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	414 value = HASH_ONE_CHAR (value, ch);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	415 return value % n_buckets;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	416
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	417 # undef HASH_ONE_CHAR
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	418 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	419
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	420 #else /* not USE_DIFF_HASH */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	421
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	422 /* This one comes from 'recode', and performs a bit better than the above as
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	423 per a few experiments. It is inspired from a hashing routine found in the
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	424 very old Cyber 'snoop', itself written in typical Greg Mansfield style.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	425 (By the way, what happened to this excellent man? Is he still alive?) */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	426
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	427 size_t
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	428 hash_string (const char *string, size_t n_buckets)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	429 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	430 size_t value = 0;
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	431 unsigned char ch;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	432
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	433 for (; (ch = *string); string++)
a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	434 value = (value * 31 + ch) % n_buckets;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	435 return value;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	436 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	437
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	438 #endif /* not USE_DIFF_HASH */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	439
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	440 /* Return true if CANDIDATE is a prime number. CANDIDATE should be an odd
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	441 number at least equal to 11. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	442
16128 6beadb731202 mark functions with const and pure attributes Jim Meyering <meyering@redhat.com> parents: 16100 diff changeset	443 static bool _GL_ATTRIBUTE_CONST
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	444 is_prime (size_t candidate)
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	445 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	446 size_t divisor = 3;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	447 size_t square = divisor * divisor;
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	448
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	449 while (square < candidate && (candidate % divisor))
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	450 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	451 divisor++;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	452 square += 4 * divisor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	453 divisor++;
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	454 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	455
3076 a76b9dec6ef8 add omitted semicolon Jim Meyering <jim@meyering.net> parents: 3073 diff changeset	456 return (candidate % divisor ? true : false);
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	457 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	458
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	459 /* Round a given CANDIDATE number up to the nearest prime, and return that
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	460 prime. Primes lower than 10 are merely skipped. */
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	461
16128 6beadb731202 mark functions with const and pure attributes Jim Meyering <meyering@redhat.com> parents: 16100 diff changeset	462 static size_t _GL_ATTRIBUTE_CONST
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	463 next_prime (size_t candidate)
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	464 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	465 /* Skip small primes. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	466 if (candidate < 10)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	467 candidate = 10;
1360 89ddc5685941 (is_prime): Ansideclify. Jim Meyering <jim@meyering.net> parents: 1318 diff changeset	468
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	469 /* Make it definitely odd. */
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	470 candidate \|= 1;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	471
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	472 while (SIZE_MAX != candidate && !is_prime (candidate))
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	473 candidate += 2;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	474
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	475 return candidate;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	476 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	477
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	478 void
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	479 hash_reset_tuning (Hash_tuning *tuning)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	480 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	481 *tuning = default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	482 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	483
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	484 /* If the user passes a NULL hasher, we hash the raw pointer. */
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	485 static size_t
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	486 raw_hasher (const void *data, size_t n)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	487 {
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	488 /* When hashing unique pointers, it is often the case that they were
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	489 generated by malloc and thus have the property that the low-order
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	490 bits are 0. As this tends to give poorer performance with small
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	491 tables, we rotate the pointer value before performing division,
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	492 in an attempt to improve hash quality. */
11640 66e1eeffb344 hash: make rotation more obvious Eric Blake <ebb9@byu.net> parents: 11639 diff changeset	493 size_t val = rotr_sz ((size_t) data, 3);
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	494 return val % n;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	495 }
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	496
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	497 /* If the user passes a NULL comparator, we use pointer comparison. */
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	498 static bool
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	499 raw_comparator (const void a, const void b)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	500 {
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	501 return a == b;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	502 }
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	503
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	504
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	505 /* For the given hash TABLE, check the user supplied tuning structure for
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	506 reasonable values, and return true if there is no gross error with it.
2105 b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	507 Otherwise, definitively reset the TUNING field to some acceptable default
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	508 in the hash table (that is, the user loses the right of further modifying
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	509 tuning arguments), and return false. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	510
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	511 static bool
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	512 check_tuning (Hash_table *table)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	513 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	514 const Hash_tuning *tuning = table->tuning;
12117 fa148b84c9fd hash: allow C89 compilation Eric Blake <ebb9@byu.net> parents: 11645 diff changeset	515 float epsilon;
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	516 if (tuning == &default_tuning)
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	517 return true;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	518
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	519 /* Be a bit stricter than mathematics would require, so that
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	520 rounding errors in size calculations do not cause allocations to
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	521 fail to grow or shrink as they should. The smallest allocation
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	522 is 11 (due to next_prime's algorithm), so an epsilon of 0.1
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	523 should be good enough. */
12117 fa148b84c9fd hash: allow C89 compilation Eric Blake <ebb9@byu.net> parents: 11645 diff changeset	524 epsilon = 0.1f;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	525
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	526 if (epsilon < tuning->growth_threshold
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	527 && tuning->growth_threshold < 1 - epsilon
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	528 && 1 + epsilon < tuning->growth_factor
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	529 && 0 <= tuning->shrink_threshold
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	530 && tuning->shrink_threshold + epsilon < tuning->shrink_factor
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	531 && tuning->shrink_factor <= 1
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	532 && tuning->shrink_threshold + epsilon < tuning->growth_threshold)
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	533 return true;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	534
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	535 table->tuning = &default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	536 return false;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	537 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	538
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	539 /* Compute the size of the bucket array for the given CANDIDATE and
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	540 TUNING, or return 0 if there is no possible way to allocate that
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	541 many entries. */
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	542
16132 46ec538d9591 hash: mark compute_bucket_size with the pure attribute Jim Meyering <meyering@redhat.com> parents: 16128 diff changeset	543 static size_t _GL_ATTRIBUTE_PURE
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	544 compute_bucket_size (size_t candidate, const Hash_tuning *tuning)
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	545 {
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	546 if (!tuning->is_n_buckets)
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	547 {
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	548 float new_candidate = candidate / tuning->growth_threshold;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	549 if (SIZE_MAX <= new_candidate)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	550 return 0;
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	551 candidate = new_candidate;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	552 }
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	553 candidate = next_prime (candidate);
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	554 if (xalloc_oversized (candidate, sizeof (struct hash_entry *)))
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	555 return 0;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	556 return candidate;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	557 }
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	558
2105 b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	559 /* Allocate and return a new hash table, or NULL upon failure. The initial
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	560 number of buckets is automatically selected so as to _guarantee_ that you
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	561 may insert at least CANDIDATE different user entries before any growth of
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	562 the hash table size occurs. So, if have a reasonably tight a-priori upper
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	563 bound on the number of entries you intend to insert in the hash table, you
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	564 may save some table memory and insertion time, by specifying it here. If
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	565 the IS_N_BUCKETS field of the TUNING structure is true, the CANDIDATE
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	566 argument has its meaning changed to the wanted number of buckets.
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	567
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	568 TUNING points to a structure of user-supplied values, in case some fine
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	569 tuning is wanted over the default behavior of the hasher. If TUNING is
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	570 NULL, the default tuning parameters are used instead. If TUNING is
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	571 provided but the values requested are out of bounds or might cause
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	572 rounding errors, return NULL.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	573
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	574 The user-supplied HASHER function, when not NULL, accepts two
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	575 arguments ENTRY and TABLE_SIZE. It computes, by hashing ENTRY contents, a
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	576 slot number for that entry which should be in the range 0..TABLE_SIZE-1.
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	577 This slot number is then returned.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	578
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	579 The user-supplied COMPARATOR function, when not NULL, accepts two
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	580 arguments pointing to user data, it then returns true for a pair of entries
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	581 that compare equal, or false otherwise. This function is internally called
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	582 on entries which are already known to hash to the same bucket index,
95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	583 but which are distinct pointers.
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	584
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	585 The user-supplied DATA_FREER function, when not NULL, may be later called
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	586 with the user data as an argument, just before the entry containing the
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	587 data gets freed. This happens from within 'hash_free' or 'hash_clear'.
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	588 You should specify this function only if you want these functions to free
16235 18a38c9615f0 In commentary, do not use ` to quote. Paul Eggert <eggert@cs.ucla.edu> parents: 16201 diff changeset	589 all of your 'data' data. This is typically the case when your data is
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	590 simply an auxiliary struct that you have malloc'd to aggregate several
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	591 values. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	592
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	593 Hash_table *
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	594 hash_initialize (size_t candidate, const Hash_tuning *tuning,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	595 Hash_hasher hasher, Hash_comparator comparator,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	596 Hash_data_freer data_freer)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	597 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	598 Hash_table *table;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	599
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	600 if (hasher == NULL)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	601 hasher = raw_hasher;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	602 if (comparator == NULL)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	603 comparator = raw_comparator;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	604
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	605 table = malloc (sizeof *table);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	606 if (table == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	607 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	608
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	609 if (!tuning)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	610 tuning = &default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	611 table->tuning = tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	612 if (!check_tuning (table))
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	613 {
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	614 /* Fail if the tuning options are invalid. This is the only occasion
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	615 when the user gets some feedback about it. Once the table is created,
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	616 if the user provides invalid tuning options, we silently revert to
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	617 using the defaults, and ignore further request to change the tuning
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	618 options. */
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	619 goto fail;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	620 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	621
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	622 table->n_buckets = compute_bucket_size (candidate, tuning);
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	623 if (!table->n_buckets)
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	624 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	625
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	626 table->bucket = calloc (table->n_buckets, sizeof *table->bucket);
9200 da3798e554d6 * lib/hash.c (hash_initialize): Detect calloc failure. Jim Meyering <jim@meyering.net> parents: 7302 diff changeset	627 if (table->bucket == NULL)
da3798e554d6 * lib/hash.c (hash_initialize): Detect calloc failure. Jim Meyering <jim@meyering.net> parents: 7302 diff changeset	628 goto fail;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	629 table->bucket_limit = table->bucket + table->n_buckets;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	630 table->n_buckets_used = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	631 table->n_entries = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	632
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	633 table->hasher = hasher;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	634 table->comparator = comparator;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	635 table->data_freer = data_freer;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	636
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	637 table->free_entry_list = NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	638 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	639 obstack_init (&table->entry_stack);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	640 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	641 return table;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	642
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	643 fail:
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	644 free (table);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	645 return NULL;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	646 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	647
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	648 /* Make all buckets empty, placing any chained entries on the free list.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	649 Apply the user-specified function data_freer (if any) to the datas of any
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	650 affected entries. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	651
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	652 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	653 hash_clear (Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	654 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	655 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	656
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	657 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	658 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	659 if (bucket->data)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	660 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	661 struct hash_entry *cursor;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	662 struct hash_entry *next;
3582 abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	663
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	664 /* Free the bucket overflow. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	665 for (cursor = bucket->next; cursor; cursor = next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	666 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	667 if (table->data_freer)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	668 table->data_freer (cursor->data);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	669 cursor->data = NULL;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	670
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	671 next = cursor->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	672 /* Relinking is done one entry at a time, as it is to be expected
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	673 that overflows are either rare or short. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	674 cursor->next = table->free_entry_list;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	675 table->free_entry_list = cursor;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	676 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	677
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	678 /* Free the bucket head. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	679 if (table->data_freer)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	680 table->data_freer (bucket->data);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	681 bucket->data = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	682 bucket->next = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	683 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	684 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	685
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	686 table->n_buckets_used = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	687 table->n_entries = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	688 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	689
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	690 /* Reclaim all storage associated with a hash table. If a data_freer
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	691 function has been supplied by the user when the hash table was created,
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	692 this function applies it to the data of each entry before freeing that
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	693 entry. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	694
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	695 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	696 hash_free (Hash_table *table)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	697 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	698 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	699 struct hash_entry *cursor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	700 struct hash_entry *next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	701
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	702 /* Call the user data_freer function. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	703 if (table->data_freer && table->n_entries)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	704 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	705 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	706 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	707 if (bucket->data)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	708 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	709 for (cursor = bucket; cursor; cursor = cursor->next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	710 table->data_freer (cursor->data);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	711 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	712 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	713 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	714
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	715 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	716
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	717 obstack_free (&table->entry_stack, NULL);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	718
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	719 #else
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	720
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	721 /* Free all bucket overflowed entries. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	722 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	723 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	724 for (cursor = bucket->next; cursor; cursor = next)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	725 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	726 next = cursor->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	727 free (cursor);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	728 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	729 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	730
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	731 /* Also reclaim the internal list of previously freed entries. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	732 for (cursor = table->free_entry_list; cursor; cursor = next)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	733 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	734 next = cursor->next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	735 free (cursor);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	736 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	737
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	738 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	739
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	740 /* Free the remainder of the hash table structure. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	741 free (table->bucket);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	742 free (table);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	743 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	744
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	745 /* Insertion and deletion. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	746
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	747 /* Get a new hash entry for a bucket overflow, possibly by recycling a
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	748 previously freed one. If this is not possible, allocate a new one. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	749
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	750 static struct hash_entry *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	751 allocate_entry (Hash_table *table)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	752 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	753 struct hash_entry *new;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	754
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	755 if (table->free_entry_list)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	756 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	757 new = table->free_entry_list;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	758 table->free_entry_list = new->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	759 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	760 else
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	761 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	762 #if USE_OBSTACK
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	763 new = obstack_alloc (&table->entry_stack, sizeof *new);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	764 #else
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	765 new = malloc (sizeof *new);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	766 #endif
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	767 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	768
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	769 return new;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	770 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	771
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	772 /* Free a hash entry which was part of some bucket overflow,
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	773 saving it for later recycling. */
1039 4d7cd20a6c87 (hash_free_0): Remove prototype. Jim Meyering <jim@meyering.net> parents: 1038 diff changeset	774
4d7cd20a6c87 (hash_free_0): Remove prototype. Jim Meyering <jim@meyering.net> parents: 1038 diff changeset	775 static void
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	776 free_entry (Hash_table table, struct hash_entry entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	777 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	778 entry->data = NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	779 entry->next = table->free_entry_list;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	780 table->free_entry_list = entry;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	781 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	782
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	783 /* This private function is used to help with insertion and deletion. When
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	784 ENTRY matches an entry in the table, return a pointer to the corresponding
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	785 user data and set *BUCKET_HEAD to the head of the selected bucket.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	786 Otherwise, return NULL. When DELETE is true and ENTRY matches an entry in
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	787 the table, unlink the matching entry. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	788
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	789 static void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	790 hash_find_entry (Hash_table table, const void entry,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	791 struct hash_entry **bucket_head, bool delete)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	792 {
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	793 struct hash_entry *bucket = safe_hasher (table, entry);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	794 struct hash_entry *cursor;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	795
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	796 *bucket_head = bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	797
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	798 /* Test for empty bucket. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	799 if (bucket->data == NULL)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	800 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	801
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	802 /* See if the entry is the first in the bucket. */
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	803 if (entry == bucket->data \|\| table->comparator (entry, bucket->data))
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	804 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	805 void *data = bucket->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	806
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	807 if (delete)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	808 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	809 if (bucket->next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	810 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	811 struct hash_entry *next = bucket->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	812
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	813 /* Bump the first overflow entry into the bucket head, then save
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	814 the previous first overflow entry for later recycling. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	815 bucket = next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	816 free_entry (table, next);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	817 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	818 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	819 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	820 bucket->data = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	821 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	822 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	823
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	824 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	825 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	826
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	827 /* Scan the bucket overflow. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	828 for (cursor = bucket; cursor->next; cursor = cursor->next)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	829 {
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	830 if (entry == cursor->next->data
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	831 \|\| table->comparator (entry, cursor->next->data))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	832 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	833 void *data = cursor->next->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	834
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	835 if (delete)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	836 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	837 struct hash_entry *next = cursor->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	838
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	839 /* Unlink the entry to delete, then save the freed entry for later
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	840 recycling. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	841 cursor->next = next->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	842 free_entry (table, next);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	843 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	844
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	845 return data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	846 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	847 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	848
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	849 /* No entry found. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	850 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	851 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	852
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	853 /* Internal helper, to move entries from SRC to DST. Both tables must
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	854 share the same free entry list. If SAFE, only move overflow
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	855 entries, saving bucket heads for later, so that no allocations will
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	856 occur. Return false if the free entry list is exhausted and an
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	857 allocation fails. */
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	858
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	859 static bool
11645 ce9c1cd30e58 hash: reverse order of src/dst parameters in an internal interface Jim Meyering <meyering@redhat.com> parents: 11642 diff changeset	860 transfer_entries (Hash_table dst, Hash_table src, bool safe)
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	861 {
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	862 struct hash_entry *bucket;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	863 struct hash_entry *cursor;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	864 struct hash_entry *next;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	865 for (bucket = src->bucket; bucket < src->bucket_limit; bucket++)
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	866 if (bucket->data)
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	867 {
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	868 void *data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	869 struct hash_entry *new_bucket;
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	870
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	871 /* Within each bucket, transfer overflow entries first and
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	872 then the bucket head, to minimize memory pressure. After
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	873 all, the only time we might allocate is when moving the
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	874 bucket head, but moving overflow entries first may create
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	875 free entries that can be recycled by the time we finally
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	876 get to the bucket head. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	877 for (cursor = bucket->next; cursor; cursor = next)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	878 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	879 data = cursor->data;
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	880 new_bucket = safe_hasher (dst, data);
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	881
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	882 next = cursor->next;
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	883
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	884 if (new_bucket->data)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	885 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	886 /* Merely relink an existing entry, when moving from a
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	887 bucket overflow into a bucket overflow. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	888 cursor->next = new_bucket->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	889 new_bucket->next = cursor;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	890 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	891 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	892 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	893 /* Free an existing entry, when moving from a bucket
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	894 overflow into a bucket header. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	895 new_bucket->data = data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	896 dst->n_buckets_used++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	897 free_entry (dst, cursor);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	898 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	899 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	900 /* Now move the bucket head. Be sure that if we fail due to
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	901 allocation failure that the src table is in a consistent
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	902 state. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	903 data = bucket->data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	904 bucket->next = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	905 if (safe)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	906 continue;
13613 7f0f04d7017a hash: factor, and guard against misbehaving hasher function Eric Blake <eblake@redhat.com> parents: 13612 diff changeset	907 new_bucket = safe_hasher (dst, data);
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	908
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	909 if (new_bucket->data)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	910 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	911 /* Allocate or recycle an entry, when moving from a bucket
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	912 header into a bucket overflow. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	913 struct hash_entry *new_entry = allocate_entry (dst);
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	914
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	915 if (new_entry == NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	916 return false;
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	917
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	918 new_entry->data = data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	919 new_entry->next = new_bucket->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	920 new_bucket->next = new_entry;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	921 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	922 else
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	923 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	924 /* Move from one bucket header to another. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	925 new_bucket->data = data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	926 dst->n_buckets_used++;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	927 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	928 bucket->data = NULL;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	929 src->n_buckets_used--;
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	930 }
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	931 return true;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	932 }
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	933
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	934 /* For an already existing hash table, change the number of buckets through
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	935 specifying CANDIDATE. The contents of the hash table are preserved. The
2105 b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	936 new number of buckets is automatically selected so as to _guarantee_ that
b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	937 the table may receive at least CANDIDATE different user entries, including
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	938 those already in the table, before any other growth of the hash table size
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	939 occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	940 exact number of buckets desired. Return true iff the rehash succeeded. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	941
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	942 bool
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	943 hash_rehash (Hash_table *table, size_t candidate)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	944 {
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	945 Hash_table storage;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	946 Hash_table *new_table;
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	947 size_t new_size = compute_bucket_size (candidate, table->tuning);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	948
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	949 if (!new_size)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	950 return false;
11641 6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	951 if (new_size == table->n_buckets)
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	952 return true;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	953 new_table = &storage;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	954 new_table->bucket = calloc (new_size, sizeof *new_table->bucket);
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	955 if (new_table->bucket == NULL)
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	956 return false;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	957 new_table->n_buckets = new_size;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	958 new_table->bucket_limit = new_table->bucket + new_size;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	959 new_table->n_buckets_used = 0;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	960 new_table->n_entries = 0;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	961 new_table->tuning = table->tuning;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	962 new_table->hasher = table->hasher;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	963 new_table->comparator = table->comparator;
6c4ae0846ee9 hash: reduce memory pressure in hash_rehash no-op case Eric Blake <ebb9@byu.net> parents: 11640 diff changeset	964 new_table->data_freer = table->data_freer;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	965
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	966 /* In order for the transfer to successfully complete, we need
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	967 additional overflow entries when distinct buckets in the old
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	968 table collide into a common bucket in the new table. The worst
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	969 case possible is a hasher that gives a good spread with the old
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	970 size, but returns a constant with the new size; if we were to
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	971 guarantee table->n_buckets_used-1 free entries in advance, then
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	972 the transfer would be guaranteed to not allocate memory.
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	973 However, for large tables, a guarantee of no further allocation
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	974 introduces a lot of extra memory pressure, all for an unlikely
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	975 corner case (most rehashes reduce, rather than increase, the
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	976 number of overflow entries needed). So, we instead ensure that
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	977 the transfer process can be reversed if we hit a memory
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	978 allocation failure mid-transfer. */
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	979
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	980 /* Merely reuse the extra old space into the new table. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	981 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	982 new_table->entry_stack = table->entry_stack;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	983 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	984 new_table->free_entry_list = table->free_entry_list;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	985
11645 ce9c1cd30e58 hash: reverse order of src/dst parameters in an internal interface Jim Meyering <meyering@redhat.com> parents: 11642 diff changeset	986 if (transfer_entries (new_table, table, false))
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	987 {
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	988 /* Entries transferred successfully; tie up the loose ends. */
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	989 free (table->bucket);
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	990 table->bucket = new_table->bucket;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	991 table->bucket_limit = new_table->bucket_limit;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	992 table->n_buckets = new_table->n_buckets;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	993 table->n_buckets_used = new_table->n_buckets_used;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	994 table->free_entry_list = new_table->free_entry_list;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	995 /* table->n_entries and table->entry_stack already hold their value. */
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	996 return true;
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	997 }
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	998
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	999 /* We've allocated new_table->bucket (and possibly some entries),
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1000 exhausted the free list, and moved some but not all entries into
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1001 new_table. We must undo the partial move before returning
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1002 failure. The only way to get into this situation is if new_table
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1003 uses fewer buckets than the old table, so we will reclaim some
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1004 free entries as overflows in the new table are put back into
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1005 distinct buckets in the old table.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1006
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1007 There are some pathological cases where a single pass through the
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1008 table requires more intermediate overflow entries than using two
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1009 passes. Two passes give worse cache performance and takes
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1010 longer, but at this point, we're already out of memory, so slow
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1011 and safe is better than failure. */
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	1012 table->free_entry_list = new_table->free_entry_list;
11645 ce9c1cd30e58 hash: reverse order of src/dst parameters in an internal interface Jim Meyering <meyering@redhat.com> parents: 11642 diff changeset	1013 if (! (transfer_entries (table, new_table, true)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1014 && transfer_entries (table, new_table, false)))
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1015 abort ();
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1016 /* table->n_entries already holds its value. */
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1017 free (new_table->bucket);
08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1018 return false;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1019 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1020
16096 13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1021 /* Insert ENTRY into hash TABLE if there is not already a matching entry.
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1022
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1023 Return -1 upon memory allocation failure.
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1024 Return 1 if insertion succeeded.
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1025 Return 0 if there is already a matching entry in the table,
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1026 and in that case, if MATCHED_ENT is non-NULL, set *MATCHED_ENT
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1027 to that entry.
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1028
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1029 This interface is easier to use than hash_insert when you must
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1030 distinguish between the latter two cases. More importantly,
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1031 hash_insert is unusable for some types of ENTRY values. When using
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1032 hash_insert, the only way to distinguish those cases is to compare
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1033 the return value and ENTRY. That works only when you can have two
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1034 different ENTRY values that point to data that compares "equal". Thus,
16100 deba2a70b794 hash: Don't refer to deprecated interfaces. Simon Josefsson <simon@josefsson.org> parents: 16096 diff changeset	1035 when the ENTRY value is a simple scalar, you must use
deba2a70b794 hash: Don't refer to deprecated interfaces. Simon Josefsson <simon@josefsson.org> parents: 16096 diff changeset	1036 hash_insert_if_absent. ENTRY must not be NULL. */
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1037 int
16096 13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1038 hash_insert_if_absent (Hash_table table, void const entry,
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1039 void const **matched_ent)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1040 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1041 void *data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1042 struct hash_entry *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1043
13448 6b0f8c52218d hash: once again explicitly disallow insertion of NULL Jim Meyering <meyering@redhat.com> parents: 13446 diff changeset	1044 /* The caller cannot insert a NULL entry, since hash_lookup returns NULL
6b0f8c52218d hash: once again explicitly disallow insertion of NULL Jim Meyering <meyering@redhat.com> parents: 13446 diff changeset	1045 to indicate "not found", and hash_find_entry uses "bucket->data == NULL"
6b0f8c52218d hash: once again explicitly disallow insertion of NULL Jim Meyering <meyering@redhat.com> parents: 13446 diff changeset	1046 to indicate an empty bucket. */
6b0f8c52218d hash: once again explicitly disallow insertion of NULL Jim Meyering <meyering@redhat.com> parents: 13446 diff changeset	1047 if (! entry)
6b0f8c52218d hash: once again explicitly disallow insertion of NULL Jim Meyering <meyering@redhat.com> parents: 13446 diff changeset	1048 abort ();
6b0f8c52218d hash: once again explicitly disallow insertion of NULL Jim Meyering <meyering@redhat.com> parents: 13446 diff changeset	1049
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	1050 /* If there's a matching entry already in the table, return that. */
8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	1051 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1052 {
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1053 if (matched_ent)
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1054 *matched_ent = data;
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1055 return 0;
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1056 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1057
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1058 /* If the growth threshold of the buckets in use has been reached, increase
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1059 the table size and rehash. There's no point in checking the number of
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1060 entries: if the hashing function is ill-conditioned, rehashing is not
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1061 likely to improve it. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1062
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1063 if (table->n_buckets_used
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1064 > table->tuning->growth_threshold * table->n_buckets)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1065 {
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1066 /* Check more fully, before starting real work. If tuning arguments
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1067 became invalid, the second check will rely on proper defaults. */
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1068 check_tuning (table);
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1069 if (table->n_buckets_used
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1070 > table->tuning->growth_threshold * table->n_buckets)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1071 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1072 const Hash_tuning *tuning = table->tuning;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1073 float candidate =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1074 (tuning->is_n_buckets
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1075 ? (table->n_buckets * tuning->growth_factor)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1076 : (table->n_buckets * tuning->growth_factor
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1077 * tuning->growth_threshold));
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1078
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1079 if (SIZE_MAX <= candidate)
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1080 return -1;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1081
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1082 /* If the rehash fails, arrange to return NULL. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1083 if (!hash_rehash (table, candidate))
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1084 return -1;
11633 e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1085
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1086 /* Update the bucket we are interested in. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1087 if (hash_find_entry (table, entry, &bucket, false) != NULL)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1088 abort ();
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1089 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1090 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1091
11633 e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1092 /* ENTRY is not matched, it should be inserted. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1093
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1094 if (bucket->data)
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1095 {
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1096 struct hash_entry *new_entry = allocate_entry (table);
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1097
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1098 if (new_entry == NULL)
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1099 return -1;
11633 e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1100
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1101 /* Add ENTRY in the overflow of the bucket. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1102
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1103 new_entry->data = (void *) entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1104 new_entry->next = bucket->next;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1105 bucket->next = new_entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1106 table->n_entries++;
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1107 return 1;
11633 e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1108 }
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1109
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1110 /* Add ENTRY right in the bucket head. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1111
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1112 bucket->data = (void *) entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1113 table->n_entries++;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1114 table->n_buckets_used++;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1115
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1116 return 1;
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1117 }
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1118
16096 13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1119 /* hash_insert0 is the deprecated name for hash_insert_if_absent.
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1120 . */
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1121 int
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1122 hash_insert0 (Hash_table table, void const entry, void const **matched_ent)
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1123 {
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1124 return hash_insert_if_absent (table, entry, matched_ent);
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1125 }
13817d3d0af6 hash: deprecate poorly-named hash_insert0: use hash_insert_if_absent Jim Meyering <meyering@redhat.com> parents: 14644 diff changeset	1126
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1127 /* If ENTRY matches an entry already in the hash table, return the pointer
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1128 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1129 Return NULL if the storage required for insertion cannot be allocated.
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1130 This implementation does not support duplicate entries or insertion of
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1131 NULL. */
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1132
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1133 void *
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1134 hash_insert (Hash_table table, void const entry)
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1135 {
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1136 void const *matched_ent;
16100 deba2a70b794 hash: Don't refer to deprecated interfaces. Simon Josefsson <simon@josefsson.org> parents: 16096 diff changeset	1137 int err = hash_insert_if_absent (table, entry, &matched_ent);
13446 6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1138 return (err == -1
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1139 ? NULL
6a37ca840ab5 hash: extend module to deal with non-pointer keys Jim Meyering <meyering@redhat.com> parents: 12559 diff changeset	1140 : (void *) (err == 0 ? matched_ent : entry));
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1141 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1142
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1143 /* If ENTRY is already in the table, remove it and return the just-deleted
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1144 data (the user may want to deallocate its storage). If ENTRY is not in the
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1145 table, don't modify the table and return NULL. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1146
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1147 void *
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1148 hash_delete (Hash_table table, const void entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1149 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1150 void *data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1151 struct hash_entry *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1152
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	1153 data = hash_find_entry (table, entry, &bucket, true);
54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	1154 if (!data)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1155 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1156
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1157 table->n_entries--;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1158 if (!bucket->data)
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1159 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1160 table->n_buckets_used--;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1161
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1162 /* If the shrink threshold of the buckets in use has been reached,
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1163 rehash into a smaller table. */
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1164
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1165 if (table->n_buckets_used
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1166 < table->tuning->shrink_threshold * table->n_buckets)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1167 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1168 /* Check more fully, before starting real work. If tuning arguments
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1169 became invalid, the second check will rely on proper defaults. */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1170 check_tuning (table);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1171 if (table->n_buckets_used
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1172 < table->tuning->shrink_threshold * table->n_buckets)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1173 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1174 const Hash_tuning *tuning = table->tuning;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1175 size_t candidate =
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1176 (tuning->is_n_buckets
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1177 ? table->n_buckets * tuning->shrink_factor
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1178 : (table->n_buckets * tuning->shrink_factor
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1179 * tuning->growth_threshold));
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1180
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1181 if (!hash_rehash (table, candidate))
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1182 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1183 /* Failure to allocate memory in an attempt to
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1184 shrink the table is not fatal. But since memory
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1185 is low, we can at least be kind and free any
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1186 spare entries, rather than keeping them tied up
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1187 in the free entry list. */
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1188 #if ! USE_OBSTACK
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1189 struct hash_entry *cursor = table->free_entry_list;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1190 struct hash_entry *next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1191 while (cursor)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1192 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1193 next = cursor->next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1194 free (cursor);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1195 cursor = next;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1196 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1197 table->free_entry_list = NULL;
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1198 #endif
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1199 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1200 }
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1201 }
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1202 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1203
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1204 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1205 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	1206
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1207 /* Testing. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1208
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1209 #if TESTING
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1210
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1211 void
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1212 hash_print (const Hash_table *table)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1213 {
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1214 struct hash_entry bucket = (struct hash_entry ) table->bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1215
11642 08911a9e5f94 hash: avoid memory leak on allocation failure Eric Blake <ebb9@byu.net> parents: 11641 diff changeset	1216 for ( ; bucket < table->bucket_limit; bucket++)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1217 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1218 struct hash_entry *cursor;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1219
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1220 if (bucket)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1221 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1222
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1223 for (cursor = bucket; cursor; cursor = cursor->next)
12421 e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1224 {
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1225 char const *s = cursor->data;
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1226 /* FIXME */
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1227 if (s)
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1228 printf (" %s\n", s);
e8d2c6fc33ad Use spaces for indentation, not tabs. Bruno Haible <bruno@clisp.org> parents: 12117 diff changeset	1229 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1230 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1231 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1232
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1233 #endif /* TESTING */

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/hash.c @ 17323:a56636d89038