X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FStringMap.cpp;h=9ac1f867fdd4576e76571d036365504976e48500;hb=69c9c8c4cf57d49a0c64507082617f433372831d;hp=a729d3d6c093bd27e6d8e467869af8ac91ae6998;hpb=4dee7fd2c2cb3fabddf99a184abe41dbc0bd4085;p=oota-llvm.git diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index a729d3d6c09..9ac1f867fdd 100644 --- a/lib/Support/StringMap.cpp +++ b/lib/Support/StringMap.cpp @@ -13,6 +13,7 @@ #include "llvm/ADT/StringMap.h" #include "llvm/ADT/StringExtras.h" +#include "llvm/Support/Compiler.h" #include using namespace llvm; @@ -39,11 +40,13 @@ void StringMapImpl::init(unsigned InitSize) { NumItems = 0; NumTombstones = 0; - TheTable = (ItemBucket*)calloc(NumBuckets+1, sizeof(ItemBucket)); - + TheTable = (StringMapEntryBase **)calloc(NumBuckets+1, + sizeof(StringMapEntryBase **) + + sizeof(unsigned)); + // Allocate one extra bucket, set it to look filled so the iterators stop at // end. - TheTable[NumBuckets].Item = (StringMapEntryBase*)2; + TheTable[NumBuckets] = (StringMapEntryBase*)2; } @@ -52,7 +55,7 @@ void StringMapImpl::init(unsigned InitSize) { /// specified bucket will be non-null. Otherwise, it will be null. In either /// case, the FullHashValue field of the bucket will be set to the hash value /// of the string. -unsigned StringMapImpl::LookupBucketFor(const StringRef &Name) { +unsigned StringMapImpl::LookupBucketFor(StringRef Name) { unsigned HTSize = NumBuckets; if (HTSize == 0) { // Hash table unallocated so far? init(16); @@ -60,29 +63,29 @@ unsigned StringMapImpl::LookupBucketFor(const StringRef &Name) { } unsigned FullHashValue = HashString(Name); unsigned BucketNo = FullHashValue & (HTSize-1); - + unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); + unsigned ProbeAmt = 1; int FirstTombstone = -1; while (1) { - ItemBucket &Bucket = TheTable[BucketNo]; - StringMapEntryBase *BucketItem = Bucket.Item; + StringMapEntryBase *BucketItem = TheTable[BucketNo]; // If we found an empty bucket, this key isn't in the table yet, return it. - if (BucketItem == 0) { + if (LLVM_LIKELY(BucketItem == 0)) { // If we found a tombstone, we want to reuse the tombstone instead of an // empty bucket. This reduces probing. if (FirstTombstone != -1) { - TheTable[FirstTombstone].FullHashValue = FullHashValue; + HashTable[FirstTombstone] = FullHashValue; return FirstTombstone; } - Bucket.FullHashValue = FullHashValue; + HashTable[BucketNo] = FullHashValue; return BucketNo; } if (BucketItem == getTombstoneVal()) { // Skip over tombstones. However, remember the first one we see. if (FirstTombstone == -1) FirstTombstone = BucketNo; - } else if (Bucket.FullHashValue == FullHashValue) { + } 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 // being non-null and for the full hash value) not at the items. This @@ -110,23 +113,23 @@ unsigned StringMapImpl::LookupBucketFor(const StringRef &Name) { /// FindKey - Look up the bucket that contains the specified key. If it exists /// in the map, return the bucket number of the key. Otherwise return -1. /// This does not modify the map. -int StringMapImpl::FindKey(const StringRef &Key) const { +int StringMapImpl::FindKey(StringRef Key) const { unsigned HTSize = NumBuckets; if (HTSize == 0) return -1; // Really empty table? unsigned FullHashValue = HashString(Key); unsigned BucketNo = FullHashValue & (HTSize-1); - + unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); + unsigned ProbeAmt = 1; while (1) { - ItemBucket &Bucket = TheTable[BucketNo]; - StringMapEntryBase *BucketItem = Bucket.Item; + StringMapEntryBase *BucketItem = TheTable[BucketNo]; // If we found an empty bucket, this key isn't in the table yet, return. - if (BucketItem == 0) + if (LLVM_LIKELY(BucketItem == 0)) return -1; if (BucketItem == getTombstoneVal()) { // Ignore tombstones. - } else if (Bucket.FullHashValue == FullHashValue) { + } 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 // being non-null and for the full hash value) not at the items. This @@ -155,20 +158,22 @@ int StringMapImpl::FindKey(const StringRef &Key) const { void StringMapImpl::RemoveKey(StringMapEntryBase *V) { const char *VStr = (char*)V + ItemSize; StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); - V2 = V2; + (void)V2; assert(V == V2 && "Didn't find key?"); } /// RemoveKey - Remove the StringMapEntry for the specified key from the /// table, returning it. If the key is not in the table, this returns null. -StringMapEntryBase *StringMapImpl::RemoveKey(const StringRef &Key) { +StringMapEntryBase *StringMapImpl::RemoveKey(StringRef Key) { int Bucket = FindKey(Key); if (Bucket == -1) return 0; - StringMapEntryBase *Result = TheTable[Bucket].Item; - TheTable[Bucket].Item = getTombstoneVal(); + StringMapEntryBase *Result = TheTable[Bucket]; + TheTable[Bucket] = getTombstoneVal(); --NumItems; ++NumTombstones; + assert(NumItems + NumTombstones <= NumBuckets); + return Result; } @@ -177,22 +182,39 @@ StringMapEntryBase *StringMapImpl::RemoveKey(const StringRef &Key) { /// RehashTable - Grow the table, redistributing values into the buckets with /// the appropriate mod-of-hashtable-size. void StringMapImpl::RehashTable() { - unsigned NewSize = NumBuckets*2; + unsigned NewSize; + unsigned *HashTable = (unsigned *)(TheTable + NumBuckets + 1); + + // If the hash table is now more than 3/4 full, or if fewer than 1/8 of + // the buckets are empty (meaning that many are filled with tombstones), + // grow/rehash the table. + if (NumItems*4 > NumBuckets*3) { + NewSize = NumBuckets*2; + } else if (NumBuckets-(NumItems+NumTombstones) <= NumBuckets/8) { + NewSize = NumBuckets; + } else { + return; + } + // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. - ItemBucket *NewTableArray =(ItemBucket*)calloc(NewSize+1, sizeof(ItemBucket)); - NewTableArray[NewSize].Item = (StringMapEntryBase*)2; - + StringMapEntryBase **NewTableArray = + (StringMapEntryBase **)calloc(NewSize+1, sizeof(StringMapEntryBase *) + + sizeof(unsigned)); + unsigned *NewHashArray = (unsigned *)(NewTableArray + NewSize + 1); + 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. - for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { - if (IB->Item && IB->Item != getTombstoneVal()) { + for (unsigned I = 0, E = NumBuckets; I != E; ++I) { + StringMapEntryBase *Bucket = TheTable[I]; + if (Bucket && Bucket != getTombstoneVal()) { // Fast case, bucket available. - unsigned FullHash = IB->FullHashValue; + unsigned FullHash = HashTable[I]; unsigned NewBucket = FullHash & (NewSize-1); - if (NewTableArray[NewBucket].Item == 0) { - NewTableArray[FullHash & (NewSize-1)].Item = IB->Item; - NewTableArray[FullHash & (NewSize-1)].FullHashValue = FullHash; + if (NewTableArray[NewBucket] == 0) { + NewTableArray[FullHash & (NewSize-1)] = Bucket; + NewHashArray[FullHash & (NewSize-1)] = FullHash; continue; } @@ -200,11 +222,11 @@ void StringMapImpl::RehashTable() { unsigned ProbeSize = 1; do { NewBucket = (NewBucket + ProbeSize++) & (NewSize-1); - } while (NewTableArray[NewBucket].Item); + } while (NewTableArray[NewBucket]); // Finally found a slot. Fill it in. - NewTableArray[NewBucket].Item = IB->Item; - NewTableArray[NewBucket].FullHashValue = FullHash; + NewTableArray[NewBucket] = Bucket; + NewHashArray[NewBucket] = FullHash; } } @@ -212,4 +234,5 @@ void StringMapImpl::RehashTable() { TheTable = NewTableArray; NumBuckets = NewSize; + NumTombstones = 0; }