Line data Source code
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 :
12 : namespace v8 {
13 : namespace internal {
14 :
15 : // Forward declarations.
16 : class Heap;
17 :
18 : // Base class of identity maps contains shared code for all template
19 : // instantions.
20 : class 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 734062 : 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.
91 : template <typename V, class AllocationPolicy>
92 : class IdentityMap : public IdentityMapBase {
93 : public:
94 : explicit IdentityMap(Heap* heap,
95 : AllocationPolicy allocator = AllocationPolicy())
96 734062 : : IdentityMapBase(heap), allocator_(allocator) {}
97 1466063 : ~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 165994446 : 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 165847 : 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 39265 : *(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 115984 : void* v = nullptr;
126 115984 : bool deleted_something = DeleteEntry(key.ptr(), &v);
127 115984 : if (deleted_value != nullptr && deleted_something) {
128 10320 : *deleted_value = *reinterpret_cast<V*>(&v);
129 : }
130 : return deleted_something;
131 : }
132 :
133 : // Removes all elements from the map.
134 796545 : 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 18767 : index_ = map_->NextIndex(index_);
142 : return *this;
143 : }
144 :
145 12992 : Object key() const { return Object(map_->KeyAtIndex(index_)); }
146 : V* entry() const {
147 24542 : 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 166 : explicit IteratableScope(IdentityMap* map) : map_(map) {
166 166 : CHECK(!map_->is_iterable());
167 166 : map_->EnableIteration();
168 166 : }
169 166 : ~IteratableScope() {
170 166 : CHECK(map_->is_iterable());
171 166 : map_->DisableIteration();
172 166 : }
173 :
174 166 : Iterator begin() { return Iterator(map_, map_->NextIndex(-1)); }
175 18933 : Iterator end() { return Iterator(map_, map_->capacity()); }
176 :
177 : private:
178 : IdentityMap* map_;
179 : DISALLOW_COPY_AND_ASSIGN(IteratableScope);
180 : };
181 :
182 : protected:
183 6696315 : void** NewPointerArray(size_t length) override {
184 13392643 : return static_cast<void**>(allocator_.New(sizeof(void*) * length));
185 : }
186 6697186 : 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_
|
