live
BasicHashTable.hh
Go to the documentation of this file.
1 /**********
2 This library is free software; you can redistribute it and/or modify it under
3 the terms of the GNU Lesser General Public License as published by the
4 Free Software Foundation; either version 3 of the License, or (at your
5 option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6 
7 This library is distributed in the hope that it will be useful, but WITHOUT
8 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9 FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10 more details.
11 
12 You should have received a copy of the GNU Lesser General Public License
13 along with this library; if not, write to the Free Software Foundation, Inc.,
14 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15 **********/
16 // Copyright (c) 1996-2022 Live Networks, Inc. All rights reserved.
17 // Basic Hash Table implementation
18 // C++ header
19 
20 #ifndef _BASIC_HASH_TABLE_HH
21 #define _BASIC_HASH_TABLE_HH
22 
23 #ifndef _HASH_TABLE_HH
24 #include "HashTable.hh"
25 #endif
26 #ifndef _NET_COMMON_H
27 #include <NetCommon.h> // to ensure that "uintptr_t" is defined
28 #endif
29 
30 // A simple hash table implementation, inspired by the hash table
31 // implementation used in Tcl 7.6: <http://www.tcl.tk/>
32 
33 #define SMALL_HASH_TABLE_SIZE 4
34 
35 class BasicHashTable: public HashTable {
36 private:
37  class TableEntry; // forward
38 
39 public:
40  BasicHashTable(int keyType);
41  virtual ~BasicHashTable();
42 
43  // Used to iterate through the members of the table:
44  class Iterator; friend class Iterator; // to make Sun's C++ compiler happy
45  class Iterator: public HashTable::Iterator {
46  public:
47  Iterator(BasicHashTable const& table);
48 
49  private: // implementation of inherited pure virtual functions
50  void* next(char const*& key); // returns 0 if none
51 
52  private:
54  unsigned fNextIndex; // index of next bucket to be enumerated after this
55  TableEntry* fNextEntry; // next entry in the current bucket
56  };
57 
58 private: // implementation of inherited pure virtual functions
59  virtual void* Add(char const* key, void* value);
60  // Returns the old value if different, otherwise 0
61  virtual Boolean Remove(char const* key);
62  virtual void* Lookup(char const* key) const;
63  // Returns 0 if not found
64  virtual unsigned numEntries() const;
65 
66 private:
67  class TableEntry {
68  public:
70  char const* key;
71  void* value;
72  };
73 
74  TableEntry* lookupKey(char const* key, unsigned& index) const;
75  // returns entry matching "key", or NULL if none
76  Boolean keyMatches(char const* key1, char const* key2) const;
77  // used to implement "lookupKey()"
78 
79  TableEntry* insertNewEntry(unsigned index, char const* key);
80  // creates a new entry, and inserts it in the table
81  void assignKey(TableEntry* entry, char const* key);
82  // used to implement "insertNewEntry()"
83 
84  void deleteEntry(unsigned index, TableEntry* entry);
85  void deleteKey(TableEntry* entry);
86  // used to implement "deleteEntry()"
87 
88  void rebuild(); // rebuilds the table as its size increases
89 
90  unsigned hashIndexFromKey(char const* key) const;
91  // used to implement many of the routines above
92 
93  unsigned randomIndex(uintptr_t i) const {
94  return (unsigned)(((i*1103515245) >> fDownShift) & fMask);
95  }
96 
97 private:
98  TableEntry** fBuckets; // pointer to bucket array
99  TableEntry* fStaticBuckets[SMALL_HASH_TABLE_SIZE];// used for small tables
101  int fKeyType;
102 };
103 
104 #endif
#define SMALL_HASH_TABLE_SIZE
unsigned char Boolean
Definition: Boolean.hh:25
Iterator(BasicHashTable const &table)
void * next(char const *&key)
BasicHashTable const & fTable
unsigned randomIndex(uintptr_t i) const
unsigned hashIndexFromKey(char const *key) const
void assignKey(TableEntry *entry, char const *key)
virtual unsigned numEntries() const
void deleteEntry(unsigned index, TableEntry *entry)
TableEntry * lookupKey(char const *key, unsigned &index) const
TableEntry * insertNewEntry(unsigned index, char const *key)
virtual ~BasicHashTable()
BasicHashTable(int keyType)
Boolean keyMatches(char const *key1, char const *key2) const
virtual void * Add(char const *key, void *value)
TableEntry ** fBuckets
unsigned fNumEntries
virtual void * Lookup(char const *key) const
unsigned fRebuildSize
void deleteKey(TableEntry *entry)
unsigned fNumBuckets
TableEntry * fStaticBuckets[SMALL_HASH_TABLE_SIZE]
virtual Boolean Remove(char const *key)