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 <new>
     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;  ///< 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