RemoteEditor/vim7: src/hashtab.c comparison

comparison src/hashtab.c @ 0:76efa0be13f1

Initial revision

author	atsuki
date	Sat, 10 Nov 2007 15:07:22 +0900
parents
children	c16898406ff2

comparison

equal deleted inserted replaced

--1:000000000000
+:76efa0be13f1
+/* 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

Mercurial > hg > RemoteEditor > vim7

comparison src/hashtab.c @ 0:76efa0be13f1