Optimize own property GetByVals with rope string subscripts.
[WebKit-https.git] / Source / JavaScriptCore / runtime / PropertyMapHashTable.h
1 /*
2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008, 2014 Apple Inc. All rights reserved.
3  *
4  *  This library is free software; you can redistribute it and/or
5  *  modify it under the terms of the GNU Library General Public
6  *  License as published by the Free Software Foundation; either
7  *  version 2 of the License, or (at your option) any later version.
8  *
9  *  This library is distributed in the hope that it will be useful,
10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
12  *  Library General Public License for more details.
13  *
14  *  You should have received a copy of the GNU Library General Public License
15  *  along with this library; see the file COPYING.LIB.  If not, write to
16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
17  *  Boston, MA 02110-1301, USA.
18  *
19  */
20
21 #ifndef PropertyMapHashTable_h
22 #define PropertyMapHashTable_h
23
24 #include "JSExportMacros.h"
25 #include "PropertyOffset.h"
26 #include "Structure.h"
27 #include "WriteBarrier.h"
28 #include <wtf/CryptographicallyRandomNumber.h>
29 #include <wtf/HashTable.h>
30 #include <wtf/MathExtras.h>
31 #include <wtf/PassOwnPtr.h>
32 #include <wtf/Vector.h>
33 #include <wtf/text/StringImpl.h>
34
35
36 #define DUMP_PROPERTYMAP_STATS 0
37 #define DUMP_PROPERTYMAP_COLLISIONS 0
38
39 #define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1)
40
41 namespace JSC {
42
43 #if DUMP_PROPERTYMAP_STATS
44
45 struct PropertyMapHashTableStats {
46     std::atomic<unsigned> numFinds;
47     std::atomic<unsigned> numCollisions;
48     std::atomic<unsigned> numLookups;
49     std::atomic<unsigned> numLookupProbing;
50     std::atomic<unsigned> numAdds;
51     std::atomic<unsigned> numRemoves;
52     std::atomic<unsigned> numRehashes;
53     std::atomic<unsigned> numReinserts;
54 };
55
56 JS_EXPORTDATA extern PropertyMapHashTableStats* propertyMapHashTableStats;
57
58 #endif
59
60 inline bool isPowerOf2(unsigned v)
61 {
62     return hasOneBitSet(v);
63 }
64
65 inline unsigned nextPowerOf2(unsigned v)
66 {
67     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
68     // Devised by Sean Anderson, Sepember 14, 2001
69
70     v--;
71     v |= v >> 1;
72     v |= v >> 2;
73     v |= v >> 4;
74     v |= v >> 8;
75     v |= v >> 16;
76     v++;
77
78     return v;
79 }
80
81 struct PropertyMapEntry {
82     StringImpl* key;
83     PropertyOffset offset;
84     unsigned attributes;
85
86     PropertyMapEntry(StringImpl* key, PropertyOffset offset, unsigned attributes)
87         : key(key)
88         , offset(offset)
89         , attributes(attributes)
90     {
91     }
92 };
93
94 class PropertyTable : public JSCell {
95
96     // This is the implementation for 'iterator' and 'const_iterator',
97     // used for iterating over the table in insertion order.
98     template<typename T>
99     class ordered_iterator {
100     public:
101         ordered_iterator<T>& operator++()
102         {
103             m_valuePtr = skipDeletedEntries(m_valuePtr + 1);
104             return *this;
105         }
106
107         bool operator==(const ordered_iterator<T>& other)
108         {
109             return m_valuePtr == other.m_valuePtr;
110         }
111
112         bool operator!=(const ordered_iterator<T>& other)
113         {
114             return m_valuePtr != other.m_valuePtr;
115         }
116
117         T& operator*()
118         {
119             return *m_valuePtr;
120         }
121
122         T* operator->()
123         {
124             return m_valuePtr;
125         }
126
127         ordered_iterator(T* valuePtr)
128             : m_valuePtr(valuePtr)
129         {
130         }
131
132     private:
133         T* m_valuePtr;
134     };
135
136 public:
137     static const bool needsDestruction = true;
138     static const bool hasImmortalStructure = true;
139     static void destroy(JSCell*);
140
141     DECLARE_EXPORT_INFO;
142
143     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
144     {
145         return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
146     }
147
148     typedef StringImpl* KeyType;
149     typedef PropertyMapEntry ValueType;
150
151     // The in order iterator provides overloaded * and -> to access the Value at the current position.
152     typedef ordered_iterator<ValueType> iterator;
153     typedef ordered_iterator<const ValueType> const_iterator;
154
155     // The find_iterator is a pair of a pointer to a Value* an the entry in the index.
156     // If 'find' does not find an entry then iter.first will be 0, and iter.second will
157     // give the point in m_index where an entry should be inserted.
158     typedef std::pair<ValueType*, unsigned> find_iterator;
159
160     // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
161     static PropertyTable* create(VM&, unsigned initialCapacity);
162     static PropertyTable* clone(VM&, const PropertyTable&);
163     static PropertyTable* clone(VM&, unsigned initialCapacity, const PropertyTable&);
164     ~PropertyTable();
165
166     // Ordered iteration methods.
167     iterator begin();
168     iterator end();
169     const_iterator begin() const;
170     const_iterator end() const;
171
172     // Find a value in the table.
173     find_iterator find(const KeyType&);
174     ValueType* get(const KeyType&);
175     // Add a value to the table
176     enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
177     std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
178     // Remove a value from the table.
179     void remove(const find_iterator& iter);
180     void remove(const KeyType& key);
181
182     // Returns the number of values in the hashtable.
183     unsigned size() const;
184
185     // Checks if there are any values in the hashtable.
186     bool isEmpty() const;
187
188     // Number of slots in the property storage array in use, included deletedOffsets.
189     unsigned propertyStorageSize() const;
190
191     // Used to maintain a list of unused entries in the property storage.
192     void clearDeletedOffsets();
193     bool hasDeletedOffset();
194     PropertyOffset getDeletedOffset();
195     void addDeletedOffset(PropertyOffset);
196     
197     PropertyOffset nextOffset(PropertyOffset inlineCapacity);
198
199     // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
200     PropertyTable* copy(VM&, unsigned newCapacity);
201
202 #ifndef NDEBUG
203     size_t sizeInMemory();
204     void checkConsistency();
205 #endif
206
207 protected:
208     static const unsigned StructureFlags = StructureIsImmortal;
209
210 private:
211     PropertyTable(VM&, unsigned initialCapacity);
212     PropertyTable(VM&, const PropertyTable&);
213     PropertyTable(VM&, unsigned initialCapacity, const PropertyTable&);
214
215     PropertyTable(const PropertyTable&);
216     // Used to insert a value known not to be in the table, and where we know capacity to be available.
217     void reinsert(const ValueType& entry);
218
219     // Rehash the table.  Used to grow, or to recover deleted slots.
220     void rehash(unsigned newCapacity);
221
222     // The capacity of the table of values is half of the size of the index.
223     unsigned tableCapacity() const;
224
225     // We keep an extra deleted slot after the array to make iteration work,
226     // and to use for deleted values. Index values into the array are 1-based,
227     // so this is tableCapacity() + 1.
228     // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the
229     // values array is actually 9 long (the 9th used for the deleted value/
230     // iteration guard).  The 8 valid entries are numbered 1..8, so the
231     // deleted index is 9 (0 being reserved for empty).
232     unsigned deletedEntryIndex() const;
233
234     // Used in iterator creation/progression.
235     template<typename T>
236     static T* skipDeletedEntries(T* valuePtr);
237
238     // The table of values lies after the hash index.
239     ValueType* table();
240     const ValueType* table() const;
241
242     // total number of  used entries in the values array - by either valid entries, or deleted ones.
243     unsigned usedCount() const;
244
245     // The size in bytes of data needed for by the table.
246     size_t dataSize();
247
248     // Calculates the appropriate table size (rounds up to a power of two).
249     static unsigned sizeForCapacity(unsigned capacity);
250
251     // Check if capacity is available.
252     bool canInsert();
253
254     unsigned m_indexSize;
255     unsigned m_indexMask;
256     unsigned* m_index;
257     unsigned m_keyCount;
258     unsigned m_deletedCount;
259     OwnPtr< Vector<PropertyOffset>> m_deletedOffsets;
260
261     static const unsigned MinimumTableSize = 16;
262     static const unsigned EmptyEntryIndex = 0;
263 };
264
265 inline PropertyTable::iterator PropertyTable::begin()
266 {
267     return iterator(skipDeletedEntries(table()));
268 }
269
270 inline PropertyTable::iterator PropertyTable::end()
271 {
272     return iterator(table() + usedCount());
273 }
274
275 inline PropertyTable::const_iterator PropertyTable::begin() const
276 {
277     return const_iterator(skipDeletedEntries(table()));
278 }
279
280 inline PropertyTable::const_iterator PropertyTable::end() const
281 {
282     return const_iterator(table() + usedCount());
283 }
284
285 inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
286 {
287     ASSERT(key);
288     ASSERT(key->isAtomic() || key->isEmptyUnique());
289     unsigned hash = key->existingHash();
290     unsigned step = 0;
291
292 #if DUMP_PROPERTYMAP_STATS
293     ++propertyMapHashTableStats->numFinds;
294 #endif
295
296     while (true) {
297         unsigned entryIndex = m_index[hash & m_indexMask];
298         if (entryIndex == EmptyEntryIndex)
299             return std::make_pair((ValueType*)0, hash & m_indexMask);
300         if (key == table()[entryIndex - 1].key)
301             return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
302
303         if (!step)
304             step = WTF::doubleHash(key->existingHash()) | 1;
305
306 #if DUMP_PROPERTYMAP_STATS
307         ++propertyMapHashTableStats->numCollisions;
308 #endif
309
310 #if DUMP_PROPERTYMAP_COLLISIONS
311         dataLog("PropertyTable collision for ", key, " (", hash, ") with step ", step, "\n");
312         dataLog("Collided with ", table()[entryIndex - 1].key, "(", table()[entryIndex - 1].key->existingHash(), ")\n");
313 #endif
314
315         hash += step;
316     }
317 }
318
319 inline PropertyTable::ValueType* PropertyTable::get(const KeyType& key)
320 {
321     ASSERT(key);
322     ASSERT(key->isAtomic() || key->isEmptyUnique());
323
324     if (!m_keyCount)
325         return nullptr;
326
327     unsigned hash = key->existingHash();
328     unsigned step = 0;
329
330 #if DUMP_PROPERTYMAP_STATS
331     ++propertyMapHashTableStats->numLookups;
332 #endif
333
334     while (true) {
335         unsigned entryIndex = m_index[hash & m_indexMask];
336         if (entryIndex == EmptyEntryIndex)
337             return nullptr;
338         if (key == table()[entryIndex - 1].key)
339             return &table()[entryIndex - 1];
340
341 #if DUMP_PROPERTYMAP_STATS
342         ++propertyMapHashTableStats->numLookupProbing;
343 #endif
344
345         if (!step)
346             step = WTF::doubleHash(key->existingHash()) | 1;
347         hash += step;
348     }
349 }
350
351 inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
352 {
353     // Look for a value with a matching key already in the array.
354     find_iterator iter = find(entry.key);
355     if (iter.first) {
356         RELEASE_ASSERT(iter.first->offset <= offset);
357         return std::make_pair(iter, false);
358     }
359
360 #if DUMP_PROPERTYMAP_STATS
361     ++propertyMapHashTableStats->numAdds;
362 #endif
363
364     // Ref the key
365     entry.key->ref();
366
367     // ensure capacity is available.
368     if (!canInsert()) {
369         rehash(m_keyCount + 1);
370         iter = find(entry.key);
371         ASSERT(!iter.first);
372     }
373
374     // Allocate a slot in the hashtable, and set the index to reference this.
375     unsigned entryIndex = usedCount() + 1;
376     m_index[iter.second] = entryIndex;
377     iter.first = &table()[entryIndex - 1];
378     *iter.first = entry;
379
380     ++m_keyCount;
381     
382     if (offsetEffect == PropertyOffsetMayChange)
383         offset = std::max(offset, entry.offset);
384     else
385         RELEASE_ASSERT(offset >= entry.offset);
386     
387     return std::make_pair(iter, true);
388 }
389
390 inline void PropertyTable::remove(const find_iterator& iter)
391 {
392     // Removing a key that doesn't exist does nothing!
393     if (!iter.first)
394         return;
395
396 #if DUMP_PROPERTYMAP_STATS
397     ++propertyMapHashTableStats->numRemoves;
398 #endif
399
400     // Replace this one element with the deleted sentinel. Also clear out
401     // the entry so we can iterate all the entries as needed.
402     m_index[iter.second] = deletedEntryIndex();
403     iter.first->key->deref();
404     iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY;
405
406     ASSERT(m_keyCount >= 1);
407     --m_keyCount;
408     ++m_deletedCount;
409
410     if (m_deletedCount * 4 >= m_indexSize)
411         rehash(m_keyCount);
412 }
413
414 inline void PropertyTable::remove(const KeyType& key)
415 {
416     remove(find(key));
417 }
418
419 // returns the number of values in the hashtable.
420 inline unsigned PropertyTable::size() const
421 {
422     return m_keyCount;
423 }
424
425 inline bool PropertyTable::isEmpty() const
426 {
427     return !m_keyCount;
428 }
429
430 inline unsigned PropertyTable::propertyStorageSize() const
431 {
432     return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0);
433 }
434
435 inline void PropertyTable::clearDeletedOffsets()
436 {
437     m_deletedOffsets.clear();
438 }
439
440 inline bool PropertyTable::hasDeletedOffset()
441 {
442     return m_deletedOffsets && !m_deletedOffsets->isEmpty();
443 }
444
445 inline PropertyOffset PropertyTable::getDeletedOffset()
446 {
447     PropertyOffset offset = m_deletedOffsets->last();
448     m_deletedOffsets->removeLast();
449     return offset;
450 }
451
452 inline void PropertyTable::addDeletedOffset(PropertyOffset offset)
453 {
454     if (!m_deletedOffsets)
455         m_deletedOffsets = adoptPtr(new Vector<PropertyOffset>);
456     m_deletedOffsets->append(offset);
457 }
458
459 inline PropertyOffset PropertyTable::nextOffset(PropertyOffset inlineCapacity)
460 {
461     if (hasDeletedOffset())
462         return getDeletedOffset();
463
464     return offsetForPropertyNumber(size(), inlineCapacity);
465 }
466
467 inline PropertyTable* PropertyTable::copy(VM& vm, unsigned newCapacity)
468 {
469     ASSERT(newCapacity >= m_keyCount);
470
471     // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
472     // save rehashing all keys.
473     if (sizeForCapacity(newCapacity) == m_indexSize)
474         return PropertyTable::clone(vm, *this);
475     return PropertyTable::clone(vm, newCapacity, *this);
476 }
477
478 #ifndef NDEBUG
479 inline size_t PropertyTable::sizeInMemory()
480 {
481     size_t result = sizeof(PropertyTable) + dataSize();
482     if (m_deletedOffsets)
483         result += (m_deletedOffsets->capacity() * sizeof(PropertyOffset));
484     return result;
485 }
486 #endif
487
488 inline void PropertyTable::reinsert(const ValueType& entry)
489 {
490 #if DUMP_PROPERTYMAP_STATS
491     ++propertyMapHashTableStats->numReinserts;
492 #endif
493
494     // Used to insert a value known not to be in the table, and where
495     // we know capacity to be available.
496     ASSERT(canInsert());
497     find_iterator iter = find(entry.key);
498     ASSERT(!iter.first);
499
500     unsigned entryIndex = usedCount() + 1;
501     m_index[iter.second] = entryIndex;
502     table()[entryIndex - 1] = entry;
503
504     ++m_keyCount;
505 }
506
507 inline void PropertyTable::rehash(unsigned newCapacity)
508 {
509 #if DUMP_PROPERTYMAP_STATS
510     ++propertyMapHashTableStats->numRehashes;
511 #endif
512
513     unsigned* oldEntryIndices = m_index;
514     iterator iter = this->begin();
515     iterator end = this->end();
516
517     m_indexSize = sizeForCapacity(newCapacity);
518     m_indexMask = m_indexSize - 1;
519     m_keyCount = 0;
520     m_deletedCount = 0;
521     m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
522
523     for (; iter != end; ++iter) {
524         ASSERT(canInsert());
525         reinsert(*iter);
526     }
527
528     fastFree(oldEntryIndices);
529 }
530
531 inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; }
532
533 inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
534
535 template<typename T>
536 inline T* PropertyTable::skipDeletedEntries(T* valuePtr)
537 {
538     while (valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY)
539         ++valuePtr;
540     return valuePtr;
541 }
542
543 inline PropertyTable::ValueType* PropertyTable::table()
544 {
545     // The table of values lies after the hash index.
546     return reinterpret_cast<ValueType*>(m_index + m_indexSize);
547 }
548
549 inline const PropertyTable::ValueType* PropertyTable::table() const
550 {
551     // The table of values lies after the hash index.
552     return reinterpret_cast<const ValueType*>(m_index + m_indexSize);
553 }
554
555 inline unsigned PropertyTable::usedCount() const
556 {
557     // Total number of  used entries in the values array - by either valid entries, or deleted ones.
558     return m_keyCount + m_deletedCount;
559 }
560
561 inline size_t PropertyTable::dataSize()
562 {
563     // The size in bytes of data needed for by the table.
564     return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType);
565 }
566
567 inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
568 {
569     if (capacity < MinimumTableSize / 2)
570         return MinimumTableSize;
571     return nextPowerOf2(capacity + 1) * 2;
572 }
573
574 inline bool PropertyTable::canInsert()
575 {
576     return usedCount() < tableCapacity();
577 }
578
579 } // namespace JSC
580
581 #endif // PropertyMapHashTable_h