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