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/Support/Compiler.h"
33#include "llvm/ADT/StringMap.h"
34#include <cassert>
35#include <new>
36
37namespace llvm {
38
39  class PooledStringPtr;
40
41  /// StringPool - An interned string pool. Use the intern method to add a
42  /// string. Strings are removed automatically as PooledStringPtrs are
43  /// destroyed.
44  class StringPool {
45    /// PooledString - This is the value of an entry in the pool's interning
46    /// table.
47    struct PooledString {
48      StringPool *Pool;  ///< So the string can remove itself.
49      unsigned Refcount; ///< Number of referencing PooledStringPtrs.
50
51    public:
52      PooledString() : Pool(nullptr), Refcount(0) { }
53    };
54
55    friend class PooledStringPtr;
56
57    typedef StringMap<PooledString> table_t;
58    typedef StringMapEntry<PooledString> entry_t;
59    table_t InternTable;
60
61  public:
62    StringPool();
63    ~StringPool();
64
65    /// intern - Adds a string to the pool and returns a reference-counted
66    /// pointer to it. No additional memory is allocated if the string already
67    /// exists in the pool.
68    PooledStringPtr intern(StringRef Str);
69
70    /// empty - Checks whether the pool is empty. Returns true if so.
71    ///
72    inline bool empty() const { return InternTable.empty(); }
73  };
74
75  /// PooledStringPtr - A pointer to an interned string. Use operator bool to
76  /// test whether the pointer is valid, and operator * to get the string if so.
77  /// This is a lightweight value class with storage requirements equivalent to
78  /// a single pointer, but it does have reference-counting overhead when
79  /// copied.
80  class PooledStringPtr {
81    typedef StringPool::entry_t entry_t;
82    entry_t *S;
83
84  public:
85    PooledStringPtr() : S(nullptr) {}
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 LLVM_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 llvm namespace
139
140#endif
141