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