swlpc Git

/*
** $Id: hash.c,v 1.6 2008/12/18 04:17:02 dredd Exp $
**
** $Source: /cvsroot/swlpc/swlpc/runtime/hash.c,v $
** $Revision: 1.6 $
** $Date: 2008/12/18 04:17:02 $
** $State: Exp $
**
** Author: Mike McGaughey & Geoff Wong, 1993-1998
**
** See the file "Copying" distributed with this file.
*/

#include "proto.h"
#include "hash.h"

int  nhash = 0;

/* s - string, maxn - maximum # of chars, hashs - htable size */
int  hashstr(char *s, int maxn, int hashs)
{
    register unsigned int h = 0;
    register unsigned char *p;

/*
 * What's faster - table memory access (with 1 cycle delays) 
 * and 2 passes through the string, or a few adds?  I'm betting on the adds.
 *
 * The following loop is carefully juggled so that the compiler
 * can fill the memory load delay slot with a multiply (multiply
 * is 1 cycle on mips, apparently) and doesn't need a temp for the
 * pointer increment (hence it's a pre-increment; saves 1 load and
 * brings the loop pipeline below 8 instructions).  Mips compiler (-O2)
 * isn't very clever about detecting this - hence the obtuse code.
 * Also: Removing the tests on maxn makes the inner loop 30% faster
 * (from 7 to 5 instructions), so it's out.  Note that the hash
 * value computed is a multiple of 3 - rectified in the return statement.
 * NB: gcc chooses to use a shift and add instead of *3, but produces
 * worse code for the rest of the loop!
 */
#if 1
    p = ((unsigned char *) s) - 1;
    do
    {
        h = h * 3 + (*++p);
    }
    while (*p);
#else
    while (*s)
    {
        h = h * 3 + (*s);
        s++;
    }
#endif
    return (h / 3) % hashs;  /* nb: h is unsigned, so this is positive */

#if 0
    for (h = 0, i = 0, p = (unsigned char *) s; *p && i < maxn; i++, p++)
        h = T[h ^ *p];
    if (hashs > 256 && *s)
    {
        int  oh = h;

        for (i = 1, p = (unsigned char *) s, h = (*p++ + 1) & 0xff; *p && i < maxn; i++, p++)
            h = T[h ^ *p];
        h += (oh << 8);
    }
    return h % hashs;  /* nb: h is unsigned, so this is positive */
#endif
}

/*
 * Internal Hash table Stuff 
 * 
 * * quadratic probing.
 * * written by Geoff Wong for Shattered World.
 * (NEED: should double size of table when 90% full)
 * (NEED: should be malloced etc. - just get it working first!)
 */

static int hash_entries = 0;
static int hash_table_size = IHSIZE;

int  iHash(char *s, char *p, int tsize)
{
    int  h = 0, countx = 120;


    while (*s && --countx)
        h = (h * P1 + *(s++) * P2 + P3) % tsize;
    while (*p && --countx)
        h = (h * P1 + *(s++) * P2 + P3) % tsize;

    return (h);
}

i_element *IHtable;
static int first = 0;

void init_Htable()
{
    int  i;

    IHtable = (i_element *) malloc(hash_table_size * sizeof(i_element));
    for (i = 0; i < IHSIZE; i++)
    {
        IHtable[i].used = 0;
        IHtable[i].deleted = 0;
    }
    first = 1;
}

void free_Htable()
{
    free(IHtable);
}

int remove_Hfunction(Shared * func_name, Shared * obj)
{
    int gap = 1;
    int h = hashstr(func_name->str, 0, (IHSIZE + 1) / 2) 
                + hashstr(obj->str, 0, (IHSIZE + 1) / 2);
    int n;

#if 0
    fprintf(stderr, "removing %s in %s.\n",
            func_name, obj);
#endif
    while (1)
    {
        if (IHtable[h].used && !(IHtable[h].deleted) &&
            (IHtable[h].obj == obj) &&
            (func_name == ((IHtable[h]).program)->name))
        {
            n = (h + gap) % IHSIZE;
            IHtable[h].deleted = IHtable[n].used;
            IHtable[h].used = IHtable[n].used;
            hash_entries--;
            return 1;
        }
        if (IHtable[h].used == 0 && IHtable[h].deleted == 0)
        {
            return 0;
        }
        h = (h + gap) % IHSIZE;
        gap++;
    }
    return 0;
}

int add_Hfunction(Func * pr, Shared * obj, short offset)
{
    int  gap = 1;
    int  h = hashstr(pr->name->str, 0, (IHSIZE + 1) / 2) 
                + hashstr(obj->str, 0, (IHSIZE + 1) / 2);

    if (!first) init_Htable();

    /* only 1 named function from each object! */
    if (Hfunction(pr->name, obj))
    {
#if 0
        fprintf(stderr, "Function %s in %s already exists.\n",
                pr->name, obj);
#endif
        return 0;
    }
#if 0
    fprintf(stderr, "Adding function %s in %s.\n",
            pr->name, obj);
#endif
    while ((IHtable[h]).used == 1 && ((IHtable[h]).deleted == 0))
    {
        h = (h + gap) % IHSIZE;
        gap++;
    }
    (IHtable[h]).used = 1;
    (IHtable[h]).deleted = 0;
    (IHtable[h]).obj = obj;
    (IHtable[h]).program = pr;
    (IHtable[h]).offset = offset;
#ifdef PROFILE
    (IHtable[h]).called = 0;
#endif
    hash_entries++;
    return 1;
}

int  prog_offset_hack = 0;

/* func_name NOT shared! */
Func * Hfunction(Shared * func_name, Shared * obj)
{
    int  gap = 1;
    int  h = hashstr(func_name->str, 0, (IHSIZE + 1) / 2) 
                + hashstr(obj->str, 0, (IHSIZE + 1) / 2);

    if (!first) init_Htable();

    while (1)
    {
        if ( (IHtable[h]).used && !((IHtable[h]).deleted) &&
             ((IHtable[h]).obj == obj) &&
             (func_name == ((IHtable[h]).program)->name) )
        {
#if 0
            fprintf(stderr, "Found function %s in %s.\n",
                    func_name, obj);
#endif
            prog_offset_hack = (IHtable[h]).offset;
#ifdef PROFILE
            (IHtable[h]).called++;
#endif
            return (IHtable[h]).program;
        }
        if ((IHtable[h]).used == 0 && (IHtable[h]).deleted == 0)
        {
#if 0
            fprintf(stderr, "Function NOT FOUND.\n");
#endif
            prog_offset_hack = 0;
            return 0;
        }
        h = (h + gap) % IHSIZE;
        gap++;
    }
    return NULL;
}

int  show_ihash_table_status()
{
    add_message("IH size = %d, IH entries = %d\n", hash_table_size,
                hash_entries);
    return (hash_table_size * sizeof(i_element));
}