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