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 <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;  ///< So the string can remove itself.
47       unsigned Refcount; ///< Number of referencing PooledStringPtrs.
48 
49     public:
PooledStringPooledString50       PooledString() : Pool(nullptr), Refcount(0) { }
51     };
52 
53     friend class PooledStringPtr;
54 
55     typedef StringMap<PooledString> table_t;
56     typedef StringMapEntry<PooledString> entry_t;
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     typedef StringPool::entry_t entry_t;
80     entry_t *S;
81 
82   public:
PooledStringPtr()83     PooledStringPtr() : S(nullptr) {}
84 
PooledStringPtr(entry_t * E)85     explicit PooledStringPtr(entry_t *E) : S(E) {
86       if (S) ++S->getValue().Refcount;
87     }
88 
PooledStringPtr(const PooledStringPtr & That)89     PooledStringPtr(const PooledStringPtr &That) : S(That.S) {
90       if (S) ++S->getValue().Refcount;
91     }
92 
93     PooledStringPtr &operator=(const PooledStringPtr &That) {
94       if (S != That.S) {
95         clear();
96         S = That.S;
97         if (S) ++S->getValue().Refcount;
98       }
99       return *this;
100     }
101 
clear()102     void clear() {
103       if (!S)
104         return;
105       if (--S->getValue().Refcount == 0) {
106         S->getValue().Pool->InternTable.remove(S);
107         S->Destroy();
108       }
109       S = nullptr;
110     }
111 
~PooledStringPtr()112     ~PooledStringPtr() { clear(); }
113 
begin()114     inline const char *begin() const {
115       assert(*this && "Attempt to dereference empty PooledStringPtr!");
116       return S->getKeyData();
117     }
118 
end()119     inline const char *end() const {
120       assert(*this && "Attempt to dereference empty PooledStringPtr!");
121       return S->getKeyData() + S->getKeyLength();
122     }
123 
size()124     inline unsigned size() const {
125       assert(*this && "Attempt to dereference empty PooledStringPtr!");
126       return S->getKeyLength();
127     }
128 
129     inline const char *operator*() const { return begin(); }
130     inline explicit operator bool() const { return S != nullptr; }
131 
132     inline bool operator==(const PooledStringPtr &That) const { return S == That.S; }
133     inline bool operator!=(const PooledStringPtr &That) const { return S != That.S; }
134   };
135 
136 } // End llvm namespace
137 
138 #endif
139