1 //===- HashTable.tcc ------------------------------------------------------===//
2 //
3 // The MCLinker Project
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 //===----------------------------------------------------------------------===//
11 // template implementation of HashTable
12 template <typename HashEntryTy,
13 typename HashFunctionTy,
14 typename EntryFactoryTy>
HashTable(size_type pSize)15 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::HashTable(
16 size_type pSize)
17 : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory() {
18 }
19
20 template <typename HashEntryTy,
21 typename HashFunctionTy,
22 typename EntryFactoryTy>
~HashTable()23 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::~HashTable() {
24 if (BaseTy::empty())
25 return;
26
27 /** clean up **/
28 for (unsigned int i = 0; i < BaseTy::m_NumOfBuckets; ++i) {
29 if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry &&
30 bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry) {
31 m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry);
32 }
33 }
34 }
35
36 template <typename HashEntryTy,
37 typename HashFunctionTy,
38 typename EntryFactoryTy>
clear()39 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::clear() {
40 if (BaseTy::empty())
41 return;
42
43 /** clean up **/
44 for (unsigned int i = 0; i < BaseTy::m_NumOfBuckets; ++i) {
45 if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry) {
46 if (bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry) {
47 m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry);
48 }
49 BaseTy::m_Buckets[i].Entry = bucket_type::getEmptyBucket();
50 }
51 }
52
53 BaseTy::clear();
54 }
55
56 /// insert - insert a new element to the container. If the element already
57 // exist, return the element.
58 template <typename HashEntryTy,
59 typename HashFunctionTy,
60 typename EntryFactoryTy>
61 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type*
insert(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey,bool & pExist)62 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::insert(
63 const typename HashTable<HashEntryTy,
64 HashFunctionTy,
65 EntryFactoryTy>::key_type& pKey,
66 bool& pExist) {
67 unsigned int index = BaseTy::lookUpBucketFor(pKey);
68 bucket_type& bucket = BaseTy::m_Buckets[index];
69 entry_type* entry = bucket.Entry;
70 if (bucket_type::getEmptyBucket() != entry &&
71 bucket_type::getTombstone() != entry) {
72 // Already exist in the table
73 pExist = true;
74 return entry;
75 }
76
77 // find a tombstone
78 if (bucket_type::getTombstone() == entry)
79 --BaseTy::m_NumOfTombstones;
80
81 entry = bucket.Entry = m_EntryFactory.produce(pKey);
82 ++BaseTy::m_NumOfEntries;
83 BaseTy::mayRehash();
84 pExist = false;
85 return entry;
86 }
87
88 /// erase - remove the elements with the pKey
89 // @return the number of removed elements.
90 template <typename HashEntryTy,
91 typename HashFunctionTy,
92 typename EntryFactoryTy>
93 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
erase(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)94 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::erase(
95 const typename HashTable<HashEntryTy,
96 HashFunctionTy,
97 EntryFactoryTy>::key_type& pKey) {
98 int index;
99 if ((index = BaseTy::findKey(pKey)) == -1)
100 return 0;
101
102 bucket_type& bucket = BaseTy::m_Buckets[index];
103 m_EntryFactory.destroy(bucket.Entry);
104 bucket.Entry = bucket_type::getTombstone();
105
106 --BaseTy::m_NumOfEntries;
107 ++BaseTy::m_NumOfTombstones;
108 BaseTy::mayRehash();
109 return 1;
110 }
111
112 template <typename HashEntryTy,
113 typename HashFunctionTy,
114 typename EntryFactoryTy>
115 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
find(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)116 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find(
117 const typename HashTable<HashEntryTy,
118 HashFunctionTy,
119 EntryFactoryTy>::key_type& pKey) {
120 int index;
121 if ((index = BaseTy::findKey(pKey)) == -1)
122 return end();
123 return iterator(this, index);
124 }
125
126 template <typename HashEntryTy,
127 typename HashFunctionTy,
128 typename EntryFactoryTy>
129 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
find(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const130 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find(
131 const typename HashTable<HashEntryTy,
132 HashFunctionTy,
133 EntryFactoryTy>::key_type& pKey) const {
134 int index;
135 if ((index = BaseTy::findKey(pKey)) == -1)
136 return end();
137 return const_iterator(this, index);
138 }
139
140 template <typename HashEntryTy,
141 typename HashFunctionTy,
142 typename EntryFactoryTy>
143 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
count(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const144 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::count(
145 const typename HashTable<HashEntryTy,
146 HashFunctionTy,
147 EntryFactoryTy>::key_type& pKey) const {
148 const_chain_iterator bucket, bEnd = end(pKey);
149 size_type count = 0;
150 for (bucket = begin(pKey); bucket != bEnd; ++bucket)
151 ++count;
152 return count;
153 }
154
155 template <typename HashEntryTy,
156 typename HashFunctionTy,
157 typename EntryFactoryTy>
load_factor() const158 float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor()
159 const {
160 return ((float)BaseTy::m_NumOfEntries / (float)BaseTy::m_NumOfBuckets);
161 }
162
163 template <typename HashEntryTy,
164 typename HashFunctionTy,
165 typename EntryFactoryTy>
rehash()166 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash() {
167 BaseTy::mayRehash();
168 }
169
170 template <typename HashEntryTy,
171 typename HashFunctionTy,
172 typename EntryFactoryTy>
rehash(typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::size_type pCount)173 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash(
174 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
175 pCount) {
176 BaseTy::doRehash(pCount);
177 }
178
179 template <typename HashEntryTy,
180 typename HashFunctionTy,
181 typename EntryFactoryTy>
182 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
begin()183 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() {
184 if (BaseTy::empty())
185 return end();
186 unsigned int index = 0;
187 while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry ||
188 bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) {
189 ++index;
190 }
191 return iterator(this, index);
192 }
193
194 template <typename HashEntryTy,
195 typename HashFunctionTy,
196 typename EntryFactoryTy>
197 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
end()198 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() {
199 return iterator(NULL, 0);
200 }
201
202 template <typename HashEntryTy,
203 typename HashFunctionTy,
204 typename EntryFactoryTy>
205 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
begin() const206 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() const {
207 if (BaseTy::empty())
208 return end();
209 unsigned int index = 0;
210 while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry ||
211 bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) {
212 ++index;
213 }
214 return const_iterator(this, index);
215 }
216
217 template <typename HashEntryTy,
218 typename HashFunctionTy,
219 typename EntryFactoryTy>
220 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
end() const221 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const {
222 return const_iterator(NULL, 0);
223 }
224
225 template <typename HashEntryTy,
226 typename HashFunctionTy,
227 typename EntryFactoryTy>
228 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
begin(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)229 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin(
230 const typename HashTable<HashEntryTy,
231 HashFunctionTy,
232 EntryFactoryTy>::key_type& pKey) {
233 return chain_iterator(this, pKey, 0x0);
234 }
235
236 template <typename HashEntryTy,
237 typename HashFunctionTy,
238 typename EntryFactoryTy>
239 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
end(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)240 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
241 const typename HashTable<HashEntryTy,
242 HashFunctionTy,
243 EntryFactoryTy>::key_type& pKey) {
244 return chain_iterator();
245 }
246
247 template <typename HashEntryTy,
248 typename HashFunctionTy,
249 typename EntryFactoryTy>
250 typename HashTable<HashEntryTy,
251 HashFunctionTy,
252 EntryFactoryTy>::const_chain_iterator
begin(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const253 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin(
254 const typename HashTable<HashEntryTy,
255 HashFunctionTy,
256 EntryFactoryTy>::key_type& pKey) const {
257 return const_chain_iterator(this, pKey, 0x0);
258 }
259
260 template <typename HashEntryTy,
261 typename HashFunctionTy,
262 typename EntryFactoryTy>
263 typename HashTable<HashEntryTy,
264 HashFunctionTy,
265 EntryFactoryTy>::const_chain_iterator
end(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const266 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
267 const typename HashTable<HashEntryTy,
268 HashFunctionTy,
269 EntryFactoryTy>::key_type& pKey) const {
270 return const_chain_iterator();
271 }
272