BasicHashTable Class Reference

#include <BasicHashTable.hh>

Inheritance diagram for BasicHashTable:

Inheritance graph
[legend]
Collaboration diagram for BasicHashTable:

Collaboration graph
[legend]

Public Member Functions

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

Static Public Member Functions

static HashTable * create (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
TableEntry * lookupKey (char const *key, unsigned &index) const
Boolean keyMatches (char const *key1, char const *key2) const
TableEntry * insertNewEntry (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 (unsigned long i) const

Private Attributes

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

Friends

class Iterator

Data Structures

class  Iterator
class  TableEntry

Detailed Description

Definition at line 32 of file BasicHashTable.hh.

Constructor & Destructor Documentation

BasicHashTable::BasicHashTable ( int  keyType  ) 

Definition at line 34 of file BasicHashTable.cpp.

References fStaticBuckets, NULL, and SMALL_HASH_TABLE_SIZE.

00035   : fBuckets(fStaticBuckets), fNumBuckets(SMALL_HASH_TABLE_SIZE),
00036     fNumEntries(0), fRebuildSize(SMALL_HASH_TABLE_SIZE*REBUILD_MULTIPLIER),
00037     fDownShift(28), fMask(0x3), fKeyType(keyType) {
00038   for (unsigned i = 0; i < SMALL_HASH_TABLE_SIZE; ++i) {
00039     fStaticBuckets[i] = NULL;
00040   }
00041 }

BasicHashTable::~BasicHashTable (  )  [virtual]

Definition at line 43 of file BasicHashTable.cpp.

References deleteEntry(), fBuckets, fNumBuckets, fStaticBuckets, and NULL.

00043                                 {
00044   // Free all the entries in the table:
00045   for (unsigned i = 0; i < fNumBuckets; ++i) {
00046     TableEntry* entry;
00047     while ((entry = fBuckets[i]) != NULL) {
00048       deleteEntry(i, entry);
00049     }
00050   }
00051 
00052   // Also free the bucket array, if it was dynamically allocated:
00053   if (fBuckets != fStaticBuckets) delete[] fBuckets;
00054 }

Member Function Documentation

void * BasicHashTable::Add ( char const *  key,
void *  value 
) [private, virtual]

Implements HashTable.

Definition at line 56 of file BasicHashTable.cpp.

References fNumEntries, fRebuildSize, insertNewEntry(), lookupKey(), NULL, rebuild(), and BasicHashTable::TableEntry::value.

00056                                                       {
00057   void* oldValue;
00058   unsigned index;
00059   TableEntry* entry = lookupKey(key, index);
00060   if (entry != NULL) {
00061     // There's already an item with this key
00062     oldValue = entry->value;
00063   } else {
00064     // There's no existing entry; create a new one:
00065     entry = insertNewEntry(index, key);
00066     oldValue = NULL;
00067   }
00068   entry->value = value;
00069 
00070   // If the table has become too large, rebuild it with more buckets:
00071   if (fNumEntries >= fRebuildSize) rebuild();
00072 
00073   return oldValue;
00074 }

Boolean BasicHashTable::Remove ( char const *  key  )  [private, virtual]

Implements HashTable.

Definition at line 76 of file BasicHashTable.cpp.

References deleteEntry(), False, lookupKey(), NULL, and True.

00076                                               {
00077   unsigned index;
00078   TableEntry* entry = lookupKey(key, index);
00079   if (entry == NULL) return False; // no such entry
00080 
00081   deleteEntry(index, entry);
00082 
00083   return True;
00084 }

void * BasicHashTable::Lookup ( char const *  key  )  const [private, virtual]

Implements HashTable.

Definition at line 86 of file BasicHashTable.cpp.

References lookupKey(), NULL, and BasicHashTable::TableEntry::value.

00086                                                   {
00087   unsigned index;
00088   TableEntry* entry = lookupKey(key, index);
00089   if (entry == NULL) return NULL; // no such entry
00090 
00091   return entry->value;
00092 }

unsigned BasicHashTable::numEntries (  )  const [private, virtual]

Implements HashTable.

Definition at line 94 of file BasicHashTable.cpp.

References fNumEntries.

00094                                           {
00095   return fNumEntries;
00096 }

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

Definition at line 130 of file BasicHashTable.cpp.

References BasicHashTable::TableEntry::fNext, BasicHashTable::TableEntry::key, and NULL.

Referenced by Add(), Lookup(), and Remove().

00130                                                   {
00131   TableEntry* entry;
00132   index = hashIndexFromKey(key);
00133 
00134   for (entry = fBuckets[index]; entry != NULL; entry = entry->fNext) {
00135     if (keyMatches(key, entry->key)) break;
00136   }
00137 
00138   return entry;
00139 }

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

Definition at line 142 of file BasicHashTable.cpp.

References False, ONE_WORD_HASH_KEYS, STRING_HASH_KEYS, and True.

00142                                                      {
00143   // The way we check the keys for a match depends upon their type:
00144   if (fKeyType == STRING_HASH_KEYS) {
00145     return (strcmp(key1, key2) == 0);
00146   } else if (fKeyType == ONE_WORD_HASH_KEYS) {
00147     return (key1 == key2);
00148   } else {
00149     unsigned* k1 = (unsigned*)key1;
00150     unsigned* k2 = (unsigned*)key2;
00151 
00152     for (int i = 0; i < fKeyType; ++i) {
00153       if (k1[i] != k2[i]) return False; // keys differ
00154     }
00155     return True;
00156   }
00157 }

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

Definition at line 160 of file BasicHashTable.cpp.

References BasicHashTable::TableEntry::fNext.

Referenced by Add().

00160                                                 {
00161   TableEntry* entry = new TableEntry();
00162   entry->fNext = fBuckets[index];
00163   fBuckets[index] = entry;
00164 
00165   ++fNumEntries;
00166   assignKey(entry, key);
00167 
00168   return entry;
00169 }

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

Definition at line 171 of file BasicHashTable.cpp.

References fKeyType, BasicHashTable::TableEntry::key, ONE_WORD_HASH_KEYS, strDup(), and STRING_HASH_KEYS.

00171                                                                  {
00172   // The way we assign the key depends upon its type:
00173   if (fKeyType == STRING_HASH_KEYS) {
00174     entry->key = strDup(key);
00175   } else if (fKeyType == ONE_WORD_HASH_KEYS) {
00176     entry->key = key;
00177   } else if (fKeyType > 0) {
00178     unsigned* keyFrom = (unsigned*)key;
00179     unsigned* keyTo = new unsigned[fKeyType];
00180     for (int i = 0; i < fKeyType; ++i) keyTo[i] = keyFrom[i];
00181 
00182     entry->key = (char const*)keyTo;
00183   }
00184 }

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

Definition at line 186 of file BasicHashTable.cpp.

References deleteKey(), False, fBuckets, BasicHashTable::TableEntry::fNext, fNumEntries, NULL, and True.

Referenced by Remove(), and ~BasicHashTable().

00186                                                                   {
00187   TableEntry** ep = &fBuckets[index];
00188 
00189   Boolean foundIt = False;
00190   while (*ep != NULL) {
00191     if (*ep == entry) {
00192       foundIt = True;
00193       *ep = entry->fNext;
00194       break;
00195     }
00196     ep = &((*ep)->fNext);
00197   }
00198 
00199   if (!foundIt) { // shouldn't happen
00200 #ifdef DEBUG
00201     fprintf(stderr, "BasicHashTable[%p]::deleteEntry(%d,%p): internal error - not found (first entry %p", this, index, entry, fBuckets[index]);
00202     if (fBuckets[index] != NULL) fprintf(stderr, ", next entry %p", fBuckets[index]->fNext);
00203     fprintf(stderr, ")\n");
00204 #endif
00205   }
00206 
00207   --fNumEntries;
00208   deleteKey(entry);
00209   delete entry;
00210 }

void BasicHashTable::deleteKey ( TableEntry *  entry  )  [private]

Definition at line 212 of file BasicHashTable.cpp.

References fKeyType, BasicHashTable::TableEntry::key, NULL, and ONE_WORD_HASH_KEYS.

Referenced by deleteEntry().

00212                                                 {
00213   // The way we delete the key depends upon its type:
00214   if (fKeyType == ONE_WORD_HASH_KEYS) {
00215     entry->key = NULL;
00216   } else {
00217     delete[] (char*)entry->key;
00218     entry->key = NULL;
00219   }
00220 }

void BasicHashTable::rebuild (  )  [private]

Definition at line 222 of file BasicHashTable.cpp.

References fBuckets, fDownShift, fMask, fNumBuckets, fRebuildSize, fStaticBuckets, hashIndexFromKey(), and NULL.

Referenced by Add().

00222                              {
00223   // Remember the existing table size:
00224   unsigned oldSize = fNumBuckets;
00225   TableEntry** oldBuckets = fBuckets;
00226 
00227   // Create the new sized table:
00228   fNumBuckets *= 4;
00229   fBuckets = new TableEntry*[fNumBuckets];
00230   for (unsigned i = 0; i < fNumBuckets; ++i) {
00231     fBuckets[i] = NULL;
00232   }
00233   fRebuildSize *= 4;
00234   fDownShift -= 2;
00235   fMask = (fMask<<2)|0x3;
00236 
00237   // Rehash the existing entries into the new table:
00238   for (TableEntry** oldChainPtr = oldBuckets; oldSize > 0;
00239        --oldSize, ++oldChainPtr) {
00240     for (TableEntry* hPtr = *oldChainPtr; hPtr != NULL;
00241          hPtr = *oldChainPtr) {
00242       *oldChainPtr = hPtr->fNext;
00243 
00244       unsigned index = hashIndexFromKey(hPtr->key);
00245 
00246       hPtr->fNext = fBuckets[index];
00247       fBuckets[index] = hPtr;
00248     }
00249   }
00250 
00251   // Free the old bucket array, if it was dynamically allocated:
00252   if (oldBuckets != fStaticBuckets) delete[] oldBuckets;
00253 }

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

Definition at line 255 of file BasicHashTable.cpp.

References fKeyType, fMask, ONE_WORD_HASH_KEYS, randomIndex(), and STRING_HASH_KEYS.

Referenced by rebuild().

00255                                                                {
00256   unsigned result = 0;
00257 
00258   if (fKeyType == STRING_HASH_KEYS) {
00259     while (1) {
00260       char c = *key++;
00261       if (c == 0) break;
00262       result += (result<<3) + (unsigned)c;
00263     }
00264     result &= fMask;
00265   } else if (fKeyType == ONE_WORD_HASH_KEYS) {
00266     result = randomIndex((unsigned long)key);
00267   } else {
00268     unsigned* k = (unsigned*)key;
00269     unsigned long sum = 0;
00270     for (int i = 0; i < fKeyType; ++i) {
00271       sum += k[i];
00272     }
00273     result = randomIndex(sum);
00274   }
00275 
00276   return result;
00277 }

unsigned BasicHashTable::randomIndex ( unsigned long  i  )  const [inline, private]

Definition at line 90 of file BasicHashTable.hh.

References fDownShift, and fMask.

Referenced by hashIndexFromKey().

00090                                               {
00091     return (((i*1103515245) >> fDownShift) & fMask);
00092   }

HashTable * HashTable::create ( int  keyType  )  [static, inherited]

Definition at line 118 of file BasicHashTable.cpp.

Referenced by getSocketTable(), MPEG2TransportFileServerMediaSubsession::MPEG2TransportFileServerMediaSubsession(), MPEG2TransportStreamFramer::MPEG2TransportStreamFramer(), OnDemandServerMediaSubsession::OnDemandServerMediaSubsession(), and socketHashTable().

00118                                         {
00119   return new BasicHashTable(keyType);
00120 }

Boolean HashTable::IsEmpty (  )  const [inline, inherited]

Definition at line 41 of file HashTable.hh.

References HashTable::numEntries().

Referenced by SocketDescriptor::deregisterRTPInterface(), DirectedNetInterfaceSet::IsEmpty(), SocketDescriptor::registerRTPInterface(), MediaLookupTable::remove(), removeSocketDescription(), and unsetGroupsockBySocket().

00041 { return numEntries() == 0; }

void * HashTable::RemoveNext (  )  [inherited]

Definition at line 33 of file HashTable.cpp.

References HashTable::Iterator::create(), iter, MediaSubsessionIterator::next(), and HashTable::Remove().

Referenced by MPEG2TransportStreamFramer::clearPIDStatusTable(), MPEG2TransportFileServerMediaSubsession::~MPEG2TransportFileServerMediaSubsession(), OnDemandServerMediaSubsession::~OnDemandServerMediaSubsession(), RTPReceptionStatsDB::~RTPReceptionStatsDB(), RTPTransmissionStatsDB::~RTPTransmissionStatsDB(), and RTSPServer::~RTSPServer().

00033                             {
00034   Iterator* iter = Iterator::create(*this);
00035   char const* key;
00036   void* removedValue = iter->next(key);
00037   if (removedValue != 0) Remove(key);
00038 
00039   delete iter;
00040   return removedValue;
00041 }

Friends And Related Function Documentation

friend class Iterator [friend]

Definition at line 41 of file BasicHashTable.hh.

Referenced by HashTable::Iterator::create().

Field Documentation

TableEntry** BasicHashTable::fBuckets [private]

Definition at line 95 of file BasicHashTable.hh.

Referenced by deleteEntry(), rebuild(), and ~BasicHashTable().

TableEntry* BasicHashTable::fStaticBuckets[SMALL_HASH_TABLE_SIZE] [private]

Definition at line 96 of file BasicHashTable.hh.

Referenced by BasicHashTable(), rebuild(), and ~BasicHashTable().

unsigned BasicHashTable::fNumBuckets [private]

Definition at line 97 of file BasicHashTable.hh.

Referenced by rebuild(), and ~BasicHashTable().

unsigned BasicHashTable::fNumEntries [private]

Definition at line 97 of file BasicHashTable.hh.

Referenced by Add(), deleteEntry(), and numEntries().

unsigned BasicHashTable::fRebuildSize [private]

Definition at line 97 of file BasicHashTable.hh.

Referenced by Add(), and rebuild().

unsigned BasicHashTable::fDownShift [private]

Definition at line 97 of file BasicHashTable.hh.

Referenced by randomIndex(), and rebuild().

unsigned BasicHashTable::fMask [private]

Definition at line 97 of file BasicHashTable.hh.

Referenced by hashIndexFromKey(), randomIndex(), and rebuild().

int BasicHashTable::fKeyType [private]

Definition at line 98 of file BasicHashTable.hh.

Referenced by assignKey(), deleteKey(), and hashIndexFromKey().

The documentation for this class was generated from the following files:
Generated on Tue Jul 22 06:40:31 2008 for live by  doxygen 1.5.2