1 // madronalib: a C++ framework for DSP applications.
2 // Copyright (c) 2020 Madrona Labs LLC. http://www.madronalabs.com
3 // Distributed under the MIT license: http://madrona-labs.mit-license.org/
4
5 #include "MLSymbol.h"
6
7 namespace ml
8 {
9 #pragma mark SymbolTable
10
SymbolTable()11 SymbolTable::SymbolTable() { clear(); }
12
~SymbolTable()13 SymbolTable::~SymbolTable()
14 {
15 // TODO better protection on delete
16 // can this be avoided with more explicit setup / shutdown
17 // (RAII in main() )
18 // std::unique_lock<std::mutex> lock(mMutex);
19 }
20
21 // clear all symbols from the table.
clear()22 void SymbolTable::clear()
23 {
24 mSize = 0;
25 // std::unique_lock<std::mutex> lock(mMutex);
26
27 mSymbolTextsByID.clear();
28 mSymbolTextsByID.reserve(kDefaultSymbolTableSize);
29
30 for (int i = 0; i < kHashTableSize; ++i)
31 {
32 clearEntry(mHashTable[i]);
33 }
34
35 // add null entry - why?
36 addEntry(HashedCharArray());
37 }
38
39 // add an entry to the table. The entry must not already exist in the table.
40 // this must be the only way of modifying the symbol table.
addEntry(const HashedCharArray & hsl)41 SymbolID SymbolTable::addEntry(const HashedCharArray& hsl)
42 {
43 mSymbolTextsByID.emplace_back(TextFragment(hsl.pChars, static_cast<int>(hsl.len)));
44
45 size_t newID = mSize++;
46 mHashTable[hsl.hash].mIDVector.emplace_back(newID);
47 return newID;
48 }
49
getSymbolID(const HashedCharArray & hsl)50 SymbolID SymbolTable::getSymbolID(const HashedCharArray& hsl)
51 {
52 SymbolID r = 0;
53
54 // get the vector of symbol IDs matching this hash. It probably has one entry
55 // but may have more.
56 const std::vector<SymbolID>& bin = mHashTable[hsl.hash].mIDVector;
57 {
58 bool found = false;
59
60 std::unique_lock<std::mutex> lock(mHashTable[hsl.hash].mMutex);
61
62 for (auto ID : bin)
63 {
64 // there should be few collisions, so probably the first ID in the hash
65 // bin will be the symbol we are looking for. Unfortunately to test for
66 // equality we may have to compare the entire string.
67 TextFragment* binFragment = &mSymbolTextsByID[ID];
68 if (compareSizedCharArrays(binFragment->getText(), binFragment->lengthInBytes(), hsl.pChars,
69 hsl.len))
70 {
71 r = ID;
72 found = true;
73 break;
74 }
75 }
76
77 if (!found)
78 {
79 mSymbolTextsByID.emplace_back(TextFragment(hsl.pChars, static_cast<int>(hsl.len)));
80 r = mSize++;
81 mHashTable[hsl.hash].mIDVector.emplace_back(r);
82 }
83 }
84 return r;
85 }
86
getSymbolID(const char * sym)87 SymbolID SymbolTable::getSymbolID(const char* sym) { return getSymbolID(HashedCharArray(sym)); }
88
getSymbolID(const char * sym,size_t lengthBytes)89 SymbolID SymbolTable::getSymbolID(const char* sym, size_t lengthBytes)
90 {
91 return getSymbolID(HashedCharArray(sym, lengthBytes));
92 }
93
getSymbolTextByID(SymbolID symID)94 const TextFragment& SymbolTable::getSymbolTextByID(SymbolID symID)
95 {
96 return mSymbolTextsByID[symID];
97 }
98
dump()99 void SymbolTable::dump()
100 {
101 std::cout << "---------------------------------------------------------\n";
102 std::cout << mSymbolTextsByID.size() << " symbols:\n";
103
104 // print symbols in order of creation.
105 for (int i = 0; i < mSymbolTextsByID.size(); ++i)
106 {
107 const TextFragment& sym = mSymbolTextsByID[i];
108 std::cout << " ID " << i << " = " << sym << "\n";
109 }
110 // print nonzero entries in hash table
111 int hash = 0;
112 for (auto& tableEntry : mHashTable)
113 {
114 auto idVec = tableEntry.mIDVector;
115 size_t idVecLen = idVec.size();
116 if (idVecLen > 0)
117 {
118 std::cout << "#" << hash << " ";
119 for (auto id : idVec)
120 {
121 std::cout << id << " " << getSymbolTextByID(id) << " ";
122 }
123
124 std::cout << "\n";
125 }
126 hash++;
127 }
128 }
129
audit()130 int SymbolTable::audit()
131 {
132 int i = 0;
133 SymbolID i2{0};
134 bool OK = true;
135 size_t size = mSymbolTextsByID.size();
136
137 for (i = 0; i < size; ++i)
138 {
139 const TextFragment& sym = getSymbolTextByID(i);
140 const char* symChars = sym.getText();
141 Symbol symB(symChars);
142
143 i2 = symB.getID();
144 if (i != i2)
145 {
146 OK = false;
147 break;
148 }
149 if (i2 > size)
150 {
151 OK = false;
152 break;
153 }
154 }
155 if (!OK)
156 {
157 const TextFragment& s = getSymbolTextByID(i);
158 std::cout << "SymbolTable: error in symbol table, line " << i << ":\n";
159 std::cout << " ID " << i << " = " << s << ", ID B = " << i2 << "\n";
160 }
161 return OK;
162 }
163
operator <<(std::ostream & out,const Symbol r)164 std::ostream& operator<<(std::ostream& out, const Symbol r)
165 {
166 out << r.getTextFragment();
167 return out;
168 }
169
170 } // namespace ml
171