StringIntHash Class Reference

Inheritance diagram for StringIntHash:

Collaboration diagram for StringIntHash:

Public Member Functions
	StringIntHash (int startsize=32)
void	Grow ()
void	Shrink ()
void	SetSize (int newsize)
void	Clear ()
int	Capacity () const
int	Entries () const
int	Integer (int i) const
int	Integer (const String &key) const
void	SetInteger (int i, int value)
void	SetInteger (const String &key, int value)
int	IncrementCount (const String &key)
int	IncrementCount (const String &key, int amount)
int	DecrementCount (const String &key)
int	GetCount (const String &key) const
int	GetCount (int index) const
int	Add (const String &s, int integer)
int	Find (const String &s, int defaultValue)
int	Find (const String &s) const
StringIntHash &	operator= (const StringIntHash &rhs)
bool	operator== (const StringIntHash &rhs) const
const String &	operator[] (int i) const
String &	operator[] (int i)
void	Delete (unsigned int index)
void	Delete (const String &key)
bool	SlotInUse (int index) const
Public Member Functions inherited from StringHashBase
void	setCaseSensitive (bool caseSensitive)

Protected Attributes
String **	strings
int *	integers
unsigned int *	keys
unsigned int	count
unsigned int	size
unsigned int	mask
Protected Attributes inherited from StringHashBase
bool	myCaseSensitive

Additional Inherited Members
Protected Member Functions inherited from StringHashBase
bool	stringsEqual (const String &string1, const String &string2) const
unsigned int	getKey (const String &string) const

Detailed Description

Definition at line 193 of file StringHash.h.

Constructor & Destructor Documentation

StringIntHash()

StringIntHash::StringIntHash

(

int

startsize = 32

)

Definition at line 239 of file StringHash.cpp.

    : StringHashBase()
{
    count = 0;
    size  = startsize;
    mask  = startsize - 1;
 
    // In this implementation, the size of hash tables must be a power of two
    if (startsize & mask)
        error("StringIntHash: Hash table size must be a power of two.\n");
 
    strings  = new String * [size];
    integers = new int [size];
    keys     = new unsigned int [size];
 
    for (unsigned int i = 0; i < size; i++)
        strings[i] = NULL;
};

~StringIntHash()

StringIntHash::~StringIntHash ( )

virtual

Definition at line 258 of file StringHash.cpp.

{
    for (unsigned int i = 0; i < size; i++)
        if (strings[i] != NULL)
            delete strings[i];
 
    if(strings) delete [] strings;
    if(integers) delete [] integers;
    if(keys) delete [] keys;
}

Member Function Documentation

Add()

int StringIntHash::Add	(	const String &	s,
		int	integer )

Definition at line 321 of file StringHash.cpp.

{
    unsigned int key = getKey(string);
    unsigned int h   = Iterate(key, string);
 
    if (strings[h] == NULL)
        Insert(h, key, string);
 
    integers[h] = value;
 
    if (count * 2 > size)
    {
        Grow();
        return Iterate(key, string);
    }
 
    return h;
}

Capacity()

int StringIntHash::Capacity ( ) const

inline

Definition at line 219 of file StringHash.h.

    {
        return size;
    }

Clear()

void StringIntHash::Clear

(

)

Definition at line 306 of file StringHash.cpp.

{
    for (unsigned int i = 0; i < size; i++)
        if (strings[i] != NULL)
        {
            delete strings[i];
            strings[i] = NULL;
        }
 
    count = 0;
 
    if (size > 256)
        SetSize(256);
}

DecrementCount()

int StringIntHash::DecrementCount

(

const String &

key

)

Definition at line 626 of file StringHash.cpp.

{
    int index = Find(key);
 
    if (index != -1)
        return --(integers[index]);
 
    SetInteger(key, -1);
    return -1;
}

Delete() [1/2]

void StringIntHash::Delete ( const String & key )

inline

Definition at line 275 of file StringHash.h.

    {
        Delete(Find(key));
    }

Delete() [2/2]

void StringIntHash::Delete

(

unsigned int

index

)

Definition at line 371 of file StringHash.cpp.

{
    if (index >= size || strings[index] == NULL)
        return;
 
    delete strings[index];
    strings[index] = NULL;
    count--;
 
    if (count * 8 < size && size > 32)
        Shrink();
    else
    {
        // rehash the next strings until we find empty slot
        index = (index + 1) & mask;
 
        while (strings[index] != NULL)
        {
            if ((keys[index] & mask) != index)
            {
                unsigned int h = Iterate(keys[index], *strings[index]);
 
                if (h != (unsigned int) index)
                {
                    keys[h] = keys[index];
                    strings[h] = strings[index];
                    integers[h] = integers[index];
 
                    strings[index] = NULL;
                }
            }
 
            index = (index + 1) & mask;
        }
    }
}

Entries()

int StringIntHash::Entries ( ) const

inline

Definition at line 223 of file StringHash.h.

    {
        return count;
    }

Find() [1/2]

int StringIntHash::Find

(

const String &

s

)

const

Definition at line 360 of file StringHash.cpp.

{
    unsigned int key = getKey(string);
    unsigned int h   = Iterate(key, string);
 
    if (strings[h] == NULL)
        return -1;
 
    return h;
}

Find() [2/2]

int StringIntHash::Find	(	const String &	s,
		int	defaultValue )

Definition at line 340 of file StringHash.cpp.

{
    unsigned int key = getKey(string);
    unsigned int h   = Iterate(key, string);
 
    if (strings[h] == NULL)
    {
        Insert(h, key, string);
        integers[h] = defaultValue;
 
        if (count * 2 > size)
        {
            Grow();
            return Iterate(key, string);
        }
    }
 
    return h;
}

GetCount() [1/2]

int StringIntHash::GetCount

(

const String &

key

)

const

Definition at line 598 of file StringHash.cpp.

{
    int index = Find(key);
    return index == -1 ?  0 : integers[index];
}

GetCount() [2/2]

int StringIntHash::GetCount ( int index ) const

inline

Definition at line 252 of file StringHash.h.

    {
        return integers[index];
    }

Grow()

void StringIntHash::Grow ( )

inline

Definition at line 206 of file StringHash.h.

    {
        SetSize(size * 2);
    }

IncrementCount() [1/2]

int StringIntHash::IncrementCount

(

const String &

key

)

Definition at line 604 of file StringHash.cpp.

{
    int index = Find(key);
 
    if (index != -1)
        return ++(integers[index]);
 
    SetInteger(key, 1);
    return 1;
}

IncrementCount() [2/2]

int StringIntHash::IncrementCount	(	const String &	key,
		int	amount )

Definition at line 615 of file StringHash.cpp.

{
    int index = Find(key);
 
    if (index != -1)
        return (integers[index] += amount);
 
    SetInteger(key, amount);
    return amount;
}

Integer() [1/2]

int StringIntHash::Integer ( const String & key ) const

inline

Definition at line 232 of file StringHash.h.

    {
        int index = Find(key);
 
        return index >= 0 ? integers[index] : -1;
    }

Integer() [2/2]

int StringIntHash::Integer ( int i ) const

inline

Definition at line 228 of file StringHash.h.

    {
        return integers[i];
    }

operator=()

StringIntHash & StringIntHash::operator=

(

const StringIntHash &

rhs

)

Definition at line 663 of file StringHash.cpp.

{
    Clear();
 
    for (int i = 0; i < rhs.Capacity(); i++)
        if (rhs.SlotInUse(i))
            Add(*(rhs.strings[i]), rhs.integers[i]);
 
    return *this;
}

operator==()

bool StringIntHash::operator==

(

const StringIntHash &

rhs

)

const

Definition at line 674 of file StringHash.cpp.

{
    if (Capacity() != rhs.Capacity()) return false;
    if (Entries() != rhs.Entries()) return false;
    for (int i = 0; i < rhs.Capacity(); i++)
    {
        if(rhs.SlotInUse(i) != SlotInUse(i))
        {
            return(false);
        }
        if (rhs.SlotInUse(i))
        {
            if(*(strings[i]) != *(rhs.strings[i]))
            {
                return(false);
            }
            if(rhs.integers[i] != integers[i])
            {
                return(false);
            }
        }
    }
    return(true);
}

operator[]() [1/2]

String & StringIntHash::operator[] ( int i )

inline

Definition at line 268 of file StringHash.h.

    {
        return *(strings[i]);
    }

operator[]() [2/2]

const String & StringIntHash::operator[] ( int i ) const

inline

Definition at line 264 of file StringHash.h.

    {
        return *(strings[i]);
    }

SetInteger() [1/2]

void StringIntHash::SetInteger ( const String & key, int value )

inline

Definition at line 243 of file StringHash.h.

    {
        Add(key, value);
    }

SetInteger() [2/2]

void StringIntHash::SetInteger ( int i, int value )

inline

Definition at line 239 of file StringHash.h.

    {
        integers[i] = value;
    }

SetSize()

void StringIntHash::SetSize ( int newsize )

virtual

Implements StringHashBase.

Definition at line 269 of file StringHash.cpp.

{
    int newmask = newsize - 1;
 
    String   ** newstrings = new String * [newsize];
    int      * newintegers = new int [newsize];
    unsigned int * newkeys = new unsigned int [newsize];
 
    for (int i = 0; i < newsize; i++)
        newstrings[i] = NULL;
 
    for (unsigned int i = 0; i < size; i++)
        if (strings[i] != NULL)
        {
            unsigned int key = keys[i];
            unsigned int h   = key & newmask;
 
            while (newstrings[h] != NULL &&
                   (newkeys[h] != key || (!stringsEqual(*(newstrings[h]), *(strings[i])))))
                h = (h + 1) & newmask;
 
            newkeys[h] = key;
            newstrings[h] = strings[i];
            newintegers[h] = integers[i];
        }
 
    if(strings) delete [] strings;
    if(integers) delete [] integers;
    if(keys) delete [] keys;
 
    strings = newstrings;
    integers = newintegers;
    keys = newkeys;
    size = newsize;
    mask = newmask;
}

Shrink()

void StringIntHash::Shrink ( )

inline

Definition at line 210 of file StringHash.h.

    {
        SetSize(size / 2);
    }

SlotInUse()

bool StringIntHash::SlotInUse ( int index ) const

inline

Definition at line 280 of file StringHash.h.

    {
        return strings[index] != NULL;
    }

Member Data Documentation

count

unsigned int StringIntHash::count

protected

Definition at line 199 of file StringHash.h.

integers

int* StringIntHash::integers

protected

Definition at line 197 of file StringHash.h.

keys

unsigned int* StringIntHash::keys

protected

Definition at line 198 of file StringHash.h.

mask

unsigned int StringIntHash::mask

protected

Definition at line 200 of file StringHash.h.

size

unsigned int StringIntHash::size

protected

Definition at line 199 of file StringHash.h.

strings

String** StringIntHash::strings

protected

Definition at line 196 of file StringHash.h.

---

The documentation for this class was generated from the following files:

• general/StringHash.h
• general/StringHash.cpp