Mercurial > hg > CbC > CbC_llvm

comparison lib/Support/StringMap.cpp @ 77:54457678186b LLVM3.6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
LLVM 3.6
author Kaito Tokumori <e105711@ie.u-ryukyu.ac.jp>
date Mon, 08 Sep 2014 22:06:00 +0900
parents 95c75e76d11b
children afa8332a0e37
comparison
equal deleted inserted replaced
34:e874dbf0ad9d 77:54457678186b
25 init(InitSize); 25 init(InitSize);
26 return; 26 return;
27 } 27 }
28 28
29 // Otherwise, initialize it with zero buckets to avoid the allocation. 29 // Otherwise, initialize it with zero buckets to avoid the allocation.
30 TheTable = 0; 30 TheTable = nullptr;
31 NumBuckets = 0; 31 NumBuckets = 0;
32 NumItems = 0; 32 NumItems = 0;
33 NumTombstones = 0; 33 NumTombstones = 0;
34 } 34 }
35 35
68 unsigned ProbeAmt = 1; 68 unsigned ProbeAmt = 1;
69 int FirstTombstone = -1; 69 int FirstTombstone = -1;
70 while (1) { 70 while (1) {
71 StringMapEntryBase *BucketItem = TheTable[BucketNo]; 71 StringMapEntryBase *BucketItem = TheTable[BucketNo];
72 // If we found an empty bucket, this key isn't in the table yet, return it. 72 // If we found an empty bucket, this key isn't in the table yet, return it.
73 if (LLVM_LIKELY(BucketItem == 0)) { 73 if (LLVM_LIKELY(!BucketItem)) {
74 // If we found a tombstone, we want to reuse the tombstone instead of an 74 // If we found a tombstone, we want to reuse the tombstone instead of an
75 // empty bucket. This reduces probing. 75 // empty bucket. This reduces probing.
76 if (FirstTombstone != -1) { 76 if (FirstTombstone != -1) {
77 HashTable[FirstTombstone] = FullHashValue; 77 HashTable[FirstTombstone] = FullHashValue;
78 return FirstTombstone; 78 return FirstTombstone;
122 122
123 unsigned ProbeAmt = 1; 123 unsigned ProbeAmt = 1;
124 while (1) { 124 while (1) {
125 StringMapEntryBase *BucketItem = TheTable[BucketNo]; 125 StringMapEntryBase *BucketItem = TheTable[BucketNo];
126 // If we found an empty bucket, this key isn't in the table yet, return. 126 // If we found an empty bucket, this key isn't in the table yet, return.
127 if (LLVM_LIKELY(BucketItem == 0)) 127 if (LLVM_LIKELY(!BucketItem))
128 return -1; 128 return -1;
129 129
130 if (BucketItem == getTombstoneVal()) { 130 if (BucketItem == getTombstoneVal()) {
131 // Ignore tombstones. 131 // Ignore tombstones.
132 } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { 132 } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) {
164 164
165 /// RemoveKey - Remove the StringMapEntry for the specified key from the 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. 166 /// table, returning it. If the key is not in the table, this returns null.
167 StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { 167 StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) {
168 int Bucket = FindKey(Key); 168 int Bucket = FindKey(Key);
169 if (Bucket == -1) return 0; 169 if (Bucket == -1) return nullptr;
170 170
171 StringMapEntryBase *Result = TheTable[Bucket]; 171 StringMapEntryBase *Result = TheTable[Bucket];
172 TheTable[Bucket] = getTombstoneVal(); 172 TheTable[Bucket] = getTombstoneVal();
173 --NumItems; 173 --NumItems;
174 ++NumTombstones; 174 ++NumTombstones;
179 179
180 180
181 181
182 /// RehashTable - Grow the table, redistributing values into the buckets with 182 /// RehashTable - Grow the table, redistributing values into the buckets with
183 /// the appropriate mod-of-hashtable-size. 183 /// the appropriate mod-of-hashtable-size.
184 void StringMapImpl::RehashTable() { 184 unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
185 unsigned NewSize; 185 unsigned NewSize;
186 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 186 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
187 187
188 // If the hash table is now more than 3/4 full, or if fewer than 1/8 of 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), 189 // the buckets are empty (meaning that many are filled with tombstones),
191 if (NumItems*4 > NumBuckets*3) { 191 if (NumItems*4 > NumBuckets*3) {
192 NewSize = NumBuckets*2; 192 NewSize = NumBuckets*2;
193 } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) { 193 } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) {
194 NewSize = NumBuckets; 194 NewSize = NumBuckets;
195 } else { 195 } else {
196 return; 196 return BucketNo;
197 } 197 }
198 198
199 unsigned NewBucketNo = BucketNo;
199 // Allocate one extra bucket which will always be non-empty. This allows the 200 // Allocate one extra bucket which will always be non-empty. This allows the
200 // iterators to stop at end. 201 // iterators to stop at end.
201 StringMapEntryBase **NewTableArray = 202 StringMapEntryBase **NewTableArray =
202 (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + 203 (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) +
203 sizeof(unsigned)); 204 sizeof(unsigned));
210 StringMapEntryBase *Bucket = TheTable[I]; 211 StringMapEntryBase *Bucket = TheTable[I];
211 if (Bucket && Bucket != getTombstoneVal()) { 212 if (Bucket && Bucket != getTombstoneVal()) {
212 // Fast case, bucket available. 213 // Fast case, bucket available.
213 unsigned FullHash = HashTable[I]; 214 unsigned FullHash = HashTable[I];
214 unsigned NewBucket = FullHash & (NewSize-1); 215 unsigned NewBucket = FullHash & (NewSize-1);
215 if (NewTableArray[NewBucket] == 0) { 216 if (!NewTableArray[NewBucket]) {
216 NewTableArray[FullHash & (NewSize-1)] = Bucket; 217 NewTableArray[FullHash & (NewSize-1)] = Bucket;
217 NewHashArray[FullHash & (NewSize-1)] = FullHash; 218 NewHashArray[FullHash & (NewSize-1)] = FullHash;
219 if (I == BucketNo)
220 NewBucketNo = NewBucket;
218 continue; 221 continue;
219 } 222 }
220 223
221 // Otherwise probe for a spot. 224 // Otherwise probe for a spot.
222 unsigned ProbeSize = 1; 225 unsigned ProbeSize = 1;
225 } while (NewTableArray[NewBucket]); 228 } while (NewTableArray[NewBucket]);
226 229
227 // Finally found a slot. Fill it in. 230 // Finally found a slot. Fill it in.
228 NewTableArray[NewBucket] = Bucket; 231 NewTableArray[NewBucket] = Bucket;
229 NewHashArray[NewBucket] = FullHash; 232 NewHashArray[NewBucket] = FullHash;
233 if (I == BucketNo)
234 NewBucketNo = NewBucket;
230 } 235 }
231 } 236 }
232 237
233 free(TheTable); 238 free(TheTable);
234 239
235 TheTable = NewTableArray; 240 TheTable = NewTableArray;
236 NumBuckets = NewSize; 241 NumBuckets = NewSize;
237 NumTombstones = 0; 242 NumTombstones = 0;
238 } 243 return NewBucketNo;
244 }