X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FSupport%2FStringMap.cpp;h=7be946642d9070987dcd429df8254d769f364325;hb=4b85564ba4a41465155b9128a68e5e14fea78365;hp=d56d1da6647ce957d4069f67f26319f4fabf5409;hpb=a86559ec426c643a151aeba1e051e4f878050f95;p=oota-llvm.git diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index d56d1da6647..7be946642d9 100644 --- a/lib/Support/StringMap.cpp +++ b/lib/Support/StringMap.cpp @@ -2,8 +2,8 @@ // // The LLVM Compiler Infrastructure // -// This file was developed by Chris Lattner and is distributed under -// the University of Illinois Open Source License. See LICENSE.TXT for details. +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. // //===----------------------------------------------------------------------===// // @@ -12,74 +12,133 @@ //===----------------------------------------------------------------------===// #include "llvm/ADT/StringMap.h" +#include "llvm/ADT/StringExtras.h" +#include "llvm/Support/Compiler.h" #include using namespace llvm; -StringMapVisitor::~StringMapVisitor() { +StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { + ItemSize = itemSize; + + // If a size is specified, initialize the table with that many buckets. + if (InitSize) { + init(InitSize); + return; + } + + // Otherwise, initialize it with zero buckets to avoid the allocation. + TheTable = nullptr; + NumBuckets = 0; + NumItems = 0; + NumTombstones = 0; } -StringMapImpl::StringMapImpl(unsigned InitSize, unsigned itemSize) { +void StringMapImpl::init(unsigned InitSize) { assert((InitSize & (InitSize-1)) == 0 && "Init Size must be a power of 2 or zero!"); - NumBuckets = InitSize ? InitSize : 512; - ItemSize = itemSize; + NumBuckets = InitSize ? InitSize : 16; NumItems = 0; + NumTombstones = 0; - TheTable = new ItemBucket[NumBuckets+1](); - memset(TheTable, 0, NumBuckets*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; } -/// HashString - Compute a hash code for the specified string. -/// -static unsigned HashString(const char *Start, const char *End) { - // Bernstein hash function. - unsigned int Result = 0; - // TODO: investigate whether a modified bernstein hash function performs - // better: http://eternallyconfuzzled.com/tuts/algorithms/jsw_tut_hashing.aspx - // X*33+c -> X*33^c - while (Start != End) - Result = Result * 33 + *Start++; - Result = Result + (Result >> 5); - return Result; -} - /// LookupBucketFor - Look up the bucket that the specified string should end /// up in. If it already exists as a key in the map, the Item pointer for the /// 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 char *NameStart, - const char *NameEnd) { +unsigned StringMapImpl::LookupBucketFor(StringRef Name) { unsigned HTSize = NumBuckets; - unsigned FullHashValue = HashString(NameStart, NameEnd); + if (HTSize == 0) { // Hash table unallocated so far? + init(16); + HTSize = NumBuckets; + } + 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) { - Bucket.FullHashValue = FullHashValue; + if (LLVM_LIKELY(!BucketItem)) { + // If we found a tombstone, we want to reuse the tombstone instead of an + // empty bucket. This reduces probing. + if (FirstTombstone != -1) { + HashTable[FirstTombstone] = FullHashValue; + return FirstTombstone; + } + + HashTable[BucketNo] = FullHashValue; return BucketNo; } - // 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 - // is important for cache locality. - if (Bucket.FullHashValue == FullHashValue) { + if (BucketItem == getTombstoneVal()) { + // Skip over tombstones. However, remember the first one we see. + 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 + // being non-null and for the full hash value) not at the items. This + // is important for cache locality. + + // Do the comparison like this because Name isn't necessarily + // null-terminated! + char *ItemStr = (char*)BucketItem+ItemSize; + if (Name == StringRef(ItemStr, BucketItem->getKeyLength())) { + // We found a match! + return BucketNo; + } + } + + // Okay, we didn't find the item. Probe to the next bucket. + 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. + ++ProbeAmt; + } +} + + +/// 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(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) { + StringMapEntryBase *BucketItem = TheTable[BucketNo]; + // If we found an empty bucket, this key isn't in the table yet, return. + if (LLVM_LIKELY(!BucketItem)) + return -1; + + if (BucketItem == getTombstoneVal()) { + // Ignore tombstones. + } 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 + // is important for cache locality. + // Do the comparison like this because NameStart isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; - unsigned ItemStrLen = BucketItem->getKeyLength(); - if (unsigned(NameEnd-NameStart) == ItemStrLen && - memcmp(ItemStr, NameStart, ItemStrLen) == 0) { + if (Key == StringRef(ItemStr, BucketItem->getKeyLength())) { // We found a match! return BucketNo; } @@ -94,52 +153,93 @@ unsigned StringMapImpl::LookupBucketFor(const char *NameStart, } } +/// 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; + StringMapEntryBase *V2 = RemoveKey(StringRef(VStr, V->getKeyLength())); + (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(StringRef Key) { + int Bucket = FindKey(Key); + if (Bucket == -1) return nullptr; + + StringMapEntryBase *Result = TheTable[Bucket]; + TheTable[Bucket] = getTombstoneVal(); + --NumItems; + ++NumTombstones; + assert(NumItems + NumTombstones <= NumBuckets); + + return Result; +} + + + /// RehashTable - Grow the table, redistributing values into the buckets with /// the appropriate mod-of-hashtable-size. -void StringMapImpl::RehashTable() { - unsigned NewSize = NumBuckets*2; +unsigned StringMapImpl::RehashTable(unsigned BucketNo) { + 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 (LLVM_UNLIKELY(NumItems * 4 > NumBuckets * 3)) { + NewSize = NumBuckets*2; + } else if (LLVM_UNLIKELY(NumBuckets - (NumItems + NumTombstones) <= + NumBuckets / 8)) { + NewSize = NumBuckets; + } else { + return BucketNo; + } + + unsigned NewBucketNo = BucketNo; // Allocate one extra bucket which will always be non-empty. This allows the // iterators to stop at end. - ItemBucket *NewTableArray = new ItemBucket[NewSize+1](); - memset(NewTableArray, 0, NewSize*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) { + 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]) { + NewTableArray[FullHash & (NewSize-1)] = Bucket; + NewHashArray[FullHash & (NewSize-1)] = FullHash; + if (I == BucketNo) + NewBucketNo = NewBucket; continue; } + // Otherwise probe for a spot. 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; + if (I == BucketNo) + NewBucketNo = NewBucket; } } - delete[] TheTable; + free(TheTable); TheTable = NewTableArray; NumBuckets = NewSize; -} - - -/// VisitEntries - This method walks through all of the items, -/// invoking Visitor.Visit for each of them. -void StringMapImpl::VisitEntries(const StringMapVisitor &Visitor) const { - for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { - if (StringMapEntryBase *Id = IB->Item) - Visitor.Visit((char*)Id + ItemSize, Id); - } + NumTombstones = 0; + return NewBucketNo; }