HashTable.tcc revision 5460a1f25d9ddecb5c70667267d66d51af177a99 
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(size_type pSize)
16  : HashTableImpl<HashEntryTy, HashFunctionTy>(pSize), m_EntryFactory()
17{
18}
19
20template<typename HashEntryTy,
21         typename HashFunctionTy,
22         typename EntryFactoryTy>
23HashTable<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
37template<typename HashEntryTy,
38         typename HashFunctionTy,
39         typename EntryFactoryTy>
40void 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  BaseTy::m_NumOfEntries = 0;
55  BaseTy::m_NumOfTombstones = 0;
56}
57
58/// insert - insert a new element to the container. If the element already
59//  exist, return the element.
60template<typename HashEntryTy,
61         typename HashFunctionTy,
62         typename EntryFactoryTy>
63typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::entry_type*
64HashTable<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.
91template<typename HashEntryTy,
92         typename HashFunctionTy,
93         typename EntryFactoryTy>
94typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
95HashTable<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
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, 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
125template<typename HashEntryTy,
126         typename HashFunctionTy,
127         typename EntryFactoryTy>
128typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
129HashTable<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
138template<typename HashEntryTy,
139         typename HashFunctionTy,
140         typename EntryFactoryTy>
141typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type
142HashTable<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
152template<typename HashEntryTy,
153         typename HashFunctionTy,
154         typename EntryFactoryTy>
155float HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::load_factor() const
156{
157  return ((float)BaseTy::m_NumOfEntries/(float)BaseTy::m_NumOfBuckets);
158}
159
160template<typename HashEntryTy,
161         typename HashFunctionTy,
162         typename EntryFactoryTy>
163void
164HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash()
165{
166  BaseTy::mayRehash();
167}
168
169template<typename HashEntryTy,
170         typename HashFunctionTy,
171         typename EntryFactoryTy>
172void
173HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::rehash(
174       typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::size_type pCount)
175{
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{
185  if (BaseTy::empty())
186    return iterator(this, 0);
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
195template<typename HashEntryTy,
196         typename HashFunctionTy,
197         typename EntryFactoryTy>
198typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::iterator
199HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end()
200{
201  return iterator(NULL, 0);
202}
203
204template<typename HashEntryTy,
205         typename HashFunctionTy,
206         typename EntryFactoryTy>
207typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
208HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin() const
209{
210  if (BaseTy::empty())
211    return const_iterator(this, 0);
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
220template<typename HashEntryTy,
221         typename HashFunctionTy,
222         typename EntryFactoryTy>
223typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_iterator
224HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end() const
225{
226  return const_iterator(NULL, 0);
227}
228
229template<typename HashEntryTy,
230         typename HashFunctionTy,
231         typename EntryFactoryTy>
232typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
233HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::begin(
234    const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
235{
236  return chain_iterator(this, pKey, 0x0);
237}
238
239template<typename HashEntryTy,
240         typename HashFunctionTy,
241         typename EntryFactoryTy>
242typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::chain_iterator
243HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
244    const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey)
245{
246  return chain_iterator();
247}
248
249template<typename HashEntryTy,
250         typename HashFunctionTy,
251         typename EntryFactoryTy>
252typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator
253HashTable<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
259template<typename HashEntryTy,
260         typename HashFunctionTy,
261         typename EntryFactoryTy>
262typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::const_chain_iterator
263HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::end(
264  const typename HashTable<HashEntryTy, HashFunctionTy, EntryFactoryTy>::key_type& pKey) const
265{
266  return const_chain_iterator();
267}
268
269