summaryrefslogtreecommitdiffstats
path: root/src/hashtab.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/hashtab.c')
-rw-r--r--src/hashtab.c482
1 files changed, 482 insertions, 0 deletions
diff --git a/src/hashtab.c b/src/hashtab.c
new file mode 100644
index 0000000..dc0cbb6
--- /dev/null
+++ b/src/hashtab.c
@@ -0,0 +1,482 @@
+/* vi:set ts=8 sts=4 sw=4 noet:
+ *
+ * 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 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(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(void)
+{
+ hashtab_T *ht;
+
+ ht = ALLOC_ONE(hashtab_T);
+ if (ht != NULL)
+ hash_init(ht);
+ return ht;
+}
+#endif
+
+/*
+ * Initialize an empty hash table.
+ */
+ void
+hash_init(hashtab_T *ht)
+{
+ // This zeroes all "ht_" entries and all the "hi_key" in "ht_smallarray".
+ CLEAR_POINTER(ht);
+ 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(hashtab_T *ht)
+{
+ if (ht->ht_array != ht->ht_smallarray)
+ vim_free(ht->ht_array);
+}
+
+#if defined(FEAT_SPELL) || defined(FEAT_TERMINAL) || defined(PROTO)
+/*
+ * 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(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);
+}
+#endif
+
+/*
+ * 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(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(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;
+ }
+}
+
+#if defined(FEAT_EVAL) || defined(FEAT_SYN_HL) || defined(PROTO)
+/*
+ * Print the efficiency of hashtable lookups.
+ * Useful when trying different hash algorithms.
+ * Called when exiting.
+ */
+ void
+hash_debug_results(void)
+{
+#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
+}
+#endif
+
+/*
+ * Add item with key "key" to hashtable "ht".
+ * Returns FAIL when out of memory or the key is already present.
+ */
+ int
+hash_add(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))
+ {
+ internal_error("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(
+ 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;
+ ++ht->ht_changed;
+ 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(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(hashtab_T *ht, hashitem_T *hi)
+{
+ --ht->ht_used;
+ ++ht->ht_changed;
+ 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(hashtab_T *ht)
+{
+ ++ht->ht_locked;
+}
+
+/*
+ * 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(hashtab_T *ht, int size)
+{
+ (void)hash_may_resize(ht, size);
+ ++ht->ht_locked;
+}
+
+/*
+ * 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(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(
+ 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 + 1) / 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;
+ CLEAR_FIELD(ht->ht_smallarray);
+ }
+ else
+ {
+ // Allocate an array.
+ newarray = ALLOC_CLEAR_MULT(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;
+ }
+
+ /*
+ * 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_changed;
+ 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(char_u *key)
+{
+ hash_T hash;
+ char_u *p;
+
+ if ((hash = *key) == 0)
+ return (hash_T)0;
+ 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;
+}