HashBase.tcc revision f33f6de54db174aa679a4b6d1e040d37e95541c0 
1//===- HashBase.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// internal non-member functions
12//===----------------------------------------------------------------------===//
13inline static unsigned int compute_bucket_count(unsigned int pNumOfBuckets)
14{
15  static const unsigned int bucket_size[] =
16  {
17    1, 3, 17, 37, 67, 97, 197, 419, 977, 2593, 4099, 8209, 12289,
18    16411, 20483, 32771, 49157, 65537, 98317, 131101, 196613
19  };
20
21  const unsigned int buckets_count =
22      sizeof(bucket_size) / sizeof(bucket_size[0]);
23  unsigned int idx = 0;
24  do {
25    if (pNumOfBuckets < bucket_size[idx]) {
26      return bucket_size[idx];
27    }
28    ++idx;
29  } while(idx < buckets_count);
30
31  return (pNumOfBuckets+131101); // rare case. increase constantly
32}
33
34//===----------------------------------------------------------------------===//
35// template implementation of HashBucket
36//===----------------------------------------------------------------------===//
37template<typename DataType>
38typename HashBucket<DataType>::entry_type*
39HashBucket<DataType>::getEmptyBucket()
40{
41  static entry_type* empty_bucket = reinterpret_cast<entry_type*>(0x0);
42  return empty_bucket;
43}
44
45template<typename DataType>
46typename HashBucket<DataType>::entry_type*
47HashBucket<DataType>::getTombstone()
48{
49  static entry_type* tombstone = reinterpret_cast<entry_type*>(0x1);
50  return tombstone;
51}
52
53//===----------------------------------------------------------------------===//
54// template implementation of HashTableImpl
55//===----------------------------------------------------------------------===//
56template<typename HashEntryTy,
57         typename HashFunctionTy>
58HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl()
59  : m_Buckets(0),
60    m_NumOfBuckets(0),
61    m_NumOfEntries(0),
62    m_NumOfTombstones(0),
63    m_Hasher() {
64}
65
66template<typename HashEntryTy,
67         typename HashFunctionTy>
68HashTableImpl<HashEntryTy, HashFunctionTy>::HashTableImpl(
69  unsigned int pInitSize)
70  : m_Hasher() {
71  if (pInitSize) {
72    init(pInitSize);
73    return;
74  }
75
76  m_Buckets = 0;
77  m_NumOfBuckets = 0;
78  m_NumOfEntries = 0;
79  m_NumOfTombstones = 0;
80}
81
82template<typename HashEntryTy,
83         typename HashFunctionTy>
84HashTableImpl<HashEntryTy, HashFunctionTy>::~HashTableImpl()
85{
86  clear();
87}
88
89/// empty - check if the hash table is empty
90template<typename HashEntryTy,
91         typename HashFunctionTy>
92bool HashTableImpl<HashEntryTy, HashFunctionTy>::empty() const
93{
94  return (0 == m_NumOfEntries);
95}
96
97/// init - initialize the hash table.
98template<typename HashEntryTy,
99         typename HashFunctionTy>
100void HashTableImpl<HashEntryTy, HashFunctionTy>::init(unsigned int pInitSize)
101{
102  m_NumOfBuckets = pInitSize? compute_bucket_count(pInitSize): NumOfInitBuckets;
103
104  m_NumOfEntries = 0;
105  m_NumOfTombstones = 0;
106
107  /** calloc also set bucket.Item = bucket_type::getEmptyStone() **/
108  m_Buckets = (bucket_type*)calloc(m_NumOfBuckets, sizeof(bucket_type));
109}
110
111/// clear - clear the hash table.
112template<typename HashEntryTy,
113         typename HashFunctionTy>
114void HashTableImpl<HashEntryTy, HashFunctionTy>::clear()
115{
116  free(m_Buckets);
117
118  m_Buckets = 0;
119  m_NumOfBuckets = 0;
120  m_NumOfEntries = 0;
121  m_NumOfTombstones = 0;
122}
123
124/// lookUpBucketFor - look up the bucket whose key is pKey
125template<typename HashEntryTy,
126         typename HashFunctionTy>
127unsigned int
128HashTableImpl<HashEntryTy, HashFunctionTy>::lookUpBucketFor(
129  const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey)
130{
131  if (0 == m_NumOfBuckets) {
132    // NumOfBuckets is changed after init(pInitSize)
133    init(NumOfInitBuckets);
134  }
135
136  unsigned int full_hash = m_Hasher(pKey);
137  unsigned int index = full_hash % m_NumOfBuckets;
138
139  const unsigned int probe = 1;
140  int firstTombstone = -1;
141
142  // linear probing
143  while(true) {
144    bucket_type& bucket = m_Buckets[index];
145    // If we found an empty bucket, this key isn't in the table yet, return it.
146    if (bucket_type::getEmptyBucket() == bucket.Entry) {
147      if (-1 != firstTombstone) {
148        m_Buckets[firstTombstone].FullHashValue = full_hash;
149        return firstTombstone;
150      }
151
152      bucket.FullHashValue = full_hash;
153      return index;
154    }
155
156    if (bucket_type::getTombstone() == bucket.Entry) {
157      if (-1 == firstTombstone) {
158        firstTombstone = index;
159      }
160    }
161    else if (bucket.FullHashValue == full_hash) {
162      if (bucket.Entry->compare(pKey)) {
163        return index;
164      }
165    }
166
167    index += probe;
168    if (index == m_NumOfBuckets)
169      index = 0;
170  }
171}
172
173template<typename HashEntryTy,
174         typename HashFunctionTy>
175int
176HashTableImpl<HashEntryTy, HashFunctionTy>::findKey(
177  const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey) const
178{
179  if (0 == m_NumOfBuckets)
180    return -1;
181
182  unsigned int full_hash = m_Hasher(pKey);
183  unsigned int index = full_hash % m_NumOfBuckets;
184
185  const unsigned int probe = 1;
186  // linear probing
187  while (true) {
188    bucket_type &bucket = m_Buckets[index];
189
190    if (bucket_type::getEmptyBucket() == bucket.Entry)
191      return -1;
192
193    if (bucket_type::getTombstone() == bucket.Entry) {
194      // Ignore tombstones.
195    }
196    else if (full_hash == bucket.FullHashValue) {
197      // get string, compare, if match, return index
198      if (bucket.Entry->compare(pKey))
199        return index;
200    }
201    index += probe;
202    if (index == m_NumOfBuckets)
203      index = 0;
204  }
205}
206
207template<typename HashEntryTy,
208         typename HashFunctionTy>
209void HashTableImpl<HashEntryTy, HashFunctionTy>::mayRehash()
210{
211
212  unsigned int new_size;
213  // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
214  // the buckets are empty (meaning that many are filled with tombstones),
215  // grow/rehash the table.
216  if ((m_NumOfEntries<<2) > m_NumOfBuckets*3)
217    new_size = compute_bucket_count(m_NumOfBuckets);
218  else if (((m_NumOfBuckets-(m_NumOfEntries+m_NumOfTombstones))<<3) < m_NumOfBuckets)
219    new_size = m_NumOfBuckets;
220  else
221    return;
222
223  doRehash(new_size);
224}
225
226template<typename HashEntryTy,
227         typename HashFunctionTy>
228void HashTableImpl<HashEntryTy, HashFunctionTy>::doRehash(unsigned int pNewSize)
229{
230  bucket_type* new_table = (bucket_type*)calloc(pNewSize, sizeof(bucket_type));
231
232  // Rehash all the items into their new buckets.  Luckily :) we already have
233  // the hash values available, so we don't have to recall hash function again.
234  for (bucket_type *IB = m_Buckets, *E = m_Buckets+m_NumOfBuckets; IB != E; ++IB) {
235    if (IB->Entry != bucket_type::getEmptyBucket() &&
236        IB->Entry != bucket_type::getTombstone()) {
237      // Fast case, bucket available.
238      unsigned full_hash = IB->FullHashValue;
239      unsigned new_bucket = full_hash % pNewSize;
240      if (bucket_type::getEmptyBucket() == new_table[new_bucket].Entry) {
241        new_table[new_bucket].Entry = IB->Entry;
242        new_table[new_bucket].FullHashValue = full_hash;
243        continue;
244      }
245
246      // Otherwise probe for a spot.
247      const unsigned int probe = 1;
248      do {
249        new_bucket += probe;
250        if (new_bucket == pNewSize)
251          new_bucket = 0;
252      } while (new_table[new_bucket].Entry != bucket_type::getEmptyBucket());
253
254      // Finally found a slot.  Fill it in.
255      new_table[new_bucket].Entry = IB->Entry;
256      new_table[new_bucket].FullHashValue = full_hash;
257    }
258  }
259
260  free(m_Buckets);
261
262  m_Buckets = new_table;
263  m_NumOfBuckets = pNewSize;
264  m_NumOfTombstones = 0;
265}
266
267