include/llvm/Support/StringPool.h

   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     ///
  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
  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 = nullptr;
 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 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