From ee182422ff0b638b17c5ee802c19b8680107c2bb Mon Sep 17 00:00:00 2001 From: Chris Lattner Date: Thu, 8 Feb 2007 19:08:37 +0000 Subject: [PATCH] Allow cstringmap to contain strings with nul characters in them. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@34062 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/ADT/CStringMap.h | 85 +++++++++++++++++++++++------------ include/llvm/ADT/StringMap.h | 85 +++++++++++++++++++++++------------ lib/Support/CStringMap.cpp | 9 ++-- lib/Support/StringMap.cpp | 9 ++-- 4 files changed, 124 insertions(+), 64 deletions(-) diff --git a/include/llvm/ADT/CStringMap.h b/include/llvm/ADT/CStringMap.h index d1beb42ebc9..feb65878ebc 100644 --- a/include/llvm/ADT/CStringMap.h +++ b/include/llvm/ADT/CStringMap.h @@ -19,14 +19,23 @@ namespace llvm { +/// StringMapEntryBase - Shared base class of StringMapEntry instances. +class StringMapEntryBase { + unsigned StrLen; +public: + StringMapEntryBase(unsigned Len) : StrLen(Len) {} + + unsigned getKeyLength() const { return StrLen; } +}; + /// CStringMapVisitor - Subclasses of this class may be implemented to walk all /// of the items in a CStringMap. class CStringMapVisitor { public: virtual ~CStringMapVisitor(); - virtual void Visit(const char *Key, void *Value) const = 0; + virtual void Visit(const char *Key, StringMapEntryBase *Value) const = 0; }; - + /// CStringMapImpl - This is the base class of CStringMap that is shared among /// all of its instantiations. class CStringMapImpl { @@ -39,7 +48,7 @@ protected: unsigned FullHashValue; /// Item - This is a pointer to the actual item object. - void *Item; + StringMapEntryBase *Item; }; ItemBucket *TheTable; @@ -64,66 +73,86 @@ public: void VisitEntries(const CStringMapVisitor &Visitor) const; }; +/// StringMapEntry - This is used to represent one value that is inserted into +/// a StringMap. It contains the Value itself and the key: the string length +/// and data. +template +class StringMapEntry : public StringMapEntryBase { + ValueTy Val; +public: + StringMapEntry(unsigned StrLen) + : StringMapEntryBase(StrLen), Val() {} + StringMapEntry(unsigned StrLen, const ValueTy &V) + : StringMapEntryBase(StrLen), Val(V) {} + + const ValueTy &getValue() const { return Val; } + ValueTy &getValue() { return Val; } + + void setValue(const ValueTy &V) { Val = V; } + + /// getKeyData - Return the start of the string data that is the key for this + /// value. The string data is always stored immediately after the + /// StringMapEntry object. + const char *getKeyData() const {return reinterpret_cast(this+1);} +}; + /// CStringMap - This is an unconventional map that is specialized for handling -/// keys that are "C strings", that is, null-terminated strings. This does some +/// keys that are "strings", which are basically ranges of bytes. This does some /// funky memory allocation and hashing things to make it extremely efficient, /// storing the string data *after* the value in the map. template class CStringMap : public CStringMapImpl { AllocatorTy Allocator; + typedef StringMapEntry MapEntryTy; public: CStringMap(unsigned InitialSize = 0) - : CStringMapImpl(InitialSize, sizeof(ValueTy)) {} + : CStringMapImpl(InitialSize, sizeof(MapEntryTy)) {} AllocatorTy &getAllocator() { return Allocator; } const AllocatorTy &getAllocator() const { return Allocator; } /// FindValue - Look up the specified key in the map. If it exists, return a /// pointer to the element, otherwise return null. - ValueTy *FindValue(const char *KeyStart, const char *KeyEnd) { + MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) { unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); - return static_cast(TheTable[BucketNo].Item); - } - - /// GetKeyForValueInMap - Given a value that is inserted into this map, return - /// the string that corresponds to it. This is an efficient operation that - /// is provided by CStringMap. The string is live as long as the value is in - /// the map. - static const char *GetKeyForValueInMap(const ValueTy &Val) { - return reinterpret_cast(&Val+1); + return static_cast(TheTable[BucketNo].Item); } /// GetOrCreateValue - Look up the specified key in the table. If a value /// exists, return it. Otherwise, default construct a value, insert it, and /// return. - ValueTy &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) { + StringMapEntry &GetOrCreateValue(const char *KeyStart, + const char *KeyEnd) { unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); ItemBucket &Bucket = TheTable[BucketNo]; if (Bucket.Item) - return *static_cast(Bucket.Item); + return *static_cast(Bucket.Item); unsigned KeyLength = KeyEnd-KeyStart; - // Okay, the item doesn't already exist, and Bucket is the bucket to fill - // in. Allocate a new item with space for the null-terminated string at the - // end. - unsigned AllocSize = sizeof(ValueTy)+KeyLength+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(MapEntryTy)+KeyLength+1; #ifdef __GNUC__ - unsigned Alignment = __alignof__(ValueTy); + unsigned Alignment = __alignof__(MapEntryTy); #else // FIXME: ugly. unsigned Alignment = 8; #endif - ValueTy *NewItem = (ValueTy*)Allocator.Allocate(AllocSize, Alignment); - new (NewItem) ValueTy(); + MapEntryTy *NewItem = + static_cast(Allocator.Allocate(AllocSize, Alignment)); + + // Default construct the value. + new (NewItem) MapEntryTy(KeyLength); ++NumItems; // Copy the string information. - char *StrBuffer = (char*)(NewItem+1); + char *StrBuffer = const_cast(NewItem->getKeyData()); memcpy(StrBuffer, KeyStart, KeyLength); - StrBuffer[KeyLength] = 0; // Null terminate string. + StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. // Fill in the bucket for the hash table. The FullHashValue was already // filled in by LookupBucketFor. @@ -137,9 +166,9 @@ public: ~CStringMap() { for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { - if (ValueTy *Id = static_cast(I->Item)) { + if (MapEntryTy *Id = static_cast(I->Item)) { // Free memory referenced by the item. - Id->~ValueTy(); + Id->~MapEntryTy(); Allocator.Deallocate(Id); } } diff --git a/include/llvm/ADT/StringMap.h b/include/llvm/ADT/StringMap.h index d1beb42ebc9..feb65878ebc 100644 --- a/include/llvm/ADT/StringMap.h +++ b/include/llvm/ADT/StringMap.h @@ -19,14 +19,23 @@ namespace llvm { +/// StringMapEntryBase - Shared base class of StringMapEntry instances. +class StringMapEntryBase { + unsigned StrLen; +public: + StringMapEntryBase(unsigned Len) : StrLen(Len) {} + + unsigned getKeyLength() const { return StrLen; } +}; + /// CStringMapVisitor - Subclasses of this class may be implemented to walk all /// of the items in a CStringMap. class CStringMapVisitor { public: virtual ~CStringMapVisitor(); - virtual void Visit(const char *Key, void *Value) const = 0; + virtual void Visit(const char *Key, StringMapEntryBase *Value) const = 0; }; - + /// CStringMapImpl - This is the base class of CStringMap that is shared among /// all of its instantiations. class CStringMapImpl { @@ -39,7 +48,7 @@ protected: unsigned FullHashValue; /// Item - This is a pointer to the actual item object. - void *Item; + StringMapEntryBase *Item; }; ItemBucket *TheTable; @@ -64,66 +73,86 @@ public: void VisitEntries(const CStringMapVisitor &Visitor) const; }; +/// StringMapEntry - This is used to represent one value that is inserted into +/// a StringMap. It contains the Value itself and the key: the string length +/// and data. +template +class StringMapEntry : public StringMapEntryBase { + ValueTy Val; +public: + StringMapEntry(unsigned StrLen) + : StringMapEntryBase(StrLen), Val() {} + StringMapEntry(unsigned StrLen, const ValueTy &V) + : StringMapEntryBase(StrLen), Val(V) {} + + const ValueTy &getValue() const { return Val; } + ValueTy &getValue() { return Val; } + + void setValue(const ValueTy &V) { Val = V; } + + /// getKeyData - Return the start of the string data that is the key for this + /// value. The string data is always stored immediately after the + /// StringMapEntry object. + const char *getKeyData() const {return reinterpret_cast(this+1);} +}; + /// CStringMap - This is an unconventional map that is specialized for handling -/// keys that are "C strings", that is, null-terminated strings. This does some +/// keys that are "strings", which are basically ranges of bytes. This does some /// funky memory allocation and hashing things to make it extremely efficient, /// storing the string data *after* the value in the map. template class CStringMap : public CStringMapImpl { AllocatorTy Allocator; + typedef StringMapEntry MapEntryTy; public: CStringMap(unsigned InitialSize = 0) - : CStringMapImpl(InitialSize, sizeof(ValueTy)) {} + : CStringMapImpl(InitialSize, sizeof(MapEntryTy)) {} AllocatorTy &getAllocator() { return Allocator; } const AllocatorTy &getAllocator() const { return Allocator; } /// FindValue - Look up the specified key in the map. If it exists, return a /// pointer to the element, otherwise return null. - ValueTy *FindValue(const char *KeyStart, const char *KeyEnd) { + MapEntryTy *FindValue(const char *KeyStart, const char *KeyEnd) { unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); - return static_cast(TheTable[BucketNo].Item); - } - - /// GetKeyForValueInMap - Given a value that is inserted into this map, return - /// the string that corresponds to it. This is an efficient operation that - /// is provided by CStringMap. The string is live as long as the value is in - /// the map. - static const char *GetKeyForValueInMap(const ValueTy &Val) { - return reinterpret_cast(&Val+1); + return static_cast(TheTable[BucketNo].Item); } /// GetOrCreateValue - Look up the specified key in the table. If a value /// exists, return it. Otherwise, default construct a value, insert it, and /// return. - ValueTy &GetOrCreateValue(const char *KeyStart, const char *KeyEnd) { + StringMapEntry &GetOrCreateValue(const char *KeyStart, + const char *KeyEnd) { unsigned BucketNo = LookupBucketFor(KeyStart, KeyEnd); ItemBucket &Bucket = TheTable[BucketNo]; if (Bucket.Item) - return *static_cast(Bucket.Item); + return *static_cast(Bucket.Item); unsigned KeyLength = KeyEnd-KeyStart; - // Okay, the item doesn't already exist, and Bucket is the bucket to fill - // in. Allocate a new item with space for the null-terminated string at the - // end. - unsigned AllocSize = sizeof(ValueTy)+KeyLength+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(MapEntryTy)+KeyLength+1; #ifdef __GNUC__ - unsigned Alignment = __alignof__(ValueTy); + unsigned Alignment = __alignof__(MapEntryTy); #else // FIXME: ugly. unsigned Alignment = 8; #endif - ValueTy *NewItem = (ValueTy*)Allocator.Allocate(AllocSize, Alignment); - new (NewItem) ValueTy(); + MapEntryTy *NewItem = + static_cast(Allocator.Allocate(AllocSize, Alignment)); + + // Default construct the value. + new (NewItem) MapEntryTy(KeyLength); ++NumItems; // Copy the string information. - char *StrBuffer = (char*)(NewItem+1); + char *StrBuffer = const_cast(NewItem->getKeyData()); memcpy(StrBuffer, KeyStart, KeyLength); - StrBuffer[KeyLength] = 0; // Null terminate string. + StrBuffer[KeyLength] = 0; // Null terminate for convenience of clients. // Fill in the bucket for the hash table. The FullHashValue was already // filled in by LookupBucketFor. @@ -137,9 +166,9 @@ public: ~CStringMap() { for (ItemBucket *I = TheTable, *E = TheTable+NumBuckets; I != E; ++I) { - if (ValueTy *Id = static_cast(I->Item)) { + if (MapEntryTy *Id = static_cast(I->Item)) { // Free memory referenced by the item. - Id->~ValueTy(); + Id->~MapEntryTy(); Allocator.Deallocate(Id); } } diff --git a/lib/Support/CStringMap.cpp b/lib/Support/CStringMap.cpp index 31b50d2f154..b145e2ef81a 100644 --- a/lib/Support/CStringMap.cpp +++ b/lib/Support/CStringMap.cpp @@ -58,7 +58,7 @@ unsigned CStringMapImpl::LookupBucketFor(const char *NameStart, unsigned ProbeAmt = 1; while (1) { ItemBucket &Bucket = TheTable[BucketNo]; - void *BucketItem = Bucket.Item; + StringMapEntryBase *BucketItem = Bucket.Item; // If we found an empty bucket, this key isn't in the table yet, return it. if (BucketItem == 0) { Bucket.FullHashValue = FullHashValue; @@ -73,8 +73,9 @@ unsigned CStringMapImpl::LookupBucketFor(const char *NameStart, // Do the comparison like this because NameStart isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; - if (strlen(ItemStr) == unsigned(NameEnd-NameStart) && - memcmp(ItemStr, NameStart, (NameEnd-NameStart)) == 0) { + unsigned ItemStrLen = BucketItem->getKeyLength(); + if (unsigned(NameEnd-NameStart) == ItemStrLen && + memcmp(ItemStr, NameStart, ItemStrLen) == 0) { // We found a match! return BucketNo; } @@ -131,7 +132,7 @@ void CStringMapImpl::RehashTable() { /// invoking Visitor.Visit for each of them. void CStringMapImpl::VisitEntries(const CStringMapVisitor &Visitor) const { for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { - if (void *Id = IB->Item) + if (StringMapEntryBase *Id = IB->Item) Visitor.Visit((char*)Id + ItemSize, Id); } } diff --git a/lib/Support/StringMap.cpp b/lib/Support/StringMap.cpp index 31b50d2f154..b145e2ef81a 100644 --- a/lib/Support/StringMap.cpp +++ b/lib/Support/StringMap.cpp @@ -58,7 +58,7 @@ unsigned CStringMapImpl::LookupBucketFor(const char *NameStart, unsigned ProbeAmt = 1; while (1) { ItemBucket &Bucket = TheTable[BucketNo]; - void *BucketItem = Bucket.Item; + StringMapEntryBase *BucketItem = Bucket.Item; // If we found an empty bucket, this key isn't in the table yet, return it. if (BucketItem == 0) { Bucket.FullHashValue = FullHashValue; @@ -73,8 +73,9 @@ unsigned CStringMapImpl::LookupBucketFor(const char *NameStart, // Do the comparison like this because NameStart isn't necessarily // null-terminated! char *ItemStr = (char*)BucketItem+ItemSize; - if (strlen(ItemStr) == unsigned(NameEnd-NameStart) && - memcmp(ItemStr, NameStart, (NameEnd-NameStart)) == 0) { + unsigned ItemStrLen = BucketItem->getKeyLength(); + if (unsigned(NameEnd-NameStart) == ItemStrLen && + memcmp(ItemStr, NameStart, ItemStrLen) == 0) { // We found a match! return BucketNo; } @@ -131,7 +132,7 @@ void CStringMapImpl::RehashTable() { /// invoking Visitor.Visit for each of them. void CStringMapImpl::VisitEntries(const CStringMapVisitor &Visitor) const { for (ItemBucket *IB = TheTable, *E = TheTable+NumBuckets; IB != E; ++IB) { - if (void *Id = IB->Item) + if (StringMapEntryBase *Id = IB->Item) Visitor.Visit((char*)Id + ItemSize, Id); } } -- 2.34.1