aboutsummaryrefslogtreecommitdiff
path: root/llvm/lib/Support/StringMap.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'llvm/lib/Support/StringMap.cpp')
-rw-r--r--llvm/lib/Support/StringMap.cpp52
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.
generated by cgit v1.2.3 (git 2.25.1) at 2024-10-28 04:22:18 +0000