common/ficl/hash.c

afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#include "ficl.h"
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#define FICL_ASSERT_PHASH(hash, expression) FICL_ASSERT(NULL, expression)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * h a s h F o r g e t
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Unlink all words in the hash that have addresses greater than or
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * equal to the address supplied. Implementation factor for FORGET
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * and MARKER.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomevoid
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlHashForget(ficlHash *hash, void *where)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlWord *pWord;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    unsigned i;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    FICL_ASSERT_PHASH(hash, hash);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    FICL_ASSERT_PHASH(hash, where);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    for (i = 0; i < hash->size; i++) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        pWord = hash->table[i];
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        while ((void *)pWord >= where) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            pWord = pWord->link;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        hash->table[i] = pWord;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * h a s h H a s h C o d e
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Generate a 16 bit hashcode from a character string using a rolling
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * shift and add stolen from PJ Weinberger of Bell Labs fame. Case folds
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * the name before hashing it...
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * N O T E : If string has zero length, returns zero.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlUnsigned16
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlHashCode(ficlString s)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    /* hashPJW */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlUnsigned8 *trace;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlUnsigned16 code = (ficlUnsigned16)s.length;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlUnsigned16 shift = 0;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    if (s.length == 0)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        return (0);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    /* changed to run without errors under Purify -- lch */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    for (trace = (ficlUnsigned8 *)s.text;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        s.length && *trace; trace++, s.length--) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        code = (ficlUnsigned16)((code << 4) + tolower(*trace));
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        shift = (ficlUnsigned16)(code & 0xf000);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        if (shift) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            code ^= (ficlUnsigned16)(shift >> 8);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            code ^= (ficlUnsigned16)shift;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    return ((ficlUnsigned16)code);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * h a s h I n s e r t W o r d
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Put a word into the hash table using the word's hashcode as
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * an index (modulo the table size).
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomevoid
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlHashInsertWord(ficlHash *hash, ficlWord *word)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlWord **pList;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    FICL_ASSERT_PHASH(hash, hash);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    FICL_ASSERT_PHASH(hash, word);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    if (hash->size == 1) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        pList = hash->table;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    } else {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        pList = hash->table + (word->hash % hash->size);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    word->link = *pList;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    *pList = word;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * h a s h L o o k u p
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Find a name in the hash table given the hashcode and text of the name.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Returns the address of the corresponding ficlWord if found,
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * otherwise NULL.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Note: outer loop on link field supports inheritance in wordlists.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * It's not part of ANS Forth - Ficl only. hashReset creates wordlists
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * with NULL link fields.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlWord *
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlHashLookup(ficlHash *hash, ficlString name, ficlUnsigned16 hashCode)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlUnsigned nCmp = name.length;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlWord *word;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    ficlUnsigned16 hashIdx;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    if (nCmp > FICL_NAME_LENGTH)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        nCmp = FICL_NAME_LENGTH;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    for (; hash != NULL; hash = hash->link) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        if (hash->size > 1)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            hashIdx = (ficlUnsigned16)(hashCode % hash->size);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        else /* avoid the modulo op for single threaded lists */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            hashIdx = 0;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        for (word = hash->table[hashIdx]; word; word = word->link) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            if ((word->length == name.length) &&
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome                (!ficlStrincmp(name.text, word->name, nCmp)))
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome                return (word);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#if FICL_ROBUST
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome            FICL_ASSERT_PHASH(hash, word != word->link);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome#endif
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    return (NULL);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome/*
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * h a s h R e s e t
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome * Initialize a ficlHash to empty state.
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome */
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soomevoid
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas SoomeficlHashReset(ficlHash *hash)
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome{
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    unsigned i;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    FICL_ASSERT_PHASH(hash, hash);
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    for (i = 0; i < hash->size; i++) {
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome        hash->table[i] = NULL;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    }
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    hash->link = NULL;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome    hash->name = NULL;
afc2ba1deb75b323afde536f2dd18bcafdaa308dToomas Soome}