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

annotate lib/hash.c @ 11639:b2e769838448

hash: fix memory leak in last patch * lib/hash.c (hash_rehash): Avoid memory leak. Signed-off-by: Eric Blake <ebb9@byu.net>

author	Eric Blake <ebb9@byu.net>
date	Thu, 18 Jun 2009 15:24:38 -0600
parents	bddc78d1a1c2
children	66e1eeffb344

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
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	3 Copyright (C) 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2006, 2007,
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	4 2009 Free 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
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	49 struct hash_entry
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	50 {
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	51 void *data;
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	52 struct hash_entry *next;
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	53 };
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	54
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	55 struct hash_table
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	56 {
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	57 /* 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	58 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	59 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	60 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	61 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	62 size_t n_buckets;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	63 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	64 size_t n_entries;
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	65
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	66 /* Tuning arguments, kept in a physically separate structure. */
3645 b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	67 const Hash_tuning *tuning;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	68
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	69 /* 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	70 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	71 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	72 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	73 function for a user entry. */
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	74 Hash_hasher hasher;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	75 Hash_comparator comparator;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	76 Hash_data_freer data_freer;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	77
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	78 /* 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	79 struct hash_entry *free_entry_list;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	80
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	81 #if USE_OBSTACK
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	82 /* 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	83 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	84 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	85 struct obstack entry_stack;
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	86 #endif
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	87 };
b80d9433325b (struct hash_table): Define it here instead. Jim Meyering <jim@meyering.net> parents: 3582 diff changeset	88
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	89 /* A hash table contains many internal entries, each holding a pointer to
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	90 some user-provided data (also called a user entry). An entry indistinctly
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	91 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	92 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	93 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	94 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	95 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	96 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	97
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	98 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	99 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	100 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	101 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	102 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	103 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	104 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	105
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	106 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	107 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	108 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	109 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	110 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	111 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	112
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	113 /* 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	114 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	115 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	116 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	117 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	118 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	119 #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	120 #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	121
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	122 /* 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	123 table size to become smaller than the shrink threshold (a number between
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	124 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	125 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	126 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	127 shrinks. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	128 #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	129 #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	130
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	131 /* 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	132 some sensible values. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	133 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	134 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	135 DEFAULT_SHRINK_THRESHOLD,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	136 DEFAULT_SHRINK_FACTOR,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	137 DEFAULT_GROWTH_THRESHOLD,
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	138 DEFAULT_GROWTH_FACTOR,
3114 475265eee049 whoops. revert last change Jim Meyering <jim@meyering.net> parents: 3112 diff changeset	139 false
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	140 };
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	141
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	142 /* Information and lookup. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	143
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	144 /* The following few functions provide information about the overall hash
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	145 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	146 length of buckets. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	147
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	148 /* 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	149 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	150 the same quantity. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	151
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	152 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	153 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	154 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	155 return table->n_buckets;
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
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	158 /* 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	159
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	160 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	161 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	162 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	163 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	164 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	165
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	166 /* 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	167
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	168 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	169 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	170 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	171 return table->n_entries;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	172 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	173
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	174 /* 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	175
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	176 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	177 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	178 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	179 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	180 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	181
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	182 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	183 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	184 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	185 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	186 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	187 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	188
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	189 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	190 bucket_length++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	191
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	192 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	193 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	194 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	195 }
1310 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 return max_bucket_length;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	198 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	199
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	200 /* 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	201 statistics. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	202
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	203 bool
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	204 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	205 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	206 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	207 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	208 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	209
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	210 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	211 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	212 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	213 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	214 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	215
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	216 /* 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	217 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	218 n_entries++;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	219
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	220 /* 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	221 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	222 n_entries++;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	223 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	224 }
1310 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 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	227 return true;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	228
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	229 return false;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	230 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	231
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	232 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	233 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	234 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	235 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	236 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	237 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	238 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	239
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	240 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	241 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	242 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	243 (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	244 (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	245 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	246 (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	247 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	248
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	249 /* If ENTRY matches an entry already in the hash table, return the
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	250 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	251
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	252 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	253 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	254 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	255 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	256 = 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	257 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	258
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	259 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	260 abort ();
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	261
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	262 if (bucket->data == NULL)
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
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	265 for (cursor = bucket; cursor; cursor = cursor->next)
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	266 if (entry == cursor->data \|\| table->comparator (entry, cursor->data))
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	267 return cursor->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	268
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	269 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	270 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	271
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	272 /* Walking. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	273
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	274 /* 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	275 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	276 should not be resized nor modified while any particular entry is being
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	277 processed. In particular, entries should not be added, and an entry
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	278 may be removed only if there is no shrink threshold and the entry being
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	279 removed has already been passed to hash_get_next. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	280
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	281 /* 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	282
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	283 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	284 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	285 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	286 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	287
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	288 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	289 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	290
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	291 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	292 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	293 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	294 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	295 return bucket->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	296 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	297
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	298 /* 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	299 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	300 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	301
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	302 void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	303 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	304 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	305 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	306 = 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	307 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	308
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	309 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	310 abort ();
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	311
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	312 /* Find next entry in the same bucket. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	313 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	314 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	315 return cursor->next->data;
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 /* 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	318 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	319 if (bucket->data)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	320 return bucket->data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	321
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	322 /* None found. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	323 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	324 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	325
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	326 /* 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	327 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	328 pointers. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	329
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	330 size_t
1318 4e3526f71a49 split a couple long lines Jim Meyering <jim@meyering.net> parents: 1317 diff changeset	331 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	332 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	333 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	334 size_t counter = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	335 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	336 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	337
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	338 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	339 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	340 if (bucket->data)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	341 {
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	342 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	343 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	344 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	345 return counter;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	346 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	347 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	348 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	349 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	350
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	351 return counter;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	352 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	353
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	354 /* 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	355 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	356 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	357 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	358 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	359 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	360 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	361
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	362 size_t
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	363 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	364 void *processor_data)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	365 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	366 size_t counter = 0;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	367 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	368 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	369
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	370 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	371 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	372 if (bucket->data)
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	373 {
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	374 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	375 {
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	376 if (! processor (cursor->data, processor_data))
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	377 return counter;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	378 counter++;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	379 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	380 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	381 }
1310 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 return counter;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	384 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	385
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	386 /* Allocation and clean-up. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	387
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	388 /* Return 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	389 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	390
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	391 #if USE_DIFF_HASH
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	392
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	393 /* 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	394 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	395 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	396 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	397 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	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
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	400 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	401 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	402 # 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	403 ((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	404 # 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	405 ((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	406
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	407 size_t value = 0;
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	408 unsigned char ch;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	409
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	410 for (; (ch = *string); string++)
a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	411 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	412 return value % n_buckets;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	413
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	414 # undef ROTATE_LEFT
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	415 # undef HASH_ONE_CHAR
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	416 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	417
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	418 #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	419
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	420 /* 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	421 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	422 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	423 (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	424
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	425 size_t
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	426 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	427 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	428 size_t value = 0;
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	429 unsigned char ch;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	430
5159 a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	431 for (; (ch = *string); string++)
a535859efd14 Merge from coreutils. Paul Eggert <eggert@cs.ucla.edu> parents: 4837 diff changeset	432 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	433 return value;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	434 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	435
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	436 #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	437
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	438 /* 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	439 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	440
1744 60bb074a9bcb (is_prime): Return bool rather than int. Jim Meyering <jim@meyering.net> parents: 1743 diff changeset	441 static bool
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	442 is_prime (size_t candidate)
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	443 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	444 size_t divisor = 3;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	445 size_t square = divisor * divisor;
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	446
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	447 while (square < candidate && (candidate % divisor))
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	448 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	449 divisor++;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	450 square += 4 * divisor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	451 divisor++;
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	452 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	453
3076 a76b9dec6ef8 add omitted semicolon Jim Meyering <jim@meyering.net> parents: 3073 diff changeset	454 return (candidate % divisor ? true : false);
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	455 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	456
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	457 /* 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	458 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	459
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	460 static size_t
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	461 next_prime (size_t candidate)
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	462 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	463 /* Skip small primes. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	464 if (candidate < 10)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	465 candidate = 10;
1360 89ddc5685941 (is_prime): Ansideclify. Jim Meyering <jim@meyering.net> parents: 1318 diff changeset	466
1033 f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	467 /* Make it definitely odd. */
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	468 candidate \|= 1;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	469
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	470 while (!is_prime (candidate))
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	471 candidate += 2;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	472
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	473 return candidate;
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	474 }
f4f00c32582a use malloc, not xmalloc in obstack #define Jim Meyering <jim@meyering.net> parents: 1031 diff changeset	475
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	476 void
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	477 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	478 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	479 *tuning = default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	480 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	481
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	482 /* If the user passes a NULL hasher, we hash the raw pointer. */
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	483 static size_t
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	484 raw_hasher (const void *data, size_t n)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	485 {
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	486 /* When hashing unique pointers, it is often the case that they were
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	487 generated by malloc and thus have the property that the low-order
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	488 bits are 0. As this tends to give poorer performance with small
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	489 tables, we rotate the pointer value before performing division,
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	490 in an attempt to improve hash quality. */
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	491 size_t val = (size_t) data;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	492 val = ((val >> 3) \| (val << (CHAR_BIT * sizeof val - 3))) & SIZE_MAX;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	493 return val % n;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	494 }
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	495
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	496 /* If the user passes a NULL comparator, we use pointer comparison. */
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	497 static bool
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	498 raw_comparator (const void a, const void b)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	499 {
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	500 return a == b;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	501 }
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	502
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	503
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	504 /* 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	505 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	506 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	507 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	508 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	509
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	510 static bool
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	511 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	512 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	513 const Hash_tuning *tuning = table->tuning;
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	514 if (tuning == &default_tuning)
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	515 return true;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	516
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	517 /* 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	518 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	519 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	520 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	521 should be good enough. */
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	522 float epsilon = 0.1f;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	523
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	524 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	525 && 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	526 && 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	527 && 0 <= tuning->shrink_threshold
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	528 && 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	529 && tuning->shrink_factor <= 1
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	530 && tuning->shrink_threshold + epsilon < tuning->growth_threshold)
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	531 return true;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	532
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	533 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	534 return false;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	535 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	536
2105 b34218ec1190 (hash_initialize): Fix typo in comment. Jim Meyering <jim@meyering.net> parents: 1744 diff changeset	537 /* 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	538 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	539 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	540 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	541 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	542 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	543 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	544 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	545
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	546 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	547 tuning is wanted over the default behavior of the hasher. If TUNING is
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	548 NULL, the default tuning parameters are used instead. If TUNING is
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	549 provided but the values requested are out of bounds or might cause
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	550 rounding errors, return NULL.
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	551
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	552 The user-supplied HASHER function, when not NULL, accepts two
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	553 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	554 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	555 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	556
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	557 The user-supplied COMPARATOR function, when not NULL, accepts two
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	558 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	559 that compare equal, or false otherwise. This function is internally called
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	560 on entries which are already known to hash to the same bucket index,
95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	561 but which are distinct pointers.
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	562
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	563 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	564 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	565 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	566 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	567 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	568 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	569 values. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	570
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	571 Hash_table *
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	572 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	573 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	574 Hash_data_freer data_freer)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	575 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	576 Hash_table *table;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	577
11637 0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	578 if (hasher == NULL)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	579 hasher = raw_hasher;
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	580 if (comparator == NULL)
0b026e877c96 hash: provide default callback functions Eric Blake <ebb9@byu.net> parents: 11636 diff changeset	581 comparator = raw_comparator;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	582
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	583 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	584 if (table == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	585 return NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	586
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	587 if (!tuning)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	588 tuning = &default_tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	589 table->tuning = tuning;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	590 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	591 {
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	592 /* Fail if the tuning options are invalid. This is the only occasion
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	593 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	594 if the user provides invalid tuning options, we silently revert to
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	595 using the defaults, and ignore further request to change the tuning
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	596 options. */
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	597 goto fail;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	598 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	599
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	600 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	601 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	602 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	603 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	604 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	605 candidate = new_candidate;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	606 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	607
4827 a6d03da0fa67 Simplify the code by using new xalloc.h features. Paul Eggert <eggert@cs.ucla.edu> parents: 4813 diff changeset	608 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	609 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	610 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	611 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	612 goto fail;
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	613
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	614 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	615 if (table->bucket == NULL)
da3798e554d6 * lib/hash.c (hash_initialize): Detect calloc failure. Jim Meyering <jim@meyering.net> parents: 7302 diff changeset	616 goto fail;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	617 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	618 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	619 table->n_entries = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	620
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	621 table->hasher = hasher;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	622 table->comparator = comparator;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	623 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	624
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	625 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	626 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	627 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	628 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	629 return table;
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	630
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	631 fail:
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	632 free (table);
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	633 return NULL;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	634 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: 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 /* 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	637 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	638 affected entries. */
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 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	641 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	642 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	643 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	644
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	645 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	646 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	647 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	648 {
3582 abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	649 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	650 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	651
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	652 /* 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	653 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	654 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	655 if (table->data_freer)
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	656 table->data_freer (cursor->data);
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	657 cursor->data = NULL;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	658
3582 abe625b0449a (hash_clear): Fix a bug that could lead to an infloop or Jim Meyering <jim@meyering.net> parents: 3564 diff changeset	659 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	660 /* 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	661 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	662 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	663 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	664 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	665
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	666 /* 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	667 if (table->data_freer)
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	668 table->data_freer (bucket->data);
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	669 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	670 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	671 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	672 }
1310 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 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	675 table->n_entries = 0;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	676 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	677
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	678 /* 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	679 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	680 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	681 entry. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	682
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	683 void
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	684 hash_free (Hash_table *table)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	685 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	686 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	687 struct hash_entry *cursor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	688 struct hash_entry *next;
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 /* 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	691 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	692 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	693 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	694 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	695 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	696 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	697 for (cursor = bucket; cursor; cursor = cursor->next)
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	698 table->data_freer (cursor->data);
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	699 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	700 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	701 }
1310 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 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	704
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	705 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	706
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	707 #else
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	708
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	709 /* 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	710 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	711 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	712 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	713 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	714 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	715 free (cursor);
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	716 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	717 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	718
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	719 /* 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	720 for (cursor = table->free_entry_list; cursor; cursor = next)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	721 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	722 next = cursor->next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	723 free (cursor);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	724 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	725
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	726 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	727
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	728 /* 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	729 free (table->bucket);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	730 free (table);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	731 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	732
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	733 /* Insertion and deletion. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	734
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	735 /* Get a new hash entry for a bucket overflow, possibly by recycling a
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	736 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	737
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	738 static struct hash_entry *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	739 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	740 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	741 struct hash_entry *new;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	742
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	743 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	744 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	745 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	746 table->free_entry_list = new->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	747 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	748 else
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	749 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	750 #if USE_OBSTACK
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	751 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	752 #else
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	753 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	754 #endif
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	755 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	756
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	757 return new;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	758 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	759
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	760 /* 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	761 saving it for later recycling. */
1039 4d7cd20a6c87 (hash_free_0): Remove prototype. Jim Meyering <jim@meyering.net> parents: 1038 diff changeset	762
4d7cd20a6c87 (hash_free_0): Remove prototype. Jim Meyering <jim@meyering.net> parents: 1038 diff changeset	763 static void
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	764 free_entry (Hash_table table, struct hash_entry entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	765 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	766 entry->data = NULL;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	767 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	768 table->free_entry_list = entry;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	769 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	770
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	771 /* 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	772 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	773 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	774 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	775 the table, unlink the matching entry. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	776
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	777 static void *
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	778 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	779 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	780 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	781 struct hash_entry *bucket
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	782 = 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	783 struct hash_entry *cursor;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	784
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	785 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	786 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	787
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	788 *bucket_head = bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	789
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	790 /* Test for empty bucket. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	791 if (bucket->data == NULL)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	792 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	793
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	794 /* See if the entry is the first in the bucket. */
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	795 if (entry == bucket->data \|\| table->comparator (entry, bucket->data))
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	796 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	797 void *data = bucket->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	798
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	799 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	800 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	801 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	802 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	803 struct hash_entry *next = bucket->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	804
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	805 /* 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	806 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	807 bucket = next;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	808 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	809 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	810 else
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	811 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	812 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	813 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	814 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	815
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	816 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	817 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	818
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	819 /* Scan the bucket overflow. */
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	820 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	821 {
11636 95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	822 if (entry == cursor->next->data
95fd221d763c hash: minor optimization Eric Blake <ebb9@byu.net> parents: 11633 diff changeset	823 \|\| table->comparator (entry, cursor->next->data))
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	824 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	825 void *data = cursor->next->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	826
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	827 if (delete)
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	828 {
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	829 struct hash_entry *next = cursor->next;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	830
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	831 /* 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	832 recycling. */
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	833 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	834 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	835 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	836
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	837 return data;
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	838 }
921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	839 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	840
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	841 /* No entry found. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	842 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	843 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	844
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	845 /* 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	846 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	847 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	848 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	849 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	850 occurs. If TUNING->IS_N_BUCKETS is true, then CANDIDATE specifies the
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	851 exact number of buckets desired. Return true iff the rehash succeeded. */
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	852
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	853 bool
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	854 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	855 {
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	856 Hash_table *new_table;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	857 struct hash_entry *bucket;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	858 struct hash_entry *cursor;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	859 struct hash_entry *next;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	860
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	861 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	862 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	863 if (new_table == NULL)
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	864 return false;
11638 bddc78d1a1c2 hash: avoid no-op rehashing Eric Blake <ebb9@byu.net> parents: 11637 diff changeset	865 if (new_table->n_buckets == table->n_buckets)
11639 b2e769838448 hash: fix memory leak in last patch Eric Blake <ebb9@byu.net> parents: 11638 diff changeset	866 {
b2e769838448 hash: fix memory leak in last patch Eric Blake <ebb9@byu.net> parents: 11638 diff changeset	867 free (new_table->bucket);
b2e769838448 hash: fix memory leak in last patch Eric Blake <ebb9@byu.net> parents: 11638 diff changeset	868 free (new_table);
b2e769838448 hash: fix memory leak in last patch Eric Blake <ebb9@byu.net> parents: 11638 diff changeset	869 return true;
b2e769838448 hash: fix memory leak in last patch Eric Blake <ebb9@byu.net> parents: 11638 diff changeset	870 }
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	871
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	872 /* 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	873 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	874 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	875 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	876 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	877 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	878
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	879 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	880 if (bucket->data)
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	881 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	882 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	883 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	884 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	885 = (new_table->bucket
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	886 + 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	887
4040 0546d7f367db (hash_lookup, hash_get_first, hash_get_next, hash_find_entry, Paul Eggert <eggert@cs.ucla.edu> parents: 4006 diff changeset	888 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	889 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	890
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	891 next = cursor->next;
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	892
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	893 if (new_bucket->data)
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	894 {
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	895 if (cursor == bucket)
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	896 {
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	897 /* Allocate or recycle an entry, when moving from a bucket
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	898 header into a bucket overflow. */
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	899 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	900
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	901 if (new_entry == NULL)
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	902 return false;
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	903
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	904 new_entry->data = data;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	905 new_entry->next = new_bucket->next;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	906 new_bucket->next = new_entry;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	907 }
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	908 else
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	909 {
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	910 /* Merely relink an existing entry, when moving from a
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	911 bucket overflow into a bucket overflow. */
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	912 cursor->next = new_bucket->next;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	913 new_bucket->next = cursor;
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	914 }
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	915 }
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	916 else
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	917 {
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	918 /* 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	919 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	920 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	921 header. */
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	922 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	923 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	924 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	925 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	926 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	927 }
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 free (table->bucket);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	930 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	931 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	932 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	933 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	934 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	935 /* 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	936 #if USE_OBSTACK
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	937 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	938 #endif
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	939 free (new_table);
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	940
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	941 return true;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	942 }
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	943
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	944 /* 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	945 to the entry from the table. Otherwise, insert ENTRY and return ENTRY.
11631 b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	946 Return NULL if the storage required for insertion cannot be allocated.
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	947 This implementation does not support duplicate entries or insertion of
b7e9a8512f19 hash: minor cleanups Eric Blake <ebb9@byu.net> parents: 9309 diff changeset	948 NULL. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	949
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	950 void *
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	951 hash_insert (Hash_table table, const void entry)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	952 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	953 void *data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	954 struct hash_entry *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	955
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	956 /* 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	957 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	958 abort ();
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	959
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	960 /* 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	961 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	962 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	963
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	964 /* 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	965 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	966 entries: if the hashing function is ill-conditioned, rehashing is not
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	967 likely to improve it. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	968
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	969 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	970 > table->tuning->growth_threshold * table->n_buckets)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	971 {
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	972 /* Check more fully, before starting real work. If tuning arguments
d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	973 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	974 check_tuning (table);
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	975 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	976 > 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	977 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	978 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	979 float candidate =
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	980 (tuning->is_n_buckets
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	981 ? (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	982 : (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	983 * tuning->growth_threshold));
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	984
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	985 if (SIZE_MAX <= candidate)
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	986 return NULL;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	987
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	988 /* 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	989 if (!hash_rehash (table, candidate))
11633 e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	990 return NULL;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	991
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	992 /* Update the bucket we are interested in. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	993 if (hash_find_entry (table, entry, &bucket, false) != NULL)
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	994 abort ();
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	995 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	996 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	997
11633 e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	998 /* ENTRY is not matched, it should be inserted. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	999
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1000 if (bucket->data)
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1001 {
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1002 struct hash_entry *new_entry = allocate_entry (table);
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1003
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1004 if (new_entry == NULL)
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1005 return NULL;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1006
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1007 /* Add ENTRY in the overflow of the bucket. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1008
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1009 new_entry->data = (void *) entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1010 new_entry->next = bucket->next;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1011 bucket->next = new_entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1012 table->n_entries++;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1013 return (void *) entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1014 }
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1015
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1016 /* Add ENTRY right in the bucket head. */
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1017
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1018 bucket->data = (void *) entry;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1019 table->n_entries++;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1020 table->n_buckets_used++;
e62851e0bf87 hash: check for resize before insertion Eric Blake <ebb9@byu.net> parents: 11631 diff changeset	1021
1739 8fa1339d0b04 (hash_insert): Remove last parameter and change semantics. Jim Meyering <jim@meyering.net> parents: 1360 diff changeset	1022 return (void *) entry;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1023 }
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 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	1026 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	1027 table, don't modify the table and return NULL. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1028
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1029 void *
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1030 hash_delete (Hash_table table, const void entry)
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 void *data;
f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1033 struct hash_entry *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1034
2524 54e1c2ea1b8e (hash_rehash): Fix a nasty bug: copy the free entry list Jim Meyering <jim@meyering.net> parents: 2293 diff changeset	1035 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	1036 if (!data)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1037 return NULL;
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1038
1742 2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1039 table->n_entries--;
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1040 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	1041 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1042 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	1043
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1044 /* 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	1045 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	1046
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1047 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	1048 < 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	1049 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1050 /* Check more fully, before starting real work. If tuning arguments
1743 d3b8540577e0 tweak comments Jim Meyering <jim@meyering.net> parents: 1742 diff changeset	1051 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	1052 check_tuning (table);
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1053 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	1054 < 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	1055 {
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1056 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	1057 size_t candidate =
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1058 (tuning->is_n_buckets
04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1059 ? 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	1060 : (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	1061 * 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	1062
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1063 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	1064 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1065 }
2ca71d0bb483 Revamp to allow fine-tuning to control when and by how Jim Meyering <jim@meyering.net> parents: 1739 diff changeset	1066 }
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1067
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1068 return data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1069 }
1317 921744743921 Add curly braces around statements in if/else/while/do/etc. that Jim Meyering <jim@meyering.net> parents: 1310 diff changeset	1070
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1071 /* Testing. */
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1072
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1073 #if TESTING
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1074
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1075 void
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1076 hash_print (const Hash_table *table)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1077 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1078 struct hash_entry const *bucket;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1079
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1080 for (bucket = table->bucket; bucket < table->bucket_limit; bucket++)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1081 {
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1082 struct hash_entry *cursor;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1083
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1084 if (bucket)
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1085 printf ("%lu:\n", (unsigned long int) (bucket - table->bucket));
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1086
1310 f9473b8f6df1 Lots of minor spec and name changes, and new comments. Jim Meyering <jim@meyering.net> parents: 1039 diff changeset	1087 for (cursor = bucket; cursor; cursor = cursor->next)
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1088 {
4813 04eb43f18dc7 Fix several address-calculation bugs in the hash modules, Paul Eggert <eggert@cs.ucla.edu> parents: 4658 diff changeset	1089 char const *s = cursor->data;
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1090 /* FIXME */
3564 132aa76b54d7 (hash_print) [TESTING]: Clean up. Jim Meyering <jim@meyering.net> parents: 3408 diff changeset	1091 if (s)
132aa76b54d7 (hash_print) [TESTING]: Clean up. Jim Meyering <jim@meyering.net> parents: 3408 diff changeset	1092 printf (" %s\n", s);
1031 e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1093 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1094 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1095 }
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1096
e34b8e81638f from ti/hdlsv Jim Meyering <jim@meyering.net> parents: diff changeset	1097 #endif /* TESTING */

Mercurial > hg > octave-kai > gnulib-hg

annotate lib/hash.c @ 11639:b2e769838448