diff options
Diffstat (limited to 'llvm/lib/Support/StringMap.cpp')
-rw-r--r-- | llvm/lib/Support/StringMap.cpp | 52 |
1 files changed, 26 insertions, 26 deletions
diff --git a/llvm/lib/Support/StringMap.cpp b/llvm/lib/Support/StringMap.cpp index 6b5ea020dd46..f65d3846623c 100644 --- a/llvm/lib/Support/StringMap.cpp +++ b/llvm/lib/Support/StringMap.cpp @@ -12,10 +12,8 @@ #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringExtras.h" -#include "llvm/Support/Compiler.h" #include "llvm/Support/DJB.h" #include "llvm/Support/MathExtras.h" -#include <cassert> using namespace llvm; @@ -50,23 +48,22 @@ StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { } void StringMapImpl::init(unsigned InitSize) { - assert((InitSize & (InitSize-1)) == 0 && + assert((InitSize & (InitSize - 1)) == 0 && "Init Size must be a power of 2 or zero!"); unsigned NewNumBuckets = InitSize ? InitSize : 16; NumItems = 0; NumTombstones = 0; - TheTable = static_cast<StringMapEntryBase **>( - safe_calloc(NewNumBuckets+1, - sizeof(StringMapEntryBase **) + sizeof(unsigned))); + TheTable = static_cast<StringMapEntryBase **>(safe_calloc( + NewNumBuckets + 1, sizeof(StringMapEntryBase **) + sizeof(unsigned))); // Set the member only if TheTable was successfully allocated NumBuckets = NewNumBuckets; // Allocate one extra bucket, set it to look filled so the iterators stop at // end. - TheTable[NumBuckets] = (StringMapEntryBase*)2; + TheTable[NumBuckets] = (StringMapEntryBase *)2; } /// LookupBucketFor - Look up the bucket that the specified string should end @@ -76,12 +73,12 @@ void StringMapImpl::init(unsigned InitSize) { /// of the string. unsigned StringMapImpl::LookupBucketFor(StringRef Name) { unsigned HTSize = NumBuckets; - if (HTSize == 0) { // Hash table unallocated so far? + if (HTSize == 0) { // Hash table unallocated so far? init(16); HTSize = NumBuckets; } unsigned FullHashValue = djbHash(Name, 0); - unsigned BucketNo = FullHashValue & (HTSize-1); + unsigned BucketNo = FullHashValue & (HTSize - 1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); unsigned ProbeAmt = 1; @@ -103,7 +100,8 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { if (BucketItem == getTombstoneVal()) { // Skip over tombstones. However, remember the first one we see. - if (FirstTombstone == -1) FirstTombstone = BucketNo; + if (FirstTombstone == -1) + FirstTombstone = BucketNo; } else if (LLVM_LIKELY(HashTable[BucketNo] == FullHashValue)) { // If the full hash value matches, check deeply for a match. The common // case here is that we are only looking at the buckets (for item info @@ -112,7 +110,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { // Do the comparison like this because Name isn't necessarily // null-terminated! - char *ItemStr = (char*)BucketItem+ItemSize; + char *ItemStr = (char *)BucketItem + ItemSize; if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; @@ -120,7 +118,7 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { } // Okay, we didn't find the item. Probe to the next bucket. - BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); + BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1); // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. @@ -133,9 +131,10 @@ unsigned StringMapImpl::LookupBucketFor(StringRef Name) { /// This does not modify the map. int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; - if (HTSize == 0) return -1; // Really empty table? + if (HTSize == 0) + return -1; // Really empty table? unsigned FullHashValue = djbHash(Key, 0); - unsigned BucketNo = FullHashValue & (HTSize-1); + unsigned BucketNo = FullHashValue & (HTSize - 1); unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); unsigned ProbeAmt = 1; @@ -155,7 +154,7 @@ int StringMapImpl::FindKey(StringRef Key) const { // Do the comparison like this because NameStart isn't necessarily // null-terminated! - char *ItemStr = (char*)BucketItem+ItemSize; + char *ItemStr = (char *)BucketItem + ItemSize; if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; @@ -163,7 +162,7 @@ int StringMapImpl::FindKey(StringRef Key) const { } // Okay, we didn't find the item. Probe to the next bucket. - BucketNo = (BucketNo+ProbeAmt) & (HTSize-1); + BucketNo = (BucketNo + ProbeAmt) & (HTSize - 1); // Use quadratic probing, it has fewer clumping artifacts than linear // probing and has good cache behavior in the common case. @@ -174,7 +173,7 @@ int StringMapImpl::FindKey(StringRef Key) const { /// RemoveKey - Remove the specified StringMapEntry from the table, but do not /// delete it. This aborts if the value isn't in the table. void StringMapImpl::RemoveKey(StringMapEntryBase *V) { - const char *VStr = (char*)V + ItemSize; + const char *VStr = (char *)V + ItemSize; StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); (void)V2; assert(V == V2 && "Didn't find key?"); @@ -184,7 +183,8 @@ void StringMapImpl::RemoveKey(StringMapEntryBase *V) { /// table, returning it. If the key is not in the table, this returns null. StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { int Bucket = FindKey(Key); - if (Bucket == -1) return nullptr; + if (Bucket == -1) + return nullptr; StringMapEntryBase *Result = TheTable[Bucket]; TheTable[Bucket] = getTombstoneVal(); @@ -205,7 +205,7 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { // the buckets are empty (meaning that many are filled with tombstones), // grow/rehash the table. if (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) { - NewSize = NumBuckets*2; + NewSize = NumBuckets * 2; } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <= NumBuckets / 8)) { NewSize = NumBuckets; @@ -216,11 +216,11 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { unsigned NewBucketNo = BucketNo; // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. - auto NewTableArray = static_cast<StringMapEntryBase **>( - safe_calloc(NewSize+1, sizeof(StringMapEntryBase *) + sizeof(unsigned))); + auto NewTableArray = static_cast<StringMapEntryBase **>(safe_calloc( + NewSize + 1, sizeof(StringMapEntryBase *) + sizeof(unsigned))); unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); - NewTableArray[NewSize] = (StringMapEntryBase*)2; + NewTableArray[NewSize] = (StringMapEntryBase *)2; // Rehash all the items into their new buckets. Luckily :) we already have // the hash values available, so we don't have to rehash any strings. @@ -229,10 +229,10 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { if (Bucket && Bucket != getTombstoneVal()) { // Fast case, bucket available. unsigned FullHash = HashTable[I]; - unsigned NewBucket = FullHash & (NewSize-1); + unsigned NewBucket = FullHash & (NewSize - 1); if (!NewTableArray[NewBucket]) { - NewTableArray[FullHash & (NewSize-1)] = Bucket; - NewHashArray[FullHash & (NewSize-1)] = FullHash; + NewTableArray[FullHash & (NewSize - 1)] = Bucket; + NewHashArray[FullHash & (NewSize - 1)] = FullHash; if (I == BucketNo) NewBucketNo = NewBucket; continue; @@ -241,7 +241,7 @@ unsigned StringMapImpl::RehashTable(unsigned BucketNo) { // Otherwise probe for a spot. unsigned ProbeSize = 1; do { - NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); + NewBucket = (NewBucket + ProbeSize++) & (NewSize - 1); } while (NewTableArray[NewBucket]); // Finally found a slot. Fill it in. |