16316fbcb04af00fe76b6526fab09f51484014b3eDaniel Dunbar//===-- StringPool.h - Interned string pool ---------------------*- C++ -*-===// 2985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// 3985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// The LLVM Compiler Infrastructure 4985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// 8985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen//===----------------------------------------------------------------------===// 9985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// 10985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// This file declares an interned string pool, which helps reduce the cost of 11985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// strings by using the same storage for identical strings. 12fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// 13985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// To intern a string: 14fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// 15985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// StringPool Pool; 16985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// PooledStringPtr Str = Pool.intern("wakka wakka"); 17fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// 18985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// To use the value of an interned string, use operator bool and operator*: 19fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// 20985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// if (Str) 21985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// cerr << "the string is" << *Str << "\n"; 22fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// 23985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// Pooled strings are immutable, but you can change a PooledStringPtr to point 24985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// to another instance. So that interned strings can eventually be freed, 25985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen// strings in the string pool are reference-counted (automatically). 26fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman// 27985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen//===----------------------------------------------------------------------===// 28985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen 29985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen#ifndef LLVM_SUPPORT_STRINGPOOL_H 30985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen#define LLVM_SUPPORT_STRINGPOOL_H 31985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen 32cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines#include "llvm/Support/Compiler.h" 338d1ea750601cd27f5d70cef1186864abcf57bdb1Gordon Henriksen#include "llvm/ADT/StringMap.h" 34985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen#include <cassert> 35255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include <new> 36985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen 37985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksennamespace llvm { 38985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen 39985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen class PooledStringPtr; 40985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen 41985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// StringPool - An interned string pool. Use the intern method to add a 42985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// string. Strings are removed automatically as PooledStringPtrs are 43985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// destroyed. 44985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen class StringPool { 457446d0cfc551c79afa4a12296f107936ebe5e315Gordon Henriksen /// PooledString - This is the value of an entry in the pool's interning 467446d0cfc551c79afa4a12296f107936ebe5e315Gordon Henriksen /// table. 47985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen struct PooledString { 48985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen StringPool *Pool; ///< So the string can remove itself. 49985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen unsigned Refcount; ///< Number of referencing PooledStringPtrs. 50fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 51985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen public: 52dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PooledString() : Pool(nullptr), Refcount(0) { } 53985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen }; 54fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 55985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen friend class PooledStringPtr; 56fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 57985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen typedef StringMap<PooledString> table_t; 58985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen typedef StringMapEntry<PooledString> entry_t; 59985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen table_t InternTable; 60fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 61985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen public: 62985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen StringPool(); 63985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen ~StringPool(); 64fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 657446d0cfc551c79afa4a12296f107936ebe5e315Gordon Henriksen /// intern - Adds a string to the pool and returns a reference-counted 667446d0cfc551c79afa4a12296f107936ebe5e315Gordon Henriksen /// pointer to it. No additional memory is allocated if the string already 677446d0cfc551c79afa4a12296f107936ebe5e315Gordon Henriksen /// exists in the pool. 6838e59891ee4417a9be2f8146ce0ba3269e38ac21Benjamin Kramer PooledStringPtr intern(StringRef Str); 69fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 7053c34b1db978f1820677f410c6f3f59046ffa4c0Gordon Henriksen /// empty - Checks whether the pool is empty. Returns true if so. 71fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman /// 7253c34b1db978f1820677f410c6f3f59046ffa4c0Gordon Henriksen inline bool empty() const { return InternTable.empty(); } 73985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen }; 74fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 75985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// PooledStringPtr - A pointer to an interned string. Use operator bool to 76985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// test whether the pointer is valid, and operator * to get the string if so. 77985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// This is a lightweight value class with storage requirements equivalent to 78985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// a single pointer, but it does have reference-counting overhead when 79985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen /// copied. 80985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen class PooledStringPtr { 81985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen typedef StringPool::entry_t entry_t; 82985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen entry_t *S; 83fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 84985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen public: 85dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines PooledStringPtr() : S(nullptr) {} 86fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 87985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen explicit PooledStringPtr(entry_t *E) : S(E) { 88985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen if (S) ++S->getValue().Refcount; 89985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 90fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 91985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen PooledStringPtr(const PooledStringPtr &That) : S(That.S) { 92985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen if (S) ++S->getValue().Refcount; 93985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 94fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 95985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen PooledStringPtr &operator=(const PooledStringPtr &That) { 96985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen if (S != That.S) { 97985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen clear(); 98985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen S = That.S; 99985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen if (S) ++S->getValue().Refcount; 100985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 101985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen return *this; 102985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 103fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 104985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen void clear() { 105985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen if (!S) 106985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen return; 107985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen if (--S->getValue().Refcount == 0) { 108985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen S->getValue().Pool->InternTable.remove(S); 109afa47c5a261e0a52b52b1e66034237dff80bc0f4Gordon Henriksen S->Destroy(); 110985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 111dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines S = nullptr; 112985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 113fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 114985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen ~PooledStringPtr() { clear(); } 115fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 116985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen inline const char *begin() const { 117985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen assert(*this && "Attempt to dereference empty PooledStringPtr!"); 118985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen return S->getKeyData(); 119985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 120fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 121985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen inline const char *end() const { 122985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen assert(*this && "Attempt to dereference empty PooledStringPtr!"); 123985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen return S->getKeyData() + S->getKeyLength(); 124985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 125fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 126985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen inline unsigned size() const { 127985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen assert(*this && "Attempt to dereference empty PooledStringPtr!"); 128985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen return S->getKeyLength(); 129985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen } 130fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 131985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen inline const char *operator*() const { return begin(); } 132cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines inline LLVM_EXPLICIT operator bool() const { return S != nullptr; } 133fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 134cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines inline bool operator==(const PooledStringPtr &That) const { return S == That.S; } 135cd81d94322a39503e4a3e87b6ee03d4fcb3465fbStephen Hines inline bool operator!=(const PooledStringPtr &That) const { return S != That.S; } 136985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen }; 137fe2cce63aa26d0916fa7be32c6bf7fa8fb059ee7Misha Brukman 138985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen} // End llvm namespace 139985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen 140985cb6223424c6c97c4b9a47ae74c2eedb5cd7c2Gordon Henriksen#endif 141