hash.cpp

来自「Shorthand是一个强大的脚本语言」· C++ 代码 · 共 273 行

///////////////////////////////////////////////////////////////////////////////
// $Header: /shorthand/src/hash.cpp 1     1/09/03 7:14p Arm $
//-----------------------------------------------------------------------------
// Project: ShortHand interpreter
// Author: Andrei Remenchuk <[e-mail]>
//-----------------------------------------------------------------------------
// sharray.cpp: ShortHand Hash Array class - implementation
///////////////////////////////////////////////////////////////////////////////
#include "hash.h"
#include "except.h"
#include <stdlib.h>

#define BUCKET_COUNT_0 64
#define BUCKET_LEVELS  1

static unsigned int makeHash(const char* s)
{
   register const char *p;
   register unsigned int h = 0;
   for(p = (const char*) s; *p != '\0'; p++) 
   {
      h = ( h << 5 ) - h + *p;
   }
   return h;
}


ShhHashEntry::ShhHashEntry(const string& index, const ShhValue& value)
: m_index(index), m_value(value)
{
    m_hash = makeHash(index.cstr());
}


ShhHashBucket::ShhHashBucket(unsigned int level, unsigned int key)
{
    m_level = level;
    m_key = key;
    m_divider = 1; 
    for(unsigned int i=0;i<=level;i++) m_divider *= BUCKET_COUNT_0;

    m_count = 0;
    m_sorted = 0;
    m_dirty = 0;
    m_capacity = 0;
    m_elements = 0;
}

void ShhHashBucket::provideCapacity(int newCapacity)
{
    if (newCapacity > m_capacity)
    {
        m_capacity = (newCapacity/32+1)*32;
        if (m_elements == NULL) 
            m_elements = (ShhHashEntry**) malloc(sizeof(ShhHashEntry*)*m_capacity);
        else 
            m_elements = (ShhHashEntry**) realloc(m_elements, sizeof(ShhHashEntry*)*m_capacity);
    }
}

ShhHashBucket::~ShhHashBucket()
{
    if (m_elements != NULL)
    {
        for(int i=0,n=m_count; i<n; i++)
        {
            if (m_elements[i] != NULL) delete m_elements[i];
        }
    }
}

typedef int (*compare_t)(const void *arg1, const void *arg2);

static int compareHashCodes(ShhHashCode **a, ShhHashCode **b)
{
    return (*a)->m_hash - (*b)->m_hash;
}



ShhHashEntry* ShhHashBucket::findElement(const string& index)
{
    int i;
    unsigned int hashCode = makeHash(index);
    if (m_sorted > 0)
    {
        ShhHashCode bKey(hashCode);
        ShhHashCode* bKeyAddress = &bKey;
        ShhHashEntry** match = (ShhHashEntry**)
            bsearch(&bKeyAddress, m_elements, m_sorted, sizeof(ShhHashEntry*), (compare_t) compareHashCodes);
        if (match != NULL)
        {
            i = match - m_elements;
            while(i>0 && m_elements[i-1]->m_hash == hashCode) i--;
            while(i<m_sorted && m_elements[i]->m_hash == hashCode)
            {
                if (strcmp(m_elements[i]->getIndex(), index) == 0) return m_elements[i];
            }
        }
    }
    for(i=m_sorted; i<m_count; i++)
    {
        if (strcmp(m_elements[i]->getIndex(), index) == 0) return m_elements[i];
    }
    return NULL;
}

ShhHashEntry* ShhHashBucket::createElement(const string& index, const ShhValue& value)
{
    provideCapacity(m_count+1);
    ShhHashEntry* element = new ShhHashEntry(index, value);
    m_elements[m_count] = element;
    m_count++;
    m_dirty++;
    if (m_dirty > 64)
    {
        qsort(m_elements, m_count, sizeof(ShhHashEntry*), (compare_t) compareHashCodes);
        m_sorted = m_count;
    }
    return element;
}



ShhHash::ShhHash(ShhModule& module, const YYLTYPE& location)
: ShhObject(module, "HASH", location)
{
    m_count = 0;
    for(int i=0,n=BUCKET_COUNT_0; i<n; i++)
    {
        m_buckets.add(new ShhHashBucket(0, i));
    }
}

ShhHash::~ShhHash()
{
}

void ShhHash::constructor(ShhValueList* args)
{
}

bool ShhHash::hasMethod(const char* name)
{
    return false;
}

ShhValue ShhHash::executeMethod(const char* name, ShhValueList* args)
{
    return ShhValue::null();
}

ShhValue& ShhHash::getProperty(const char* name)
{
    if (stricmp(name, "count") == 0)
    {
        m_count_property = m_count;
        return m_count_property;
    }
    else
        return ShhObject::getProperty(name);
}


ShhHashBucket* ShhHash::findBucket(unsigned int hashCode)
{
    int key = hashCode%BUCKET_COUNT_0;
    return m_buckets.get(key);
}

ShhHashBucket* ShhHash::createBucket(unsigned int hashCode)
{
    int key = hashCode%BUCKET_COUNT_0;
    return m_buckets.get(key);
}


ShhValue ShhHash::rvalue(const ShhValue& index) 
{
    string sIndex;
    index.toString(sIndex);
    unsigned int hashCode = makeHash(sIndex);

    ShhHashBucket* bucket = findBucket(hashCode);
    if (bucket == NULL) bucket = createBucket(hashCode);

    ShhHashEntry* element = bucket->findElement(sIndex);
    if (element == NULL) return ShhValue::null();
    else return element->getValue();
}

ShhValue& ShhHash::lvalue(const ShhValue& index) 
{
    string sIndex;
    index.toString(sIndex);
    unsigned int hashCode = makeHash(sIndex);

    ShhHashBucket* bucket = findBucket(hashCode);
    if (bucket == NULL) bucket = createBucket(hashCode);

    ShhHashEntry* element = bucket->findElement(sIndex);
    if (element == NULL) 
    {
        m_count++;
        element = bucket->createElement(sIndex, ShhValue::EMPTY);
    }
    return element->getValue();
}

void ShhHash::set(const ShhValue& index, ShhValue value)
{
    string sIndex;
    index.toString(sIndex);
    unsigned int hashCode = makeHash(sIndex);

    ShhHashBucket* bucket = findBucket(hashCode);
    if (bucket == NULL) bucket = createBucket(hashCode);

    ShhHashEntry* element = bucket->findElement(sIndex);
    if (element == NULL) 
    {
        element = bucket->createElement(sIndex, value);
        m_count++;
    }
    else
        element->getValue() = value;
}

int ShhHash::size() const
{
    return m_count;
}

ShhHashIterator::ShhHashIterator()
{
    m_hash = NULL;
    m_bucket_index = 0;
    m_element_index = 0;
}

bool ShhHashIterator::next(ShhValue& index, ShhValue& value)
{
    int bucketCount = m_hash->m_buckets.size();
    while(m_bucket_index < bucketCount)
    {
        ShhHashBucket* bucket = m_hash->m_buckets.get(m_bucket_index);
        int elementCount = bucket->m_count;
        if (m_element_index < elementCount)
        {
            ShhHashEntry* entry = bucket->m_elements[m_element_index];
            index = entry->getIndex();
            value = entry->getValue();
            m_element_index++;
            return true;
        }
        m_bucket_index++;
        m_element_index = 0;
    }
    return false;

    
}

void ShhHash::createIterator(ShhHashIterator& iterator)
{
    iterator.m_hash = this;
    iterator.m_bucket_index = 0;
    iterator.m_element_index = 0;
}