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