HashBase.tcc revision 22add6ff3426df1a85089fe6a6e1597ee3b6f300 
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  clear();
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/// clear - clear the hash table.
109template<typename HashEntryTy,
110         typename HashFunctionTy>
111void HashTableImpl<HashEntryTy, HashFunctionTy>::clear()
112{
113  free(m_Buckets);
114
115  m_Buckets = 0;
116  m_NumOfBuckets = 0;
117  m_NumOfEntries = 0;
118  m_NumOfTombstones = 0;
119}
120
121/// lookUpBucketFor - look up the bucket whose key is pKey
122template<typename HashEntryTy,
123         typename HashFunctionTy>
124unsigned int
125HashTableImpl<HashEntryTy, HashFunctionTy>::lookUpBucketFor(
126  const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey)
127{
128  if (0 == m_NumOfBuckets) {
129    // NumOfBuckets is changed after init(pInitSize)
130    init(NumOfInitBuckets);
131  }
132
133  unsigned int full_hash = m_Hasher(pKey);
134  unsigned int index = full_hash % m_NumOfBuckets;
135
136  const unsigned int probe = 1;
137  int firstTombstone = -1;
138
139  // linear probing
140  while(true) {
141    bucket_type& bucket = m_Buckets[index];
142    // If we found an empty bucket, this key isn't in the table yet, return it.
143    if (bucket_type::getEmptyBucket() == bucket.Entry) {
144      if (-1 != firstTombstone) {
145        m_Buckets[firstTombstone].FullHashValue = full_hash;
146        return firstTombstone;
147      }
148
149      bucket.FullHashValue = full_hash;
150      return index;
151    }
152
153    if (bucket_type::getTombstone() == bucket.Entry) {
154      if (-1 == firstTombstone) {
155        firstTombstone = index;
156      }
157    }
158    else if (bucket.FullHashValue == full_hash) {
159      if (bucket.Entry->compare(pKey)) {
160        return index;
161      }
162    }
163
164    index += probe;
165    if (index == m_NumOfBuckets)
166      index = 0;
167  }
168}
169
170template<typename HashEntryTy,
171         typename HashFunctionTy>
172int
173HashTableImpl<HashEntryTy, HashFunctionTy>::findKey(
174  const typename HashTableImpl<HashEntryTy, HashFunctionTy>::key_type& pKey) const
175{
176  if (0 == m_NumOfBuckets)
177    return -1;
178
179  unsigned int full_hash = m_Hasher(pKey);
180  unsigned int index = full_hash % m_NumOfBuckets;
181
182  const unsigned int probe = 1;
183  // linear probing
184  while (true) {
185    bucket_type &bucket = m_Buckets[index];
186
187    if (bucket_type::getEmptyBucket() == bucket.Entry)
188      return -1;
189
190    if (bucket_type::getTombstone() == bucket.Entry) {
191      // Ignore tombstones.
192    }
193    else if (full_hash == bucket.FullHashValue) {
194      // get string, compare, if match, return index
195      if (bucket.Entry->compare(pKey))
196        return index;
197    }
198    index += probe;
199    if (index == m_NumOfBuckets)
200      index = 0;
201  }
202}
203
204template<typename HashEntryTy,
205         typename HashFunctionTy>
206void HashTableImpl<HashEntryTy, HashFunctionTy>::mayRehash()
207{
208
209  unsigned int new_size;
210  // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
211  // the buckets are empty (meaning that many are filled with tombstones),
212  // grow/rehash the table.
213  if ((m_NumOfEntries<<2) > m_NumOfBuckets*3)
214    new_size = compute_bucket_count(m_NumOfBuckets);
215  else if (((m_NumOfBuckets-(m_NumOfEntries+m_NumOfTombstones))<<3) < m_NumOfBuckets)
216    new_size = m_NumOfBuckets;
217  else
218    return;
219
220  doRehash(new_size);
221}
222
223template<typename HashEntryTy,
224         typename HashFunctionTy>
225void HashTableImpl<HashEntryTy, HashFunctionTy>::doRehash(unsigned int pNewSize)
226{
227  bucket_type* new_table = (bucket_type*)calloc(pNewSize, sizeof(bucket_type));
228
229  // Rehash all the items into their new buckets.  Luckily :) we already have
230  // the hash values available, so we don't have to recall hash function again.
231  for (bucket_type *IB = m_Buckets, *E = m_Buckets+m_NumOfBuckets; IB != E; ++IB) {
232    if (IB->Entry != bucket_type::getEmptyBucket() &&
233        IB->Entry != bucket_type::getTombstone()) {
234      // Fast case, bucket available.
235      unsigned full_hash = IB->FullHashValue;
236      unsigned new_bucket = full_hash % pNewSize;
237      if (bucket_type::getEmptyBucket() == new_table[new_bucket].Entry) {
238        new_table[new_bucket].Entry = IB->Entry;
239        new_table[new_bucket].FullHashValue = full_hash;
240        continue;
241      }
242
243      // Otherwise probe for a spot.
244      const unsigned int probe = 1;
245      do {
246        new_bucket += probe;
247        if (new_bucket == pNewSize)
248          new_bucket = 0;
249      } while (new_table[new_bucket].Entry != bucket_type::getEmptyBucket());
250
251      // Finally found a slot.  Fill it in.
252      new_table[new_bucket].Entry = IB->Entry;
253      new_table[new_bucket].FullHashValue = full_hash;
254    }
255  }
256
257  free(m_Buckets);
258
259  m_Buckets = new_table;
260  m_NumOfBuckets = pNewSize;
261  m_NumOfTombstones = 0;
262}
263
264