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 :
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 546704 : is_iterable_(false) {}
42 : virtual ~IdentityMapBase();
43 :
44 : RawEntry GetEntry(Object* key);
45 : RawEntry FindEntry(Object* key) const;
46 : void* DeleteEntry(Object* key);
47 : void Clear();
48 :
49 : V8_EXPORT_PRIVATE RawEntry EntryAtIndex(int index) const;
50 : V8_EXPORT_PRIVATE int NextIndex(int index) const;
51 :
52 : void EnableIteration();
53 : void DisableIteration();
54 :
55 : virtual void** NewPointerArray(size_t length) = 0;
56 : virtual void DeleteArray(void* array) = 0;
57 :
58 : private:
59 : // Internal implementation should not be called directly by subclasses.
60 : int ScanKeysFor(Object* address) const;
61 : int InsertKey(Object* address);
62 : int Lookup(Object* key) const;
63 : int LookupOrInsert(Object* key);
64 : void* DeleteIndex(int index);
65 : void Rehash();
66 : void Resize(int new_capacity);
67 : int Hash(Object* address) const;
68 :
69 : base::hash<uintptr_t> hasher_;
70 : Heap* heap_;
71 : int gc_counter_;
72 : int size_;
73 : int capacity_;
74 : int mask_;
75 : Object** keys_;
76 : void** values_;
77 : bool is_iterable_;
78 :
79 : DISALLOW_COPY_AND_ASSIGN(IdentityMapBase);
80 : };
81 :
82 : // Implements an identity map from object addresses to a given value type {V}.
83 : // The map is robust w.r.t. garbage collection by synchronization with the
84 : // supplied {heap}.
85 : // * Keys are treated as strong roots.
86 : // * The value type {V} must be reinterpret_cast'able to {void*}
87 : // * The value type {V} must not be a heap type.
88 : template <typename V, class AllocationPolicy>
89 : class IdentityMap : public IdentityMapBase {
90 : public:
91 : explicit IdentityMap(Heap* heap,
92 : AllocationPolicy allocator = AllocationPolicy())
93 546704 : : IdentityMapBase(heap), allocator_(allocator) {}
94 1089134 : ~IdentityMap() override { Clear(); };
95 :
96 : // Searches this map for the given key using the object's address
97 : // as the identity, returning:
98 : // found => a pointer to the storage location for the value
99 : // not found => a pointer to a new storage location for the value
100 : V* Get(Handle<Object> key) { return Get(*key); }
101 25651448 : V* Get(Object* key) { return reinterpret_cast<V*>(GetEntry(key)); }
102 :
103 : // Searches this map for the given key using the object's address
104 : // as the identity, returning:
105 : // found => a pointer to the storage location for the value
106 : // not found => {nullptr}
107 : V* Find(Handle<Object> key) const { return Find(*key); }
108 23951 : V* Find(Object* key) const { return reinterpret_cast<V*>(FindEntry(key)); }
109 :
110 : // Set the value for the given key.
111 : void Set(Handle<Object> key, V v) { Set(*key, v); }
112 5978 : void Set(Object* key, V v) { *(reinterpret_cast<V*>(GetEntry(key))) = v; }
113 :
114 : V Delete(Handle<Object> key) { return Delete(*key); }
115 28 : V Delete(Object* key) { return reinterpret_cast<V>(DeleteEntry(key)); }
116 :
117 : // Removes all elements from the map.
118 663788 : void Clear() { IdentityMapBase::Clear(); }
119 :
120 : // Iterator over IdentityMap. The IteratableScope used to create this Iterator
121 : // must be live for the duration of the iteration.
122 : class Iterator {
123 : public:
124 : Iterator& operator++() {
125 : index_ = map_->NextIndex(index_);
126 : return *this;
127 : }
128 :
129 : V* operator*() { return reinterpret_cast<V*>(map_->EntryAtIndex(index_)); }
130 : V* operator->() { return reinterpret_cast<V*>(map_->EntryAtIndex(index_)); }
131 : bool operator!=(const Iterator& other) { return index_ != other.index_; }
132 :
133 : private:
134 : Iterator(IdentityMap* map, int index) : map_(map), index_(index) {}
135 :
136 : IdentityMap* map_;
137 : int index_;
138 :
139 : friend class IdentityMap;
140 : };
141 :
142 : class IteratableScope {
143 : public:
144 : explicit IteratableScope(IdentityMap* map) : map_(map) {
145 : CHECK(!map_->is_iterable());
146 : map_->EnableIteration();
147 : }
148 : ~IteratableScope() {
149 : CHECK(map_->is_iterable());
150 : map_->DisableIteration();
151 : }
152 :
153 : Iterator begin() { return Iterator(map_, map_->NextIndex(-1)); }
154 : Iterator end() { return Iterator(map_, map_->capacity()); }
155 :
156 : private:
157 : IdentityMap* map_;
158 : DISALLOW_COPY_AND_ASSIGN(IteratableScope);
159 : };
160 :
161 : protected:
162 2431930 : void** NewPointerArray(size_t length) override {
163 4863860 : return static_cast<void**>(allocator_.New(sizeof(void*) * length));
164 : }
165 2434439 : void DeleteArray(void* array) override { allocator_.Delete(array); }
166 :
167 : private:
168 : AllocationPolicy allocator_;
169 : DISALLOW_COPY_AND_ASSIGN(IdentityMap);
170 : };
171 :
172 : } // namespace internal
173 : } // namespace v8
174 :
175 : #endif // V8_IDENTITY_MAP_H_
|
