1 // Copyright 2015 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_IDENTITY_MAP_H_ 6 #define V8_IDENTITY_MAP_H_ 7 8 #include "src/base/functional.h" 9 #include "src/handles.h" 10 11 namespace v8 { 12 namespace internal { 13 14 // Forward declarations. 15 class Heap; 16 17 // Base class of identity maps contains shared code for all template 18 // instantions. 19 class IdentityMapBase { 20 public: 21 bool empty() const { return size_ == 0; } 22 int size() const { return size_; } 23 int capacity() const { return capacity_; } 24 bool is_iterable() const { return is_iterable_; } 25 26 protected: 27 // Allow Tester to access internals, including changing the address of objects 28 // within the {keys_} array in order to simulate a moving GC. 29 friend class IdentityMapTester; 30 31 typedef void** RawEntry; 32 33 explicit IdentityMapBase(Heap* heap) 34 : heap_(heap), 35 gc_counter_(-1), 36 size_(0), 37 capacity_(0), 38 mask_(0), 39 keys_(nullptr), 40 values_(nullptr), 41 is_iterable_(false) {} 42 virtual ~IdentityMapBase(); 43 44 RawEntry GetEntry(Object* key); 45 RawEntry FindEntry(Object* key) const; 46 bool DeleteEntry(Object* key, void** deleted_value); 47 void Clear(); 48 49 Object* KeyAtIndex(int index) const; 50 51 V8_EXPORT_PRIVATE RawEntry EntryAtIndex(int index) const; 52 V8_EXPORT_PRIVATE int NextIndex(int index) const; 53 54 void EnableIteration(); 55 void DisableIteration(); 56 57 virtual void** NewPointerArray(size_t length) = 0; 58 virtual void DeleteArray(void* array) = 0; 59 60 private: 61 // Internal implementation should not be called directly by subclasses. 62 int ScanKeysFor(Object* address) const; 63 int InsertKey(Object* address); 64 int Lookup(Object* key) const; 65 int LookupOrInsert(Object* key); 66 bool DeleteIndex(int index, void** deleted_value); 67 void Rehash(); 68 void Resize(int new_capacity); 69 int Hash(Object* address) const; 70 71 base::hash<uintptr_t> hasher_; 72 Heap* heap_; 73 int gc_counter_; 74 int size_; 75 int capacity_; 76 int mask_; 77 Object** keys_; 78 void** values_; 79 bool is_iterable_; 80 81 DISALLOW_COPY_AND_ASSIGN(IdentityMapBase); 82 }; 83 84 // Implements an identity map from object addresses to a given value type {V}. 85 // The map is robust w.r.t. garbage collection by synchronization with the 86 // supplied {heap}. 87 // * Keys are treated as strong roots. 88 // * The value type {V} must be reinterpret_cast'able to {void*} 89 // * The value type {V} must not be a heap type. 90 template <typename V, class AllocationPolicy> 91 class IdentityMap : public IdentityMapBase { 92 public: 93 explicit IdentityMap(Heap* heap, 94 AllocationPolicy allocator = AllocationPolicy()) 95 : IdentityMapBase(heap), allocator_(allocator) {} 96 ~IdentityMap() override { Clear(); }; 97 98 // Searches this map for the given key using the object's address 99 // as the identity, returning: 100 // found => a pointer to the storage location for the value 101 // not found => a pointer to a new storage location for the value 102 V* Get(Handle<Object> key) { return Get(*key); } 103 V* Get(Object* key) { return reinterpret_cast<V*>(GetEntry(key)); } 104 105 // Searches this map for the given key using the object's address 106 // as the identity, returning: 107 // found => a pointer to the storage location for the value 108 // not found => {nullptr} 109 V* Find(Handle<Object> key) const { return Find(*key); } 110 V* Find(Object* key) const { return reinterpret_cast<V*>(FindEntry(key)); } 111 112 // Set the value for the given key. 113 void Set(Handle<Object> key, V v) { Set(*key, v); } 114 void Set(Object* key, V v) { *(reinterpret_cast<V*>(GetEntry(key))) = v; } 115 116 bool Delete(Handle<Object> key, V* deleted_value) { 117 return Delete(*key, deleted_value); 118 } 119 bool Delete(Object* key, V* deleted_value) { 120 void* v = nullptr; 121 bool deleted_something = DeleteEntry(key, &v); 122 if (deleted_value != nullptr && deleted_something) { 123 *deleted_value = (V) reinterpret_cast<intptr_t>(v); 124 } 125 return deleted_something; 126 } 127 128 // Removes all elements from the map. 129 void Clear() { IdentityMapBase::Clear(); } 130 131 // Iterator over IdentityMap. The IteratableScope used to create this Iterator 132 // must be live for the duration of the iteration. 133 class Iterator { 134 public: 135 Iterator& operator++() { 136 index_ = map_->NextIndex(index_); 137 return *this; 138 } 139 140 Object* key() const { return map_->KeyAtIndex(index_); } 141 V* entry() const { 142 return reinterpret_cast<V*>(map_->EntryAtIndex(index_)); 143 } 144 145 V* operator*() { return entry(); } 146 V* operator->() { return entry(); } 147 bool operator!=(const Iterator& other) { return index_ != other.index_; } 148 149 private: 150 Iterator(IdentityMap* map, int index) : map_(map), index_(index) {} 151 152 IdentityMap* map_; 153 int index_; 154 155 friend class IdentityMap; 156 }; 157 158 class IteratableScope { 159 public: 160 explicit IteratableScope(IdentityMap* map) : map_(map) { 161 CHECK(!map_->is_iterable()); 162 map_->EnableIteration(); 163 } 164 ~IteratableScope() { 165 CHECK(map_->is_iterable()); 166 map_->DisableIteration(); 167 } 168 169 Iterator begin() { return Iterator(map_, map_->NextIndex(-1)); } 170 Iterator end() { return Iterator(map_, map_->capacity()); } 171 172 private: 173 IdentityMap* map_; 174 DISALLOW_COPY_AND_ASSIGN(IteratableScope); 175 }; 176 177 protected: 178 void** NewPointerArray(size_t length) override { 179 return static_cast<void**>(allocator_.New(sizeof(void*) * length)); 180 } 181 void DeleteArray(void* array) override { allocator_.Delete(array); } 182 183 private: 184 AllocationPolicy allocator_; 185 DISALLOW_COPY_AND_ASSIGN(IdentityMap); 186 }; 187 188 } // namespace internal 189 } // namespace v8 190 191 #endif // V8_IDENTITY_MAP_H_ 192