live
Data Structures | Public Member Functions | Static Public Member Functions | Private Member Functions | Private Attributes | Friends
BasicHashTable Class Reference

#include <BasicHashTable.hh>

Inheritance diagram for BasicHashTable:
Inheritance graph
[legend]
Collaboration diagram for BasicHashTable:
Collaboration graph
[legend]

Data Structures

class  Iterator
 
class  TableEntry
 

Public Member Functions

 BasicHashTable (int keyType)
 
virtual ~BasicHashTable ()
 
Boolean IsEmpty () const
 
void * RemoveNext ()
 
void * getFirst ()
 

Static Public Member Functions

static HashTablecreate (int keyType)
 

Private Member Functions

virtual void * Add (char const *key, void *value)
 
virtual Boolean Remove (char const *key)
 
virtual void * Lookup (char const *key) const
 
virtual unsigned numEntries () const
 
TableEntrylookupKey (char const *key, unsigned &index) const
 
Boolean keyMatches (char const *key1, char const *key2) const
 
TableEntryinsertNewEntry (unsigned index, char const *key)
 
void assignKey (TableEntry *entry, char const *key)
 
void deleteEntry (unsigned index, TableEntry *entry)
 
void deleteKey (TableEntry *entry)
 
void rebuild ()
 
unsigned hashIndexFromKey (char const *key) const
 
unsigned randomIndex (uintptr_t i) const
 

Private Attributes

TableEntry ** fBuckets
 
TableEntryfStaticBuckets [SMALL_HASH_TABLE_SIZE]
 
unsigned fNumBuckets
 
unsigned fNumEntries
 
unsigned fRebuildSize
 
unsigned fDownShift
 
unsigned fMask
 
int fKeyType
 

Friends

class Iterator
 

Detailed Description

Definition at line 35 of file BasicHashTable.hh.

Constructor & Destructor Documentation

◆ BasicHashTable()

BasicHashTable::BasicHashTable ( int  keyType)

◆ ~BasicHashTable()

virtual BasicHashTable::~BasicHashTable ( )
virtual

Member Function Documentation

◆ Add()

virtual void* BasicHashTable::Add ( char const *  key,
void *  value 
)
privatevirtual

Implements HashTable.

◆ assignKey()

void BasicHashTable::assignKey ( TableEntry entry,
char const *  key 
)
private

◆ create()

static HashTable* HashTable::create ( int  keyType)
staticinherited

◆ deleteEntry()

void BasicHashTable::deleteEntry ( unsigned  index,
TableEntry entry 
)
private

◆ deleteKey()

void BasicHashTable::deleteKey ( TableEntry entry)
private

◆ getFirst()

void* HashTable::getFirst ( )
inherited

◆ hashIndexFromKey()

unsigned BasicHashTable::hashIndexFromKey ( char const *  key) const
private

◆ insertNewEntry()

TableEntry* BasicHashTable::insertNewEntry ( unsigned  index,
char const *  key 
)
private

◆ IsEmpty()

Boolean HashTable::IsEmpty ( ) const
inlineinherited

Definition at line 41 of file HashTable.hh.

41 { return numEntries() == 0; }
virtual unsigned numEntries() const =0

References HashTable::numEntries().

◆ keyMatches()

Boolean BasicHashTable::keyMatches ( char const *  key1,
char const *  key2 
) const
private

◆ Lookup()

virtual void* BasicHashTable::Lookup ( char const *  key) const
privatevirtual

Implements HashTable.

◆ lookupKey()

TableEntry* BasicHashTable::lookupKey ( char const *  key,
unsigned &  index 
) const
private

◆ numEntries()

virtual unsigned BasicHashTable::numEntries ( ) const
privatevirtual

Implements HashTable.

◆ randomIndex()

unsigned BasicHashTable::randomIndex ( uintptr_t  i) const
inlineprivate

Definition at line 93 of file BasicHashTable.hh.

93  {
94  return (unsigned)(((i*1103515245) >> fDownShift) & fMask);
95  }

References fDownShift, and fMask.

◆ rebuild()

void BasicHashTable::rebuild ( )
private

◆ Remove()

virtual Boolean BasicHashTable::Remove ( char const *  key)
privatevirtual

Implements HashTable.

◆ RemoveNext()

void* HashTable::RemoveNext ( )
inherited

Friends And Related Function Documentation

◆ Iterator

friend class Iterator
friend

Definition at line 44 of file BasicHashTable.hh.

Field Documentation

◆ fBuckets

TableEntry** BasicHashTable::fBuckets
private

Definition at line 98 of file BasicHashTable.hh.

◆ fDownShift

unsigned BasicHashTable::fDownShift
private

Definition at line 100 of file BasicHashTable.hh.

Referenced by randomIndex().

◆ fKeyType

int BasicHashTable::fKeyType
private

Definition at line 101 of file BasicHashTable.hh.

◆ fMask

unsigned BasicHashTable::fMask
private

Definition at line 100 of file BasicHashTable.hh.

Referenced by randomIndex().

◆ fNumBuckets

unsigned BasicHashTable::fNumBuckets
private

Definition at line 100 of file BasicHashTable.hh.

◆ fNumEntries

unsigned BasicHashTable::fNumEntries
private

Definition at line 100 of file BasicHashTable.hh.

◆ fRebuildSize

unsigned BasicHashTable::fRebuildSize
private

Definition at line 100 of file BasicHashTable.hh.

◆ fStaticBuckets

TableEntry* BasicHashTable::fStaticBuckets[SMALL_HASH_TABLE_SIZE]
private

Definition at line 99 of file BasicHashTable.hh.


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