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