|
120
|
1 /* 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
|
|
154
|
34 #if 0
|
|
120
|
35 # 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
|
|
135
|
41 static int hash_may_resize __ARGS((hashtab_T *ht));
|
|
120
|
42
|
|
|
43 #if 0 /* not used */
|
|
|
44 /*
|
|
|
45 * Create an empty hash table.
|
|
|
46 * Returns NULL when out of memory.
|
|
|
47 */
|
|
135
|
48 hashtab_T *
|
|
120
|
49 hash_create()
|
|
|
50 {
|
|
135
|
51 hashtab_T *ht;
|
|
120
|
52
|
|
135
|
53 ht = (hashtab_T *)alloc(sizeof(hashtab_T));
|
|
120
|
54 if (ht != NULL)
|
|
|
55 hash_init(ht);
|
|
|
56 return ht;
|
|
|
57 }
|
|
|
58 #endif
|
|
|
59
|
|
|
60 /*
|
|
|
61 * Initialize an empty hash table.
|
|
|
62 */
|
|
|
63 void
|
|
|
64 hash_init(ht)
|
|
135
|
65 hashtab_T *ht;
|
|
120
|
66 {
|
|
|
67 /* This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". */
|
|
135
|
68 vim_memset(ht, 0, sizeof(hashtab_T));
|
|
120
|
69 ht->ht_array = ht->ht_smallarray;
|
|
|
70 ht->ht_mask = HT_INIT_SIZE - 1;
|
|
|
71 }
|
|
|
72
|
|
|
73 /*
|
|
123
|
74 * 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!
|
|
120
|
76 */
|
|
|
77 void
|
|
123
|
78 hash_clear(ht)
|
|
135
|
79 hashtab_T *ht;
|
|
120
|
80 {
|
|
|
81 if (ht->ht_array != ht->ht_smallarray)
|
|
|
82 vim_free(ht->ht_array);
|
|
|
83 }
|
|
|
84
|
|
|
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 */
|
|
135
|
93 hashitem_T *
|
|
120
|
94 hash_find(ht, key)
|
|
135
|
95 hashtab_T *ht;
|
|
120
|
96 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 */
|
|
135
|
104 hashitem_T *
|
|
120
|
105 hash_lookup(ht, key, hash)
|
|
135
|
106 hashtab_T *ht;
|
|
120
|
107 char_u *key;
|
|
135
|
108 hash_T hash;
|
|
120
|
109 {
|
|
135
|
110 hash_T perturb;
|
|
|
111 hashitem_T *freeitem;
|
|
|
112 hashitem_T *hi;
|
|
120
|
113 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
|
|
|
162 hash_add(ht, key)
|
|
135
|
163 hashtab_T *ht;
|
|
120
|
164 char_u *key;
|
|
|
165 {
|
|
135
|
166 hash_T hash = hash_hash(key);
|
|
|
167 hashitem_T *hi;
|
|
120
|
168
|
|
|
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 */
|
|
135
|
184 int
|
|
120
|
185 hash_add_item(ht, hi, key, hash)
|
|
135
|
186 hashtab_T *ht;
|
|
|
187 hashitem_T *hi;
|
|
120
|
188 char_u *key;
|
|
135
|
189 hash_T hash;
|
|
120
|
190 {
|
|
|
191 /* If resizing failed before and it fails again we can't add an item. */
|
|
|
192 if (ht->ht_error && hash_may_resize(ht) == FAIL)
|
|
|
193 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. */
|
|
|
202 return hash_may_resize(ht);
|
|
|
203 }
|
|
|
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
|
|
|
216 hash_set(hi, key)
|
|
135
|
217 hashitem_T *hi;
|
|
120
|
218 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
|
|
123
|
226 * hash_lookup() and point to an empty item.
|
|
|
227 * The caller must take care of freeing the item itself.
|
|
120
|
228 */
|
|
|
229 void
|
|
|
230 hash_remove(ht, hi)
|
|
135
|
231 hashtab_T *ht;
|
|
|
232 hashitem_T *hi;
|
|
120
|
233 {
|
|
|
234 --ht->ht_used;
|
|
|
235 hi->hi_key = HI_KEY_REMOVED;
|
|
|
236 hash_may_resize(ht);
|
|
|
237 }
|
|
|
238
|
|
|
239 /*
|
|
123
|
240 * 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
|
|
|
245 hash_lock(ht)
|
|
135
|
246 hashtab_T *ht;
|
|
123
|
247 {
|
|
|
248 ++ht->ht_locked;
|
|
|
249 }
|
|
|
250
|
|
|
251 /*
|
|
|
252 * Unlock a hashtable: allow ht_array changes again.
|
|
|
253 * Table will be resized (shrink) when necessary.
|
|
|
254 * This must balance a call to hash_lock().
|
|
|
255 */
|
|
|
256 void
|
|
|
257 hash_unlock(ht)
|
|
135
|
258 hashtab_T *ht;
|
|
123
|
259 {
|
|
|
260 --ht->ht_locked;
|
|
|
261 (void)hash_may_resize(ht);
|
|
|
262 }
|
|
|
263
|
|
|
264 /*
|
|
120
|
265 * Shrink a hashtable when there is too much empty space.
|
|
|
266 * Grow a hashtable when there is not enough empty space.
|
|
|
267 * Returns OK or FAIL (out of memory).
|
|
|
268 */
|
|
|
269 static int
|
|
|
270 hash_may_resize(ht)
|
|
135
|
271 hashtab_T *ht;
|
|
120
|
272 {
|
|
135
|
273 hashitem_T temparray[HT_INIT_SIZE];
|
|
|
274 hashitem_T *oldarray, *newarray;
|
|
|
275 hashitem_T *olditem, *newitem;
|
|
120
|
276 int newi;
|
|
|
277 int todo;
|
|
|
278 long_u oldsize, newsize;
|
|
|
279 long_u minsize;
|
|
|
280 long_u newmask;
|
|
135
|
281 hash_T perturb;
|
|
120
|
282
|
|
123
|
283 /* Don't resize a locked table. */
|
|
|
284 if (ht->ht_locked > 0)
|
|
|
285 return OK;
|
|
|
286
|
|
120
|
287 #ifdef HT_DEBUG
|
|
|
288 if (ht->ht_used > ht->ht_filled)
|
|
|
289 EMSG("hash_may_resize(): more used than filled");
|
|
|
290 if (ht->ht_filled >= ht->ht_mask + 1)
|
|
|
291 EMSG("hash_may_resize(): table completely filled");
|
|
|
292 #endif
|
|
|
293
|
|
|
294 /* Return quickly for small tables with at least two NULL items. NULL
|
|
|
295 * items are required for the lookup to decide a key isn't there. */
|
|
|
296 if (ht->ht_filled < HT_INIT_SIZE - 1 && ht->ht_array == ht->ht_smallarray)
|
|
|
297 return OK;
|
|
|
298
|
|
|
299 /*
|
|
|
300 * Grow or refill the array when it's more than 2/3 full (including
|
|
|
301 * removed items, so that they get cleaned up).
|
|
|
302 * Shrink the array when it's less than 1/5 full. When growing it is at
|
|
|
303 * least 1/4 full (avoids repeated grow-shrink operations)
|
|
|
304 */
|
|
|
305 oldsize = ht->ht_mask + 1;
|
|
|
306 if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5)
|
|
|
307 return OK;
|
|
|
308
|
|
123
|
309 if (ht->ht_used > 1000)
|
|
120
|
310 minsize = ht->ht_used * 2; /* it's big, don't make too much room */
|
|
|
311 else
|
|
|
312 minsize = ht->ht_used * 4; /* make plenty of room */
|
|
|
313 newsize = HT_INIT_SIZE;
|
|
|
314 while (newsize < minsize)
|
|
|
315 {
|
|
|
316 newsize <<= 1; /* make sure it's always a power of 2 */
|
|
|
317 if (newsize == 0)
|
|
|
318 return FAIL; /* overflow */
|
|
|
319 }
|
|
|
320
|
|
|
321 if (newsize == HT_INIT_SIZE)
|
|
|
322 {
|
|
|
323 /* Use the small array inside the hashdict structure. */
|
|
|
324 newarray = ht->ht_smallarray;
|
|
|
325 if (ht->ht_array == newarray)
|
|
|
326 {
|
|
|
327 /* Moving from ht_smallarray to ht_smallarray! Happens when there
|
|
|
328 * are many removed items. Copy the items to be able to clean up
|
|
|
329 * removed items. */
|
|
|
330 mch_memmove(temparray, newarray, sizeof(temparray));
|
|
|
331 oldarray = temparray;
|
|
|
332 }
|
|
|
333 else
|
|
|
334 oldarray = ht->ht_array;
|
|
|
335 }
|
|
|
336 else
|
|
|
337 {
|
|
|
338 /* Allocate an array. */
|
|
140
|
339 newarray = (hashitem_T *)alloc((unsigned)
|
|
|
340 (sizeof(hashitem_T) * newsize));
|
|
120
|
341 if (newarray == NULL)
|
|
|
342 {
|
|
|
343 /* Out of memory. When there are NULL items still return OK.
|
|
|
344 * Otherwise set ht_error, because lookup may result in a hang if
|
|
|
345 * we add another item. */
|
|
|
346 if (ht->ht_filled < ht->ht_mask)
|
|
|
347 return OK;
|
|
|
348 ht->ht_error = TRUE;
|
|
|
349 return FAIL;
|
|
|
350 }
|
|
|
351 oldarray = ht->ht_array;
|
|
|
352 }
|
|
135
|
353 vim_memset(newarray, 0, (size_t)(sizeof(hashitem_T) * newsize));
|
|
120
|
354
|
|
|
355 /*
|
|
|
356 * Move all the items from the old array to the new one, placing them in
|
|
|
357 * the right spot. The new array won't have any removed items, thus this
|
|
|
358 * is also a cleanup action.
|
|
|
359 */
|
|
|
360 newmask = newsize - 1;
|
|
|
361 todo = ht->ht_used;
|
|
|
362 for (olditem = oldarray; todo > 0; ++olditem)
|
|
154
|
363 if (!HASHITEM_EMPTY(olditem))
|
|
120
|
364 {
|
|
|
365 /*
|
|
|
366 * The algorithm to find the spot to add the item is identical to
|
|
|
367 * the algorithm to find an item in hash_lookup(). But we only
|
|
|
368 * need to search for a NULL key, thus it's simpler.
|
|
|
369 */
|
|
|
370 newi = olditem->hi_hash & newmask;
|
|
|
371 newitem = &newarray[newi];
|
|
|
372
|
|
|
373 if (newitem->hi_key != NULL)
|
|
|
374 for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT)
|
|
|
375 {
|
|
|
376 newi = (newi << 2) + newi + perturb + 1;
|
|
|
377 newitem = &newarray[newi & newmask];
|
|
|
378 if (newitem->hi_key == NULL)
|
|
|
379 break;
|
|
|
380 }
|
|
|
381 *newitem = *olditem;
|
|
|
382 --todo;
|
|
|
383 }
|
|
|
384
|
|
|
385 if (ht->ht_array != ht->ht_smallarray)
|
|
|
386 vim_free(ht->ht_array);
|
|
|
387 ht->ht_array = newarray;
|
|
|
388 ht->ht_mask = newmask;
|
|
|
389 ht->ht_filled = ht->ht_used;
|
|
|
390 ht->ht_error = FALSE;
|
|
|
391
|
|
|
392 return OK;
|
|
|
393 }
|
|
|
394
|
|
|
395 /*
|
|
|
396 * Get the hash number for a key. Uses the ElfHash algorithm, which is
|
|
|
397 * supposed to have an even distribution (suggested by Charles Campbell).
|
|
|
398 */
|
|
135
|
399 hash_T
|
|
120
|
400 hash_hash(key)
|
|
|
401 char_u *key;
|
|
|
402 {
|
|
135
|
403 hash_T hash = 0;
|
|
|
404 hash_T g;
|
|
120
|
405 char_u *p = key;
|
|
|
406
|
|
|
407 while (*p != NUL)
|
|
|
408 {
|
|
|
409 hash = (hash << 4) + *p++; /* clear low 4 bits of hash, add char */
|
|
|
410 g = hash & 0xf0000000L; /* g has high 4 bits of hash only */
|
|
|
411 if (g != 0)
|
|
|
412 hash ^= g >> 24; /* xor g's high 4 bits into hash */
|
|
|
413 }
|
|
|
414
|
|
|
415 return hash;
|
|
|
416 }
|
|
|
417
|
|
|
418 #endif
|
