#ifdef RCSID
static char RCSid[] =
"$Header: d:/cvsroot/tads/tads3/vmhash.cpp,v 1.3 1999/07/11 00:46:59 MJRoberts Exp $";
#endif

/* 
 *   Copyright (c) 1997, 2002 Michael J. Roberts.  All Rights Reserved.
 *   
 *   Please see the accompanying license file, LICENSE.TXT, for information
 *   on using and copying this software.  
 */
/*
Name
  vmhash.cpp - hash table implementation
Function
  
Notes
  
Modified
  10/25/97 MJRoberts  - Creation
*/

#include <assert.h>
#include <memory.h>
#include <string.h>

#ifndef STD_H
#include "t3std.h"
#endif
#ifndef VMHASH_H
#include "vmhash.h"
#endif


/* ------------------------------------------------------------------------ */
/*
 *   Simple case-insensitive hash function implementation.
 */
unsigned int CVmHashFuncCI::compute_hash(const char *s, size_t l) const
{
    uint acc;

    /*
     *   Add up all the character values in the string, converting all
     *   characters to upper-case.
     */
    for (acc = 0 ; l != 0 ; ++s, --l)
    {
        uchar c;

        c = (uchar)(is_lower(*s) ? to_upper(*s) : *s);
        acc += c;
    }

    /* return the accumulated value */
    return acc;
}

/* ------------------------------------------------------------------------ */
/*
 *   Simple case-sensitive hash function implementation 
 */
unsigned int CVmHashFuncCS::compute_hash(const char *s, size_t l) const
{
    uint acc;

    /*
     *   add up all the character values in the string, treating case as
     *   significant 
     */
    for (acc = 0 ; l != 0 ; ++s, --l)
    {
        uchar c;

        c = (uchar)*s;
        acc += c;
    }

    /* return the accumulated value */
    return acc;
}


/* ------------------------------------------------------------------------ */
/*
 *   Hash table symbol entry.  This is an abstract class; subclasses must
 *   provide a symbol-matching method.  
 */
CVmHashEntry::CVmHashEntry(const char *str, size_t len, int copy)
{
    /* not linked into a list yet */
    nxt_ = 0;

    /* see if we can use the original string or need to make a private copy */
    if (copy)
    {
        char *buf;

        /* allocate space for a copy */
        buf = new char[len];

        /* copy it into our buffer */
        memcpy(buf, str, len * sizeof(*buf));

        /* remember it */
        str_ = buf;
    }
    else
    {
        /* we can use the original */
        str_ = str;
    }

    /* remember the length */
    len_ = len;

    /* remember whether or not we own the string */
    copy_ = copy;
}

CVmHashEntry::~CVmHashEntry()
{
    /* if we made a private copy of the string, we own it, so delete it */
    if (copy_)
        delete [] (char *)str_;
}


/* ------------------------------------------------------------------------ */
/*
 *   Concrete subclass of CVmHashEntry providing a case-insensitive
 *   symbol match implementation 
 */
int CVmHashEntryCI::matches(const char *str, size_t len) const
{
    /*
     *   it's a match if the strings are the same length and all
     *   characters match, ignoring case 
     */
    return (len == len_
            && memicmp(str, str_, len * sizeof(*str)) == 0);
}


/* ------------------------------------------------------------------------ */
/*
 *   Concrete subclass of CVmHashEntry providing a case-sensitive symbol
 *   match implementation 
 */
int CVmHashEntryCS::matches(const char *str, size_t len) const
{
    /*
     *   it's a match if the strings are the same length and all
     *   characters match, treating case as significant 
     */
    return (len == len_
            && memcmp(str, str_, len * sizeof(*str)) == 0);
}

/* ------------------------------------------------------------------------ */
/*
 *   Hash table 
 */

void CVmHashTable::init(int hash_table_size,
                        CVmHashFunc *hash_function, int own_hash_func,
                        CVmHashEntry **hash_array)
{
    CVmHashEntry **entry;
    size_t i;

    /* make sure it's a power of two */
    assert(is_power_of_two(hash_table_size));

    /* make sure we got a hash function */
    assert(hash_function != 0);

    /* save the hash function */
    hash_function_ = hash_function;
    own_hash_func_ = own_hash_func;

    /* check to see if the caller provided the hash array */
    if (hash_array != 0)
    {
        /* the caller allocated the table - store a reference to it */
        table_ = hash_array;
        table_size_ = hash_table_size;

        /* note that the table belongs to the caller, so we don't delete it */
        own_hash_table_ = FALSE;
    }
    else
    {
        /* allocate the table */
        table_ = new CVmHashEntry *[hash_table_size];
        table_size_ = hash_table_size;

        /* note that we own the table and must delete it */
        own_hash_table_ = TRUE;
    }

    /* clear the table */
    for (entry = table_, i = 0 ; i < table_size_ ; ++i, ++entry)
        *entry = 0;
}

CVmHashTable::~CVmHashTable()
{
    /* delete the hash function object if I own it */
    if (own_hash_func_)
        delete hash_function_;

    /* delete each entry in the hash table */
    delete_all_entries();

    /* delete the hash table */
    if (own_hash_table_)
        delete [] table_;
}

/*
 *   delete all entries in the hash table, but keep the table itself 
 */
void CVmHashTable::delete_all_entries()
{
    CVmHashEntry **tableptr;
    size_t i;

    for (tableptr = table_, i = 0 ; i < table_size_ ; ++i, ++tableptr)
    {
        CVmHashEntry *entry;
        CVmHashEntry *nxt;

        /* delete each entry in the list at this element */
        for (entry = *tableptr ; entry ; entry = nxt)
        {
            /* remember the next entry */
            nxt = entry->nxt_;

            /* delete this entry */
            delete entry;
        }

        /* there's nothing at this table entry now */
        *tableptr = 0;
    }
}

/*
 *   Verify that a value is a power of two.  Hash table sizes must be
 *   powers of two. 
 */
int CVmHashTable::is_power_of_two(int n)
{
    /* divide by two until we have an odd number */
    while ((n & 1) == 0) n >>= 1;

    /* make sure the result is 1 */
    return (n == 1);
}

/*
 *   Compute the hash value for an entry 
 */
unsigned int CVmHashTable::compute_hash(CVmHashEntry *entry) const
{
    return compute_hash(entry->getstr(), entry->getlen());
}

/*
 *   Compute the hash value for a string 
 */
unsigned int CVmHashTable::compute_hash(const char *str, size_t len) const
{
    return adjust_hash(hash_function_->compute_hash(str, len));
}

/*
 *   Add an object to the table
 */
void CVmHashTable::add(CVmHashEntry *entry)
{
    unsigned int hash;

    /* compute the hash value for this entry */
    hash = compute_hash(entry);

    /* link it into the slot for this hash value */
    entry->nxt_ = table_[hash];
    table_[hash] = entry;
}

/*
 *   Remove an object 
 */
void CVmHashTable::remove(CVmHashEntry *entry)
{
    unsigned int hash;

    /* compute the hash value for this entry */
    hash = compute_hash(entry);

    /* 
     *   if it's the first item in the chain, advance the head over it;
     *   otherwise, we'll need to find the previous item to unlink it 
     */
    if (table_[hash] == entry)
    {
        /* it's the first item - simply advance the head to the next item */
        table_[hash] = entry->nxt_;
    }
    else
    {
        CVmHashEntry *prv;
        
        /* find the previous item in the list for this hash value */
        for (prv = table_[hash] ; prv != 0 && prv->nxt_ != entry ;
             prv = prv->nxt_) ;

        /* if we found it, unlink this item */
        if (prv != 0)
            prv->nxt_ = entry->nxt_;
    }
}

/*
 *   Find an object in the table matching a given string. 
 */
CVmHashEntry *CVmHashTable::find(const char *str, size_t len) const
{
    unsigned int hash;
    CVmHashEntry *entry;

    /* compute the hash value for this entry */
    hash = compute_hash(str, len);

    /* scan the list at this hash value looking for a match */
    for (entry = table_[hash] ; entry ; entry = entry->nxt_)
    {
        /* if this one matches, return it */
        if (entry->matches(str, len))
            return entry;
    }

    /* didn't find anything */
    return 0;
}

/*
 *   Enumerate hash matches for a given string
 */
void CVmHashTable::enum_hash_matches(const char *str, size_t len,
                                     void (*cb)(void *cbctx,
                                                CVmHashEntry *entry),
                                     void *cbctx)
{
    unsigned int hash;

    /* compute the hash value for this entry */
    hash = compute_hash(str, len);

    /* enumerate matches at the hash value */
    enum_hash_matches(hash, cb, cbctx);
}

/*
 *   Enumerate hash matches for a given hash code 
 */
void CVmHashTable::enum_hash_matches(unsigned int hash,
                                     void (*cb)(void *cbctx,
                                                CVmHashEntry *entry),
                                     void *cbctx)
{
    CVmHashEntry *entry;

    /* adjust the hash value for the table size */
    hash = adjust_hash(hash);

    /* enumerate the complete list of entries at this hash value */
    for (entry = table_[hash] ; entry ; entry = entry->nxt_)
    {
        /* call the callback with this entry */
        (*cb)(cbctx, entry);
    }
}

/*
 *   Find an object in the table matching a given leading substring.
 *   We'll return the longest-named entry that matches a leading substring
 *   of the given string.  For example, if there's are entires A, AB, ABC,
 *   and ABCE, and this routine is called to find something matching
 *   ABCDEFGH, we'll return ABC as the match (not ABCE, since it doesn't
 *   match any leading substring of the given string, and not A or AB,
 *   even though they match, since ABC also matches and it's longer).  
 */
CVmHashEntry *CVmHashTable::find_leading_substr(const char *str, size_t len)
{
    size_t sublen;
    CVmHashEntry *entry;

    /* 
     *   try to find each leading substring, starting with the longest,
     *   decreasing by one character on each iteration, until we've used
     *   the whole string 
     */
    for (sublen = len ; sublen > 0 ; --sublen)
    {
        /* if this substring matches, use it */
        if ((entry = find(str, sublen)) != 0)
            return entry;
    }

    /* we didn't find it */
    return 0;
}

/*
 *   Enumerate all entries 
 */
void CVmHashTable::enum_entries(void (*func)(void *, CVmHashEntry *),
                                void *ctx)
{
    CVmHashEntry **tableptr;
    size_t i;

    /* go through each hash value */
    for (tableptr = table_, i = 0 ; i < table_size_ ; ++i, ++tableptr)
    {
        CVmHashEntry *entry;
        CVmHashEntry *nxt;

        /* go through each entry at this hash value */
        for (entry = *tableptr ; entry ; entry = nxt)
        {
            /* 
             *   remember the next entry, in case the callback deletes the
             *   current entry 
             */
            nxt = entry->nxt_;

            /* invoke the callback on this entry */
            (*func)(ctx, entry);
        }
    }
}

/*
 *   Enumerate all entries - ultra-safe version.  This version should be
 *   used when the callback code might delete arbitrary entries from the
 *   hash table.  This version is slower than the standard enum_entries, but
 *   will tolerate any changes to the table made in the callback.  
 */
void CVmHashTable::safe_enum_entries(void (*func)(void *, CVmHashEntry *),
                                     void *ctx)
{
    CVmHashEntry **tableptr;
    size_t i;

    /* go through each hash value */
    for (tableptr = table_, i = 0 ; i < table_size_ ; ++i, ++tableptr)
    {
        size_t list_idx;

        /* 
         *   start at the first (0th) entry in the current hash chain, and
         *   keep going until we run out of entries in the chain 
         */
        for (list_idx = 0 ; ; ++list_idx)
        {
            CVmHashEntry *entry;
            size_t j;

            /* 
             *   Scan the hash chain for the current entry index.
             *   
             *   This is the part that makes this version slower than the
             *   standard version and safer than the standard version.  It's
             *   slower than enum_entries() because we must scan the chain
             *   list on every iteration to find the next entry, whereas
             *   enum_entries() simply keeps a pointer to the next entry.
             *   It's safer because we don't keep any pointers - if next
             *   element is deleted in the callback in enum_entries(), that
             *   stored next pointer would be invalid, but we store no
             *   pointers that could become stale.  
             */
            for (j = 0, entry = *tableptr ; j < list_idx && entry != 0 ;
                 entry = entry->nxt_, ++j) ;

            /* if we failed to find the entry, we're done with this chain */
            if (entry == 0)
                break;

            /* invoke the callback on this entry */
            (*func)(ctx, entry);
        }
    }
}


/*
 *   Move all entries in this table to a new table 
 */
void CVmHashTable::move_entries_to(CVmHashTable *new_tab)
{
    CVmHashEntry **tableptr;
    size_t i;

    /* go through each hash value */
    for (tableptr = table_, i = 0 ; i < table_size_ ; ++i, ++tableptr)
    {
        CVmHashEntry *entry;
        CVmHashEntry *nxt;

        /* go through each entry at this hash value */
        for (entry = *tableptr ; entry ; entry = nxt)
        {
            /* 
             *   remember the next entry, since we'll be unlinking it from
             *   this table, which will render the nxt_ member unusable
             *   for the purposes of completing this enumeration 
             */
            nxt = entry->nxt_;

            /* 
             *   clear the 'next' pointer in this entry, to unlink it from
             *   our table - since everything is being removed, there's no
             *   need to worry about what came before us 
             */
            entry->nxt_ = 0;

            /* add the entry to the new hash table */
            new_tab->add(entry);
        }

        /* 
         *   clear this hash value chain head - we've now removed
         *   everything from it 
         */
        *tableptr = 0;
    }
}

/* ------------------------------------------------------------------------ */
/*
 *   Debugging Functions 
 */

#ifdef T3_DEBUG

/*
 *   dump information the hash table to stderr
 */
void CVmHashTable::debug_dump() const
{
    long total;
    long longest;
    long avg;
    int over_avg;
    int empty;
    size_t i;
    
    /* gather statistics on the hash table */
    for (total = longest = 0, empty = 0, i = 0 ; i < table_size_ ; ++i)
    {
        CVmHashEntry *cur;
        int curlen;
        
        /* scan this chain */
        for (curlen = 0, cur = table_[i] ; cur != 0 ; cur = cur->nxt_)
        {
            ++curlen;
            ++total;
        }

        /* if it's empty, so note */
        if (curlen == 0)
            ++empty;

        /* if it's longer than the longest, so note */
        if (curlen > longest)
            longest = curlen;
    }

    /* calculate the average length */
    avg = total/table_size_;

    /* count chains over average length */
    for (over_avg = 0, i = 0 ; i < table_size_ ; ++i)
    {
        CVmHashEntry *cur;
        int curlen;

        /* scan this chain */
        for (curlen = 0, cur = table_[i] ; cur != 0 ; cur = cur->nxt_)
            ++curlen;

        /* if it's over average length, note it */
        if (curlen > avg)
            ++over_avg;
    }

        
    /* display the statistics */
    fprintf(stderr,
            "hash table: total %ld, longest %ld, average %ld\n"
            "number of buckets over average length: %d\n"
            "number of empty buckets: %d\n",
            total, longest, avg, over_avg, empty);
}

#else /* T3_DEBUG */

/* dummy functions for release builds */
void CVmHashTable::debug_dump() const { }


#endif /* T3_DEBUG */