1 /* PSPP - computes sample statistics.
2 Copyright (C) 1997-9, 2000 Free Software Foundation, Inc.
3 Written by Ben Pfaff <blp@gnu.org>.
5 This program is free software; you can redistribute it and/or
6 modify it under the terms of the GNU General Public License as
7 published by the Free Software Foundation; either version 2 of the
8 License, or (at your option) any later version.
10 This program is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with this program; if not, write to the Free Software
17 Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
28 /* Note for constructing hash functions:
30 You can store the hash values in the records, then compare hash
31 values (in the compare function) before bothering to compare keys.
32 Hash values can simply be returned from the records instead of
33 recalculating when rehashing. */
37 Since hash_probe and hash_find take void * pointers, it's easy to
38 pass a void ** to your data by accidentally inserting an `&'
39 reference operator where one shouldn't go. It took me an hour to
40 hunt down a bug like that once. */
42 /* Prime numbers and hash functions. */
44 static int hsh_prime_tab[] =
46 13, 31, 47, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411,
47 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319,
48 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
49 536870923, 1073741827, INT_MAX,
52 /* Returns pointer into hsh_prime_tab[], pointing to the first prime
53 in the table greater than X. */
55 hsh_next_prime (int x)
61 for (p = hsh_prime_tab; *p < x; p++)
64 assert (*p != INT_MAX);
69 /* P.J. Weinberger's hash function, recommended by the Red Dragon
70 Book. Hashes the d-string between S1 and S2. Returns unbounded
71 nonnegative result. */
73 hashpjw_d (const char *s1, const char *s2)
78 for (h = 0, p = s1; p < s2; p++)
80 h = (h << 4) + *(unsigned char *) p;
87 /* Alternate entry point for hashpjw_d() that takes an s-string. */
89 hashpjw (const char *s)
91 return hashpjw_d (s, &s[strlen (s)]);
96 /* Creates a hash table with at least M entries. COMPARE is a
97 function that compares two entries and returns 0 if they are
98 identical, nonzero otherwise; HASH returns a nonnegative hash value
99 for an entry; FREE destroys an entry. */
102 int (*compare) (const void *, const void *, void *param),
103 unsigned (*hash) (const void *, void *param),
104 void (*free) (void *, void *param),
107 struct hsh_table *h = xmalloc (sizeof *h);
111 h->mp = hsh_next_prime (m);
113 h->table = xmalloc (sizeof *h->table * h->m);
114 for (i = 0; i < h->m; i++)
117 h->compare = compare;
123 /* Destroys the contents of table H. */
125 hsh_clear (struct hsh_table *h)
130 for (i = 0; i < h->m; i++)
131 h->free (h->table[i], h->param);
136 h->mp = hsh_next_prime (31);
138 h->table = xmalloc (sizeof *h->table * h->m);
141 for (i = 0; i < h->m; i++)
145 /* Destroys table H and all its contents. */
147 hsh_destroy (struct hsh_table *h)
154 for (i = 0; i < h->m; i++)
156 void *p = h->table[i];
158 h->free (p, h->param);
164 /* Increases the capacity of H. */
166 hsh_rehash (struct hsh_table *h)
168 void **begin = h->table;
169 void **end = &h->table[h->m];
174 h->table = xmalloc (sizeof *h->table * h->m);
175 for (i = 0; i < h->m; i++)
177 for (table_p = begin; table_p < end; table_p++)
181 if (*table_p == NULL)
183 entry = &h->table[h->hash (*table_p, h->param) % h->m];
185 if (--entry < h->table)
186 entry = &h->table[h->m - 1];
192 /* Static variables for hsh_sort(). */
193 static void *hsh_param;
194 static int (*hsh_compare) (const void *, const void *, void *param);
196 /* hsh_sort() helper function that ensures NULLs are sorted after the
197 rest of the table. */
199 internal_comparison_fn (const void *pa, const void *pb)
201 void *a = *(void **) pa;
202 void *b = *(void **) pb;
203 return a == NULL ? 1 : (b == NULL ? -1 : hsh_compare (a, b, hsh_param));
206 /* Sorts hash table H based on function COMPARE. NULLs are sent to
207 the end of the table. The resultant table is returned (it is
208 guaranteed to be NULL-terminated). H should not be used again as a
209 hash table until and unless hsh_clear() called. */
211 hsh_sort (struct hsh_table *h,
212 int (*compare) (const void *, const void *, void *param))
215 static int reentrant;
220 hsh_param = h->param;
221 hsh_compare = compare ? compare : h->compare;
222 qsort (h->table, h->m, sizeof *h->table, internal_comparison_fn);
231 /* Searches hash table H for TARGET. If found, returns a pointer to a
232 pointer to that entry; otherwise returns a pointer to a NULL entry
233 which _must_ be used to insert a new entry having the same key
236 hsh_probe (struct hsh_table *h, const void *target)
240 /* Order of these statements is important! */
243 entry = &h->table[h->hash (target, h->param) % h->m];
247 if (!h->compare (*entry, target, h->param))
250 if (--entry < h->table)
251 entry = &h->table[h->m - 1];
257 /* Returns the entry in hash table H that matches TARGET, NULL if
260 hsh_find (struct hsh_table *h, const void *target)
262 void **entry = &h->table[h->hash (target, h->param) % h->m];
266 if (!h->compare (*entry, target, h->param))
268 if (--entry < h->table)
269 entry = &h->table[h->m - 1];
274 /* Iterates throught hash table TABLE with iterator ITER. Returns the
275 next non-NULL entry in TABLE, or NULL after the last non-NULL
276 entry. After NULL is returned, ITER is returned to a condition in
277 which hsh_foreach() will return the first non-NULL entry if any on
278 the next call. Do not add entries to TABLE between call to
279 hsh_foreach() between NULL returns.
281 Before calling hsh_foreach with a particular iterator for the first
282 time, you must initialize the iterator with a call to
283 hsh_iterator_init. */
285 hsh_foreach (struct hsh_table *table, struct hsh_iterator *iter)
296 for (i = iter->next; i < table->m; i++)
300 return table->table[i];
309 /* Displays contents of hash table H on stdout. */
311 hsh_dump (struct hsh_table *h)
313 void **entry = h->table;
316 printf (_("hash table:"));
317 for (i = 0; i < h->m; i++)
318 printf (" %p", *entry++);
322 /* This wrapper around hsh_probe() assures that it returns a pointer
323 to a NULL pointer. This function is used when it is known that the
324 entry to be inserted does not already exist in the table. */
326 force_hsh_insert (struct hsh_table *h, void *p)
328 void **pp = hsh_probe (h, p);
334 /* This wrapper around hsh_find() assures that it returns non-NULL.
335 This function is for use when it is known that the entry being
336 searched for must exist in the table. */
338 force_hsh_find (struct hsh_table *h, const void *p)