| /* vi:set ts=8 sts=4 sw=4: |
| * |
| * VIM - Vi IMproved by Bram Moolenaar |
| * |
| * Do ":help uganda" in Vim to read copying and usage conditions. |
| * Do ":help credits" in Vim to see a list of people who contributed. |
| * See README.txt for an overview of the Vim source code. |
| */ |
| |
| /* |
| * hashtab.c: Handling of a hashtable with Vim-specific properties. |
| * |
| * Each item in a hashtable has a NUL terminated string key. A key can appear |
| * only once in the table. |
| * |
| * A hash number is computed from the key for quick lookup. When the hashes |
| * of two different keys point to the same entry an algorithm is used to |
| * iterate over other entries in the table until the right one is found. |
| * To make the iteration work removed keys are different from entries where a |
| * key was never present. |
| * |
| * The mechanism has been partly based on how Python Dictionaries are |
| * implemented. The algorithm is from Knuth Vol. 3, Sec. 6.4. |
| * |
| * The hashtable grows to accommodate more entries when needed. At least 1/3 |
| * of the entries is empty to keep the lookup efficient (at the cost of extra |
| * memory). |
| */ |
| |
| #include "vim.h" |
| |
| #if defined(FEAT_EVAL) || defined(FEAT_SYN_HL) || defined(PROTO) |
| |
| #if 0 |
| # define HT_DEBUG /* extra checks for table consistency and statistics */ |
| |
| static long hash_count_lookup = 0; /* count number of hashtab lookups */ |
| static long hash_count_perturb = 0; /* count number of "misses" */ |
| #endif |
| |
| /* Magic value for algorithm that walks through the array. */ |
| #define PERTURB_SHIFT 5 |
| |
| static int hash_may_resize __ARGS((hashtab_T *ht, int minitems)); |
| |
| #if 0 /* currently not used */ |
| /* |
| * Create an empty hash table. |
| * Returns NULL when out of memory. |
| */ |
| hashtab_T * |
| hash_create() |
| { |
| hashtab_T *ht; |
| |
| ht = (hashtab_T *)alloc(sizeof(hashtab_T)); |
| if (ht != NULL) |
| hash_init(ht); |
| return ht; |
| } |
| #endif |
| |
| /* |
| * Initialize an empty hash table. |
| */ |
| void |
| hash_init(ht) |
| hashtab_T *ht; |
| { |
| /* This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray". */ |
| vim_memset(ht, 0, sizeof(hashtab_T)); |
| ht->ht_array = ht->ht_smallarray; |
| ht->ht_mask = HT_INIT_SIZE - 1; |
| } |
| |
| /* |
| * Free the array of a hash table. Does not free the items it contains! |
| * If "ht" is not freed then you should call hash_init() next! |
| */ |
| void |
| hash_clear(ht) |
| hashtab_T *ht; |
| { |
| if (ht->ht_array != ht->ht_smallarray) |
| vim_free(ht->ht_array); |
| } |
| |
| /* |
| * Free the array of a hash table and all the keys it contains. The keys must |
| * have been allocated. "off" is the offset from the start of the allocate |
| * memory to the location of the key (it's always positive). |
| */ |
| void |
| hash_clear_all(ht, off) |
| hashtab_T *ht; |
| int off; |
| { |
| long todo; |
| hashitem_T *hi; |
| |
| todo = (long)ht->ht_used; |
| for (hi = ht->ht_array; todo > 0; ++hi) |
| { |
| if (!HASHITEM_EMPTY(hi)) |
| { |
| vim_free(hi->hi_key - off); |
| --todo; |
| } |
| } |
| hash_clear(ht); |
| } |
| |
| /* |
| * Find "key" in hashtable "ht". "key" must not be NULL. |
| * Always returns a pointer to a hashitem. If the item was not found then |
| * HASHITEM_EMPTY() is TRUE. The pointer is then the place where the key |
| * would be added. |
| * WARNING: The returned pointer becomes invalid when the hashtable is changed |
| * (adding, setting or removing an item)! |
| */ |
| hashitem_T * |
| hash_find(ht, key) |
| hashtab_T *ht; |
| char_u *key; |
| { |
| return hash_lookup(ht, key, hash_hash(key)); |
| } |
| |
| /* |
| * Like hash_find(), but caller computes "hash". |
| */ |
| hashitem_T * |
| hash_lookup(ht, key, hash) |
| hashtab_T *ht; |
| char_u *key; |
| hash_T hash; |
| { |
| hash_T perturb; |
| hashitem_T *freeitem; |
| hashitem_T *hi; |
| unsigned idx; |
| |
| #ifdef HT_DEBUG |
| ++hash_count_lookup; |
| #endif |
| |
| /* |
| * Quickly handle the most common situations: |
| * - return if there is no item at all |
| * - skip over a removed item |
| * - return if the item matches |
| */ |
| idx = (unsigned)(hash & ht->ht_mask); |
| hi = &ht->ht_array[idx]; |
| |
| if (hi->hi_key == NULL) |
| return hi; |
| if (hi->hi_key == HI_KEY_REMOVED) |
| freeitem = hi; |
| else if (hi->hi_hash == hash && STRCMP(hi->hi_key, key) == 0) |
| return hi; |
| else |
| freeitem = NULL; |
| |
| /* |
| * Need to search through the table to find the key. The algorithm |
| * to step through the table starts with large steps, gradually becoming |
| * smaller down to (1/4 table size + 1). This means it goes through all |
| * table entries in the end. |
| * When we run into a NULL key it's clear that the key isn't there. |
| * Return the first available slot found (can be a slot of a removed |
| * item). |
| */ |
| for (perturb = hash; ; perturb >>= PERTURB_SHIFT) |
| { |
| #ifdef HT_DEBUG |
| ++hash_count_perturb; /* count a "miss" for hashtab lookup */ |
| #endif |
| idx = (unsigned)((idx << 2U) + idx + perturb + 1U); |
| hi = &ht->ht_array[idx & ht->ht_mask]; |
| if (hi->hi_key == NULL) |
| return freeitem == NULL ? hi : freeitem; |
| if (hi->hi_hash == hash |
| && hi->hi_key != HI_KEY_REMOVED |
| && STRCMP(hi->hi_key, key) == 0) |
| return hi; |
| if (hi->hi_key == HI_KEY_REMOVED && freeitem == NULL) |
| freeitem = hi; |
| } |
| } |
| |
| /* |
| * Print the efficiency of hashtable lookups. |
| * Useful when trying different hash algorithms. |
| * Called when exiting. |
| */ |
| void |
| hash_debug_results() |
| { |
| #ifdef HT_DEBUG |
| fprintf(stderr, "\r\n\r\n\r\n\r\n"); |
| fprintf(stderr, "Number of hashtable lookups: %ld\r\n", hash_count_lookup); |
| fprintf(stderr, "Number of perturb loops: %ld\r\n", hash_count_perturb); |
| fprintf(stderr, "Percentage of perturb loops: %ld%%\r\n", |
| hash_count_perturb * 100 / hash_count_lookup); |
| #endif |
| } |
| |
| /* |
| * Add item with key "key" to hashtable "ht". |
| * Returns FAIL when out of memory or the key is already present. |
| */ |
| int |
| hash_add(ht, key) |
| hashtab_T *ht; |
| char_u *key; |
| { |
| hash_T hash = hash_hash(key); |
| hashitem_T *hi; |
| |
| hi = hash_lookup(ht, key, hash); |
| if (!HASHITEM_EMPTY(hi)) |
| { |
| EMSG2(_(e_intern2), "hash_add()"); |
| return FAIL; |
| } |
| return hash_add_item(ht, hi, key, hash); |
| } |
| |
| /* |
| * Add item "hi" with "key" to hashtable "ht". "key" must not be NULL and |
| * "hi" must have been obtained with hash_lookup() and point to an empty item. |
| * "hi" is invalid after this! |
| * Returns OK or FAIL (out of memory). |
| */ |
| int |
| hash_add_item(ht, hi, key, hash) |
| hashtab_T *ht; |
| hashitem_T *hi; |
| char_u *key; |
| hash_T hash; |
| { |
| /* If resizing failed before and it fails again we can't add an item. */ |
| if (ht->ht_error && hash_may_resize(ht, 0) == FAIL) |
| return FAIL; |
| |
| ++ht->ht_used; |
| if (hi->hi_key == NULL) |
| ++ht->ht_filled; |
| hi->hi_key = key; |
| hi->hi_hash = hash; |
| |
| /* When the space gets low may resize the array. */ |
| return hash_may_resize(ht, 0); |
| } |
| |
| #if 0 /* not used */ |
| /* |
| * Overwrite hashtable item "hi" with "key". "hi" must point to the item that |
| * is to be overwritten. Thus the number of items in the hashtable doesn't |
| * change. |
| * Although the key must be identical, the pointer may be different, thus it's |
| * set anyway (the key is part of an item with that key). |
| * The caller must take care of freeing the old item. |
| * "hi" is invalid after this! |
| */ |
| void |
| hash_set(hi, key) |
| hashitem_T *hi; |
| char_u *key; |
| { |
| hi->hi_key = key; |
| } |
| #endif |
| |
| /* |
| * Remove item "hi" from hashtable "ht". "hi" must have been obtained with |
| * hash_lookup(). |
| * The caller must take care of freeing the item itself. |
| */ |
| void |
| hash_remove(ht, hi) |
| hashtab_T *ht; |
| hashitem_T *hi; |
| { |
| --ht->ht_used; |
| hi->hi_key = HI_KEY_REMOVED; |
| hash_may_resize(ht, 0); |
| } |
| |
| /* |
| * Lock a hashtable: prevent that ht_array changes. |
| * Don't use this when items are to be added! |
| * Must call hash_unlock() later. |
| */ |
| void |
| hash_lock(ht) |
| hashtab_T *ht; |
| { |
| ++ht->ht_locked; |
| } |
| |
| #if 0 /* currently not used */ |
| /* |
| * Lock a hashtable at the specified number of entries. |
| * Caller must make sure no more than "size" entries will be added. |
| * Must call hash_unlock() later. |
| */ |
| void |
| hash_lock_size(ht, size) |
| hashtab_T *ht; |
| int size; |
| { |
| (void)hash_may_resize(ht, size); |
| ++ht->ht_locked; |
| } |
| #endif |
| |
| /* |
| * Unlock a hashtable: allow ht_array changes again. |
| * Table will be resized (shrink) when necessary. |
| * This must balance a call to hash_lock(). |
| */ |
| void |
| hash_unlock(ht) |
| hashtab_T *ht; |
| { |
| --ht->ht_locked; |
| (void)hash_may_resize(ht, 0); |
| } |
| |
| /* |
| * Shrink a hashtable when there is too much empty space. |
| * Grow a hashtable when there is not enough empty space. |
| * Returns OK or FAIL (out of memory). |
| */ |
| static int |
| hash_may_resize(ht, minitems) |
| hashtab_T *ht; |
| int minitems; /* minimal number of items */ |
| { |
| hashitem_T temparray[HT_INIT_SIZE]; |
| hashitem_T *oldarray, *newarray; |
| hashitem_T *olditem, *newitem; |
| unsigned newi; |
| int todo; |
| long_u oldsize, newsize; |
| long_u minsize; |
| long_u newmask; |
| hash_T perturb; |
| |
| /* Don't resize a locked table. */ |
| if (ht->ht_locked > 0) |
| return OK; |
| |
| #ifdef HT_DEBUG |
| if (ht->ht_used > ht->ht_filled) |
| EMSG("hash_may_resize(): more used than filled"); |
| if (ht->ht_filled >= ht->ht_mask + 1) |
| EMSG("hash_may_resize(): table completely filled"); |
| #endif |
| |
| if (minitems == 0) |
| { |
| /* Return quickly for small tables with at least two NULL items. NULL |
| * items are required for the lookup to decide a key isn't there. */ |
| if (ht->ht_filled < HT_INIT_SIZE - 1 |
| && ht->ht_array == ht->ht_smallarray) |
| return OK; |
| |
| /* |
| * Grow or refill the array when it's more than 2/3 full (including |
| * removed items, so that they get cleaned up). |
| * Shrink the array when it's less than 1/5 full. When growing it is |
| * at least 1/4 full (avoids repeated grow-shrink operations) |
| */ |
| oldsize = ht->ht_mask + 1; |
| if (ht->ht_filled * 3 < oldsize * 2 && ht->ht_used > oldsize / 5) |
| return OK; |
| |
| if (ht->ht_used > 1000) |
| minsize = ht->ht_used * 2; /* it's big, don't make too much room */ |
| else |
| minsize = ht->ht_used * 4; /* make plenty of room */ |
| } |
| else |
| { |
| /* Use specified size. */ |
| if ((long_u)minitems < ht->ht_used) /* just in case... */ |
| minitems = (int)ht->ht_used; |
| minsize = minitems * 3 / 2; /* array is up to 2/3 full */ |
| } |
| |
| newsize = HT_INIT_SIZE; |
| while (newsize < minsize) |
| { |
| newsize <<= 1; /* make sure it's always a power of 2 */ |
| if (newsize == 0) |
| return FAIL; /* overflow */ |
| } |
| |
| if (newsize == HT_INIT_SIZE) |
| { |
| /* Use the small array inside the hashdict structure. */ |
| newarray = ht->ht_smallarray; |
| if (ht->ht_array == newarray) |
| { |
| /* Moving from ht_smallarray to ht_smallarray! Happens when there |
| * are many removed items. Copy the items to be able to clean up |
| * removed items. */ |
| mch_memmove(temparray, newarray, sizeof(temparray)); |
| oldarray = temparray; |
| } |
| else |
| oldarray = ht->ht_array; |
| } |
| else |
| { |
| /* Allocate an array. */ |
| newarray = (hashitem_T *)alloc((unsigned) |
| (sizeof(hashitem_T) * newsize)); |
| if (newarray == NULL) |
| { |
| /* Out of memory. When there are NULL items still return OK. |
| * Otherwise set ht_error, because lookup may result in a hang if |
| * we add another item. */ |
| if (ht->ht_filled < ht->ht_mask) |
| return OK; |
| ht->ht_error = TRUE; |
| return FAIL; |
| } |
| oldarray = ht->ht_array; |
| } |
| vim_memset(newarray, 0, (size_t)(sizeof(hashitem_T) * newsize)); |
| |
| /* |
| * Move all the items from the old array to the new one, placing them in |
| * the right spot. The new array won't have any removed items, thus this |
| * is also a cleanup action. |
| */ |
| newmask = newsize - 1; |
| todo = (int)ht->ht_used; |
| for (olditem = oldarray; todo > 0; ++olditem) |
| if (!HASHITEM_EMPTY(olditem)) |
| { |
| /* |
| * The algorithm to find the spot to add the item is identical to |
| * the algorithm to find an item in hash_lookup(). But we only |
| * need to search for a NULL key, thus it's simpler. |
| */ |
| newi = (unsigned)(olditem->hi_hash & newmask); |
| newitem = &newarray[newi]; |
| |
| if (newitem->hi_key != NULL) |
| for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT) |
| { |
| newi = (unsigned)((newi << 2U) + newi + perturb + 1U); |
| newitem = &newarray[newi & newmask]; |
| if (newitem->hi_key == NULL) |
| break; |
| } |
| *newitem = *olditem; |
| --todo; |
| } |
| |
| if (ht->ht_array != ht->ht_smallarray) |
| vim_free(ht->ht_array); |
| ht->ht_array = newarray; |
| ht->ht_mask = newmask; |
| ht->ht_filled = ht->ht_used; |
| ht->ht_error = FALSE; |
| |
| return OK; |
| } |
| |
| /* |
| * Get the hash number for a key. |
| * If you think you know a better hash function: Compile with HT_DEBUG set and |
| * run a script that uses hashtables a lot. Vim will then print statistics |
| * when exiting. Try that with the current hash algorithm and yours. The |
| * lower the percentage the better. |
| */ |
| hash_T |
| hash_hash(key) |
| char_u *key; |
| { |
| hash_T hash; |
| char_u *p; |
| |
| if ((hash = *key) == 0) |
| return (hash_T)0; /* Empty keys are not allowed, but we don't |
| want to crash if we get one. */ |
| p = key + 1; |
| |
| /* A simplistic algorithm that appears to do very well. |
| * Suggested by George Reilly. */ |
| while (*p != NUL) |
| hash = hash * 101 + *p++; |
| |
| return hash; |
| } |
| |
| #endif |