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