xref: /illumos-gate/usr/src/common/ficl/hash.c (revision afc2ba1d)

#include "ficl.h"

#define	FICL_ASSERT_PHASH(hash, expression)	FICL_ASSERT(NULL, expression)

/*
 * h a s h F o r g e t
 * Unlink all words in the hash that have addresses greater than or
 * equal to the address supplied. Implementation factor for FORGET
 * and MARKER.
 */
void
ficlHashForget(ficlHash *hash, void *where)
{
	ficlWord *pWord;
	unsigned i;

	FICL_ASSERT_PHASH(hash, hash);
	FICL_ASSERT_PHASH(hash, where);

	for (i = 0; i < hash->size; i++) {
		pWord = hash->table[i];

		while ((void *)pWord >= where) {
			pWord = pWord->link;
		}

		hash->table[i] = pWord;
	}
}

/*
 * h a s h H a s h C o d e
 *
 * Generate a 16 bit hashcode from a character string using a rolling
 * shift and add stolen from PJ Weinberger of Bell Labs fame. Case folds
 * the name before hashing it...
 * N O T E : If string has zero length, returns zero.
 */
ficlUnsigned16
ficlHashCode(ficlString s)
{
	/* hashPJW */
	ficlUnsigned8 *trace;
	ficlUnsigned16 code = (ficlUnsigned16)s.length;
	ficlUnsigned16 shift = 0;

	if (s.length == 0)
		return (0);

	/* changed to run without errors under Purify -- lch */
	for (trace = (ficlUnsigned8 *)s.text;
	    s.length && *trace; trace++, s.length--) {
		code = (ficlUnsigned16)((code << 4) + tolower(*trace));
		shift = (ficlUnsigned16)(code & 0xf000);
		if (shift) {
			code ^= (ficlUnsigned16)(shift >> 8);
			code ^= (ficlUnsigned16)shift;
		}
	}

	return ((ficlUnsigned16)code);
}

/*
 * h a s h I n s e r t W o r d
 * Put a word into the hash table using the word's hashcode as
 * an index (modulo the table size).
 */
void
ficlHashInsertWord(ficlHash *hash, ficlWord *word)
{
	ficlWord **pList;

	FICL_ASSERT_PHASH(hash, hash);
	FICL_ASSERT_PHASH(hash, word);

	if (hash->size == 1) {
		pList = hash->table;
	} else {
		pList = hash->table + (word->hash % hash->size);
	}

	word->link = *pList;
	*pList = word;
}

/*
 * h a s h L o o k u p
 * Find a name in the hash table given the hashcode and text of the name.
 * Returns the address of the corresponding ficlWord if found,
 * otherwise NULL.
 * Note: outer loop on link field supports inheritance in wordlists.
 * It's not part of ANS Forth - Ficl only. hashReset creates wordlists
 * with NULL link fields.
 */
ficlWord *
ficlHashLookup(ficlHash *hash, ficlString name, ficlUnsigned16 hashCode)
{
	ficlUnsigned nCmp = name.length;
	ficlWord *word;
	ficlUnsigned16 hashIdx;

	if (nCmp > FICL_NAME_LENGTH)
		nCmp = FICL_NAME_LENGTH;

	for (; hash != NULL; hash = hash->link) {
		if (hash->size > 1)
			hashIdx = (ficlUnsigned16)(hashCode % hash->size);
		else /* avoid the modulo op for single threaded lists */
			hashIdx = 0;

		for (word = hash->table[hashIdx]; word; word = word->link) {
			if ((word->length == name.length) &&
			    (!ficlStrincmp(name.text, word->name, nCmp)))
				return (word);
#if FICL_ROBUST
			FICL_ASSERT_PHASH(hash, word != word->link);
#endif
		}
	}

	return (NULL);
}

/*
 * h a s h R e s e t
 * Initialize a ficlHash to empty state.
 */
void
ficlHashReset(ficlHash *hash)
{
	unsigned i;

	FICL_ASSERT_PHASH(hash, hash);

	for (i = 0; i < hash->size; i++) {
		hash->table[i] = NULL;
	}

	hash->link = NULL;
	hash->name = NULL;
}