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