Mercurial > hg > Members > tobaru > cbc > CbC_llvm

comparison lib/Support/StringMap.cpp @ 0:95c75e76d11b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.4
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Thu, 12 Dec 2013 13:56:28 +0900
parents
children 54457678186b
comparison
equal deleted inserted replaced
-1:000000000000 0:95c75e76d11b
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>
18 using namespace llvm;
19
20 StringMapImpl::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 = 0;
31 NumBuckets = 0;
32 NumItems = 0;
33 NumTombstones = 0;
34 }
35
36 void 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.
58 unsigned 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 == 0)) {
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.
116 int 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 == 0))
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.
158 void 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.
167 StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
168 int Bucket = FindKey(Key);
169 if (Bucket == -1) return 0;
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.
184 void StringMapImpl::RehashTable() {
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;
197 }
198
199 // Allocate one extra bucket which will always be non-empty. This allows the
200 // iterators to stop at end.
201 StringMapEntryBase **NewTableArray =
202 (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
203 sizeof(unsigned));
204 unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1);
205 NewTableArray[NewSize] = (StringMapEntryBase*)2;
206
207 // Rehash all the items into their new buckets. Luckily :) we already have
208 // the hash values available, so we don't have to rehash any strings.
209 for (unsigned I = 0, E = NumBuckets; I != E; ++I) {
210 StringMapEntryBase *Bucket = TheTable[I];
211 if (Bucket && Bucket != getTombstoneVal()) {
212 // Fast case, bucket available.
213 unsigned FullHash = HashTable[I];
214 unsigned NewBucket = FullHash & (NewSize-1);
215 if (NewTableArray[NewBucket] == 0) {
216 NewTableArray[FullHash & (NewSize-1)] = Bucket;
217 NewHashArray[FullHash & (NewSize-1)] = FullHash;
218 continue;
219 }
220
221 // Otherwise probe for a spot.
222 unsigned ProbeSize = 1;
223 do {
224 NewBucket = (NewBucket + ProbeSize++) & (NewSize-1);
225 } while (NewTableArray[NewBucket]);
226
227 // Finally found a slot. Fill it in.
228 NewTableArray[NewBucket] = Bucket;
229 NewHashArray[NewBucket] = FullHash;
230 }
231 }
232
233 free(TheTable);
234
235 TheTable = NewTableArray;
236 NumBuckets = NewSize;
237 NumTombstones = 0;
238 }