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