Subversion Repositories planix.SVN

/* 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