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
27 /* Note for constructing hash functions:
29 You can store the hash values in the records, then compare hash
30 values (in the compare function) before bothering to compare keys.
31 Hash values can simply be returned from the records instead of
32 recalculating when rehashing. */
36 Since hash_probe and hash_find take void * pointers, it's easy to
37 pass a void ** to your data by accidentally inserting an `&'
38 reference operator where one shouldn't go. It took me an hour to
39 hunt down a bug like that once. */
41 /* Prime numbers and hash functions. */
43 static int hsh_prime_tab[] =
45 13, 31, 47, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411,
46 32771, 65537, 131101, 262147, 524309, 1048583, 2097169, 4194319,
47 8388617, 16777259, 33554467, 67108879, 134217757, 268435459,
48 536870923, 1073741827, INT_MAX,
51 /* Returns pointer into hsh_prime_tab[], pointing to the first prime
52 in the table greater than X. */
54 hsh_next_prime (int x)
60 for (p = hsh_prime_tab; *p < x; p++)
63 assert (*p != INT_MAX);
68 /* P.J. Weinberger's hash function, recommended by the Red Dragon
69 Book. Hashes the d-string between S1 and S2. Returns unbounded
70 nonnegative result. */
72 hashpjw_d (const char *s1, const char *s2)
77 for (h = 0, p = s1; p < s2; p++)
79 h = (h << 4) + *(unsigned char *) p;
86 /* Alternate entry point for hashpjw_d() that takes an s-string. */
88 hashpjw (const char *s)
90 return hashpjw_d (s, &s[strlen (s)]);
95 /* Creates a hash table with at least M entries. COMPARE is a
96 function that compares two entries and returns 0 if they are
97 identical, nonzero otherwise; HASH returns a nonnegative hash value
98 for an entry; FREE destroys an entry. */
101 int (*compare) (const void *, const void *, void *param),
102 unsigned (*hash) (const void *, void *param),
103 void (*free) (void *, void *param),
106 struct hsh_table *h = xmalloc (sizeof *h);
110 h->mp = hsh_next_prime (m);
112 h->table = xmalloc (sizeof *h->table * h->m);
113 for (i = 0; i < h->m; i++)
116 h->compare = compare;
122 /* Destroys the contents of table H. */
124 hsh_clear (struct hsh_table *h)
129 for (i = 0; i < h->m; i++)
130 h->free (h->table[i], h->param);
135 h->mp = hsh_next_prime (31);
137 h->table = xmalloc (sizeof *h->table * h->m);
140 for (i = 0; i < h->m; i++)
144 /* Destroys table H and all its contents. */
146 hsh_destroy (struct hsh_table *h)
153 for (i = 0; i < h->m; i++)
155 void *p = h->table[i];
157 h->free (p, h->param);
163 /* Increases the capacity of H. */
165 hsh_rehash (struct hsh_table *h)
167 void **begin = h->table;
168 void **end = &h->table[h->m];
173 h->table = xmalloc (sizeof *h->table * h->m);
174 for (i = 0; i < h->m; i++)
176 for (table_p = begin; table_p < end; table_p++)
180 if (*table_p == NULL)
182 entry = &h->table[h->hash (*table_p, h->param) % h->m];
184 if (--entry < h->table)
185 entry = &h->table[h->m - 1];
191 /* Static variables for hsh_sort(). */
192 static void *hsh_param;
193 static int (*hsh_compare) (const void *, const void *, void *param);
195 /* hsh_sort() helper function that ensures NULLs are sorted after the
196 rest of the table. */
198 internal_comparison_fn (const void *pa, const void *pb)
200 void *a = *(void **) pa;
201 void *b = *(void **) pb;
202 return a == NULL ? 1 : (b == NULL ? -1 : hsh_compare (a, b, hsh_param));
205 /* Sorts hash table H based on function COMPARE. NULLs are sent to
206 the end of the table. The resultant table is returned (it is
207 guaranteed to be NULL-terminated). H should not be used again as a
208 hash table until and unless hsh_clear() called. */
210 hsh_sort (struct hsh_table *h,
211 int (*compare) (const void *, const void *, void *param))
214 static int reentrant;
219 hsh_param = h->param;
220 hsh_compare = compare ? compare : h->compare;
221 qsort (h->table, h->m, sizeof *h->table, internal_comparison_fn);
230 /* Searches hash table H for TARGET. If found, returns a pointer to a
231 pointer to that entry; otherwise returns a pointer to a NULL entry
232 which _must_ be used to insert a new entry having the same key
235 hsh_probe (struct hsh_table *h, const void *target)
239 /* Order of these statements is important! */
242 entry = &h->table[h->hash (target, h->param) % h->m];
246 if (!h->compare (*entry, target, h->param))
249 if (--entry < h->table)
250 entry = &h->table[h->m - 1];
256 /* Returns the entry in hash table H that matches TARGET, NULL if
259 hsh_find (struct hsh_table *h, const void *target)
261 void **entry = &h->table[h->hash (target, h->param) % h->m];
265 if (!h->compare (*entry, target, h->param))
267 if (--entry < h->table)
268 entry = &h->table[h->m - 1];
273 /* Iterates throught hash table TABLE with iterator ITER. Returns the
274 next non-NULL entry in TABLE, or NULL after the last non-NULL
275 entry. After NULL is returned, ITER is returned to a condition in
276 which hsh_foreach() will return the first non-NULL entry if any on
277 the next call. Do not add entries to TABLE between call to
278 hsh_foreach() between NULL returns.
280 Before calling hsh_foreach with a particular iterator for the first
281 time, you must initialize the iterator with a call to
282 hsh_iterator_init. */
284 hsh_foreach (struct hsh_table *table, struct hsh_iterator *iter)
295 for (i = iter->next; i < table->m; i++)
299 return table->table[i];
308 /* Displays contents of hash table H on stdout. */
310 hsh_dump (struct hsh_table *h)
312 void **entry = h->table;
315 printf (_("hash table:"));
316 for (i = 0; i < h->m; i++)
317 printf (" %p", *entry++);
321 /* This wrapper around hsh_probe() assures that it returns a pointer
322 to a NULL pointer. This function is used when it is known that the
323 entry to be inserted does not already exist in the table. */
325 force_hsh_insert (struct hsh_table *h, void *p)
327 void **pp = hsh_probe (h, p);
333 /* This wrapper around hsh_find() assures that it returns non-NULL.
334 This function is for use when it is known that the entry being
335 searched for must exist in the table. */
337 force_hsh_find (struct hsh_table *h, const void *p)