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