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