1 // Copyright 2016 the V8 project 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 V8_BASE_HASHMAP_ENTRY_H_ 6 #define V8_BASE_HASHMAP_ENTRY_H_ 7 8 #include <cstdint> 9 #include <type_traits> 10 11 #include "src/base/memory.h" 12 13 namespace v8 { 14 namespace base { 15 16 // Marker type for hashmaps without a value (i.e. hashsets). These won't 17 // allocate space for the value in the entry. 18 struct NoHashMapValue {}; 19 20 // HashMap entries are (key, value, hash) triplets, with a boolean indicating if 21 // they are an empty entry. Some clients may not need to use the value slot 22 // (e.g. implementers of sets, where the key is the value), in which case they 23 // should use NoHashMapValue. 24 template <typename Key, typename Value> 25 struct TemplateHashMapEntry { 26 STATIC_ASSERT((!std::is_same<Value, NoHashMapValue>::value)); 27 28 Key key; 29 Value value; 30 uint32_t hash; // The full hash value for key 31 TemplateHashMapEntryTemplateHashMapEntry32 TemplateHashMapEntry(Key key, Value value, uint32_t hash) 33 : key(key), value(value), hash(hash), exists_(true) {} 34 existsTemplateHashMapEntry35 bool exists() const { return exists_; } 36 clearTemplateHashMapEntry37 void clear() { exists_ = false; } 38 39 private: 40 bool exists_; 41 }; 42 43 // Specialization for pointer-valued keys 44 template <typename Key, typename Value> 45 struct TemplateHashMapEntry<Key*, Value> { 46 STATIC_ASSERT((!std::is_same<Value, NoHashMapValue>::value)); 47 48 Key* key; 49 Value value; 50 uint32_t hash; // The full hash value for key 51 52 TemplateHashMapEntry(Key* key, Value value, uint32_t hash) 53 : key(key), value(value), hash(hash) {} 54 55 bool exists() const { return key != nullptr; } 56 57 void clear() { key = nullptr; } 58 }; 59 60 // Specialization for no value. 61 template <typename Key> 62 struct TemplateHashMapEntry<Key, NoHashMapValue> { 63 union { 64 Key key; 65 NoHashMapValue value; // Value in union with key to not take up space. 66 }; 67 uint32_t hash; // The full hash value for key 68 69 TemplateHashMapEntry(Key key, NoHashMapValue value, uint32_t hash) 70 : key(key), hash(hash), exists_(true) {} 71 72 bool exists() const { return exists_; } 73 74 void clear() { exists_ = false; } 75 76 private: 77 bool exists_; 78 }; 79 80 // Specialization for pointer-valued keys and no value. 81 template <typename Key> 82 struct TemplateHashMapEntry<Key*, NoHashMapValue> { 83 union { 84 Key* key; 85 NoHashMapValue value; // Value in union with key to not take up space. 86 }; 87 uint32_t hash; // The full hash value for key 88 89 TemplateHashMapEntry(Key* key, NoHashMapValue value, uint32_t hash) 90 : key(key), hash(hash) {} 91 92 bool exists() const { return key != nullptr; } 93 94 void clear() { key = nullptr; } 95 }; 96 97 } // namespace base 98 } // namespace v8 99 100 #endif // V8_BASE_HASHMAP_ENTRY_H_ 101