ref: 43bfd7255c75836a4956c698fc28e378135867bc
dir: /hashtab.c/
/* 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;
int 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 = (int)(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 = (int)((idx << 2) + idx + perturb + 1);
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;
int 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 = (int)(olditem->hi_hash & newmask);
newitem = &newarray[newi];
if (newitem->hi_key != NULL)
for (perturb = olditem->hi_hash; ; perturb >>= PERTURB_SHIFT)
{
newi = (int)((newi << 2) + newi + perturb + 1);
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;
#if 0
/* ElfHash algorithm, which is supposed to have an even distribution.
* Suggested by Charles Campbell. */
hash_T g;
while (*p != NUL)
{
hash = (hash << 4) + *p++; /* clear low 4 bits of hash, add char */
g = hash & 0xf0000000L; /* g has high 4 bits of hash only */
if (g != 0)
hash ^= g >> 24; /* xor g's high 4 bits into hash */
}
#else
/* A simplistic algorithm that appears to do very well.
* Suggested by George Reilly. */
while (*p != NUL)
hash = hash * 101 + *p++;
#endif
return hash;
}
#endif