blob: 0263f6f73fc85f2d2d8c447883014d5aa198c871 [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 Moolenaar6abd8e92005-01-19 22:21:15 +000035# define HT_DEBUG /* extra checks for table consistency */
36#endif
37
38/* Magic value for algorithm that walks through the array. */
39#define PERTURB_SHIFT 5
40
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +000041static int hash_may_resize __ARGS((hashtab_T *ht, int minitems));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000042
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +000043#if defined(FEAT_SYN_HL) || defined(PROTO)
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000044/*
45 * Create an empty hash table.
46 * Returns NULL when out of memory.
47 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +000048 hashtab_T *
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000049hash_create()
50{
Bram Moolenaar7df2d662005-01-25 22:18:08 +000051 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000052
Bram Moolenaar7df2d662005-01-25 22:18:08 +000053 ht = (hashtab_T *)alloc(sizeof(hashtab_T));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000054 if (ht != NULL)
55 hash_init(ht);
56 return ht;
57}
58#endif
59
60/*
61 * Initialize an empty hash table.
62 */
63 void
64hash_init(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +000065 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000066{
67 /* This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". */
Bram Moolenaar7df2d662005-01-25 22:18:08 +000068 vim_memset(ht, 0, sizeof(hashtab_T));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000069 ht->ht_array = ht->ht_smallarray;
70 ht->ht_mask = HT_INIT_SIZE - 1;
71}
72
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000073/*
Bram Moolenaardcaf10e2005-01-21 11:55:25 +000074 * Free the array of a hash table. Does not free the items it contains!
75 * If "ht" is not freed then you should call hash_init() next!
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000076 */
77 void
Bram Moolenaardcaf10e2005-01-21 11:55:25 +000078hash_clear(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +000079 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000080{
81 if (ht->ht_array != ht->ht_smallarray)
82 vim_free(ht->ht_array);
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000083}
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000084
85/*
86 * Find "key" in hashtable "ht". "key" must not be NULL.
87 * Always returns a pointer to a hashitem. If the item was not found then
88 * HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key
89 * would be added.
90 * WARNING: The returned pointer becomes invalid when the hashtable is changed
91 * (adding, setting or removing an item)!
92 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +000093 hashitem_T *
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000094hash_find(ht, key)
Bram Moolenaar7df2d662005-01-25 22:18:08 +000095 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +000096 char_u *key;
97{
98 return hash_lookup(ht, key, hash_hash(key));
99}
100
101/*
102 * Like hash_find(), but caller computes "hash".
103 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000104 hashitem_T *
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000105hash_lookup(ht, key, hash)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000106 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000107 char_u *key;
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000108 hash_T hash;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000109{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000110 hash_T perturb;
111 hashitem_T *freeitem;
112 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000113 int idx;
114
115 /*
116 * Quickly handle the most common situations:
117 * - return if there is no item at all
118 * - skip over a removed item
119 * - return if the item matches
120 */
121 idx = hash & ht->ht_mask;
122 hi = &ht->ht_array[idx];
123
124 if (hi->hi_key == NULL)
125 return hi;
126 if (hi->hi_key == HI_KEY_REMOVED)
127 freeitem = hi;
128 else if (hi->hi_hash == hash && STRCMP(hi->hi_key, key) == 0)
129 return hi;
130 else
131 freeitem = NULL;
132
133 /*
134 * Need to search through the table to find the key. The algorithm
135 * to step through the table starts with large steps, gradually becoming
136 * smaller down to (1/4 table size + 1). This means it goes through all
137 * table entries in the end.
138 * When we run into a NULL key it's clear that the key isn't there.
139 * Return the first available slot found (can be a slot of a removed
140 * item).
141 */
142 for (perturb = hash; ; perturb >>= PERTURB_SHIFT)
143 {
144 idx = (idx << 2) + idx + perturb + 1;
145 hi = &ht->ht_array[idx & ht->ht_mask];
146 if (hi->hi_key == NULL)
147 return freeitem == NULL ? hi : freeitem;
148 if (hi->hi_hash == hash
149 && hi->hi_key != HI_KEY_REMOVED
150 && STRCMP(hi->hi_key, key) == 0)
151 return hi;
152 if (hi->hi_key == HI_KEY_REMOVED && freeitem == NULL)
153 freeitem = hi;
154 }
155}
156
157/*
158 * Add item with key "key" to hashtable "ht".
159 * Returns FAIL when out of memory or the key is already present.
160 */
161 int
162hash_add(ht, key)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000163 hashtab_T *ht;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000164 char_u *key;
165{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000166 hash_T hash = hash_hash(key);
167 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000168
169 hi = hash_lookup(ht, key, hash);
170 if (!HASHITEM_EMPTY(hi))
171 {
172 EMSG2(_(e_intern2), "hash_add()");
173 return FAIL;
174 }
175 return hash_add_item(ht, hi, key, hash);
176}
177
178/*
179 * Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and
180 * "hi" must have been obtained with hash_lookup() and point to an empty item.
181 * "hi" is invalid after this!
182 * Returns OK or FAIL (out of memory).
183 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000184 int
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000185hash_add_item(ht, hi, key, hash)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000186 hashtab_T *ht;
187 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000188 char_u *key;
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000189 hash_T hash;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000190{
191 /* If resizing failed before and it fails again we can't add an item. */
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000192 if (ht->ht_error && hash_may_resize(ht, 0) == FAIL)
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000193 return FAIL;
194
195 ++ht->ht_used;
196 if (hi->hi_key == NULL)
197 ++ht->ht_filled;
198 hi->hi_key = key;
199 hi->hi_hash = hash;
200
201 /* When the space gets low may resize the array. */
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000202 return hash_may_resize(ht, 0);
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000203}
204
205#if 0 /* not used */
206/*
207 * Overwrite hashtable item "hi" with "key". "hi" must point to the item that
208 * is to be overwritten. Thus the number of items in the hashtable doesn't
209 * change.
210 * Although the key must be identical, the pointer may be different, thus it's
211 * set anyway (the key is part of an item with that key).
212 * The caller must take care of freeing the old item.
213 * "hi" is invalid after this!
214 */
215 void
216hash_set(hi, key)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000217 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000218 char_u *key;
219{
220 hi->hi_key = key;
221}
222#endif
223
224/*
225 * Remove item "hi" from hashtable "ht". "hi" must have been obtained with
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000226 * hash_lookup() and point to an empty item.
227 * The caller must take care of freeing the item itself.
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000228 */
229 void
230hash_remove(ht, hi)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000231 hashtab_T *ht;
232 hashitem_T *hi;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000233{
234 --ht->ht_used;
235 hi->hi_key = HI_KEY_REMOVED;
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000236 hash_may_resize(ht, 0);
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000237}
238
239/*
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000240 * Lock a hashtable: prevent that ht_array changes.
241 * Don't use this when items are to be added!
242 * Must call hash_unlock() later.
243 */
244 void
245hash_lock(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000246 hashtab_T *ht;
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000247{
248 ++ht->ht_locked;
249}
250
251/*
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000252 * Lock a hashtable at the specified number of entries.
253 * Caller must make sure no more than "size" entries will be added.
254 * Must call hash_unlock() later.
255 */
256 void
257hash_lock_size(ht, size)
258 hashtab_T *ht;
259 int size;
260{
261 (void)hash_may_resize(ht, size);
262 ++ht->ht_locked;
263}
264
265/*
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000266 * Unlock a hashtable: allow ht_array changes again.
267 * Table will be resized (shrink) when necessary.
268 * This must balance a call to hash_lock().
269 */
270 void
271hash_unlock(ht)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000272 hashtab_T *ht;
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000273{
274 --ht->ht_locked;
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000275 (void)hash_may_resize(ht, 0);
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000276}
277
278/*
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000279 * Shrink a hashtable when there is too much empty space.
280 * Grow a hashtable when there is not enough empty space.
281 * Returns OK or FAIL (out of memory).
282 */
283 static int
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000284hash_may_resize(ht, minitems)
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000285 hashtab_T *ht;
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000286 int minitems; /* minimal number of items */
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000287{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000288 hashitem_T temparray[HT_INIT_SIZE];
289 hashitem_T *oldarray, *newarray;
290 hashitem_T *olditem, *newitem;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000291 int newi;
292 int todo;
293 long_u oldsize, newsize;
294 long_u minsize;
295 long_u newmask;
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000296 hash_T perturb;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000297
Bram Moolenaardcaf10e2005-01-21 11:55:25 +0000298 /* Don't resize a locked table. */
299 if (ht->ht_locked > 0)
300 return OK;
301
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000302#ifdef HT_DEBUG
303 if (ht->ht_used > ht->ht_filled)
304 EMSG("hash_may_resize(): more used than filled");
305 if (ht->ht_filled >= ht->ht_mask + 1)
306 EMSG("hash_may_resize(): table completely filled");
307#endif
308
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000309 if (minitems == 0)
310 {
311 /* Return quickly for small tables with at least two NULL items. NULL
312 * items are required for the lookup to decide a key isn't there. */
313 if (ht->ht_filled < HT_INIT_SIZE - 1
314 && ht->ht_array == ht->ht_smallarray)
315 return OK;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000316
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000317 /*
318 * Grow or refill the array when it's more than 2/3 full (including
319 * removed items, so that they get cleaned up).
320 * Shrink the array when it's less than 1/5 full. When growing it is
321 * at least 1/4 full (avoids repeated grow-shrink operations)
322 */
323 oldsize = ht->ht_mask + 1;
324 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5)
325 return OK;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000326
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000327 if (ht->ht_used > 1000)
328 minsize = ht->ht_used * 2; /* it's big, don't make too much room */
329 else
330 minsize = ht->ht_used * 4; /* make plenty of room */
331 }
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000332 else
Bram Moolenaar13fcaaf2005-04-15 21:13:42 +0000333 {
334 /* Use specified size. */
335 if (minitems < ht->ht_used) /* just in case... */
336 minitems = ht->ht_used;
337 minsize = minitems * 3 / 2; /* array is up to 2/3 full */
338 }
339
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000340 newsize = HT_INIT_SIZE;
341 while (newsize < minsize)
342 {
343 newsize <<= 1; /* make sure it's always a power of 2 */
344 if (newsize == 0)
345 return FAIL; /* overflow */
346 }
347
348 if (newsize == HT_INIT_SIZE)
349 {
350 /* Use the small array inside the hashdict structure. */
351 newarray = ht->ht_smallarray;
352 if (ht->ht_array == newarray)
353 {
354 /* Moving from ht_smallarray to ht_smallarray! Happens when there
355 * are many removed items. Copy the items to be able to clean up
356 * removed items. */
357 mch_memmove(temparray, newarray, sizeof(temparray));
358 oldarray = temparray;
359 }
360 else
361 oldarray = ht->ht_array;
362 }
363 else
364 {
365 /* Allocate an array. */
Bram Moolenaar677ee682005-01-27 14:41:15 +0000366 newarray = (hashitem_T *)alloc((unsigned)
367 (sizeof(hashitem_T) * newsize));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000368 if (newarray == NULL)
369 {
370 /* Out of memory. When there are NULL items still return OK.
371 * Otherwise set ht_error, because lookup may result in a hang if
372 * we add another item. */
373 if (ht->ht_filled < ht->ht_mask)
374 return OK;
375 ht->ht_error = TRUE;
376 return FAIL;
377 }
378 oldarray = ht->ht_array;
379 }
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000380 vim_memset(newarray, 0, (size_t)(sizeof(hashitem_T) * newsize));
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000381
382 /*
383 * Move all the items from the old array to the new one, placing them in
384 * the right spot. The new array won't have any removed items, thus this
385 * is also a cleanup action.
386 */
387 newmask = newsize - 1;
388 todo = ht->ht_used;
389 for (olditem = oldarray; todo > 0; ++olditem)
Bram Moolenaar6ac54292005-02-02 23:07:25 +0000390 if (!HASHITEM_EMPTY(olditem))
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000391 {
392 /*
393 * The algorithm to find the spot to add the item is identical to
394 * the algorithm to find an item in hash_lookup(). But we only
395 * need to search for a NULL key, thus it's simpler.
396 */
397 newi = olditem->hi_hash & newmask;
398 newitem = &newarray[newi];
399
400 if (newitem->hi_key != NULL)
401 for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT)
402 {
403 newi = (newi << 2) + newi + perturb + 1;
404 newitem = &newarray[newi & newmask];
405 if (newitem->hi_key == NULL)
406 break;
407 }
408 *newitem = *olditem;
409 --todo;
410 }
411
412 if (ht->ht_array != ht->ht_smallarray)
413 vim_free(ht->ht_array);
414 ht->ht_array = newarray;
415 ht->ht_mask = newmask;
416 ht->ht_filled = ht->ht_used;
417 ht->ht_error = FALSE;
418
419 return OK;
420}
421
422/*
423 * Get the hash number for a key. Uses the ElfHash algorithm, which is
424 * supposed to have an even distribution (suggested by Charles Campbell).
425 */
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000426 hash_T
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000427hash_hash(key)
428 char_u *key;
429{
Bram Moolenaar7df2d662005-01-25 22:18:08 +0000430 hash_T hash = 0;
431 hash_T g;
Bram Moolenaar6abd8e92005-01-19 22:21:15 +0000432 char_u *p = key;
433
434 while (*p != NUL)
435 {
436 hash = (hash << 4) + *p++; /* clear low 4 bits of hash, add char */
437 g = hash & 0xf0000000L; /* g has high 4 bits of hash only */
438 if (g != 0)
439 hash ^= g >> 24; /* xor g's high 4 bits into hash */
440 }
441
442 return hash;
443}
444
445#endif