/**********
This library is free software; you can redistribute it and/or modify it under
the terms of the GNU Lesser General Public License as published by the
Free Software Foundation; either version 3 of the License, or (at your
option) any later version. (See <http://www.gnu.org/copyleft/lesser.html>.)
This library is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for
more details.
You should have received a copy of the GNU Lesser General Public License
along with this library; if not, write to the Free Software Foundation, Inc.,
51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
**********/
// Copyright (c) 1996-2024 Live Networks, Inc. All rights reserved.
// Basic Hash Table implementation
// Implementation
#include "BasicHashTable.hh"
#include "strDup.hh"
#if defined(__WIN32__) || defined(_WIN32)
#else
#include <stddef.h>
#endif
#include <string.h>
// When there are this many entries per bucket, on average, rebuild
// the table to increase the number of buckets
#define REBUILD_MULTIPLIER 3
BasicHashTable::BasicHashTable(int keyType)
: fBuckets(fStaticBuckets), fNumBuckets(SMALL_HASH_TABLE_SIZE),
fNumEntries(0), fRebuildSize(SMALL_HASH_TABLE_SIZE*REBUILD_MULTIPLIER),
fDownShift(28), fMask(0x3), fKeyType(keyType) {
for (unsigned i = 0; i < SMALL_HASH_TABLE_SIZE; ++i) {
fStaticBuckets[i] = NULL;
}
}
BasicHashTable::~BasicHashTable() {
// Free all the entries in the table:
for (unsigned i = 0; i < fNumBuckets; ++i) {
TableEntry* entry;
while ((entry = fBuckets[i]) != NULL) {
deleteEntry(i, entry);
}
}
// Also free the bucket array, if it was dynamically allocated:
if (fBuckets != fStaticBuckets) delete[] fBuckets;
}
// 添加一个键值对到哈希表，2024-07-22 23:49:05
void* BasicHashTable::Add(char const* key, void* value) {
void* oldValue;
unsigned index;
TableEntry* entry = lookupKey(key, index);
if (entry != NULL) {
// There's already an item with this key
oldValue = entry->value;
} else {
// There's no existing entry; create a new one:
entry = insertNewEntry(index, key);
oldValue = NULL;
}
entry->value = value;
// If the table has become too large, rebuild it with more buckets:
if (fNumEntries >= fRebuildSize) rebuild();
return oldValue;
}
// 删除一个键值对(entry)，2024-07-22 23:49:08
Boolean BasicHashTable::Remove(char const* key) {
unsigned index;
TableEntry* entry = lookupKey(key, index);
if (entry == NULL) return False; // no such entry
deleteEntry(index, entry);
return True;
}
// 查找，根据key找到value，2024-07-22 23:48:20
void* BasicHashTable::Lookup(char const* key) const {
unsigned index;
TableEntry* entry = lookupKey(key, index);
if (entry == NULL) return NULL; // no such entry
return entry->value;
}
// 哈希表总的键值对(entry)个数，2024-07-22 23:47:35
unsigned BasicHashTable::numEntries() const {
return fNumEntries;
}
// 迭代器，用于迭代传入的哈希表 2024-07-22 23:43:05
BasicHashTable::Iterator::Iterator(BasicHashTable const& table)
: fTable(table), fNextIndex(0), fNextEntry(NULL) {
}
// 返回下一个键值对(entry)的关键字(key)和值(value),2024-07-22 23:46:50
void* BasicHashTable::Iterator::next(char const*& key) {
while (fNextEntry == NULL) {
if (fNextIndex >= fTable.fNumBuckets) return NULL;
fNextEntry = fTable.fBuckets[fNextIndex++];
}
BasicHashTable::TableEntry* entry = fNextEntry;
fNextEntry = entry->fNext;
key = entry->key;
return entry->value;
}
////////// Implementation of HashTable creation functions //////////
HashTable* HashTable::create(int keyType) {
return new BasicHashTable(keyType);// 父类指针指向子类对象 2024-07-22 23:44:39
}
HashTable::Iterator* HashTable::Iterator::create(HashTable const& hashTable) {
// "hashTable" is assumed to be a BasicHashTable
return new BasicHashTable::Iterator((BasicHashTable const&)hashTable);// 父类指针指向子类对象 2024-07-22 23:44:39
}
////////// Implementation of internal member functions //////////
// 根据key找到一个键值对(entry),下标index，2024-07-22 23:36:55
BasicHashTable::TableEntry* BasicHashTable
::lookupKey(char const* key, unsigned& index) const {
TableEntry* entry;
index = hashIndexFromKey(key);
for (entry = fBuckets[index]; entry != NULL; entry = entry->fNext) {
if (keyMatches(key, entry->key)) break;
}
return entry;
}
// 比较两个key是否一致 2024-07-22 23:35:24
Boolean BasicHashTable
::keyMatches(char const* key1, char const* key2) const {
// The way we check the keys for a match depends upon their type:
if (fKeyType == STRING_HASH_KEYS) {
return (strcmp(key1, key2) == 0);
} else if (fKeyType == ONE_WORD_HASH_KEYS) {
return (key1 == key2);
} else {
unsigned* k1 = (unsigned*)key1;
unsigned* k2 = (unsigned*)key2;
for (int i = 0; i < fKeyType; ++i) {
if (k1[i] != k2[i]) return False; // keys differ
}
return True;
}
}
// 生成一个entry, 插入到链表，并给entry->key赋值，2024-07-22 23:34:42
BasicHashTable::TableEntry* BasicHashTable
::insertNewEntry(unsigned index, char const* key) {
TableEntry* entry = new TableEntry();
entry->fNext = fBuckets[index];
fBuckets[index] = entry;
++fNumEntries;
assignKey(entry, key);
return entry;
}
// 根据键值类型、key值，创建一个 Key，并赋值到entry的key字段 2024-07-22 21:16:20
void BasicHashTable::assignKey(TableEntry* entry, char const* key) {
// The way we assign the key depends upon its type:
if (fKeyType == STRING_HASH_KEYS) {
entry->key = strDup(key);
} else if (fKeyType == ONE_WORD_HASH_KEYS) {
entry->key = key;
} else if (fKeyType > 0) {
unsigned* keyFrom = (unsigned*)key;
unsigned* keyTo = new unsigned[fKeyType];
for (int i = 0; i < fKeyType; ++i) keyTo[i] = keyFrom[i];
entry->key = (char const*)keyTo;
}
}
// 删除指定下标的一个键值对(Entry)，2024-07-22 21:20:18
void BasicHashTable::deleteEntry(unsigned index, TableEntry* entry) {
TableEntry** ep = &fBuckets[index]; // 找到存在数组的位置
Boolean foundIt = False;
while (*ep != NULL) { // 遍历链表
if (*ep == entry) {
foundIt = True;
*ep = entry->fNext;
break;
}
ep = &((*ep)->fNext);
}
if (!foundIt) { // shouldn't happen
#ifdef DEBUG
fprintf(stderr, "BasicHashTable[%p]::deleteEntry(%d,%p): internal error - not found (first entry %p", this, index, entry, fBuckets[index]);
if (fBuckets[index] != NULL) fprintf(stderr, ", next entry %p", fBuckets[index]->fNext);
fprintf(stderr, ")\n");
#endif
}
--fNumEntries;
deleteKey(entry);
delete entry;
}
// 删除一个键值对(Entry)的Key，2024-07-22 21:21:12
void BasicHashTable::deleteKey(TableEntry* entry) {
// The way we delete the key depends upon its type:
if (fKeyType == ONE_WORD_HASH_KEYS) {
entry->key = NULL;
} else {
delete[] (char*)entry->key;
entry->key = NULL;
}
}
// 重新建立一个哈希表，2024-07-22 21:22:08
void BasicHashTable::rebuild() {
// Remember the existing table size:
unsigned oldSize = fNumBuckets;
TableEntry** oldBuckets = fBuckets;
// Create the new sized table:
fNumBuckets *= 4;
fBuckets = new TableEntry*[fNumBuckets];
for (unsigned i = 0; i < fNumBuckets; ++i) {
fBuckets[i] = NULL;
}
fRebuildSize *= 4;
fDownShift -= 2;
fMask = (fMask<<2)|0x3;
// Rehash the existing entries into the new table:
for (TableEntry** oldChainPtr = oldBuckets; oldSize > 0;
--oldSize, ++oldChainPtr) {
for (TableEntry* hPtr = *oldChainPtr; hPtr != NULL;
hPtr = *oldChainPtr) {
*oldChainPtr = hPtr->fNext;
unsigned index = hashIndexFromKey(hPtr->key);
