ItemBucket *TheTable;
unsigned NumBuckets;
unsigned NumItems;
+ unsigned NumTombstones;
unsigned ItemSize;
protected:
+ StringMapImpl(unsigned itemSize) : ItemSize(itemSize) {
+ // Initialize the map with zero buckets to allocation.
+ TheTable = 0;
+ NumBuckets = 0;
+ NumItems = 0;
+ NumTombstones = 0;
+ }
StringMapImpl(unsigned InitSize, unsigned ItemSize);
void RehashTable();
+ /// ShouldRehash - Return true if the table should be rehashed after a new
+ /// element was recently inserted.
+ bool ShouldRehash() const {
+ // 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 the table.
+ return NumItems*4 > NumBuckets*3 ||
+ NumBuckets-(NumItems+NumTombstones) < NumBuckets/8;
+ }
+
/// 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
/// of the string.
unsigned LookupBucketFor(const char *KeyStart, const char *KeyEnd);
+ /// 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 FindKey(const char *KeyStart, const char *KeyEnd) 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 RemoveKey(StringMapEntryBase *V);
+
+ /// 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 *RemoveKey(const char *KeyStart, const char *KeyEnd);
+private:
+ void init(unsigned Size);
public:
static StringMapEntryBase *getTombstoneVal() {
return (StringMapEntryBase*)-1;
// Okay, the item doesn't already exist, and 'Bucket' is the bucket to fill
// in. Allocate a new item with space for the string at the end and a null
// terminator.
+
unsigned AllocSize = sizeof(StringMapEntry)+KeyLength+1;
+ unsigned Alignment = alignof<StringMapEntry>();
-#ifdef __GNUC__
- unsigned Alignment = __alignof__(StringMapEntry);
-#else
- // FIXME: ugly.
- unsigned Alignment = 8;
-#endif
- StringMapEntry *NewItem =
- static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize, Alignment));
+ StringMapEntry *NewItem =
+ static_cast<StringMapEntry*>(Allocator.Allocate(AllocSize,Alignment));
// Default construct the value.
new (NewItem) StringMapEntry(KeyLength);
MallocAllocator A;
return Create(KeyStart, KeyEnd, A);
}
-
+
+
+ /// GetStringMapEntryFromValue - Given a value that is known to be embedded
+ /// into a StringMapEntry, return the StringMapEntry itself.
+ static StringMapEntry &GetStringMapEntryFromValue(ValueTy &V) {
+ StringMapEntry *EPtr = 0;
+ char *Ptr = reinterpret_cast<char*>(&V) -
+ (reinterpret_cast<char*>(&EPtr->Val) -
+ reinterpret_cast<char*>(EPtr));
+ return *reinterpret_cast<StringMapEntry*>(Ptr);
+ }
+ static const StringMapEntry &GetStringMapEntryFromValue(const ValueTy &V) {
+ return GetStringMapEntryFromValue(const_cast<ValueTy&>(V));
+ }
+
/// Destroy - Destroy this StringMapEntry, releasing memory back to the
/// specified allocator.
template<typename AllocatorTy>
AllocatorTy Allocator;
typedef StringMapEntry<ValueTy> MapEntryTy;
public:
- StringMap(unsigned InitialSize = 0)
+ StringMap() : StringMapImpl(sizeof(MapEntryTy)) {}
+ StringMap(unsigned InitialSize)
: StringMapImpl(InitialSize, sizeof(MapEntryTy)) {}
AllocatorTy &getAllocator() { return Allocator; }
typedef StringMapConstIterator<ValueTy> const_iterator;
typedef StringMapIterator<ValueTy> iterator;
- iterator begin() { return iterator(TheTable); }
- iterator end() { return iterator(TheTable+NumBuckets); }
- const_iterator begin() const { return const_iterator(TheTable); }
- const_iterator end() const { return const_iterator(TheTable+NumBuckets); }
+ iterator begin() {
+ return iterator(TheTable, NumBuckets == 0);
+ }
+ iterator end() {
+ return iterator(TheTable+NumBuckets, true);
+ }
+ const_iterator begin() const {
+ return const_iterator(TheTable, NumBuckets == 0);
+ }
+ const_iterator end() const {
+ return const_iterator(TheTable+NumBuckets, true);
+ }
+
+ iterator find(const char *KeyStart, const char *KeyEnd) {
+ int Bucket = FindKey(KeyStart, KeyEnd);
+ if (Bucket == -1) return end();
+ return iterator(TheTable+Bucket);
+ }
+
+ const_iterator find(const char *KeyStart, const char *KeyEnd) const {
+ int Bucket = FindKey(KeyStart, KeyEnd);
+ if (Bucket == -1) return end();
+ return const_iterator(TheTable+Bucket);
+ }
- /// FindValue - Look up the specified key in the map. If it exists, return a
- /// pointer to the element, otherwise return null.
- MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) {
- unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
- return static_cast<MapEntryTy*>(TheTable[BucketNo].Item);
+ /// insert - Insert the specified key/value pair into the map. If the key
+ /// already exists in the map, return false and ignore the request, otherwise
+ /// insert it and return true.
+ bool insert(MapEntryTy *KeyValue) {
+ unsigned BucketNo =
+ LookupBucketFor(KeyValue->getKeyData(),
+ KeyValue->getKeyData()+KeyValue->getKeyLength());
+ ItemBucket &Bucket = TheTable[BucketNo];
+ if (Bucket.Item && Bucket.Item != getTombstoneVal())
+ return false; // Already exists in map.
+
+ if (Bucket.Item == getTombstoneVal())
+ --NumTombstones;
+ Bucket.Item = KeyValue;
+ ++NumItems;
+
+ if (ShouldRehash())
+ RehashTable();
+ return true;
}
/// GetOrCreateValue - Look up the specified key in the table. If a value
const char *KeyEnd) {
unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd);
ItemBucket &Bucket = TheTable[BucketNo];
- if (Bucket.Item)
+ if (Bucket.Item && Bucket.Item != getTombstoneVal())
return *static_cast<MapEntryTy*>(Bucket.Item);
MapEntryTy *NewItem = MapEntryTy::Create(KeyStart, KeyEnd, Allocator);
+
+ if (Bucket.Item == getTombstoneVal())
+ --NumTombstones;
++NumItems;
// Fill in the bucket for the hash table. The FullHashValue was already
// filled in by LookupBucketFor.
Bucket.Item = NewItem;
- // If the hash table is now more than 3/4 full, rehash into a larger table.
- if (NumItems > NumBuckets*3/4)
+ if (ShouldRehash())
RehashTable();
return *NewItem;
}
+ /// remove - Remove the specified key/value pair from the map, but do not
+ /// erase it. This aborts if the key is not in the map.
+ void remove(MapEntryTy *KeyValue) {
+ RemoveKey(KeyValue);
+ }
+
+ void erase(iterator I) {
+ MapEntryTy &V = *I;
+ remove(&V);
+ V.Destroy(Allocator);
+ }
+
~StringMap() {
for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) {
- if (MapEntryTy *Id = static_cast<MapEntryTy*>(I->Item))
- Id->Destroy(Allocator);
+ if (I->Item && I->Item != getTombstoneVal())
+ static_cast<MapEntryTy*>(I->Item)->Destroy(Allocator);
}
- delete [] TheTable;
+ free(TheTable);
}
+private:
+ StringMap(const StringMap &); // FIXME: Implement.
+ void operator=(const StringMap &); // FIXME: Implement.
};
template<typename ValueTy>
class StringMapConstIterator {
+protected:
StringMapImpl::ItemBucket *Ptr;
public:
- StringMapConstIterator(StringMapImpl::ItemBucket *Bucket) : Ptr(Bucket) {
- AdvancePastEmptyBuckets();
+ StringMapConstIterator(StringMapImpl::ItemBucket *Bucket,
+ bool NoAdvance = false)
+ : Ptr(Bucket) {
+ if (!NoAdvance) AdvancePastEmptyBuckets();
}
const StringMapEntry<ValueTy> &operator*() const {
template<typename ValueTy>
class StringMapIterator : public StringMapConstIterator<ValueTy> {
public:
- StringMapIterator(StringMapImpl::ItemBucket *Bucket)
- : StringMapConstIterator<ValueTy>(Bucket) {
+ StringMapIterator(StringMapImpl::ItemBucket *Bucket,
+ bool NoAdvance = false)
+ : StringMapConstIterator<ValueTy>(Bucket, NoAdvance) {
}
StringMapEntry<ValueTy> &operator*() const {
return *static_cast<StringMapEntry<ValueTy>*>(this->Ptr->Item);
projects / oota-llvm.git / blobdiff