|
| 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 2.1 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-2015 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: |
| 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 | + |
| 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: |
| 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 | + |
| 97 | +private: |
| 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 |
0 commit comments