blob: 904be4704caf21ae9830ca2ab6d7072a4cbeb591 [file] [log] [blame]
Bram Moolenaar6abd8e92005-01-19 22:21:15 +00001/* vi:set ts=8 sts=4 sw=4:
2 *
3 * VIM - Vi IMproved by Bram Moolenaar
4 *
5 * Do ":help uganda" in Vim to read copying and usage conditions.
6 * Do ":help credits" in Vim to see a list of people who contributed.
7 * See README.txt for an overview of the Vim source code.
8 */
9
10/*
11 * hashtable.c: Handling of a hashtable with Vim-specific properties.
12 *
13 * Each item in a hashtable has a NUL terminated string key. A key can appear
14 * only once in the table.
15 *
16 * A hash number is computed from the key for quick lookup. When the hashes
17 * of two different keys point to the same entry an algorithm is used to
18 * iterate over other entries in the table until the right one is found.
19 * To make the iteration work removed keys are different from entries where a
20 * key was never present.
21 *
22 * The mechanism has been partly based on how Python Dictionaries are
23 * implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4.
24 *
25 * The hashtable grows to accommodate more entries when needed. At least 1/3
26 * of the entries is empty to keep the lookup efficient (at the cost of extra
27 * memory).
28 */
29
30#include "vim.h"
31
32#if defined(FEAT_EVAL) || defined(FEAT_SYN_HL) || defined(PROTO)
33
Bram Moolenaar6ac54292005-02-02 23:07:25 +000034#if 0
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +000035# define HT_DEBUG /* extra checks for table consistency and statistics */
36
37static long hash_count_lookup = 0; /* count number of hashtab lookups */
38static long hash_count_perturb = 0; /* count number of "misses" */
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000039#endif
40
41/* Magic value for algorithm that walks through the array. */
42#define PERTURB_SHIFT 5
43
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +000044static int hash_may_resize __ARGS((hashtab_T *ht, int minitems));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000045
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +000046#if 0 /* currently not used */
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000047/*
48 * Create an empty hash table.
49 * Returns NULL when out of memory.
50 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +000051 hashtab_T *
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000052hash_create()
53{
Bram Moolenaar7df2d662005-01-25 22:18:08 +000054 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000055
Bram Moolenaar7df2d662005-01-25 22:18:08 +000056 ht = (hashtab_T *)alloc(sizeof(hashtab_T));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000057 if (ht != NULL)
58 hash_init(ht);
59 return ht;
60}
61#endif
62
63/*
64 * Initialize an empty hash table.
65 */
66 void
67hash_init(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +000068 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000069{
70 /* This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". */
Bram Moolenaar7df2d662005-01-25 22:18:08 +000071 vim_memset(ht, 0, sizeof(hashtab_T));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000072 ht->ht_array = ht->ht_smallarray;
73 ht->ht_mask = HT_INIT_SIZE - 1;
74}
75
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000076/*
Bram Moolenaardcaf10e2005-01-21 11:55:25 +000077 * Free the array of a hash table. Does not free the items it contains!
78 * If "ht" is not freed then you should call hash_init() next!
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000079 */
80 void
Bram Moolenaardcaf10e2005-01-21 11:55:25 +000081hash_clear(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +000082 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000083{
84 if (ht->ht_array != ht->ht_smallarray)
85 vim_free(ht->ht_array);
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000086}
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000087
88/*
89 * Find "key" in hashtable "ht". "key" must not be NULL.
90 * Always returns a pointer to a hashitem. If the item was not found then
91 * HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key
92 * would be added.
93 * WARNING: The returned pointer becomes invalid when the hashtable is changed
94 * (adding, setting or removing an item)!
95 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +000096 hashitem_T *
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000097hash_find(ht, key)
Bram Moolenaar7df2d662005-01-25 22:18:08 +000098 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000099 char_u *key;
100{
101 return hash_lookup(ht, key, hash_hash(key));
102}
103
104/*
105 * Like hash_find(), but caller computes "hash".
106 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000107 hashitem_T *
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000108hash_lookup(ht, key, hash)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000109 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000110 char_u *key;
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000111 hash_T hash;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000112{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000113 hash_T perturb;
114 hashitem_T *freeitem;
115 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000116 int idx;
117
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000118#ifdef HT_DEBUG
119 ++hash_count_lookup;
120#endif
121
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000122 /*
123 * Quickly handle the most common situations:
124 * - return if there is no item at all
125 * - skip over a removed item
126 * - return if the item matches
127 */
128 idx = hash & ht->ht_mask;
129 hi = &ht->ht_array[idx];
130
131 if (hi->hi_key == NULL)
132 return hi;
133 if (hi->hi_key == HI_KEY_REMOVED)
134 freeitem = hi;
135 else if (hi->hi_hash == hash && STRCMP(hi->hi_key, key) == 0)
136 return hi;
137 else
138 freeitem = NULL;
139
140 /*
141 * Need to search through the table to find the key. The algorithm
142 * to step through the table starts with large steps, gradually becoming
143 * smaller down to (1/4 table size + 1). This means it goes through all
144 * table entries in the end.
145 * When we run into a NULL key it's clear that the key isn't there.
146 * Return the first available slot found (can be a slot of a removed
147 * item).
148 */
149 for (perturb = hash; ; perturb >>= PERTURB_SHIFT)
150 {
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000151#ifdef HT_DEBUG
152 ++hash_count_perturb; /* count a "miss" for hashtab lookup */
153#endif
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000154 idx = (idx << 2) + idx + perturb + 1;
155 hi = &ht->ht_array[idx & ht->ht_mask];
156 if (hi->hi_key == NULL)
157 return freeitem == NULL ? hi : freeitem;
158 if (hi->hi_hash == hash
159 && hi->hi_key != HI_KEY_REMOVED
160 && STRCMP(hi->hi_key, key) == 0)
161 return hi;
162 if (hi->hi_key == HI_KEY_REMOVED && freeitem == NULL)
163 freeitem = hi;
164 }
165}
166
167/*
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000168 * Print the efficiency of hashtable lookups.
169 * Useful when trying different hash algorithms.
170 * Called when exiting.
171 */
172 void
173hash_debug_results()
174{
175#ifdef HT_DEBUG
176 fprintf(stderr, "\r\n\r\n\r\n\r\n");
177 fprintf(stderr, "Number of hashtable lookups: %ld\r\n", hash_count_lookup);
178 fprintf(stderr, "Number of perturb loops: %ld\r\n", hash_count_perturb);
179 fprintf(stderr, "Percentage of perturb loops: %ld%%\r\n",
180 hash_count_perturb * 100 / hash_count_lookup);
181#endif
182}
183
184/*
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000185 * Add item with key "key" to hashtable "ht".
186 * Returns FAIL when out of memory or the key is already present.
187 */
188 int
189hash_add(ht, key)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000190 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000191 char_u *key;
192{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000193 hash_T hash = hash_hash(key);
194 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000195
196 hi = hash_lookup(ht, key, hash);
197 if (!HASHITEM_EMPTY(hi))
198 {
199 EMSG2(_(e_intern2), "hash_add()");
200 return FAIL;
201 }
202 return hash_add_item(ht, hi, key, hash);
203}
204
205/*
206 * Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and
207 * "hi" must have been obtained with hash_lookup() and point to an empty item.
208 * "hi" is invalid after this!
209 * Returns OK or FAIL (out of memory).
210 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000211 int
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000212hash_add_item(ht, hi, key, hash)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000213 hashtab_T *ht;
214 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000215 char_u *key;
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000216 hash_T hash;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000217{
218 /* If resizing failed before and it fails again we can't add an item. */
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000219 if (ht->ht_error && hash_may_resize(ht, 0) == FAIL)
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000220 return FAIL;
221
222 ++ht->ht_used;
223 if (hi->hi_key == NULL)
224 ++ht->ht_filled;
225 hi->hi_key = key;
226 hi->hi_hash = hash;
227
228 /* When the space gets low may resize the array. */
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000229 return hash_may_resize(ht, 0);
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000230}
231
232#if 0 /* not used */
233/*
234 * Overwrite hashtable item "hi" with "key". "hi" must point to the item that
235 * is to be overwritten. Thus the number of items in the hashtable doesn't
236 * change.
237 * Although the key must be identical, the pointer may be different, thus it's
238 * set anyway (the key is part of an item with that key).
239 * The caller must take care of freeing the old item.
240 * "hi" is invalid after this!
241 */
242 void
243hash_set(hi, key)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000244 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000245 char_u *key;
246{
247 hi->hi_key = key;
248}
249#endif
250
251/*
252 * Remove item "hi" from hashtable "ht". "hi" must have been obtained with
Bram Moolenaar9a50b1b2005-06-27 22:48:21 +0000253 * hash_lookup().
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000254 * The caller must take care of freeing the item itself.
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000255 */
256 void
257hash_remove(ht, hi)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000258 hashtab_T *ht;
259 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000260{
261 --ht->ht_used;
262 hi->hi_key = HI_KEY_REMOVED;
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000263 hash_may_resize(ht, 0);
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000264}
265
266/*
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000267 * Lock a hashtable: prevent that ht_array changes.
268 * Don't use this when items are to be added!
269 * Must call hash_unlock() later.
270 */
271 void
272hash_lock(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000273 hashtab_T *ht;
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000274{
275 ++ht->ht_locked;
276}
277
Bram Moolenaar75c50c42005-06-04 22:06:24 +0000278#if 0 /* currently not used */
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000279/*
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000280 * Lock a hashtable at the specified number of entries.
281 * Caller must make sure no more than "size" entries will be added.
282 * Must call hash_unlock() later.
283 */
284 void
285hash_lock_size(ht, size)
286 hashtab_T *ht;
287 int size;
288{
289 (void)hash_may_resize(ht, size);
290 ++ht->ht_locked;
291}
Bram Moolenaar75c50c42005-06-04 22:06:24 +0000292#endif
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000293
294/*
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000295 * Unlock a hashtable: allow ht_array changes again.
296 * Table will be resized (shrink) when necessary.
297 * This must balance a call to hash_lock().
298 */
299 void
300hash_unlock(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000301 hashtab_T *ht;
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000302{
303 --ht->ht_locked;
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000304 (void)hash_may_resize(ht, 0);
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000305}
306
307/*
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000308 * Shrink a hashtable when there is too much empty space.
309 * Grow a hashtable when there is not enough empty space.
310 * Returns OK or FAIL (out of memory).
311 */
312 static int
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000313hash_may_resize(ht, minitems)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000314 hashtab_T *ht;
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000315 int minitems; /* minimal number of items */
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000316{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000317 hashitem_T temparray[HT_INIT_SIZE];
318 hashitem_T *oldarray, *newarray;
319 hashitem_T *olditem, *newitem;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000320 int newi;
321 int todo;
322 long_u oldsize, newsize;
323 long_u minsize;
324 long_u newmask;
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000325 hash_T perturb;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000326
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000327 /* Don't resize a locked table. */
328 if (ht->ht_locked > 0)
329 return OK;
330
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000331#ifdef HT_DEBUG
332 if (ht->ht_used > ht->ht_filled)
333 EMSG("hash_may_resize(): more used than filled");
334 if (ht->ht_filled >= ht->ht_mask + 1)
335 EMSG("hash_may_resize(): table completely filled");
336#endif
337
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000338 if (minitems == 0)
339 {
340 /* Return quickly for small tables with at least two NULL items. NULL
341 * items are required for the lookup to decide a key isn't there. */
342 if (ht->ht_filled < HT_INIT_SIZE - 1
343 && ht->ht_array == ht->ht_smallarray)
344 return OK;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000345
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000346 /*
347 * Grow or refill the array when it's more than 2/3 full (including
348 * removed items, so that they get cleaned up).
349 * Shrink the array when it's less than 1/5 full. When growing it is
350 * at least 1/4 full (avoids repeated grow-shrink operations)
351 */
352 oldsize = ht->ht_mask + 1;
353 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5)
354 return OK;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000355
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000356 if (ht->ht_used > 1000)
357 minsize = ht->ht_used * 2; /* it's big, don't make too much room */
358 else
359 minsize = ht->ht_used * 4; /* make plenty of room */
360 }
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000361 else
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000362 {
363 /* Use specified size. */
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000364 if ((long_u)minitems < ht->ht_used) /* just in case... */
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000365 minitems = ht->ht_used;
366 minsize = minitems * 3 / 2; /* array is up to 2/3 full */
367 }
368
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000369 newsize = HT_INIT_SIZE;
370 while (newsize < minsize)
371 {
372 newsize <<= 1; /* make sure it's always a power of 2 */
373 if (newsize == 0)
374 return FAIL; /* overflow */
375 }
376
377 if (newsize == HT_INIT_SIZE)
378 {
379 /* Use the small array inside the hashdict structure. */
380 newarray = ht->ht_smallarray;
381 if (ht->ht_array == newarray)
382 {
383 /* Moving from ht_smallarray to ht_smallarray! Happens when there
384 * are many removed items. Copy the items to be able to clean up
385 * removed items. */
386 mch_memmove(temparray, newarray, sizeof(temparray));
387 oldarray = temparray;
388 }
389 else
390 oldarray = ht->ht_array;
391 }
392 else
393 {
394 /* Allocate an array. */
Bram Moolenaar677ee682005-01-27 14:41:15 +0000395 newarray = (hashitem_T *)alloc((unsigned)
396 (sizeof(hashitem_T) * newsize));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000397 if (newarray == NULL)
398 {
399 /* Out of memory. When there are NULL items still return OK.
400 * Otherwise set ht_error, because lookup may result in a hang if
401 * we add another item. */
402 if (ht->ht_filled < ht->ht_mask)
403 return OK;
404 ht->ht_error = TRUE;
405 return FAIL;
406 }
407 oldarray = ht->ht_array;
408 }
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000409 vim_memset(newarray, 0, (size_t)(sizeof(hashitem_T) * newsize));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000410
411 /*
412 * Move all the items from the old array to the new one, placing them in
413 * the right spot. The new array won't have any removed items, thus this
414 * is also a cleanup action.
415 */
416 newmask = newsize - 1;
417 todo = ht->ht_used;
418 for (olditem = oldarray; todo > 0; ++olditem)
Bram Moolenaar6ac54292005-02-02 23:07:25 +0000419 if (!HASHITEM_EMPTY(olditem))
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000420 {
421 /*
422 * The algorithm to find the spot to add the item is identical to
423 * the algorithm to find an item in hash_lookup(). But we only
424 * need to search for a NULL key, thus it's simpler.
425 */
426 newi = olditem->hi_hash & newmask;
427 newitem = &newarray[newi];
428
429 if (newitem->hi_key != NULL)
430 for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT)
431 {
432 newi = (newi << 2) + newi + perturb + 1;
433 newitem = &newarray[newi & newmask];
434 if (newitem->hi_key == NULL)
435 break;
436 }
437 *newitem = *olditem;
438 --todo;
439 }
440
441 if (ht->ht_array != ht->ht_smallarray)
442 vim_free(ht->ht_array);
443 ht->ht_array = newarray;
444 ht->ht_mask = newmask;
445 ht->ht_filled = ht->ht_used;
446 ht->ht_error = FALSE;
447
448 return OK;
449}
450
451/*
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000452 * Get the hash number for a key.
453 * If you think you know a better hash function: Compile with HT_DEBUG set and
454 * run a script that uses hashtables a lot. Vim will then print statistics
455 * when exiting. Try that with the current hash algorithm and yours. The
456 * lower the percentage the better.
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000457 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000458 hash_T
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000459hash_hash(key)
460 char_u *key;
461{
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000462 hash_T hash;
463 char_u *p;
464
465 if ((hash = *key) == 0)
466 return (hash_T)0; /* Empty keys are not allowed, but we don't
467 want to crash if we get one. */
468 p = key + 1;
469
470#if 0
471 /* ElfHash algorithm, which is supposed to have an even distribution.
472 * Suggested by Charles Campbell. */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000473 hash_T g;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000474
475 while (*p != NUL)
476 {
477 hash = (hash << 4) + *p++; /* clear low 4 bits of hash, add char */
478 g = hash & 0xf0000000L; /* g has high 4 bits of hash only */
479 if (g != 0)
480 hash ^= g >> 24; /* xor g's high 4 bits into hash */
481 }
Bram Moolenaar0e21a3f2005-04-17 20:28:32 +0000482#else
483
484 /* A simplistic algorithm that appears to do very well.
485 * Suggested by George Reilly. */
486 while (*p != NUL)
487 hash = hash * 101 + *p++;
488#endif
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000489
490 return hash;
491}
492
493#endif