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(size_type pSize)
16 : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory()
17 {
18 }
19
20 template<typename HashEntryTy,
21 typename HashFunctionTy,
22 typename EntryFactoryTy>
~HashTable()23 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::~HashTable()
24 {
25 if (BaseTy::empty())
26 return;
27
28 /** clean up **/
29 for (unsigned int i=0; i < BaseTy::m_NumOfBuckets; ++i) {
30 if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry &&
31 bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry ) {
32 m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry);
33 }
34 }
35 }
36
37 template<typename HashEntryTy,
38 typename HashFunctionTy,
39 typename EntryFactoryTy>
clear()40 void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::clear()
41 {
42 if (BaseTy::empty())
43 return;
44
45 /** clean up **/
46 for (unsigned int i=0; i < BaseTy::m_NumOfBuckets; ++i) {
47 if (bucket_type::getEmptyBucket() != BaseTy::m_Buckets[i].Entry ) {
48 if (bucket_type::getTombstone() != BaseTy::m_Buckets[i].Entry ) {
49 m_EntryFactory.destroy(BaseTy::m_Buckets[i].Entry);
50 }
51 BaseTy::m_Buckets[i].Entry = bucket_type::getEmptyBucket();
52 }
53 }
54
55 BaseTy::clear();
56 }
57
58 /// insert - insert a new element to the container. If the element already
59 // exist, return the element.
60 template<typename HashEntryTy,
61 typename HashFunctionTy,
62 typename EntryFactoryTy>
63 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type*
insert(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey,bool & pExist)64 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::insert(
65 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey,
66 bool& pExist)
67 {
68 unsigned int index = BaseTy::lookUpBucketFor(pKey);
69 bucket_type& bucket = BaseTy::m_Buckets[index];
70 entry_type* entry = bucket.Entry;
71 if (bucket_type::getEmptyBucket() != entry &&
72 bucket_type::getTombstone() != entry) {
73 // Already exist in the table
74 pExist = true;
75 return entry;
76 }
77
78 // find a tombstone
79 if (bucket_type::getTombstone() == entry)
80 --BaseTy::m_NumOfTombstones;
81
82 entry = bucket.Entry = m_EntryFactory.produce(pKey);
83 ++BaseTy::m_NumOfEntries;
84 BaseTy::mayRehash();
85 pExist = false;
86 return entry;
87 }
88
89 /// erase - remove the elements with the pKey
90 // @return the number of removed elements.
91 template<typename HashEntryTy,
92 typename HashFunctionTy,
93 typename EntryFactoryTy>
94 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
erase(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)95 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::erase(
96 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
97 {
98 int index;
99 if (-1 == (index = BaseTy::findKey(pKey)))
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, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
118 {
119 int index;
120 if (-1 == (index = BaseTy::findKey(pKey)))
121 return end();
122 return iterator(this, index);
123 }
124
125 template<typename HashEntryTy,
126 typename HashFunctionTy,
127 typename EntryFactoryTy>
128 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
find(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const129 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::find(
130 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
131 {
132 int index;
133 if (-1 == (index = BaseTy::findKey(pKey)))
134 return end();
135 return const_iterator(this, index);
136 }
137
138 template<typename HashEntryTy,
139 typename HashFunctionTy,
140 typename EntryFactoryTy>
141 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
count(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const142 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::count(
143 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
144 {
145 const_chain_iterator bucket, bEnd = end(pKey);
146 size_type count = 0;
147 for (bucket = begin(pKey); bucket != bEnd; ++bucket)
148 ++count;
149 return count;
150 }
151
152 template<typename HashEntryTy,
153 typename HashFunctionTy,
154 typename EntryFactoryTy>
load_factor() const155 float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor() const
156 {
157 return ((float)BaseTy::m_NumOfEntries/(float)BaseTy::m_NumOfBuckets);
158 }
159
160 template<typename HashEntryTy,
161 typename HashFunctionTy,
162 typename EntryFactoryTy>
163 void
rehash()164 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash()
165 {
166 BaseTy::mayRehash();
167 }
168
169 template<typename HashEntryTy,
170 typename HashFunctionTy,
171 typename EntryFactoryTy>
172 void
rehash(typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::size_type pCount)173 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash(
174 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type pCount)
175 {
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 {
185 if (BaseTy::empty())
186 return end();
187 unsigned int index = 0;
188 while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry ||
189 bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) {
190 ++index;
191 }
192 return iterator(this, index);
193 }
194
195 template<typename HashEntryTy,
196 typename HashFunctionTy,
197 typename EntryFactoryTy>
198 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
end()199 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end()
200 {
201 return iterator(NULL, 0);
202 }
203
204 template<typename HashEntryTy,
205 typename HashFunctionTy,
206 typename EntryFactoryTy>
207 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
begin() const208 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() const
209 {
210 if (BaseTy::empty())
211 return end();
212 unsigned int index = 0;
213 while (bucket_type::getTombstone() == BaseTy::m_Buckets[index].Entry ||
214 bucket_type::getEmptyBucket() == BaseTy::m_Buckets[index].Entry) {
215 ++index;
216 }
217 return const_iterator(this, index);
218 }
219
220 template<typename HashEntryTy,
221 typename HashFunctionTy,
222 typename EntryFactoryTy>
223 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
end() const224 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const
225 {
226 return const_iterator(NULL, 0);
227 }
228
229 template<typename HashEntryTy,
230 typename HashFunctionTy,
231 typename EntryFactoryTy>
232 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
begin(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)233 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin(
234 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
235 {
236 return chain_iterator(this, pKey, 0x0);
237 }
238
239 template<typename HashEntryTy,
240 typename HashFunctionTy,
241 typename EntryFactoryTy>
242 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
end(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey)243 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
244 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
245 {
246 return chain_iterator();
247 }
248
249 template<typename HashEntryTy,
250 typename HashFunctionTy,
251 typename EntryFactoryTy>
252 typename HashTable<HashEntryTy, HashFunctionTy, 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, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
255 {
256 return const_chain_iterator(this, pKey, 0x0);
257 }
258
259 template<typename HashEntryTy,
260 typename HashFunctionTy,
261 typename EntryFactoryTy>
262 typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator
end(const typename HashTable<HashEntryTy,HashFunctionTy,EntryFactoryTy>::key_type & pKey) const263 HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
264 const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
265 {
266 return const_chain_iterator();
267 }
268
269