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