Line data Source code
1 : // Copyright 2017 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_OBJECTS_DICTIONARY_H_
6 : #define V8_OBJECTS_DICTIONARY_H_
7 :
8 : #include "src/objects/hash-table.h"
9 :
10 : #include "src/base/export-template.h"
11 : #include "src/globals.h"
12 :
13 : // Has to be the last include (doesn't have include guards):
14 : #include "src/objects/object-macros.h"
15 :
16 : namespace v8 {
17 : namespace internal {
18 :
19 : template <typename T>
20 : class Handle;
21 :
22 : class Isolate;
23 :
24 : template <typename Derived, typename Shape>
25 : class Dictionary : public HashTable<Derived, Shape> {
26 : typedef HashTable<Derived, Shape> DerivedHashTable;
27 :
28 : public:
29 : typedef typename Shape::Key Key;
30 : // Returns the value at entry.
31 19298626 : Object* ValueAt(int entry) {
32 38597252 : return this->get(DerivedHashTable::EntryToIndex(entry) + 1);
33 : }
34 :
35 : // Set the value for entry.
36 0 : void ValueAtPut(int entry, Object* value) {
37 8631527 : this->set(DerivedHashTable::EntryToIndex(entry) + 1, value);
38 0 : }
39 :
40 : // Returns the property details for the property at entry.
41 0 : PropertyDetails DetailsAt(int entry) {
42 203490922 : return Shape::DetailsAt(static_cast<Derived*>(this), entry);
43 : }
44 :
45 : // Set the details for entry.
46 0 : void DetailsAtPut(int entry, PropertyDetails value) {
47 23627845 : Shape::DetailsAtPut(static_cast<Derived*>(this), entry, value);
48 0 : }
49 :
50 : // Delete a property from the dictionary.
51 : MUST_USE_RESULT static Handle<Derived> DeleteEntry(Handle<Derived> dictionary,
52 : int entry);
53 :
54 : // Attempt to shrink the dictionary after deletion of key.
55 284 : MUST_USE_RESULT static inline Handle<Derived> Shrink(
56 : Handle<Derived> dictionary) {
57 83125 : return DerivedHashTable::Shrink(dictionary);
58 : }
59 :
60 : int NumberOfEnumerableProperties();
61 :
62 : #ifdef OBJECT_PRINT
63 : // For our gdb macros, we should perhaps change these in the future.
64 : void Print();
65 :
66 : void Print(std::ostream& os); // NOLINT
67 : #endif
68 : // Returns the key (slow).
69 : Object* SlowReverseLookup(Object* value);
70 :
71 : // Sets the entry to (key, value) pair.
72 : inline void ClearEntry(int entry);
73 : inline void SetEntry(int entry, Object* key, Object* value,
74 : PropertyDetails details);
75 :
76 : MUST_USE_RESULT static Handle<Derived> Add(Handle<Derived> dictionary,
77 : Key key, Handle<Object> value,
78 : PropertyDetails details,
79 : int* entry_out = nullptr);
80 :
81 : protected:
82 : // Generic at put operation.
83 : MUST_USE_RESULT static Handle<Derived> AtPut(Handle<Derived> dictionary,
84 : Key key, Handle<Object> value,
85 : PropertyDetails details);
86 : };
87 :
88 : template <typename Key>
89 : class BaseDictionaryShape : public BaseShape<Key> {
90 : public:
91 : static const bool kHasDetails = true;
92 : template <typename Dictionary>
93 83290859 : static inline PropertyDetails DetailsAt(Dictionary* dict, int entry) {
94 : STATIC_ASSERT(Dictionary::kEntrySize == 3);
95 : DCHECK_GE(entry, 0); // Not found is -1, which is not caught by get().
96 : return PropertyDetails(Smi::cast(dict->get(
97 166581718 : Dictionary::EntryToIndex(entry) + Dictionary::kEntryDetailsIndex)));
98 : }
99 :
100 : template <typename Dictionary>
101 16452783 : static inline void DetailsAtPut(Dictionary* dict, int entry,
102 : PropertyDetails value) {
103 : STATIC_ASSERT(Dictionary::kEntrySize == 3);
104 : dict->set(Dictionary::EntryToIndex(entry) + Dictionary::kEntryDetailsIndex,
105 : value.AsSmi());
106 16452783 : }
107 : };
108 :
109 : class NameDictionaryShape : public BaseDictionaryShape<Handle<Name>> {
110 : public:
111 : static inline bool IsMatch(Handle<Name> key, Object* other);
112 : static inline uint32_t Hash(Isolate* isolate, Handle<Name> key);
113 : static inline uint32_t HashForObject(Isolate* isolate, Object* object);
114 : static inline Handle<Object> AsHandle(Isolate* isolate, Handle<Name> key);
115 : static const int kPrefixSize = 2;
116 : static const int kEntrySize = 3;
117 : static const int kEntryValueIndex = 1;
118 : static const bool kNeedsHoleCheck = false;
119 : };
120 :
121 : template <typename Derived, typename Shape>
122 : class BaseNameDictionary : public Dictionary<Derived, Shape> {
123 : typedef typename Shape::Key Key;
124 :
125 : public:
126 : static const int kNextEnumerationIndexIndex =
127 : HashTableBase::kPrefixStartIndex;
128 : static const int kObjectHashIndex = kNextEnumerationIndexIndex + 1;
129 : static const int kEntryValueIndex = 1;
130 :
131 : // Accessors for next enumeration index.
132 : void SetNextEnumerationIndex(int index) {
133 : DCHECK_NE(0, index);
134 : this->set(kNextEnumerationIndexIndex, Smi::FromInt(index));
135 : }
136 :
137 : int NextEnumerationIndex() {
138 : return Smi::ToInt(this->get(kNextEnumerationIndexIndex));
139 : }
140 :
141 : void SetHash(int hash) {
142 : DCHECK(PropertyArray::HashField::is_valid(hash));
143 : this->set(kObjectHashIndex, Smi::FromInt(hash));
144 : }
145 :
146 : int Hash() const {
147 : Object* hash_obj = this->get(kObjectHashIndex);
148 : int hash = Smi::ToInt(hash_obj);
149 : DCHECK(PropertyArray::HashField::is_valid(hash));
150 : return hash;
151 : }
152 :
153 : // Creates a new dictionary.
154 : MUST_USE_RESULT static Handle<Derived> New(
155 : Isolate* isolate, int at_least_space_for,
156 : PretenureFlag pretenure = NOT_TENURED,
157 : MinimumCapacity capacity_option = USE_DEFAULT_MINIMUM_CAPACITY);
158 :
159 : // Collect the keys into the given KeyAccumulator, in ascending chronological
160 : // order of property creation.
161 79310 : static void CollectKeysTo(Handle<Derived> dictionary, KeyAccumulator* keys);
162 :
163 : // Return the key indices sorted by its enumeration index.
164 : static Handle<FixedArray> IterationIndices(Handle<Derived> dictionary);
165 :
166 : // Copies enumerable keys to preallocated fixed array.
167 : static void CopyEnumKeysTo(Handle<Derived> dictionary,
168 : Handle<FixedArray> storage, KeyCollectionMode mode,
169 : KeyAccumulator* accumulator);
170 :
171 : // Ensure enough space for n additional elements.
172 : static Handle<Derived> EnsureCapacity(Handle<Derived> dictionary, int n);
173 :
174 : MUST_USE_RESULT static Handle<Derived> Add(Handle<Derived> dictionary,
175 : Key key, Handle<Object> value,
176 : PropertyDetails details,
177 : int* entry_out = nullptr);
178 : };
179 :
180 : class NameDictionary
181 : : public BaseNameDictionary<NameDictionary, NameDictionaryShape> {
182 : public:
183 : DECL_CAST(NameDictionary)
184 :
185 : static const int kEntryDetailsIndex = 2;
186 : static const int kInitialCapacity = 2;
187 :
188 : inline Name* NameAt(int entry);
189 : inline void set_hash(int hash);
190 : inline int hash() const;
191 : };
192 :
193 : class GlobalDictionaryShape : public NameDictionaryShape {
194 : public:
195 : static inline bool IsMatch(Handle<Name> key, Object* other);
196 : static inline uint32_t HashForObject(Isolate* isolate, Object* object);
197 :
198 : static const int kEntrySize = 1; // Overrides NameDictionaryShape::kEntrySize
199 :
200 : template <typename Dictionary>
201 : static inline PropertyDetails DetailsAt(Dictionary* dict, int entry);
202 :
203 : template <typename Dictionary>
204 : static inline void DetailsAtPut(Dictionary* dict, int entry,
205 : PropertyDetails value);
206 :
207 : static inline Object* Unwrap(Object* key);
208 : static inline bool IsKey(Isolate* isolate, Object* k);
209 : static inline bool IsLive(Isolate* isolate, Object* key);
210 : };
211 :
212 : class GlobalDictionary
213 : : public BaseNameDictionary<GlobalDictionary, GlobalDictionaryShape> {
214 : public:
215 : DECL_CAST(GlobalDictionary)
216 :
217 : inline Object* ValueAt(int entry);
218 : inline PropertyCell* CellAt(int entry);
219 : inline void SetEntry(int entry, Object* key, Object* value,
220 : PropertyDetails details);
221 : inline Name* NameAt(int entry);
222 : inline void ValueAtPut(int entry, Object* value);
223 : };
224 :
225 : class NumberDictionaryShape : public BaseDictionaryShape<uint32_t> {
226 : public:
227 : static inline bool IsMatch(uint32_t key, Object* other);
228 : static inline Handle<Object> AsHandle(Isolate* isolate, uint32_t key);
229 : };
230 :
231 : class SeededNumberDictionaryShape : public NumberDictionaryShape {
232 : public:
233 : static const int kPrefixSize = 1;
234 : static const int kEntrySize = 3;
235 :
236 : static inline uint32_t Hash(Isolate* isolate, uint32_t key);
237 : static inline uint32_t HashForObject(Isolate* isolate, Object* object);
238 : };
239 :
240 : class UnseededNumberDictionaryShape : public NumberDictionaryShape {
241 : public:
242 : static const bool kHasDetails = false;
243 : static const int kPrefixSize = 0;
244 : static const int kEntrySize = 2;
245 :
246 : static inline uint32_t Hash(Isolate* isolate, uint32_t key);
247 : static inline uint32_t HashForObject(Isolate* isolate, Object* object);
248 :
249 : template <typename Dictionary>
250 0 : static inline PropertyDetails DetailsAt(Dictionary* dict, int entry) {
251 0 : UNREACHABLE();
252 : }
253 :
254 : template <typename Dictionary>
255 0 : static inline void DetailsAtPut(Dictionary* dict, int entry,
256 : PropertyDetails value) {
257 0 : UNREACHABLE();
258 : }
259 :
260 : static inline Map* GetMap(Isolate* isolate);
261 : };
262 :
263 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
264 : HashTable<SeededNumberDictionary, SeededNumberDictionaryShape>;
265 :
266 : extern template class EXPORT_TEMPLATE_DECLARE(V8_EXPORT_PRIVATE)
267 : Dictionary<SeededNumberDictionary, SeededNumberDictionaryShape>;
268 :
269 : class SeededNumberDictionary
270 : : public Dictionary<SeededNumberDictionary, SeededNumberDictionaryShape> {
271 : public:
272 : DECL_CAST(SeededNumberDictionary)
273 :
274 : // Type specific at put (default NONE attributes is used when adding).
275 : MUST_USE_RESULT static Handle<SeededNumberDictionary> Set(
276 : Handle<SeededNumberDictionary> dictionary, uint32_t key,
277 : Handle<Object> value, Handle<JSObject> dictionary_holder,
278 : PropertyDetails details = PropertyDetails::Empty());
279 :
280 : static const int kMaxNumberKeyIndex = kPrefixStartIndex;
281 : void UpdateMaxNumberKey(uint32_t key, Handle<JSObject> dictionary_holder);
282 :
283 : // Returns true if the dictionary contains any elements that are non-writable,
284 : // non-configurable, non-enumerable, or have getters/setters.
285 : bool HasComplexElements();
286 :
287 : // Sorting support
288 : void CopyValuesTo(FixedArray* elements);
289 :
290 : // If slow elements are required we will never go back to fast-case
291 : // for the elements kept in this dictionary. We require slow
292 : // elements if an element has been added at an index larger than
293 : // kRequiresSlowElementsLimit or set_requires_slow_elements() has been called
294 : // when defining a getter or setter with a number key.
295 : inline bool requires_slow_elements();
296 : inline void set_requires_slow_elements();
297 :
298 : // Get the value of the max number key that has been added to this
299 : // dictionary. max_number_key can only be called if
300 : // requires_slow_elements returns false.
301 : inline uint32_t max_number_key();
302 :
303 : static const int kEntryValueIndex = 1;
304 : static const int kEntryDetailsIndex = 2;
305 :
306 : // Bit masks.
307 : static const int kRequiresSlowElementsMask = 1;
308 : static const int kRequiresSlowElementsTagSize = 1;
309 : static const uint32_t kRequiresSlowElementsLimit = (1 << 29) - 1;
310 :
311 : // JSObjects prefer dictionary elements if the dictionary saves this much
312 : // memory compared to a fast elements backing store.
313 : static const uint32_t kPreferFastElementsSizeFactor = 3;
314 : };
315 :
316 : class UnseededNumberDictionary
317 : : public Dictionary<UnseededNumberDictionary,
318 : UnseededNumberDictionaryShape> {
319 : public:
320 : DECL_CAST(UnseededNumberDictionary)
321 :
322 : // Type specific at put (default NONE attributes is used when adding).
323 : MUST_USE_RESULT static Handle<UnseededNumberDictionary> Set(
324 : Handle<UnseededNumberDictionary> dictionary, uint32_t key,
325 : Handle<Object> value);
326 :
327 : static const int kEntryValueIndex = 1;
328 : };
329 :
330 : } // namespace internal
331 : } // namespace v8
332 :
333 : #include "src/objects/object-macros-undef.h"
334 :
335 : #endif // V8_OBJECTS_DICTIONARY_H_
|
