Reformatted.
[chise/xemacs-chise.git] / src / hash.c
1 /* Hash tables.
2    Copyright (C) 1992, 1993, 1994 Free Software Foundation, Inc.
3
4 This file is part of XEmacs.
5
6 XEmacs is free software; you can redistribute it and/or modify it
7 under the terms of the GNU General Public License as published by the
8 Free Software Foundation; either version 2, or (at your option) any
9 later version.
10
11 XEmacs is distributed in the hope that it will be useful, but WITHOUT
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14 for more details.
15
16 You should have received a copy of the GNU General Public License
17 along with XEmacs; see the file COPYING.  If not, write to
18 the Free Software Foundation, Inc., 59 Temple Place - Suite 330,
19 Boston, MA 02111-1307, USA.  */
20
21 /* Synched up with: Not in FSF. */
22
23 #include <config.h>
24 #include "lisp.h"
25 #include "hash.h"
26
27 #define NULL_ENTRY ((void *) 0xdeadbeef)
28
29 #define COMFORTABLE_SIZE(size) (21 * (size) / 16)
30
31 #define KEYS_DIFFER_P(old, new, testfun) \
32   (((old) != (new)) && (!(testfun) || !(testfun) ((old),(new))))
33
34 static void rehash (hentry *harray, struct hash_table *ht, hash_size_t size);
35
36 unsigned long
37 memory_hash (const void *xv, size_t size)
38 {
39   unsigned int h = 0;
40   unsigned const char *x = (unsigned const char *) xv;
41
42   if (!x) return 0;
43
44   while (size--)
45     {
46       unsigned int g;
47       h = (h << 4) + *x++;
48       if ((g = h & 0xf0000000) != 0)
49         h = (h ^ (g >> 24)) ^ g;
50     }
51
52   return h;
53 }
54
55 unsigned long
56 string_hash (const char *xv)
57 {
58   unsigned int h = 0;
59   unsigned const char *x = (unsigned const char *) xv;
60
61   if (!x) return 0;
62
63   while (*x)
64     {
65       unsigned int g;
66       h = (h << 4) + *x++;
67       if ((g = h & 0xf0000000) != 0)
68         h = (h ^ (g >> 24)) ^ g;
69     }
70
71   return h;
72 }
73
74 /* Return a suitable size for a hash table, with at least SIZE slots. */
75 static size_t
76 hash_table_size (size_t requested_size)
77 {
78   /* Return some prime near, but greater than or equal to, SIZE.
79      Decades from the time of writing, someone will have a system large
80      enough that the list below will be too short... */
81   static const size_t primes [] =
82   {
83     19, 29, 41, 59, 79, 107, 149, 197, 263, 347, 457, 599, 787, 1031,
84     1361, 1777, 2333, 3037, 3967, 5167, 6719, 8737, 11369, 14783,
85     19219, 24989, 32491, 42257, 54941, 71429, 92861, 120721, 156941,
86     204047, 265271, 344857, 448321, 582821, 757693, 985003, 1280519,
87     1664681, 2164111, 2813353, 3657361, 4754591, 6180989, 8035301,
88     10445899, 13579681, 17653589, 22949669, 29834603, 38784989,
89     50420551, 65546729, 85210757, 110774011, 144006217, 187208107,
90     243370577, 316381771, 411296309, 534685237, 695090819, 903618083,
91     1174703521, 1527114613, 1985248999, 2580823717UL, 3355070839UL
92   };
93   /* We've heard of binary search. */
94   int low, high;
95   for (low = 0, high = countof (primes) - 1; high - low > 1;)
96     {
97       /* Loop Invariant: size < primes [high] */
98       int mid = (low + high) / 2;
99       if (primes [mid] < requested_size)
100         low = mid;
101       else
102         high = mid;
103     }
104   return primes [high];
105 }
106
107 const void *
108 gethash (const void *key, struct hash_table *hash_table, const void **ret_value)
109 {
110   if (!key)
111     {
112       *ret_value = hash_table->zero_entry;
113       return (void *) hash_table->zero_set;
114     }
115   else
116     {
117       hentry *harray = hash_table->harray;
118       hash_table_test_function test_function = hash_table->test_function;
119       hash_size_t size = hash_table->size;
120       unsigned int hcode_initial =
121         hash_table->hash_function ?
122         hash_table->hash_function (key) :
123         (unsigned long) key;
124       unsigned int hcode = hcode_initial % size;
125       hentry *e = &harray [hcode];
126       const void *e_key = e->key;
127
128       if (e_key ?
129           KEYS_DIFFER_P (e_key, key, test_function) :
130           e->contents == NULL_ENTRY)
131         {
132           size_t h2 = size - 2;
133           unsigned int incr = 1 + (hcode_initial % h2);
134           do
135             {
136               hcode += incr; if (hcode >= size) hcode -= size;
137               e = &harray [hcode];
138               e_key = e->key;
139             }
140           while (e_key ?
141                  KEYS_DIFFER_P (e_key, key, test_function) :
142                  e->contents == NULL_ENTRY);
143         }
144
145       *ret_value = e->contents;
146       return e->key;
147     }
148 }
149
150 void
151 clrhash (struct hash_table *hash_table)
152 {
153   memset (hash_table->harray, 0, sizeof (hentry) * hash_table->size);
154   hash_table->zero_entry = 0;
155   hash_table->zero_set   = 0;
156   hash_table->fullness   = 0;
157 }
158
159 void
160 free_hash_table (struct hash_table *hash_table)
161 {
162   xfree (hash_table->harray);
163   xfree (hash_table);
164 }
165
166 struct hash_table*
167 make_hash_table (hash_size_t size)
168 {
169   struct hash_table *hash_table = xnew_and_zero (struct hash_table);
170   hash_table->size = hash_table_size (COMFORTABLE_SIZE (size));
171   hash_table->harray = xnew_array (hentry, hash_table->size);
172   clrhash (hash_table);
173   return hash_table;
174 }
175
176 struct hash_table *
177 make_general_hash_table (hash_size_t size,
178                         hash_table_hash_function hash_function,
179                         hash_table_test_function test_function)
180 {
181   struct hash_table* hash_table = make_hash_table (size);
182   hash_table->hash_function = hash_function;
183   hash_table->test_function = test_function;
184   return hash_table;
185 }
186
187 static void
188 grow_hash_table (struct hash_table *hash_table, hash_size_t new_size)
189 {
190   hash_size_t old_size   = hash_table->size;
191   hentry     *old_harray = hash_table->harray;
192
193   hash_table->size   = hash_table_size (new_size);
194   hash_table->harray = xnew_array (hentry, hash_table->size);
195
196   /* do the rehash on the "grown" table */
197   {
198     long old_zero_set    = hash_table->zero_set;
199     void *old_zero_entry = hash_table->zero_entry;
200     clrhash (hash_table);
201     hash_table->zero_set   = old_zero_set;
202     hash_table->zero_entry = old_zero_entry;
203     rehash (old_harray, hash_table, old_size);
204   }
205
206   xfree (old_harray);
207 }
208
209 void
210 puthash (const void *key, void *contents, struct hash_table *hash_table)
211 {
212   if (!key)
213     {
214       hash_table->zero_entry = contents;
215       hash_table->zero_set = 1;
216     }
217   else
218     {
219       hash_table_test_function test_function = hash_table->test_function;
220       hash_size_t size = hash_table->size;
221       hentry *harray   = hash_table->harray;
222       unsigned int hcode_initial =
223         hash_table->hash_function ?
224         hash_table->hash_function (key) :
225         (unsigned long) key;
226       unsigned int hcode = hcode_initial % size;
227       size_t h2 = size - 2;
228       unsigned int incr = 1 + (hcode_initial % h2);
229       const void *e_key = harray [hcode].key;
230       const void *oldcontents;
231
232       if (e_key && KEYS_DIFFER_P (e_key, key, test_function))
233         {
234           do
235             {
236               hcode += incr; if (hcode >= size) hcode -= size;
237               e_key = harray [hcode].key;
238             }
239           while (e_key && KEYS_DIFFER_P (e_key, key, test_function));
240         }
241       oldcontents = harray [hcode].contents;
242       harray [hcode].key = key;
243       harray [hcode].contents = contents;
244       /* If the entry that we used was a deleted entry,
245          check for a non deleted entry of the same key,
246          then delete it. */
247       if (!e_key && oldcontents == NULL_ENTRY)
248         {
249           hentry *e;
250
251           do
252             {
253               hcode += incr; if (hcode >= size) hcode -= size;
254               e = &harray [hcode];
255               e_key = e->key;
256             }
257           while (e_key ?
258                  KEYS_DIFFER_P (e_key, key, test_function):
259                  e->contents == NULL_ENTRY);
260
261           if (e_key)
262             {
263               e->key = 0;
264               e->contents = NULL_ENTRY;
265             }
266         }
267
268       /* only increment the fullness when we used up a new hentry */
269       if (!e_key || KEYS_DIFFER_P (e_key, key, test_function))
270         {
271           hash_size_t comfortable_size = COMFORTABLE_SIZE (++(hash_table->fullness));
272           if (hash_table->size < comfortable_size)
273             grow_hash_table (hash_table, comfortable_size + 1);
274         }
275     }
276 }
277
278 static void
279 rehash (hentry *harray, struct hash_table *hash_table, hash_size_t size)
280 {
281   hentry *limit = harray + size;
282   hentry *e;
283   for (e = harray; e < limit; e++)
284     {
285       if (e->key)
286         puthash (e->key, e->contents, hash_table);
287     }
288 }
289
290 void
291 remhash (const void *key, struct hash_table *hash_table)
292 {
293   if (!key)
294     {
295       hash_table->zero_entry = 0;
296       hash_table->zero_set = 0;
297     }
298   else
299     {
300       hentry *harray = hash_table->harray;
301       hash_table_test_function test_function = hash_table->test_function;
302       hash_size_t size = hash_table->size;
303       unsigned int hcode_initial =
304         (hash_table->hash_function) ?
305         (hash_table->hash_function (key)) :
306         ((unsigned long) key);
307       unsigned int hcode = hcode_initial % size;
308       hentry *e = &harray [hcode];
309       const void *e_key = e->key;
310
311       if (e_key ?
312           KEYS_DIFFER_P (e_key, key, test_function) :
313           e->contents == NULL_ENTRY)
314         {
315           size_t h2 = size - 2;
316           unsigned int incr = 1 + (hcode_initial % h2);
317           do
318             {
319               hcode += incr; if (hcode >= size) hcode -= size;
320               e = &harray [hcode];
321               e_key = e->key;
322             }
323           while (e_key?
324                  KEYS_DIFFER_P (e_key, key, test_function):
325                  e->contents == NULL_ENTRY);
326         }
327       if (e_key)
328         {
329           e->key = 0;
330           e->contents = NULL_ENTRY;
331           /* Note: you can't do fullness-- here, it breaks the world. */
332         }
333     }
334 }
335
336 void
337 maphash (maphash_function mf, struct hash_table *hash_table, void *arg)
338 {
339   hentry *e;
340   hentry *limit;
341
342   if (hash_table->zero_set)
343     {
344       if (mf (0, hash_table->zero_entry, arg))
345         return;
346     }
347
348   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
349     {
350       if (e->key && mf (e->key, e->contents, arg))
351         return;
352     }
353 }
354
355 void
356 map_remhash (remhash_predicate predicate, struct hash_table *hash_table, void *arg)
357 {
358   hentry *e;
359   hentry *limit;
360
361   if (hash_table->zero_set && predicate (0, hash_table->zero_entry, arg))
362     {
363       hash_table->zero_set = 0;
364       hash_table->zero_entry = 0;
365     }
366
367   for (e = hash_table->harray, limit = e + hash_table->size; e < limit; e++)
368     if (predicate (e->key, e->contents, arg))
369       {
370         e->key = 0;
371         e->contents = NULL_ENTRY;
372       }
373 }