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 class Zone; 17 18 // Base class of identity maps contains shared code for all template 19 // instantions. 20 class IdentityMapBase { 21 protected: 22 // Allow Tester to access internals, including changing the address of objects 23 // within the {keys_} array in order to simulate a moving GC. 24 friend class IdentityMapTester; 25 26 typedef void** RawEntry; 27 IdentityMapBase(Heap * heap,Zone * zone)28 IdentityMapBase(Heap* heap, Zone* zone) 29 : heap_(heap), 30 zone_(zone), 31 gc_counter_(-1), 32 size_(0), 33 mask_(0), 34 keys_(nullptr), 35 values_(nullptr) {} 36 ~IdentityMapBase(); 37 38 RawEntry GetEntry(Object* key); 39 RawEntry FindEntry(Object* key); 40 void Clear(); 41 42 private: 43 // Internal implementation should not be called directly by subclasses. 44 int LookupIndex(Object* address); 45 int InsertIndex(Object* address); 46 void Rehash(); 47 void Resize(); 48 RawEntry Lookup(Object* key); 49 RawEntry Insert(Object* key); 50 int Hash(Object* address); 51 52 base::hash<uintptr_t> hasher_; 53 Heap* heap_; 54 Zone* zone_; 55 int gc_counter_; 56 int size_; 57 int mask_; 58 Object** keys_; 59 void** values_; 60 }; 61 62 // Implements an identity map from object addresses to a given value type {V}. 63 // The map is robust w.r.t. garbage collection by synchronization with the 64 // supplied {heap}. 65 // * Keys are treated as strong roots. 66 // * SMIs are valid keys, except SMI #0. 67 // * The value type {V} must be reinterpret_cast'able to {void*} 68 // * The value type {V} must not be a heap type. 69 template <typename V> 70 class IdentityMap : public IdentityMapBase { 71 public: IdentityMap(Heap * heap,Zone * zone)72 IdentityMap(Heap* heap, Zone* zone) : IdentityMapBase(heap, zone) {} 73 74 // Searches this map for the given key using the object's address 75 // as the identity, returning: 76 // found => a pointer to the storage location for the value 77 // not found => a pointer to a new storage location for the value Get(Handle<Object> key)78 V* Get(Handle<Object> key) { return Get(*key); } Get(Object * key)79 V* Get(Object* key) { return reinterpret_cast<V*>(GetEntry(key)); } 80 81 // Searches this map for the given key using the object's address 82 // as the identity, returning: 83 // found => a pointer to the storage location for the value 84 // not found => {nullptr} Find(Handle<Object> key)85 V* Find(Handle<Object> key) { return Find(*key); } Find(Object * key)86 V* Find(Object* key) { return reinterpret_cast<V*>(FindEntry(key)); } 87 88 // Set the value for the given key. Set(Handle<Object> key,V v)89 void Set(Handle<Object> key, V v) { Set(*key, v); } Set(Object * key,V v)90 void Set(Object* key, V v) { *(reinterpret_cast<V*>(GetEntry(key))) = v; } 91 92 // Removes all elements from the map. Clear()93 void Clear() { IdentityMapBase::Clear(); } 94 }; 95 } // namespace internal 96 } // namespace v8 97 98 #endif // V8_IDENTITY_MAP_H_ 99