Line data    Source code

       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           0 :     PooledStringPtr() = default;
      86             : 
      87         155 :     explicit PooledStringPtr(entry_t *E) : S(E) {
      88         155 :       if (S) ++S->getValue().Refcount;
      89             :     }
      90             : 
      91         295 :     PooledStringPtr(const PooledStringPtr &That) : S(That.S) {
      92         224 :       if (S) ++S->getValue().Refcount;
      93             :     }
      94             : 
      95           0 :     PooledStringPtr &operator=(const PooledStringPtr &That) {
      96           0 :       if (S != That.S) {
      97           0 :         clear();
      98           0 :         S = That.S;
      99           0 :         if (S) ++S->getValue().Refcount;
     100             :       }
     101           0 :       return *this;
     102             :     }
     103             : 
     104           0 :     void clear() {
     105           0 :       if (!S)
     106           0 :         return;
     107           0 :       if (--S->getValue().Refcount == 0) {
     108           0 :         S->getValue().Pool->InternTable.remove(S);
     109           0 :         S->Destroy();
     110             :       }
     111           0 :       S = nullptr;
     112             :     }
     113             : 
     114         359 :     ~PooledStringPtr() { clear(); }
     115             : 
     116           0 :     inline const char *begin() const {
     117             :       assert(*this && "Attempt to dereference empty PooledStringPtr!");
     118           0 :       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         488 :     inline const char *operator*() const { return begin(); }
     132           0 :     inline explicit operator bool() const { return S != nullptr; }
     133             : 
     134           0 :     inline bool operator==(const PooledStringPtr &That) const { return S == That.S; }
     135           1 :     inline bool operator!=(const PooledStringPtr &That) const { return S != That.S; }
     136             :   };
     137             : 
     138             : } // end namespace llvm
     139             : 
     140             : #endif // LLVM_SUPPORT_STRINGPOOL_H