OLD | NEW |
(Empty) | |
| 1 //===- subzero/src/IceStringPool.h - String pooling -------------*- C++ -*-===// |
| 2 // |
| 3 // The Subzero Code Generator |
| 4 // |
| 5 // This file is distributed under the University of Illinois Open Source |
| 6 // License. See LICENSE.TXT for details. |
| 7 // |
| 8 //===----------------------------------------------------------------------===// |
| 9 /// |
| 10 /// \file |
| 11 /// \brief Defines unique pooled strings with short unique IDs. This makes |
| 12 /// hashing, equality testing, and ordered comparison faster, and avoids a lot |
| 13 /// of memory allocation compared to directly using std::string. |
| 14 /// |
| 15 //===----------------------------------------------------------------------===// |
| 16 |
| 17 #ifndef SUBZERO_SRC_ICESTRINGPOOL_H |
| 18 #define SUBZERO_SRC_ICESTRINGPOOL_H |
| 19 |
| 20 #include <cstdint> // uintptr_t |
| 21 #include <string> |
| 22 |
| 23 namespace Ice { |
| 24 |
| 25 class StringPool { |
| 26 StringPool(const StringPool &) = delete; |
| 27 StringPool &operator=(const StringPool &) = delete; |
| 28 |
| 29 public: |
| 30 using IDType = uintptr_t; |
| 31 |
| 32 StringPool() = default; |
| 33 ~StringPool() = default; |
| 34 IDType getNewID() { |
| 35 // TODO(stichnot): Make it so that the GlobalString ctor doesn't have to |
| 36 // grab the lock, and instead does an atomic increment of NextID. |
| 37 auto NewID = NextID; |
| 38 NextID += IDIncrement; |
| 39 return NewID; |
| 40 } |
| 41 IDType getOrAddString(const std::string &Value) { |
| 42 auto Iter = StringToId.find(Value); |
| 43 if (Iter == StringToId.end()) { |
| 44 auto *NewStr = new std::string(Value); |
| 45 auto ID = reinterpret_cast<IDType>(NewStr); |
| 46 assert(StringToId.find(Value) == StringToId.end()); |
| 47 StringToId[Value].reset(NewStr); |
| 48 return ID; |
| 49 } |
| 50 return reinterpret_cast<IDType>(Iter->second.get()); |
| 51 } |
| 52 void dump(Ostream &Str) { |
| 53 if (StringToId.empty()) |
| 54 return; |
| 55 Str << "String pool (NumStrings=" << StringToId.size() |
| 56 << " NumIDs=" << ((NextID - FirstID) / IDIncrement) << "):"; |
| 57 for (auto &Tuple : StringToId) { |
| 58 Str << " " << Tuple.first; |
| 59 } |
| 60 Str << "\n"; |
| 61 } |
| 62 |
| 63 private: |
| 64 static constexpr IDType FirstID = 1; |
| 65 static constexpr IDType IDIncrement = 2; |
| 66 IDType NextID = FirstID; |
| 67 std::unordered_map<std::string, std::unique_ptr<std::string>> StringToId; |
| 68 }; |
| 69 |
| 70 template <typename Traits> class StringID { |
| 71 public: |
| 72 using IDType = StringPool::IDType; |
| 73 |
| 74 StringID(const StringID &) = default; |
| 75 StringID &operator=(const StringID &) = default; |
| 76 // Create a default, invalid StringID. |
| 77 StringID() = default; |
| 78 /// Create a unique StringID without an actual string, by grabbing the next |
| 79 /// unique integral ID from the Owner. |
| 80 explicit StringID(const typename Traits::OwnerType *Owner) |
| 81 : ID(Traits::getStrings(Owner)->getNewID()) {} |
| 82 /// Create a unique StringID that holds an actual string, by fetching or |
| 83 /// adding the string from the Owner's pool. |
| 84 StringID(const typename Traits::OwnerType *Owner, const std::string &Value) |
| 85 : ID(Traits::getStrings(Owner)->getOrAddString(Value)) { |
| 86 assert(hasString()); |
| 87 } |
| 88 |
| 89 static bool hasString(IDType ID) { return isValid(ID) && ((ID & 0x1) == 0); } |
| 90 bool hasString() const { return hasString(ID); } |
| 91 |
| 92 IDType getID() const { |
| 93 assert(isValid()); |
| 94 return ID; |
| 95 } |
| 96 const std::string &toString() const { |
| 97 assert(hasString()); |
| 98 return *reinterpret_cast<std::string *>(ID); |
| 99 } |
| 100 std::string toStringOrEmpty() const { |
| 101 if (hasString()) |
| 102 return toString(); |
| 103 return ""; |
| 104 } |
| 105 |
| 106 bool operator==(const StringID &Other) const { return ID == Other.ID; } |
| 107 bool operator!=(const StringID &Other) const { return !(*this == Other); } |
| 108 bool operator<(const StringID &Other) const { |
| 109 const bool ThisHasString = hasString(); |
| 110 const bool OtherHasString = Other.hasString(); |
| 111 // Do a normal string comparison if both have strings. |
| 112 if (ThisHasString && OtherHasString) |
| 113 return this->toString() < Other.toString(); |
| 114 // Use the ID as a tiebreaker if neither has a string. |
| 115 if (!ThisHasString && !OtherHasString) |
| 116 return ID < Other.ID; |
| 117 // If exactly one has a string, then that one comes first. |
| 118 assert(!OtherHasString); |
| 119 return ThisHasString; |
| 120 } |
| 121 |
| 122 private: |
| 123 static constexpr IDType InvalidID = 0; |
| 124 IDType ID = InvalidID; |
| 125 |
| 126 static bool isValid(IDType ID) { return ID != InvalidID; } |
| 127 bool isValid() const { return isValid(ID); } |
| 128 }; |
| 129 |
| 130 struct GlobalStringPoolTraits { |
| 131 using OwnerType = GlobalContext; |
| 132 static LockedPtr<StringPool> getStrings(const OwnerType *Owner); |
| 133 }; |
| 134 |
| 135 using GlobalString = StringID<struct GlobalStringPoolTraits>; |
| 136 |
| 137 template <typename T> |
| 138 Ostream &operator<<(Ostream &Str, const StringID<T> &Name) { |
| 139 return Str << Name.toString(); |
| 140 } |
| 141 |
| 142 template <typename T> |
| 143 std::string operator+(const std::string &A, const StringID<T> &B) { |
| 144 return A + B.toString(); |
| 145 } |
| 146 |
| 147 template <typename T> |
| 148 std::string operator+(const StringID<T> &A, const std::string &B) { |
| 149 return A.toString() + B; |
| 150 } |
| 151 |
| 152 } // end of namespace Ice |
| 153 |
| 154 namespace std { |
| 155 template <typename T> struct hash<Ice::StringID<T>> { |
| 156 size_t operator()(const Ice::StringID<T> &Key) const { |
| 157 if (Key.hasString()) |
| 158 return hash<std::string>()(Key.toString()); |
| 159 return hash<Ice::StringPool::IDType>()(Key.getID()); |
| 160 } |
| 161 }; |
| 162 } // end of namespace std |
| 163 |
| 164 #endif // SUBZERO_SRC_ICESTRINGPOOL_H |
OLD | NEW |