include/llvm/Support/StringPool.h

   1 //===-- StringPool.h - Interned string pool -------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Gordon Henriksen and is distributed under the
   6 // University of Illinois Open Source 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     struct PooledString {
  45       StringPool *Pool;  ///< So the string can remove itself.
  46       unsigned Refcount; ///< Number of referencing PooledStringPtrs.
  47
  48     public:
  49       PooledString() : Pool(0), Refcount(0) { }
  50     };
  51
  52     friend class PooledStringPtr;
  53
  54     typedef StringMap<PooledString> table_t;
  55     typedef StringMapEntry<PooledString> entry_t;
  56     table_t InternTable;
  57
  58   public:
  59     StringPool();
  60     ~StringPool();
  61
  62     PooledStringPtr intern(const char *Begin, const char *End);
  63     inline PooledStringPtr intern(const char *Str);
  64   };
  65
  66   /// PooledStringPtr - A pointer to an interned string. Use operator bool to
  67   /// test whether the pointer is valid, and operator * to get the string if so.
  68   /// This is a lightweight value class with storage requirements equivalent to
  69   /// a single pointer, but it does have reference-counting overhead when
  70   /// copied.
  71   class PooledStringPtr {
  72     typedef StringPool::entry_t entry_t;
  73     entry_t *S;
  74
  75   public:
  76     PooledStringPtr() : S(0) {}
  77
  78     explicit PooledStringPtr(entry_t *E) : S(E) {
  79       if (S) ++S->getValue().Refcount;
  80     }
  81
  82     PooledStringPtr(const PooledStringPtr &That) : S(That.S) {
  83       if (S) ++S->getValue().Refcount;
  84     }
  85
  86     PooledStringPtr &operator=(const PooledStringPtr &That) {
  87       if (S != That.S) {
  88         clear();
  89         S = That.S;
  90         if (S) ++S->getValue().Refcount;
  91       }
  92       return *this;
  93     }
  94
  95     void clear() {
  96       if (!S)
  97         return;
  98       if (--S->getValue().Refcount == 0) {
  99         S->getValue().Pool->InternTable.remove(S);
 100         delete S;
 101       }
 102       S = 0;
 103     }
 104
 105     ~PooledStringPtr() { clear(); }
 106
 107     inline const char *begin() const {
 108       assert(*this && "Attempt to dereference empty PooledStringPtr!");
 109       return S->getKeyData();
 110     }
 111
 112     inline const char *end() const {
 113       assert(*this && "Attempt to dereference empty PooledStringPtr!");
 114       return S->getKeyData() + S->getKeyLength();
 115     }
 116
 117     inline unsigned size() const {
 118       assert(*this && "Attempt to dereference empty PooledStringPtr!");
 119       return S->getKeyLength();
 120     }
 121
 122     inline const char *operator*() const { return begin(); }
 123     inline operator bool() const { return S != 0; }
 124
 125     inline bool operator==(const PooledStringPtr &That) { return S == That.S; }
 126     inline bool operator!=(const PooledStringPtr &That) { return S != That.S; }
 127   };
 128
 129   PooledStringPtr StringPool::intern(const char *Str) {
 130     return intern(Str, Str + strlen(Str));
 131   }
 132
 133 } // End llvm namespace
 134
 135 #endif