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

annotate lib/hash.c @ 10667:678640901735

Move the isnanf(), isnand(), isnanl() declarations to <math.h>.

author	Bruno Haible <bruno@clisp.org>
date	Sun, 19 Oct 2008 14:05:30 +0200
parents	bbbbbf4cd1c5
children	b7e9a8512f19

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
9200 da3798e554d6 * lib/hash.c (hash_initialize): Detect calloc failure. Jim Meyering <jim@meyering.net> parents: 7302 diff changeset	3 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007 Free
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	4 Software Foundation, Inc.
4251 3e9d34851e81 Include <stdbool.h> unconditionally. Paul Eggert <eggert@cs.ucla.edu> parents: 4040 diff changeset	5
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	6 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	7
9309 bbbbbf4cd1c5 Change copyright notice from GPLv2+ to GPLv3+. Bruno Haible <bruno@clisp.org> parents: 9200 diff changeset	8 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	9 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	10 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	11 (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	12
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	13 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	14 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	15 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	16 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	17
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	18 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	19 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	20
1038 b12d8086ca7a (ZALLOC): Take Ht parameter instead of relying on one being in scope. Jim Meyering <jim@meyering.net> parents: 1037 diff changeset	21 /* A generic hash table package. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	22
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	23 /* 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	24 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	25
7302 8a1a9361108c * _fpending.c: Include <config.h> unconditionally, since we no Paul Eggert <eggert@cs.ucla.edu> parents: 6259 diff changeset	26 #include <config.h>
4251 3e9d34851e81 Include <stdbool.h> unconditionally. Paul Eggert <eggert@cs.ucla.edu> parents: 4040 diff changeset	27
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	28 #include "hash.h"
4837 1625c6204e0b Include "xalloc.h" for use of xalloc_oversized. Jim Meyering <jim@meyering.net> parents: 4827 diff changeset	29 #include "xalloc.h"
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	30
4333 fcd34d3861a4 in lib: Paul Eggert <eggert@cs.ucla.edu> parents: 4251 diff changeset	31 #include <limits.h>
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	32 #include <stdio.h>
4658 6ef2ff78cbad Remove K&R cruft. Paul Eggert <eggert@cs.ucla.edu> parents: 4333 diff changeset	33 #include <stdlib.h>
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	34
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	35 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	36 # include "obstack.h"
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	37 # ifndef obstack_chunk_alloc
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	38 # 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	39 # endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	40 # ifndef obstack_chunk_free
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	41 # 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	42 # endif
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
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	45 #ifndef SIZE_MAX
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	46 # define SIZE_MAX ((size_t) -1)
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	47 #endif
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	48
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	49 struct hash_table
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	50 {
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	51 /* 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	52 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	53 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	54 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	55 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	56 size_t n_buckets;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	57 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	58 size_t n_entries;
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	59
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	60 /* Tuning arguments, kept in a physicaly separate structure. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	61 const Hash_tuning *tuning;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	62
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	63 /* Three functions are given to `hash_initialize', see the documentation
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	64 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	65 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	66 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	67 function for a user entry. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	68 Hash_hasher hasher;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	69 Hash_comparator comparator;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	70 Hash_data_freer data_freer;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	71
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	72 /* 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	73 struct hash_entry *free_entry_list;
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 #if USE_OBSTACK
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	76 /* 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	77 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	78 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	79 struct obstack entry_stack;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	80 #endif
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	81 };
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	82
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	83 /* A hash table contains many internal entries, each holding a pointer to
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	84 some user provided data (also called a user entry). An entry indistinctly
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	85 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	86 entry contents may be hashed by a randomization function (the hashing
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	87 function, or just `hasher' for short) into a number (or `slot') between 0
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	88 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	89 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	90 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	91
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	92 A good `hasher' function will distribute entries rather evenly in buckets.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	93 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	94 entries divided by the table size. Finding the slot for a data is usually
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	95 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	96 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	97 larger hash table size (that is, a larger number of buckets) is prone to
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	98 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	99
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	100 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	101 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	102 become inordinate, as unused slots in the hash table take some space. The
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	103 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	104 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	105 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	106
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	107 /* 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	108 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	109 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	110 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	111 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	112 every second time 80% of the buckets get used. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	113 #define DEFAULT_GROWTH_THRESHOLD 0.8
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	114 #define DEFAULT_GROWTH_FACTOR 1.414
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	115
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	116 /* 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	117 table size to become smaller than the shrink threshold (a number between
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	118 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	119 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	120 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	121 shrinks. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	122 #define DEFAULT_SHRINK_THRESHOLD 0.0
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	123 #define DEFAULT_SHRINK_FACTOR 1.0
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	124
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	125 /* 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	126 some sensible values. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	127 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	128 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	129 DEFAULT_SHRINK_THRESHOLD,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	130 DEFAULT_SHRINK_FACTOR,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	131 DEFAULT_GROWTH_THRESHOLD,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	132 DEFAULT_GROWTH_FACTOR,
3114 475265eee049 whoops. revert last change Jim Meyering <jim@meyering.net> parents: 3112 diff changeset	133 false
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	134 };
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	135
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	136 /* Information and lookup. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	137
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	138 /* The following few functions provide information about the overall hash
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	139 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	140 length of buckets. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	141
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	142 /* 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	143 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	144 the same quantity. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	145
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	146 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	147 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	148 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	149 return table->n_buckets;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	150 }
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 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	153
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	154 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	155 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	156 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	157 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	158 }
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 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	161
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	162 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	163 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	164 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	165 return table->n_entries;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	166 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	167
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	168 /* 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	169
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	170 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	171 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	172 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	173 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	174 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	175
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	176 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	177 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	178 if (bucket->data)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	179 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	180 struct hash_entry const *cursor = bucket;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	181 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	182
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	183 while (cursor = cursor->next, cursor)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	184 bucket_length++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	185
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	186 if (bucket_length > max_bucket_length)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	187 max_bucket_length = bucket_length;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	188 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	189 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	190
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	191 return max_bucket_length;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	192 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	193
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	194 /* 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	195 statistics. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	196
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	197 bool
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	198 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	199 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	200 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	201 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	202 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	203
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	204 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	205 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	206 if (bucket->data)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	207 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	208 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	209
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	210 /* Count bucket head. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	211 n_buckets_used++;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	212 n_entries++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	213
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	214 /* Count bucket overflow. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	215 while (cursor = cursor->next, cursor)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	216 n_entries++;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	217 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	218 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	219
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	220 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	221 return true;
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 return false;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	224 }
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 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	227 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	228 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	229 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	230 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	231 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	232 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	233
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	234 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	235 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	236 fprintf (stream, "# buckets used: %lu (%.2f%%)\n",
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	237 (unsigned long int) n_buckets_used,
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	238 (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	239 fprintf (stream, "max bucket length: %lu\n",
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	240 (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	241 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	242
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	243 /* If ENTRY matches an entry already in the hash table, return the
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	244 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	245
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	246 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	247 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	248 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	249 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	250 = table->bucket + table->hasher (entry, table->n_buckets);
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	251 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	252
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	253 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	254 abort ();
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	255
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	256 if (bucket->data == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	257 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	258
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	259 for (cursor = bucket; cursor; cursor = cursor->next)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	260 if (table->comparator (entry, cursor->data))
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	261 return cursor->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	262
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	263 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	264 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	265
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	266 /* Walking. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	267
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	268 /* 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	269 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	270 should not be resized nor modified while any particular entry is being
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	271 processed. In particular, entries should not be added or removed. */
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 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	274
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	275 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	276 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	277 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	278 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	279
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	280 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	281 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	282
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	283 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	284 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	285 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	286 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	287 return bucket->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	288 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	289
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	290 /* Return the user data for the entry following ENTRY, where ENTRY has been
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	291 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	292 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	293
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	294 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	295 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	296 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	297 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	298 = table->bucket + table->hasher (entry, table->n_buckets);
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	299 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	300
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	301 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	302 abort ();
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	303
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	304 /* Find next entry in the same bucket. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	305 for (cursor = bucket; cursor; cursor = cursor->next)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	306 if (cursor->data == entry && cursor->next)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	307 return cursor->next->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	308
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	309 /* 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	310 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	311 if (bucket->data)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	312 return bucket->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	313
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	314 /* None found. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	315 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	316 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	317
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	318 /* 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	319 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	320 pointers. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	321
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	322 size_t
1318 4e3526f71a49 split a couple long lines Jim Meyering <jim@meyering.net> parents: 1317 diff changeset	323 hash_get_entries (const Hash_table table, void *buffer,
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	324 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	325 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	326 size_t counter = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	327 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	328 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	329
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	330 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	331 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	332 if (bucket->data)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	333 {
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	334 for (cursor = bucket; cursor; cursor = cursor->next)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	335 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	336 if (counter >= buffer_size)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	337 return counter;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	338 buffer[counter++] = cursor->data;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	339 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	340 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	341 }
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 return counter;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	344 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	345
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	346 /* 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	347 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	348 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	349 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	350 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	351 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	352 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	353
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	354 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	355 hash_do_for_each (const Hash_table *table, Hash_processor processor,
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	356 void *processor_data)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	357 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	358 size_t counter = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	359 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	360 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	361
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	362 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	363 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	364 if (bucket->data)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	365 {
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	366 for (cursor = bucket; cursor; cursor = cursor->next)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	367 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	368 if (!(*processor) (cursor->data, processor_data))
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	369 return counter;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	370 counter++;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	371 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	372 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	373 }
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 return counter;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	376 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	377
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	378 /* Allocation and clean-up. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	379
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	380 /* 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	381 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	382
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	383 #if USE_DIFF_HASH
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	384
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	385 /* 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	386 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	387 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	388 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	389 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	390
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	391 size_t
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	392 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	393 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	394 # define ROTATE_LEFT(Value, Shift) \
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	395 ((Value) << (Shift) \| (Value) >> ((sizeof (size_t) * CHAR_BIT) - (Shift)))
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	396 # define HASH_ONE_CHAR(Value, Byte) \
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	397 ((Byte) + ROTATE_LEFT (Value, 7))
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	398
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	399 size_t value = 0;
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	400 unsigned char ch;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	401
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	402 for (; (ch = *string); string++)
a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	403 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	404 return value % n_buckets;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	405
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	406 # undef ROTATE_LEFT
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	407 # undef HASH_ONE_CHAR
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	408 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	409
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	410 #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	411
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	412 /* This one comes from `recode', and performs a bit better than the above as
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	413 per a few experiments. It is inspired from a hashing routine found in the
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	414 very old Cyber `snoop', itself written in typical Greg Mansfield style.
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	415 (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	416
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	417 size_t
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	418 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	419 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	420 size_t value = 0;
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	421 unsigned char ch;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	422
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	423 for (; (ch = *string); string++)
a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	424 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	425 return value;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	426 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	427
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	428 #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	429
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	430 /* 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	431 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	432
1744 60bb074a9bcb (is_prime): Return bool rather than int. Jim Meyering <jim@meyering.net> parents: 1743 diff changeset	433 static bool
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	434 is_prime (size_t candidate)
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	435 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	436 size_t divisor = 3;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	437 size_t square = divisor * divisor;
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	438
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	439 while (square < candidate && (candidate % divisor))
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	440 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	441 divisor++;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	442 square += 4 * divisor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	443 divisor++;
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	444 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	445
3076 a76b9dec6ef8 add omitted semicolon Jim Meyering <jim@meyering.net> parents: 3073 diff changeset	446 return (candidate % divisor ? true : false);
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	447 }
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 /* 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	450 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	451
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	452 static size_t
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	453 next_prime (size_t candidate)
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	454 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	455 /* Skip small primes. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	456 if (candidate < 10)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	457 candidate = 10;
1360 89ddc5685941 (is_prime): Ansideclify. Jim Meyering <jim@meyering.net> parents: 1318 diff changeset	458
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	459 /* Make it definitely odd. */
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	460 candidate \|= 1;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	461
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	462 while (!is_prime (candidate))
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	463 candidate += 2;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	464
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	465 return candidate;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	466 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	467
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	468 void
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	469 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	470 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	471 *tuning = default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	472 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	473
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	474 /* 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	475 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	476 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	477 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	478 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	479
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	480 static bool
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	481 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	482 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	483 const Hash_tuning *tuning = table->tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	484
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	485 /* 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	486 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	487 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	488 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	489 should be good enough. */
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	490 float epsilon = 0.1f;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	491
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	492 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	493 && 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	494 && 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	495 && 0 <= tuning->shrink_threshold
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	496 && 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	497 && tuning->shrink_factor <= 1
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	498 && 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	499 return true;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	500
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	501 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	502 return false;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	503 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	504
2105 b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	505 /* 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	506 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	507 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	508 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	509 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	510 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	511 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	512 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	513
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	514 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	515 tuning is wanted over the default behavior of the hasher. If TUNING is
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	516 NULL, the default tuning parameters are used instead.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	517
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	518 The user-supplied HASHER function should be provided. It accepts two
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	519 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	520 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	521 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	522
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	523 The user-supplied COMPARATOR function should be provided. It accepts two
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	524 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	525 that compare equal, or false otherwise. This function is internally called
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	526 on entries which are already known to hash to the same bucket index.
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	527
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	528 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	529 with the user data as an argument, just before the entry containing the
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	530 data gets freed. This happens from within `hash_free' or `hash_clear'.
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	531 You should specify this function only if you want these functions to free
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	532 all of your `data' data. This is typically the case when your data is
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	533 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	534 values. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	535
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	536 Hash_table *
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	537 hash_initialize (size_t candidate, const Hash_tuning *tuning,
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	538 Hash_hasher hasher, Hash_comparator comparator,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	539 Hash_data_freer data_freer)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	540 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	541 Hash_table *table;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	542
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	543 if (hasher == NULL \|\| comparator == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	544 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	545
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	546 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	547 if (table == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	548 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	549
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	550 if (!tuning)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	551 tuning = &default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	552 table->tuning = tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	553 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	554 {
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	555 /* Fail if the tuning options are invalid. This is the only occasion
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	556 when the user gets some feedback about it. Once the table is created,
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	557 if the user provides invalid tuning options, we silently revert to
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	558 using the defaults, and ignore further request to change the tuning
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	559 options. */
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	560 goto fail;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	561 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	562
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	563 if (!tuning->is_n_buckets)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	564 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	565 float new_candidate = candidate / tuning->growth_threshold;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	566 if (SIZE_MAX <= new_candidate)
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	567 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	568 candidate = new_candidate;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	569 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	570
4827 a6d03da0fa67 Simplify the code by using new xalloc.h features. Paul Eggert <eggert@cs.ucla.edu> parents: 4813 diff changeset	571 if (xalloc_oversized (candidate, sizeof *table->bucket))
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	572 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	573 table->n_buckets = next_prime (candidate);
4827 a6d03da0fa67 Simplify the code by using new xalloc.h features. Paul Eggert <eggert@cs.ucla.edu> parents: 4813 diff changeset	574 if (xalloc_oversized (table->n_buckets, sizeof *table->bucket))
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	575 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	576
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	577 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	578 if (table->bucket == NULL)
da3798e554d6 * lib/hash.c (hash_initialize): Detect calloc failure. Jim Meyering <jim@meyering.net> parents: 7302 diff changeset	579 goto fail;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	580 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	581 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	582 table->n_entries = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	583
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	584 table->hasher = hasher;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	585 table->comparator = comparator;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	586 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	587
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	588 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	589 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	590 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	591 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	592 return table;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	593
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	594 fail:
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	595 free (table);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	596 return NULL;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	597 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	598
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	599 /* 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	600 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	601 affected entries. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	602
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	603 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	604 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	605 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	606 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	607
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	608 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	609 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	610 if (bucket->data)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	611 {
3582 abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	612 struct hash_entry *cursor;
abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	613 struct hash_entry *next;
abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	614
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	615 /* Free the bucket overflow. */
3582 abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	616 for (cursor = bucket->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	617 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	618 if (table->data_freer)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	619 (*table->data_freer) (cursor->data);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	620 cursor->data = NULL;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	621
3582 abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	622 next = 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	623 /* Relinking is done one entry at a time, as it is to be expected
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	624 that overflows are either rare or short. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	625 cursor->next = table->free_entry_list;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	626 table->free_entry_list = cursor;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	627 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	628
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	629 /* Free the bucket head. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	630 if (table->data_freer)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	631 (*table->data_freer) (bucket->data);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	632 bucket->data = NULL;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	633 bucket->next = NULL;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	634 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	635 }
1310 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->n_buckets_used = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	638 table->n_entries = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	639 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	640
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	641 /* 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	642 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	643 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	644 entry. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	645
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	646 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	647 hash_free (Hash_table *table)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	648 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	649 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	650 struct hash_entry *cursor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	651 struct hash_entry *next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	652
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	653 /* 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	654 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	655 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	656 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	657 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	658 if (bucket->data)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	659 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	660 for (cursor = bucket; cursor; cursor = cursor->next)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	661 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	662 (*table->data_freer) (cursor->data);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	663 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	664 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	665 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	666 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	667
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	668 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	669
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	670 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	671
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	672 #else
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	673
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	674 /* 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	675 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	676 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	677 for (cursor = bucket->next; cursor; cursor = next)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	678 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	679 next = cursor->next;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	680 free (cursor);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	681 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	682 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	683
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	684 /* 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	685 for (cursor = table->free_entry_list; cursor; cursor = next)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	686 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	687 next = cursor->next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	688 free (cursor);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	689 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	690
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	691 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	692
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	693 /* 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	694 free (table->bucket);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	695 free (table);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	696 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 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 /* Insertion and deletion. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	699
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	700 /* Get a new hash entry for a bucket overflow, possibly by reclying a
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	701 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	702
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	703 static struct hash_entry *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	704 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	705 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	706 struct hash_entry *new;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	707
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	708 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	709 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	710 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	711 table->free_entry_list = new->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	712 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	713 else
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	714 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	715 #if USE_OBSTACK
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	716 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	717 #else
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	718 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	719 #endif
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	720 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	721
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	722 return new;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	723 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	724
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	725 /* 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	726 saving it for later recycling. */
1039 4d7cd20a6c87 (hash_free_0): Remove prototype. Jim Meyering <jim@meyering.net> parents: 1038 diff changeset	727
4d7cd20a6c87 (hash_free_0): Remove prototype. Jim Meyering <jim@meyering.net> parents: 1038 diff changeset	728 static void
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	729 free_entry (Hash_table table, struct hash_entry entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	730 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	731 entry->data = NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	732 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	733 table->free_entry_list = entry;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	734 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	735
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	736 /* 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	737 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	738 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	739 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	740 the table, unlink the matching entry. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	741
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	742 static void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	743 hash_find_entry (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	744 struct hash_entry **bucket_head, bool delete)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	745 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	746 struct hash_entry *bucket
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	747 = table->bucket + table->hasher (entry, table->n_buckets);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	748 struct hash_entry *cursor;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	749
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	750 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	751 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	752
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	753 *bucket_head = bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	754
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	755 /* Test for empty bucket. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	756 if (bucket->data == NULL)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	757 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	758
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	759 /* See if the entry is the first in the bucket. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	760 if ((*table->comparator) (entry, bucket->data))
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	761 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	762 void *data = bucket->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	763
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	764 if (delete)
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	765 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	766 if (bucket->next)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	767 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	768 struct hash_entry *next = bucket->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	769
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	770 /* Bump the first overflow entry into the bucket head, then save
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	771 the previous first overflow entry for later recycling. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	772 bucket = next;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	773 free_entry (table, next);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	774 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	775 else
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	776 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	777 bucket->data = NULL;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	778 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	779 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	780
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	781 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	782 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	783
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	784 /* Scan the bucket overflow. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	785 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	786 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	787 if ((*table->comparator) (entry, cursor->next->data))
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	788 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	789 void *data = cursor->next->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	790
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	791 if (delete)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	792 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	793 struct hash_entry *next = cursor->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	794
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	795 /* Unlink the entry to delete, then save the freed entry for later
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	796 recycling. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	797 cursor->next = next->next;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	798 free_entry (table, next);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	799 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	800
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	801 return data;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	802 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	803 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	804
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	805 /* No entry found. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	806 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	807 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	808
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	809 /* 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	810 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	811 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	812 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	813 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	814 occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	815 exact number of buckets desired. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	816
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	817 bool
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	818 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	819 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	820 Hash_table *new_table;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	821 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	822 struct hash_entry *cursor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	823 struct hash_entry *next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	824
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	825 new_table = hash_initialize (candidate, table->tuning, table->hasher,
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	826 table->comparator, table->data_freer);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	827 if (new_table == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	828 return false;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	829
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	830 /* 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	831 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	832 obstack_free (&new_table->entry_stack, NULL);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	833 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	834 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	835 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	836
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	837 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	838 if (bucket->data)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	839 for (cursor = bucket; cursor; cursor = next)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	840 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	841 void *data = cursor->data;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	842 struct hash_entry *new_bucket
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	843 = (new_table->bucket
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	844 + new_table->hasher (data, new_table->n_buckets));
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	845
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	846 if (! (new_bucket < new_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	847 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	848
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	849 next = cursor->next;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	850
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	851 if (new_bucket->data)
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	852 {
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	853 if (cursor == bucket)
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	854 {
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	855 /* Allocate or recycle an entry, when moving from a bucket
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	856 header into a bucket overflow. */
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	857 struct hash_entry *new_entry = allocate_entry (new_table);
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	858
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	859 if (new_entry == NULL)
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	860 return false;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	861
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	862 new_entry->data = data;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	863 new_entry->next = new_bucket->next;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	864 new_bucket->next = new_entry;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	865 }
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	866 else
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	867 {
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	868 /* Merely relink an existing entry, when moving from a
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	869 bucket overflow into a bucket overflow. */
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	870 cursor->next = new_bucket->next;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	871 new_bucket->next = cursor;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	872 }
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	873 }
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	874 else
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	875 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	876 /* Free an existing entry, when moving from a bucket
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	877 overflow into a bucket header. Also take care of the
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	878 simple case of moving from a bucket header into a bucket
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	879 header. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	880 new_bucket->data = data;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	881 new_table->n_buckets_used++;
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	882 if (cursor != bucket)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	883 free_entry (new_table, cursor);
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	884 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	885 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	886
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	887 free (table->bucket);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	888 table->bucket = new_table->bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	889 table->bucket_limit = new_table->bucket_limit;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	890 table->n_buckets = new_table->n_buckets;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	891 table->n_buckets_used = new_table->n_buckets_used;
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	892 table->free_entry_list = new_table->free_entry_list;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	893 /* table->n_entries already holds its value. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	894 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	895 table->entry_stack = new_table->entry_stack;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	896 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	897 free (new_table);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	898
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	899 return true;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	900 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	901
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	902 /* If ENTRY matches an entry already in the hash table, return the pointer
8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	903 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	904 Return NULL if the storage required for insertion cannot be allocated. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	905
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	906 void *
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	907 hash_insert (Hash_table table, const void entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	908 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	909 void *data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	910 struct hash_entry *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	911
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	912 /* The caller cannot insert a NULL entry. */
608641351e57 Avoid use of <assert.h>, as the GNU Coding Standards hint that one Paul Eggert <eggert@cs.ucla.edu> parents: 3645 diff changeset	913 if (! entry)
608641351e57 Avoid use of <assert.h>, as the GNU Coding Standards hint that one Paul Eggert <eggert@cs.ucla.edu> parents: 3645 diff changeset	914 abort ();
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	915
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	916 /* 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	917 if ((data = hash_find_entry (table, entry, &bucket, false)) != NULL)
8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	918 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	919
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	920 /* ENTRY is not matched, it should be inserted. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	921
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	922 if (bucket->data)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	923 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	924 struct hash_entry *new_entry = allocate_entry (table);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	925
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	926 if (new_entry == NULL)
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	927 return NULL;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	928
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	929 /* Add ENTRY in the overflow of the bucket. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	930
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	931 new_entry->data = (void *) entry;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	932 new_entry->next = bucket->next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	933 bucket->next = new_entry;
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	934 table->n_entries++;
8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	935 return (void *) entry;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	936 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	937
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	938 /* Add ENTRY right in the bucket head. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	939
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	940 bucket->data = (void *) entry;
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	941 table->n_entries++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	942 table->n_buckets_used++;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	943
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	944 /* 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	945 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	946 entries: if the hashing function is ill-conditioned, rehashing is not
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	947 likely to improve it. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	948
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	949 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	950 > table->tuning->growth_threshold * table->n_buckets)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	951 {
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	952 /* Check more fully, before starting real work. If tuning arguments
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	953 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	954 check_tuning (table);
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	955 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	956 > table->tuning->growth_threshold * table->n_buckets)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	957 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	958 const Hash_tuning *tuning = table->tuning;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	959 float candidate =
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	960 (tuning->is_n_buckets
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	961 ? (table->n_buckets * tuning->growth_factor)
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	962 : (table->n_buckets * tuning->growth_factor
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	963 * tuning->growth_threshold));
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	964
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	965 if (SIZE_MAX <= candidate)
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	966 return NULL;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	967
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	968 /* If the rehash fails, arrange to return NULL. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	969 if (!hash_rehash (table, candidate))
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	970 entry = NULL;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	971 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	972 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	973
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	974 return (void *) entry;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	975 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	976
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	977 /* 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	978 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	979 table, don't modify the table and return NULL. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	980
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	981 void *
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	982 hash_delete (Hash_table table, const void entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	983 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	984 void *data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	985 struct hash_entry *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	986
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	987 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	988 if (!data)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	989 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	990
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	991 table->n_entries--;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	992 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	993 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	994 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	995
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	996 /* If the shrink threshold of the buckets in use has been reached,
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	997 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	998
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	999 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	1000 < table->tuning->shrink_threshold * table->n_buckets)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1001 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1002 /* Check more fully, before starting real work. If tuning arguments
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1003 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	1004 check_tuning (table);
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1005 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	1006 < table->tuning->shrink_threshold * table->n_buckets)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1007 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1008 const Hash_tuning *tuning = table->tuning;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1009 size_t candidate =
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1010 (tuning->is_n_buckets
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1011 ? table->n_buckets * tuning->shrink_factor
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1012 : (table->n_buckets * tuning->shrink_factor
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1013 * 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	1014
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1015 hash_rehash (table, candidate);
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1016 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1017 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1018 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1019
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1020 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1021 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	1022
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1023 /* Testing. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1024
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1025 #if TESTING
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1026
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1027 void
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1028 hash_print (const Hash_table *table)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1029 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1030 struct hash_entry const *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1031
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1032 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1033 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1034 struct hash_entry *cursor;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1035
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1036 if (bucket)
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1037 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1038
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1039 for (cursor = bucket; cursor; cursor = cursor->next)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1040 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1041 char const *s = cursor->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1042 /* FIXME */
3564 132aa76b54d7 (hash_print) [TESTING]: Clean up. Jim Meyering <jim@meyering.net> parents: 3408 diff changeset	1043 if (s)
132aa76b54d7 (hash_print) [TESTING]: Clean up. Jim Meyering <jim@meyering.net> parents: 3408 diff changeset	1044 printf (" %s\n", s);
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1045 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1046 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1047 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1048
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1049 #endif /* TESTING */

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/hash.c @ 10667:678640901735