1 //===- StringPool.h - Interned string pool ----------------------*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 // 10 // This file declares an interned string pool, which helps reduce the cost of 11 // strings by using the same storage for identical strings. 12 // 13 // To intern a string: 14 // 15 // StringPool Pool; 16 // PooledStringPtr Str = Pool.intern("wakka wakka"); 17 // 18 // To use the value of an interned string, use operator bool and operator*: 19 // 20 // if (Str) 21 // cerr << "the string is" << *Str << "\n"; 22 // 23 // Pooled strings are immutable, but you can change a PooledStringPtr to point 24 // to another instance. So that interned strings can eventually be freed, 25 // strings in the string pool are reference-counted (automatically). 26 // 27 //===----------------------------------------------------------------------===// 28 29 #ifndef LLVM_SUPPORT_STRINGPOOL_H 30 #define LLVM_SUPPORT_STRINGPOOL_H 31 32 #include "llvm/ADT/StringMap.h" 33 #include "llvm/ADT/StringRef.h" 34 #include <cassert> 35 36 namespace llvm { 37 38 class PooledStringPtr; 39 40 /// StringPool - An interned string pool. Use the intern method to add a 41 /// string. Strings are removed automatically as PooledStringPtrs are 42 /// destroyed. 43 class StringPool { 44 /// PooledString - This is the value of an entry in the pool's interning 45 /// table. 46 struct PooledString { 47 StringPool *Pool = nullptr; ///< So the string can remove itself. 48 unsigned Refcount = 0; ///< Number of referencing PooledStringPtrs. 49 50 public: 51 PooledString() = default; 52 }; 53 54 friend class PooledStringPtr; 55 56 using table_t = StringMap<PooledString>; 57 using entry_t = StringMapEntry<PooledString>; 58 table_t InternTable; 59 60 public: 61 StringPool(); 62 ~StringPool(); 63 64 /// intern - Adds a string to the pool and returns a reference-counted 65 /// pointer to it. No additional memory is allocated if the string already 66 /// exists in the pool. 67 PooledStringPtr intern(StringRef Str); 68 69 /// empty - Checks whether the pool is empty. Returns true if so. 70 /// 71 inline bool empty() const { return InternTable.empty(); } 72 }; 73 74 /// PooledStringPtr - A pointer to an interned string. Use operator bool to 75 /// test whether the pointer is valid, and operator * to get the string if so. 76 /// This is a lightweight value class with storage requirements equivalent to 77 /// a single pointer, but it does have reference-counting overhead when 78 /// copied. 79 class PooledStringPtr { 80 using entry_t = StringPool::entry_t; 81 82 entry_t *S = nullptr; 83 84 public: 85 PooledStringPtr() = default; 86 87 explicit PooledStringPtr(entry_t *E) : S(E) { 88 if (S) ++S->getValue().Refcount; 89 } 90 91 PooledStringPtr(const PooledStringPtr &That) : S(That.S) { 92 if (S) ++S->getValue().Refcount; 93 } 94 95 PooledStringPtr &operator=(const PooledStringPtr &That) { 96 if (S != That.S) { 97 clear(); 98 S = That.S; 99 if (S) ++S->getValue().Refcount; 100 } 101 return *this; 102 } 103 104 void clear() { 105 if (!S) 106 return; 107 if (--S->getValue().Refcount == 0) { 108 S->getValue().Pool->InternTable.remove(S); 109 S->Destroy(); 110 } 111 S = nullptr; 112 } 113 114 ~PooledStringPtr() { clear(); } 115 116 inline const char *begin() const { 117 assert(*this && "Attempt to dereference empty PooledStringPtr!"); 118 return S->getKeyData(); 119 } 120 121 inline const char *end() const { 122 assert(*this && "Attempt to dereference empty PooledStringPtr!"); 123 return S->getKeyData() + S->getKeyLength(); 124 } 125 126 inline unsigned size() const { 127 assert(*this && "Attempt to dereference empty PooledStringPtr!"); 128 return S->getKeyLength(); 129 } 130 131 inline const char *operator*() const { return begin(); } 132 inline explicit operator bool() const { return S != nullptr; } 133 134 inline bool operator==(const PooledStringPtr &That) const { return S == That.S; } 135 inline bool operator!=(const PooledStringPtr &That) const { return S != That.S; } 136 }; 137 138 } // end namespace llvm 139 140 #endif // LLVM_SUPPORT_STRINGPOOL_H 141