1/**********
2This library is free software; you can redistribute it and/or modify it under
3the terms of the GNU Lesser General Public License as published by the
4Free Software Foundation; either version 3 of the License, or (at your
5option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
6
7This library is distributed in the hope that it will be useful, but WITHOUT
8ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
9FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
10more details.
11
12You should have received a copy of the GNU Lesser General Public License
13along with this library; if not, write to the Free Software Foundation, Inc.,
1451 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
15**********/
16// Copyright (c) 1996-2020 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
35class BasicHashTable: public HashTable {
36private:
37 class TableEntry; // forward
38
39public:
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:
53 BasicHashTable const& fTable;
54 unsigned fNextIndex; // index of next bucket to be enumerated after this
55 TableEntry* fNextEntry; // next entry in the current bucket
56 };
57
58private: // 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
66private:
67 class TableEntry {
68 public:
69 TableEntry* fNext;
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
97private:
98 TableEntry** fBuckets; // pointer to bucket array
99 TableEntry* fStaticBuckets[SMALL_HASH_TABLE_SIZE];// used for small tables
100 unsigned fNumBuckets, fNumEntries, fRebuildSize, fDownShift, fMask;
101 int fKeyType;
102};
103
104#endif
105