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#include <new>
35
36namespace 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;  ///< So the string can remove itself.
48      unsigned Refcount; ///< Number of referencing PooledStringPtrs.
49
50    public:
51      PooledString() : Pool(0), Refcount(0) { }
52    };
53
54    friend class PooledStringPtr;
55
56    typedef StringMap<PooledString> table_t;
57    typedef StringMapEntry<PooledString> entry_t;
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    typedef StringPool::entry_t entry_t;
81    entry_t *S;
82
83  public:
84    PooledStringPtr() : S(0) {}
85
86    explicit PooledStringPtr(entry_t *E) : S(E) {
87      if (S) ++S->getValue().Refcount;
88    }
89
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
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 = 0;
111    }
112
113    ~PooledStringPtr() { clear(); }
114
115    inline const char *begin() const {
116      assert(*this && "Attempt to dereference empty PooledStringPtr!");
117      return S->getKeyData();
118    }
119
120    inline const char *end() const {
121      assert(*this && "Attempt to dereference empty PooledStringPtr!");
122      return S->getKeyData() + S->getKeyLength();
123    }
124
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 operator bool() const { return S != 0; }
132
133    inline bool operator==(const PooledStringPtr &That) { return S == That.S; }
134    inline bool operator!=(const PooledStringPtr &That) { return S != That.S; }
135  };
136
137} // End llvm namespace
138
139#endif
140