BasicUsageEnvironment/include/BasicHashTable.hh

Go to the documentation of this file.
00001 /**********
00002 This library is free software; you can redistribute it and/or modify it under
00003 the terms of the GNU Lesser General Public License as published by the
00004 Free Software Foundation; either version 2.1 of the License, or (at your
00005 option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
00006 
00007 This library is distributed in the hope that it will be useful, but WITHOUT
00008 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
00009 FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public License for
00010 more details.
00011 
00012 You should have received a copy of the GNU Lesser General Public License
00013 along with this library; if not, write to the Free Software Foundation, Inc.,
00014 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301  USA
00015 **********/
00016 // Copyright (c) 1996-2008 Live Networks, Inc.  All rights reserved.
00017 // Basic Hash Table implementation
00018 // C++ header
00019 
00020 #ifndef _BASIC_HASH_TABLE_HH
00021 #define _BASIC_HASH_TABLE_HH
00022 
00023 #ifndef _HASH_TABLE_HH
00024 #include "HashTable.hh"
00025 #endif
00026 
00027 // A simple hash table implementation, inspired by the hash table
00028 // implementation used in Tcl 7.6: <http://www.tcl.tk/>
00029 
00030 #define SMALL_HASH_TABLE_SIZE 4
00031 
00032 class BasicHashTable: public HashTable {
00033 private:
00034         class TableEntry; // forward
00035 
00036 public:
00037   BasicHashTable(int keyType);
00038   virtual ~BasicHashTable();
00039 
00040   // Used to iterate through the members of the table:
00041   class Iterator; friend class Iterator; // to make Sun's C++ compiler happy
00042   class Iterator: public HashTable::Iterator {
00043   public:
00044     Iterator(BasicHashTable& table);
00045 
00046   private: // implementation of inherited pure virtual functions
00047     void* next(char const*& key); // returns 0 if none
00048 
00049   private:
00050     BasicHashTable& fTable;
00051     unsigned fNextIndex; // index of next bucket to be enumerated after this
00052     TableEntry* fNextEntry; // next entry in the current bucket
00053   };
00054 
00055 private: // implementation of inherited pure virtual functions
00056   virtual void* Add(char const* key, void* value);
00057   // Returns the old value if different, otherwise 0
00058   virtual Boolean Remove(char const* key);
00059   virtual void* Lookup(char const* key) const;
00060   // Returns 0 if not found
00061   virtual unsigned numEntries() const;
00062 
00063 private:
00064   class TableEntry {
00065   public:
00066     TableEntry* fNext;
00067     char const* key;
00068     void* value;
00069   };
00070 
00071   TableEntry* lookupKey(char const* key, unsigned& index) const;
00072     // returns entry matching "key", or NULL if none
00073   Boolean keyMatches(char const* key1, char const* key2) const;
00074     // used to implement "lookupKey()"
00075 
00076   TableEntry* insertNewEntry(unsigned index, char const* key);
00077     // creates a new entry, and inserts it in the table
00078   void assignKey(TableEntry* entry, char const* key);
00079     // used to implement "insertNewEntry()"
00080 
00081   void deleteEntry(unsigned index, TableEntry* entry);
00082   void deleteKey(TableEntry* entry);
00083     // used to implement "deleteEntry()"
00084 
00085   void rebuild(); // rebuilds the table as its size increases
00086 
00087   unsigned hashIndexFromKey(char const* key) const;
00088     // used to implement many of the routines above
00089 
00090   unsigned randomIndex(unsigned long i) const {
00091     return (((i*1103515245) >> fDownShift) & fMask);
00092   }
00093 
00094 private:
00095   TableEntry** fBuckets; // pointer to bucket array
00096   TableEntry* fStaticBuckets[SMALL_HASH_TABLE_SIZE];// used for small tables
00097   unsigned fNumBuckets, fNumEntries, fRebuildSize, fDownShift, fMask;
00098   int fKeyType;
00099 };
00100 
00101 #endif

Generated on Tue Oct 7 15:38:08 2008 for live by  doxygen 1.5.2