Mercurial > hg > Members > tobaru > cbc > CbC_llvm

comparison lib/Support/StringMap.cpp @ 120:1172e4bd9c6f

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
update 4.0.0
author mir3636
date Fri, 25 Nov 2016 19:14:25 +0900
parents afa8332a0e37
children 803732b1fca8
comparison
equal deleted inserted replaced
101:34baf5011add 120:1172e4bd9c6f
12 //===----------------------------------------------------------------------===// 12 //===----------------------------------------------------------------------===//
13 13
14 #include "llvm/ADT/StringMap.h" 14 #include "llvm/ADT/StringMap.h"
15 #include "llvm/ADT/StringExtras.h" 15 #include "llvm/ADT/StringExtras.h"
16 #include "llvm/Support/Compiler.h" 16 #include "llvm/Support/Compiler.h"
17 #include "llvm/Support/MathExtras.h"
17 #include <cassert> 18 #include <cassert>
19
18 using namespace llvm; 20 using namespace llvm;
21
22 /// Returns the number of buckets to allocate to ensure that the DenseMap can
23 /// accommodate \p NumEntries without need to grow().
24 static unsigned getMinBucketToReserveForEntries(unsigned NumEntries) {
25 // Ensure that "NumEntries * 4 < NumBuckets * 3"
26 if (NumEntries == 0)
27 return 0;
28 // +1 is required because of the strict equality.
29 // For example if NumEntries is 48, we need to return 401.
30 return NextPowerOf2(NumEntries * 4 / 3 + 1);
31 }
19 32
20 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { 33 StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) {
21 ItemSize = itemSize; 34 ItemSize = itemSize;
22 35
23 // If a size is specified, initialize the table with that many buckets. 36 // If a size is specified, initialize the table with that many buckets.
24 if (InitSize) { 37 if (InitSize) {
25 init(InitSize); 38 // The table will grow when the number of entries reach 3/4 of the number of
39 // buckets. To guarantee that "InitSize" number of entries can be inserted
40 // in the table without growing, we allocate just what is needed here.
41 init(getMinBucketToReserveForEntries(InitSize));
26 return; 42 return;
27 } 43 }
28 44
29 // Otherwise, initialize it with zero buckets to avoid the allocation. 45 // Otherwise, initialize it with zero buckets to avoid the allocation.
30 TheTable = nullptr; 46 TheTable = nullptr;
46 62
47 // Allocate one extra bucket, set it to look filled so the iterators stop at 63 // Allocate one extra bucket, set it to look filled so the iterators stop at
48 // end. 64 // end.
49 TheTable[NumBuckets] = (StringMapEntryBase*)2; 65 TheTable[NumBuckets] = (StringMapEntryBase*)2;
50 } 66 }
51
52 67
53 /// LookupBucketFor - Look up the bucket that the specified string should end 68 /// 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 69 /// 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 70 /// 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 71 /// case, the FullHashValue field of the bucket will be set to the hash value
65 unsigned BucketNo = FullHashValue & (HTSize-1); 80 unsigned BucketNo = FullHashValue & (HTSize-1);
66 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 81 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
67 82
68 unsigned ProbeAmt = 1; 83 unsigned ProbeAmt = 1;
69 int FirstTombstone = -1; 84 int FirstTombstone = -1;
70 while (1) { 85 while (true) {
71 StringMapEntryBase *BucketItem = TheTable[BucketNo]; 86 StringMapEntryBase *BucketItem = TheTable[BucketNo];
72 // If we found an empty bucket, this key isn't in the table yet, return it. 87 // If we found an empty bucket, this key isn't in the table yet, return it.
73 if (LLVM_LIKELY(!BucketItem)) { 88 if (LLVM_LIKELY(!BucketItem)) {
74 // If we found a tombstone, we want to reuse the tombstone instead of an 89 // If we found a tombstone, we want to reuse the tombstone instead of an
75 // empty bucket. This reduces probing. 90 // empty bucket. This reduces probing.
106 // Use quadratic probing, it has fewer clumping artifacts than linear 121 // Use quadratic probing, it has fewer clumping artifacts than linear
107 // probing and has good cache behavior in the common case. 122 // probing and has good cache behavior in the common case.
108 ++ProbeAmt; 123 ++ProbeAmt;
109 } 124 }
110 } 125 }
111
112 126
113 /// FindKey - Look up the bucket that contains the specified key. If it exists 127 /// 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. 128 /// in the map, return the bucket number of the key. Otherwise return -1.
115 /// This does not modify the map. 129 /// This does not modify the map.
116 int StringMapImpl::FindKey(StringRef Key) const { 130 int StringMapImpl::FindKey(StringRef Key) const {
119 unsigned FullHashValue = HashString(Key); 133 unsigned FullHashValue = HashString(Key);
120 unsigned BucketNo = FullHashValue & (HTSize-1); 134 unsigned BucketNo = FullHashValue & (HTSize-1);
121 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); 135 unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1);
122 136
123 unsigned ProbeAmt = 1; 137 unsigned ProbeAmt = 1;
124 while (1) { 138 while (true) {
125 StringMapEntryBase *BucketItem = TheTable[BucketNo]; 139 StringMapEntryBase *BucketItem = TheTable[BucketNo];
126 // If we found an empty bucket, this key isn't in the table yet, return. 140 // If we found an empty bucket, this key isn't in the table yet, return.
127 if (LLVM_LIKELY(!BucketItem)) 141 if (LLVM_LIKELY(!BucketItem))
128 return -1; 142 return -1;
129 143
174 ++NumTombstones; 188 ++NumTombstones;
175 assert(NumItems + NumTombstones <= NumBuckets); 189 assert(NumItems + NumTombstones <= NumBuckets);
176 190
177 return Result; 191 return Result;
178 } 192 }
179
180
181 193
182 /// RehashTable - Grow the table, redistributing values into the buckets with 194 /// RehashTable - Grow the table, redistributing values into the buckets with
183 /// the appropriate mod-of-hashtable-size. 195 /// the appropriate mod-of-hashtable-size.
184 unsigned StringMapImpl::RehashTable(unsigned BucketNo) { 196 unsigned StringMapImpl::RehashTable(unsigned BucketNo) {
185 unsigned NewSize; 197 unsigned NewSize;