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
12template <typename HashEntryTy,
13          typename HashFunctionTy,
14          typename EntryFactoryTy>
15HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::HashTable(
16    size_type pSize)
17    : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory() {
18}
19
20template <typename HashEntryTy,
21          typename HashFunctionTy,
22          typename EntryFactoryTy>
23HashTable<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
36template <typename HashEntryTy,
37          typename HashFunctionTy,
38          typename EntryFactoryTy>
39void 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.
58template <typename HashEntryTy,
59          typename HashFunctionTy,
60          typename EntryFactoryTy>
61typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type*
62HashTable<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.
90template <typename HashEntryTy,
91          typename HashFunctionTy,
92          typename EntryFactoryTy>
93typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
94HashTable<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
112template <typename HashEntryTy,
113          typename HashFunctionTy,
114          typename EntryFactoryTy>
115typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
116HashTable<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
126template <typename HashEntryTy,
127          typename HashFunctionTy,
128          typename EntryFactoryTy>
129typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
130HashTable<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
140template <typename HashEntryTy,
141          typename HashFunctionTy,
142          typename EntryFactoryTy>
143typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
144HashTable<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
155template <typename HashEntryTy,
156          typename HashFunctionTy,
157          typename EntryFactoryTy>
158float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor()
159    const {
160  return ((float)BaseTy::m_NumOfEntries / (float)BaseTy::m_NumOfBuckets);
161}
162
163template <typename HashEntryTy,
164          typename HashFunctionTy,
165          typename EntryFactoryTy>
166void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash() {
167  BaseTy::mayRehash();
168}
169
170template <typename HashEntryTy,
171          typename HashFunctionTy,
172          typename EntryFactoryTy>
173void HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash(
174    typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
175        pCount) {
176  BaseTy::doRehash(pCount);
177}
178
179template <typename HashEntryTy,
180          typename HashFunctionTy,
181          typename EntryFactoryTy>
182typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
183HashTable<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
194template <typename HashEntryTy,
195          typename HashFunctionTy,
196          typename EntryFactoryTy>
197typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
198HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() {
199  return iterator(NULL, 0);
200}
201
202template <typename HashEntryTy,
203          typename HashFunctionTy,
204          typename EntryFactoryTy>
205typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
206HashTable<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
217template <typename HashEntryTy,
218          typename HashFunctionTy,
219          typename EntryFactoryTy>
220typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
221HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const {
222  return const_iterator(NULL, 0);
223}
224
225template <typename HashEntryTy,
226          typename HashFunctionTy,
227          typename EntryFactoryTy>
228typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
229HashTable<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
236template <typename HashEntryTy,
237          typename HashFunctionTy,
238          typename EntryFactoryTy>
239typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
240HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
241    const typename HashTable<HashEntryTy,
242                             HashFunctionTy,
243                             EntryFactoryTy>::key_type& pKey) {
244  return chain_iterator();
245}
246
247template <typename HashEntryTy,
248          typename HashFunctionTy,
249          typename EntryFactoryTy>
250typename HashTable<HashEntryTy,
251                   HashFunctionTy,
252                   EntryFactoryTy>::const_chain_iterator
253HashTable<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
260template <typename HashEntryTy,
261          typename HashFunctionTy,
262          typename EntryFactoryTy>
263typename HashTable<HashEntryTy,
264                   HashFunctionTy,
265                   EntryFactoryTy>::const_chain_iterator
266HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
267    const typename HashTable<HashEntryTy,
268                             HashFunctionTy,
269                             EntryFactoryTy>::key_type& pKey) const {
270  return const_chain_iterator();
271}
272