1 // Copyright (c) 2020 The Chromium Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style license that can be 3 // found in the LICENSE file. 4 5 #ifndef TOOLS_GN_STRING_ATOM_H_ 6 #define TOOLS_GN_STRING_ATOM_H_ 7 8 #include <functional> 9 #include <string> 10 11 // A StringAtom models a pointer to a globally unique constant string. 12 // 13 // They are useful as key types for sets and map container types, especially 14 // when a program uses multiple instances that tend to use the same strings 15 // (as happen very frequently in GN). 16 // 17 // Note that default equality and comparison functions will compare the 18 // string content, not the pointers, ensuring that the behaviour of 19 // standard containers using StringAtom key types is the same as if 20 // std::string was used. 21 // 22 // In addition, _ordered_ containers support heterogeneous lookups (i.e. 23 // using an std::string_view, and by automatic conversion, a const char* 24 // of const char[] literal) as a key type. 25 // 26 // Additionally, it is also possible to implement very fast _unordered_ 27 // containers by using the StringAtom::Fast{Hash,Equal,Compare} structs, 28 // which will force containers to hash/compare pointer values instead, 29 // for example: 30 // 31 // // A fast unordered set of unique strings. 32 // // 33 // // Implementation uses a hash table so performance will be bounded 34 // // by the string hash function. Does not support heterogeneous lookups. 35 // // 36 // using FastStringSet = std::unordered_set<StringAtom, 37 // StringAtom::PtrHash, 38 // StringAtom::PtrEqual>; 39 // 40 // // A fast unordered set of unique strings. 41 // // 42 // // Implementation uses a balanced binary tree so performance will 43 // // be bounded by string comparisons. Does support heterogeneous lookups, 44 // // but not that this does not extend to the [] operator, only to the 45 // // find() method. 46 // // 47 // using FastStringSet = std::set<StringAtom, StringAtom::PtrCompare> 48 // 49 // // A fast unordered { string -> VALUE } map. 50 // // 51 // // Implementation uses a balanced binary tree. Supports heterogeneous 52 // // lookups. 53 // template <typename VALUE> 54 // using FastStringMap = std::map<StringAtom, VALUE, StringAtom::PtrCompare> 55 // 56 class StringAtom { 57 public: 58 // Default constructor. Value points to a globally unique empty string. 59 StringAtom(); 60 61 // Destructor should do nothing at all. 62 ~StringAtom() = default; 63 64 // Non-explicit constructors. 65 StringAtom(std::string_view str) noexcept; 66 67 // Copy and move operations. StringAtom(const StringAtom & other)68 StringAtom(const StringAtom& other) noexcept : value_(other.value_) {} 69 StringAtom& operator=(const StringAtom& other) noexcept { 70 if (this != &other) { 71 this->~StringAtom(); // really a no-op 72 new (this) StringAtom(other); 73 } 74 return *this; 75 } 76 StringAtom(StringAtom && other)77 StringAtom(StringAtom&& other) noexcept : value_(other.value_) {} 78 StringAtom& operator=(const StringAtom&& other) noexcept { 79 if (this != &other) { 80 this->~StringAtom(); // really a no-op 81 new (this) StringAtom(std::move(other)); 82 } 83 return *this; 84 } 85 empty()86 bool empty() const { return value_.empty(); } 87 88 // Explicit conversions. str()89 const std::string& str() const { return value_; } 90 91 // Implicit conversions. string_view()92 operator std::string_view() const { return {value_}; } 93 94 // Returns true iff this is the same key. 95 // Note that the default comparison functions compare the value instead 96 // in order to use them in standard containers without surprises by 97 // default. SameAs(const StringAtom & other)98 bool SameAs(const StringAtom& other) const { 99 return &value_ == &other.value_; 100 } 101 102 // Default comparison functions. 103 bool operator==(const StringAtom& other) const { 104 return value_ == other.value_; 105 } 106 107 bool operator!=(const StringAtom& other) const { 108 return value_ != other.value_; 109 } 110 111 bool operator<(const StringAtom& other) const { 112 return value_ < other.value_; 113 } 114 hash()115 size_t hash() const { return std::hash<std::string>()(value_); } 116 117 // Use the following structs to implement containers that use StringAtom 118 // values as keys, but only compare/hash the pointer values for speed. 119 // E.g.: 120 // using FastSet = std::unordered_set<StringAtom, PtrHash, PtrEqual>; 121 // using FastMap = std::map<StringAtom, Value, PtrCompare>; 122 // 123 // IMPORTANT: Note that FastMap above is ordered based in the StringAtom 124 // pointer value, not the string content. 125 // 126 struct PtrHash { operatorPtrHash127 size_t operator()(const StringAtom& key) const noexcept { 128 return std::hash<const std::string*>()(&key.value_); 129 } 130 }; 131 132 struct PtrEqual { operatorPtrEqual133 bool operator()(const StringAtom& a, const StringAtom& b) const noexcept { 134 return &a.value_ == &b.value_; 135 } 136 }; 137 138 struct PtrCompare { operatorPtrCompare139 bool operator()(const StringAtom& a, const StringAtom& b) const noexcept { 140 return &a.value_ < &b.value_; 141 } 142 }; 143 144 protected: 145 const std::string& value_; 146 }; 147 148 namespace std { 149 150 // Ensure default heterogeneous lookups with other types like std::string_view. 151 template <> 152 struct less<StringAtom> { 153 using is_transparent = int; 154 155 bool operator()(const StringAtom& a, const StringAtom& b) const noexcept { 156 return a.str() < b.str(); 157 } 158 template <typename U> 159 bool operator()(const StringAtom& a, const U& b) const noexcept { 160 return a.str() < b; 161 } 162 template <typename U> 163 bool operator()(const U& a, const StringAtom& b) const noexcept { 164 return a < b.str(); 165 }; 166 }; 167 168 template <> 169 struct hash<StringAtom> { 170 size_t operator()(const StringAtom& key) const noexcept { return key.hash(); } 171 }; 172 173 } // namespace std 174 175 #endif // TOOLS_GN_STRING_ATOM_H_ 176