1//===--- StringMap.cpp - String Hash table map implementation -------------===//
2//
3//                     The LLVM Compiler Infrastructure
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9//
10// This file implements the StringMap class.
11//
12//===----------------------------------------------------------------------===//
13
14#include "llvm/ADT/StringMap.h"
15#include "llvm/ADT/StringExtras.h"
16#include "llvm/Support/Compiler.h"
17#include <cassert>
18using namespace llvm;
19
20/// Returns the number of buckets to allocate to ensure that the DenseMap can
21/// accommodate \p NumEntries without need to grow().
22static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
23  // Ensure that "NumEntries * 4 < NumBuckets * 3"
24  if (NumEntries == 0)
25    return 0;
26  // +1 is required because of the strict equality.
27  // For example if NumEntries is 48, we need to return 401.
28  return NextPowerOf2(NumEntries * 4 / 3 + 1);
29}
30
31StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
32  ItemSize = itemSize;
33
34  // If a size is specified, initialize the table with that many buckets.
35  if (InitSize) {
36    // The table will grow when the number of entries reach 3/4 of the number of
37    // buckets. To guarantee that "InitSize" number of entries can be inserted
38    // in the table without growing, we allocate just what is needed here.
39    init(getMinBucketToReserveForEntries(InitSize));
40    return;
41  }
42
43  // Otherwise, initialize it with zero buckets to avoid the allocation.
44  TheTable = nullptr;
45  NumBuckets = 0;
46  NumItems = 0;
47  NumTombstones = 0;
48}
49
50void StringMapImpl::init(unsigned InitSize) {
51  assert((InitSize & (InitSize-1)) == 0 &&
52         "Init Size must be a power of 2 or zero!");
53  NumBuckets = InitSize ? InitSize : 16;
54  NumItems = 0;
55  NumTombstones = 0;
56
57  TheTable = (StringMapEntryBase **)calloc(NumBuckets+1,
58                                           sizeof(StringMapEntryBase **) +
59                                           sizeof(unsigned));
60
61  // Allocate one extra bucket, set it to look filled so the iterators stop at
62  // end.
63  TheTable[NumBuckets] = (StringMapEntryBase*)2;
64}
65
66
67/// LookupBucketFor - Look up the bucket that the specified string should end
68/// up in.  If it already exists as a key in the map, the Item pointer for the
69/// specified bucket will be non-null.  Otherwise, it will be null.  In either
70/// case, the FullHashValue field of the bucket will be set to the hash value
71/// of the string.
72unsigned StringMapImpl::LookupBucketFor(StringRef Name) {
73  unsigned HTSize = NumBuckets;
74  if (HTSize == 0) {  // Hash table unallocated so far?
75    init(16);
76    HTSize = NumBuckets;
77  }
78  unsigned FullHashValue = HashString(Name);
79  unsigned BucketNo = FullHashValue & (HTSize-1);
80  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
81
82  unsigned ProbeAmt = 1;
83  int FirstTombstone = -1;
84  while (1) {
85    StringMapEntryBase *BucketItem = TheTable[BucketNo];
86    // If we found an empty bucket, this key isn't in the table yet, return it.
87    if (LLVM_LIKELY(!BucketItem)) {
88      // If we found a tombstone, we want to reuse the tombstone instead of an
89      // empty bucket.  This reduces probing.
90      if (FirstTombstone != -1) {
91        HashTable[FirstTombstone] = FullHashValue;
92        return FirstTombstone;
93      }
94
95      HashTable[BucketNo] = FullHashValue;
96      return BucketNo;
97    }
98
99    if (BucketItem == getTombstoneVal()) {
100      // Skip over tombstones.  However, remember the first one we see.
101      if (FirstTombstone == -1) FirstTombstone = BucketNo;
102    } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
103      // If the full hash value matches, check deeply for a match.  The common
104      // case here is that we are only looking at the buckets (for item info
105      // being non-null and for the full hash value) not at the items.  This
106      // is important for cache locality.
107
108      // Do the comparison like this because Name isn't necessarily
109      // null-terminated!
110      char *ItemStr = (char*)BucketItem+ItemSize;
111      if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) {
112        // We found a match!
113        return BucketNo;
114      }
115    }
116
117    // Okay, we didn't find the item.  Probe to the next bucket.
118    BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
119
120    // Use quadratic probing, it has fewer clumping artifacts than linear
121    // probing and has good cache behavior in the common case.
122    ++ProbeAmt;
123  }
124}
125
126
127/// FindKey - Look up the bucket that contains the specified key. If it exists
128/// in the map, return the bucket number of the key.  Otherwise return -1.
129/// This does not modify the map.
130int StringMapImpl::FindKey(StringRef Key) const {
131  unsigned HTSize = NumBuckets;
132  if (HTSize == 0) return -1;  // Really empty table?
133  unsigned FullHashValue = HashString(Key);
134  unsigned BucketNo = FullHashValue & (HTSize-1);
135  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
136
137  unsigned ProbeAmt = 1;
138  while (1) {
139    StringMapEntryBase *BucketItem = TheTable[BucketNo];
140    // If we found an empty bucket, this key isn't in the table yet, return.
141    if (LLVM_LIKELY(!BucketItem))
142      return -1;
143
144    if (BucketItem == getTombstoneVal()) {
145      // Ignore tombstones.
146    } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
147      // If the full hash value matches, check deeply for a match.  The common
148      // case here is that we are only looking at the buckets (for item info
149      // being non-null and for the full hash value) not at the items.  This
150      // is important for cache locality.
151
152      // Do the comparison like this because NameStart isn't necessarily
153      // null-terminated!
154      char *ItemStr = (char*)BucketItem+ItemSize;
155      if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) {
156        // We found a match!
157        return BucketNo;
158      }
159    }
160
161    // Okay, we didn't find the item.  Probe to the next bucket.
162    BucketNo = (BucketNo+ProbeAmt) & (HTSize-1);
163
164    // Use quadratic probing, it has fewer clumping artifacts than linear
165    // probing and has good cache behavior in the common case.
166    ++ProbeAmt;
167  }
168}
169
170/// RemoveKey - Remove the specified StringMapEntry from the table, but do not
171/// delete it.  This aborts if the value isn't in the table.
172void StringMapImpl::RemoveKey(StringMapEntryBase *V) {
173  const char *VStr = (char*)V + ItemSize;
174  StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength()));
175  (void)V2;
176  assert(V == V2 && "Didn't find key?");
177}
178
179/// RemoveKey - Remove the StringMapEntry for the specified key from the
180/// table, returning it.  If the key is not in the table, this returns null.
181StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
182  int Bucket = FindKey(Key);
183  if (Bucket == -1) return nullptr;
184
185  StringMapEntryBase *Result = TheTable[Bucket];
186  TheTable[Bucket] = getTombstoneVal();
187  --NumItems;
188  ++NumTombstones;
189  assert(NumItems + NumTombstones <= NumBuckets);
190
191  return Result;
192}
193
194
195
196/// RehashTable - Grow the table, redistributing values into the buckets with
197/// the appropriate mod-of-hashtable-size.
198unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
199  unsigned NewSize;
200  unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
201
202  // If the hash table is now more than 3/4 full, or if fewer than 1/8 of
203  // the buckets are empty (meaning that many are filled with tombstones),
204  // grow/rehash the table.
205  if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) {
206    NewSize = NumBuckets*2;
207  } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <=
208                           NumBuckets / 8)) {
209    NewSize = NumBuckets;
210  } else {
211    return BucketNo;
212  }
213
214  unsigned NewBucketNo = BucketNo;
215  // Allocate one extra bucket which will always be non-empty.  This allows the
216  // iterators to stop at end.
217  StringMapEntryBase **NewTableArray =
218    (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
219                                             sizeof(unsigned));
220  unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
221  NewTableArray[NewSize] = (StringMapEntryBase*)2;
222
223  // Rehash all the items into their new buckets.  Luckily :) we already have
224  // the hash values available, so we don't have to rehash any strings.
225  for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
226    StringMapEntryBase *Bucket = TheTable[I];
227    if (Bucket && Bucket != getTombstoneVal()) {
228      // Fast case, bucket available.
229      unsigned FullHash = HashTable[I];
230      unsigned NewBucket = FullHash & (NewSize-1);
231      if (!NewTableArray[NewBucket]) {
232        NewTableArray[FullHash & (NewSize-1)] = Bucket;
233        NewHashArray[FullHash & (NewSize-1)] = FullHash;
234        if (I == BucketNo)
235          NewBucketNo = NewBucket;
236        continue;
237      }
238
239      // Otherwise probe for a spot.
240      unsigned ProbeSize = 1;
241      do {
242        NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
243      } while (NewTableArray[NewBucket]);
244
245      // Finally found a slot.  Fill it in.
246      NewTableArray[NewBucket] = Bucket;
247      NewHashArray[NewBucket] = FullHash;
248      if (I == BucketNo)
249        NewBucketNo = NewBucket;
250    }
251  }
252
253  free(TheTable);
254
255  TheTable = NewTableArray;
256  NumBuckets = NewSize;
257  NumTombstones = 0;
258  return NewBucketNo;
259}
260