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