Home | History | Annotate | Download | only in Support 
      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 "llvm/ADT/StringRef.h"
     34 #include <cassert>
     35 
     36 namespace 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 = nullptr;  ///< So the string can remove itself.
     48       unsigned Refcount = 0;       ///< Number of referencing PooledStringPtrs.
     49 
     50     public:
     51       PooledString() = default;
     52     };
     53 
     54     friend class PooledStringPtr;
     55 
     56     using table_t = StringMap<PooledString>;
     57     using entry_t = StringMapEntry<PooledString>;
     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     using entry_t = StringPool::entry_t;
     81 
     82     entry_t *S = nullptr;
     83 
     84   public:
     85     PooledStringPtr() = default;
     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 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 namespace llvm
    139 
    140 #endif // LLVM_SUPPORT_STRINGPOOL_H
    141