1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
|
// AlphabetMap.cpp
//
/////////////////////////////////////////////////////////////////////////////
//
// Copyright (c) 2002 Iain Murray
//
/////////////////////////////////////////////////////////////////////////////
#include "AlphabetMap.h"
using namespace Dasher;
using namespace std;
alphabet_map::alphabet_map(unsigned int InitialTableSize)
: HashTable(InitialTableSize<<1), Undefined(0)
{
Entries.reserve(InitialTableSize);
}
void alphabet_map::Add(const string& Key, symbol Value)
{
RecursiveAdd(Key, Value, false);
}
void alphabet_map::RecursiveAdd(const string& Key, symbol Value, bool PrefixFlag)
{
Entry*& HashEntry = HashTable[Hash(Key)];
// Loop through Entries with the correct Hash value.
for (Entry* i = HashEntry; i; i=i->Next) {
if (i->Key==Key) {
if (PrefixFlag) {
// Just tagging - don't change symbol. Recurse if necessary
i->KeyIsPrefix = true;
if (Key.size()>1)
RecursiveAdd(Key.substr(Key.size()-1), Undefined, true);
} else {
// Add symbol and leave
i->Symbol = Value;
}
return;
}
}
// When hash table gets 1/2 full...
// (no I haven't optimised when to resize)
if (Entries.size()<<1 >= HashTable.size()) {
// Double up all the storage
HashTable.clear();
HashTable.resize(Entries.size()<<2);
Entries.reserve(Entries.size()<<1);
// Rehash as the pointers will all be mangled.
for (uint j=0; j<Entries.size(); j++) {
Entry*& HashEntry2 = HashTable[Hash(Entries[j].Key)];
Entries[j].Next = HashEntry2;
HashEntry2 = &Entries[j];
}
// Have to recall this function as the key's hash needs recalculating
RecursiveAdd(Key, Value, PrefixFlag);
return;
}
Entries.push_back(Entry(Key, Value, HashEntry));
HashEntry = &Entries.back();
}
symbol alphabet_map::Get(const string& Key, bool* KeyIsPrefix) const
{
// Loop through Entries with the correct Hash value.
for (Entry* i = HashTable[Hash(Key)]; i; i=i->Next) {
if (i->Key==Key) {
if (KeyIsPrefix!=0)
*KeyIsPrefix = i->KeyIsPrefix;
return i->Symbol;
}
}
if (KeyIsPrefix!=0)
*KeyIsPrefix = false;
return Undefined;
}
|
