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 <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:
     50       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     ///
     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:
     83     PooledStringPtr() : S(nullptr) {}
     84 
     85     explicit PooledStringPtr(entry_t *E) : S(E) {
     86       if (S) ++S->getValue().Refcount;
     87     }
     88 
     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 
    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 
    112     ~PooledStringPtr() { clear(); }
    113 
    114     inline const char *begin() const {
    115       assert(*this && "Attempt to dereference empty PooledStringPtr!");
    116       return S->getKeyData();
    117     }
    118 
    119     inline const char *end() const {
    120       assert(*this && "Attempt to dereference empty PooledStringPtr!");
    121       return S->getKeyData() + S->getKeyLength();
    122     }
    123 
    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