1 // Copyright 2014 The Crashpad Authors. All rights reserved. 2 // 3 // Licensed under the Apache License, Version 2.0 (the "License"); 4 // you may not use this file except in compliance with the License. 5 // You may obtain a copy of the License at 6 // 7 // http://www.apache.org/licenses/LICENSE-2.0 8 // 9 // Unless required by applicable law or agreed to in writing, software 10 // distributed under the License is distributed on an "AS IS" BASIS, 11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 12 // See the License for the specific language governing permissions and 13 // limitations under the License. 14 15 #ifndef CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_ 16 #define CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_ 17 18 #include <string.h> 19 #include <sys/types.h> 20 21 #include <algorithm> 22 #include <type_traits> 23 24 #include "base/check_op.h" 25 #include "base/macros.h" 26 #include "base/strings/string_piece.h" 27 #include "util/misc/implicit_cast.h" 28 29 namespace crashpad { 30 31 //! \brief A map/dictionary collection implementation using a fixed amount of 32 //! storage, so that it does not perform any dynamic allocations for its 33 //! operations. 34 //! 35 //! The actual map storage (TSimpleStringDictionary::Entry) is guaranteed to be 36 //! POD, so that it can be transmitted over various IPC mechanisms. 37 //! 38 //! The template parameters control the amount of storage used for the key, 39 //! value, and map. The \a KeySize and \a ValueSize are measured in bytes, not 40 //! glyphs, and include space for a trailing `NUL` byte. This gives space for 41 //! `KeySize - 1` and `ValueSize - 1` characters in an entry. \a NumEntries is 42 //! the total number of entries that will fit in the map. 43 template <size_t KeySize = 256, size_t ValueSize = 256, size_t NumEntries = 64> 44 class TSimpleStringDictionary { 45 public: 46 //! \brief Constant and publicly accessible versions of the template 47 //! parameters. 48 //! \{ 49 static const size_t key_size = KeySize; 50 static const size_t value_size = ValueSize; 51 static const size_t num_entries = NumEntries; 52 //! \} 53 54 //! \brief A single entry in the map. 55 struct Entry { 56 //! \brief The entry’s key. 57 //! 58 //! This string is always `NUL`-terminated. If this is a 0-length 59 //! `NUL`-terminated string, the entry is inactive. 60 char key[KeySize]; 61 62 //! \brief The entry’s value. 63 //! 64 //! This string is always `NUL`-terminated. 65 char value[ValueSize]; 66 67 //! \brief Returns the validity of the entry. 68 //! 69 //! If #key is an empty string, the entry is considered inactive, and this 70 //! method returns `false`. Otherwise, returns `true`. is_activeEntry71 bool is_active() const { 72 return key[0] != '\0'; 73 } 74 }; 75 76 //! \brief An iterator to traverse all of the active entries in a 77 //! TSimpleStringDictionary. 78 class Iterator { 79 public: Iterator(const TSimpleStringDictionary & map)80 explicit Iterator(const TSimpleStringDictionary& map) 81 : map_(map), 82 current_(0) { 83 } 84 85 //! \brief Returns the next entry in the map, or `nullptr` if at the end of 86 //! the collection. Next()87 const Entry* Next() { 88 while (current_ < map_.num_entries) { 89 const Entry* entry = &map_.entries_[current_++]; 90 if (entry->is_active()) { 91 return entry; 92 } 93 } 94 return nullptr; 95 } 96 97 private: 98 const TSimpleStringDictionary& map_; 99 size_t current_; 100 101 DISALLOW_COPY_AND_ASSIGN(Iterator); 102 }; 103 TSimpleStringDictionary()104 TSimpleStringDictionary() 105 : entries_() { 106 } 107 TSimpleStringDictionary(const TSimpleStringDictionary & other)108 TSimpleStringDictionary(const TSimpleStringDictionary& other) { 109 *this = other; 110 } 111 112 TSimpleStringDictionary& operator=(const TSimpleStringDictionary& other) { 113 memcpy(entries_, other.entries_, sizeof(entries_)); 114 return *this; 115 } 116 117 //! \brief Returns the number of active key/value pairs. The upper limit for 118 //! this is \a NumEntries. GetCount()119 size_t GetCount() const { 120 size_t count = 0; 121 for (size_t i = 0; i < num_entries; ++i) { 122 if (entries_[i].is_active()) { 123 ++count; 124 } 125 } 126 return count; 127 } 128 129 //! \brief Given \a key, returns its corresponding value. 130 //! 131 //! \param[in] key The key to look up. This must not be `nullptr`, nor an 132 //! empty string. It must not contain embedded `NUL`s. 133 //! 134 //! \return The corresponding value for \a key, or if \a key is not found, 135 //! `nullptr`. GetValueForKey(base::StringPiece key)136 const char* GetValueForKey(base::StringPiece key) const { 137 DCHECK(key.data()); 138 DCHECK(key.size()); 139 DCHECK_EQ(key.find('\0', 0), base::StringPiece::npos); 140 if (!key.data() || !key.size()) { 141 return nullptr; 142 } 143 144 const Entry* entry = GetConstEntryForKey(key); 145 if (!entry) { 146 return nullptr; 147 } 148 149 return entry->value; 150 } 151 152 //! \brief Stores \a value into \a key, replacing the existing value if \a key 153 //! is already present. 154 //! 155 //! If \a key is not yet in the map and the map is already full (containing 156 //! \a NumEntries active entries), this operation silently fails. 157 //! 158 //! \param[in] key The key to store. This must not be `nullptr`, nor an empty 159 //! string. It must not contain embedded `NUL`s. 160 //! \param[in] value The value to store. If `nullptr`, \a key is removed from 161 //! the map. Must not contain embedded `NUL`s. SetKeyValue(base::StringPiece key,base::StringPiece value)162 void SetKeyValue(base::StringPiece key, base::StringPiece value) { 163 if (!value.data()) { 164 RemoveKey(key); 165 return; 166 } 167 168 DCHECK(key.data()); 169 DCHECK(key.size()); 170 DCHECK_EQ(key.find('\0', 0), base::StringPiece::npos); 171 if (!key.data() || !key.size()) { 172 return; 173 } 174 175 // |key| must not be an empty string. 176 DCHECK_NE(key[0], '\0'); 177 if (key[0] == '\0') { 178 return; 179 } 180 181 // |value| must not contain embedded NULs. 182 DCHECK_EQ(value.find('\0', 0), base::StringPiece::npos); 183 184 Entry* entry = GetEntryForKey(key); 185 186 // If it does not yet exist, attempt to insert it. 187 if (!entry) { 188 for (size_t i = 0; i < num_entries; ++i) { 189 if (!entries_[i].is_active()) { 190 entry = &entries_[i]; 191 SetFromStringPiece(key, entry->key, key_size); 192 break; 193 } 194 } 195 } 196 197 // If the map is out of space, |entry| will be nullptr. 198 if (!entry) { 199 return; 200 } 201 202 #ifndef NDEBUG 203 // Sanity check that the key only appears once. 204 int count = 0; 205 for (size_t i = 0; i < num_entries; ++i) { 206 if (EntryKeyEquals(key, entries_[i])) { 207 ++count; 208 } 209 } 210 DCHECK_EQ(count, 1); 211 #endif 212 213 SetFromStringPiece(value, entry->value, value_size); 214 } 215 216 //! \brief Removes \a key from the map. 217 //! 218 //! If \a key is not found, this is a no-op. 219 //! 220 //! \param[in] key The key of the entry to remove. This must not be `nullptr`, 221 //! nor an empty string. It must not contain embedded `NUL`s. RemoveKey(base::StringPiece key)222 void RemoveKey(base::StringPiece key) { 223 DCHECK(key.data()); 224 DCHECK(key.size()); 225 DCHECK_EQ(key.find('\0', 0), base::StringPiece::npos); 226 if (!key.data() || !key.size()) { 227 return; 228 } 229 230 Entry* entry = GetEntryForKey(key); 231 if (entry) { 232 entry->key[0] = '\0'; 233 entry->value[0] = '\0'; 234 } 235 236 DCHECK_EQ(GetEntryForKey(key), implicit_cast<Entry*>(nullptr)); 237 } 238 239 private: SetFromStringPiece(base::StringPiece src,char * dst,size_t dst_size)240 static void SetFromStringPiece(base::StringPiece src, 241 char* dst, 242 size_t dst_size) { 243 size_t copy_len = std::min(dst_size - 1, src.size()); 244 src.copy(dst, copy_len); 245 dst[copy_len] = '\0'; 246 } 247 EntryKeyEquals(base::StringPiece key,const Entry & entry)248 static bool EntryKeyEquals(base::StringPiece key, const Entry& entry) { 249 if (key.size() >= KeySize) 250 return false; 251 252 // Test for a NUL terminator and early out if it's absent. 253 if (entry.key[key.size()] != '\0') 254 return false; 255 256 // As there's a NUL terminator at the right position in the entries 257 // string, strncmp can do the rest. 258 return strncmp(key.data(), entry.key, key.size()) == 0; 259 } 260 GetConstEntryForKey(base::StringPiece key)261 const Entry* GetConstEntryForKey(base::StringPiece key) const { 262 for (size_t i = 0; i < num_entries; ++i) { 263 if (EntryKeyEquals(key, entries_[i])) { 264 return &entries_[i]; 265 } 266 } 267 return nullptr; 268 } 269 GetEntryForKey(base::StringPiece key)270 Entry* GetEntryForKey(base::StringPiece key) { 271 return const_cast<Entry*>(GetConstEntryForKey(key)); 272 } 273 274 Entry entries_[NumEntries]; 275 }; 276 277 //! \brief A TSimpleStringDictionary with default template parameters. 278 //! 279 //! For historical reasons this specialized version is available with the same 280 //! size factors as a previous implementation. 281 using SimpleStringDictionary = TSimpleStringDictionary<256, 256, 64>; 282 283 static_assert(std::is_standard_layout<SimpleStringDictionary>::value, 284 "SimpleStringDictionary must be standard layout"); 285 286 } // namespace crashpad 287 288 #endif // CRASHPAD_CLIENT_SIMPLE_STRING_DICTIONARY_H_ 289