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