2 * Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
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.
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.
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.
21 #ifndef PropertyMapHashTable_h
22 #define PropertyMapHashTable_h
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>
36 #define DUMP_PROPERTYMAP_STATS 0
37 #define DUMP_PROPERTYMAP_COLLISIONS 0
39 #define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1)
43 #if DUMP_PROPERTYMAP_STATS
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
;
56 JS_EXPORTDATA
extern PropertyMapHashTableStats
* propertyMapHashTableStats
;
60 inline bool isPowerOf2(unsigned v
)
62 return hasOneBitSet(v
);
65 inline unsigned nextPowerOf2(unsigned v
)
67 // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
68 // Devised by Sean Anderson, Sepember 14, 2001
81 struct PropertyMapEntry
{
83 PropertyOffset offset
;
85 WriteBarrier
<JSCell
> specificValue
;
87 PropertyMapEntry(VM
& vm
, JSCell
* owner
, StringImpl
* key
, PropertyOffset offset
, unsigned attributes
, JSCell
* specificValue
)
90 , attributes(attributes
)
91 , specificValue(vm
, owner
, specificValue
, WriteBarrier
<JSCell
>::MayBeNull
)
96 class PropertyTable
: public JSCell
{
98 // This is the implementation for 'iterator' and 'const_iterator',
99 // used for iterating over the table in insertion order.
101 class ordered_iterator
{
103 ordered_iterator
<T
>& operator++()
105 m_valuePtr
= skipDeletedEntries(m_valuePtr
+ 1);
109 bool operator==(const ordered_iterator
<T
>& other
)
111 return m_valuePtr
== other
.m_valuePtr
;
114 bool operator!=(const ordered_iterator
<T
>& other
)
116 return m_valuePtr
!= other
.m_valuePtr
;
129 ordered_iterator(T
* valuePtr
)
130 : m_valuePtr(valuePtr
)
139 static const bool needsDestruction
= true;
140 static const bool hasImmortalStructure
= true;
141 static void destroy(JSCell
*);
145 static Structure
* createStructure(VM
& vm
, JSGlobalObject
* globalObject
, JSValue prototype
)
147 return Structure::create(vm
, globalObject
, prototype
, TypeInfo(CompoundType
, StructureFlags
), info());
150 static void visitChildren(JSCell
*, SlotVisitor
&);
152 typedef StringImpl
* KeyType
;
153 typedef PropertyMapEntry ValueType
;
155 // The in order iterator provides overloaded * and -> to access the Value at the current position.
156 typedef ordered_iterator
<ValueType
> iterator
;
157 typedef ordered_iterator
<const ValueType
> const_iterator
;
159 // The find_iterator is a pair of a pointer to a Value* an the entry in the index.
160 // If 'find' does not find an entry then iter.first will be 0, and iter.second will
161 // give the point in m_index where an entry should be inserted.
162 typedef std::pair
<ValueType
*, unsigned> find_iterator
;
164 // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
165 static PropertyTable
* create(VM
&, unsigned initialCapacity
);
166 static PropertyTable
* clone(VM
&, const PropertyTable
&);
167 static PropertyTable
* clone(VM
&, unsigned initialCapacity
, const PropertyTable
&);
170 // Ordered iteration methods.
173 const_iterator
begin() const;
174 const_iterator
end() const;
176 // Find a value in the table.
177 find_iterator
find(const KeyType
&);
178 find_iterator
findWithString(const KeyType
&);
179 ValueType
* get(const KeyType
&);
180 // Add a value to the table
181 enum EffectOnPropertyOffset
{ PropertyOffsetMayChange
, PropertyOffsetMustNotChange
};
182 std::pair
<find_iterator
, bool> add(const ValueType
& entry
, PropertyOffset
&, EffectOnPropertyOffset
);
183 // Remove a value from the table.
184 void remove(const find_iterator
& iter
);
185 void remove(const KeyType
& key
);
187 // Returns the number of values in the hashtable.
188 unsigned size() const;
190 // Checks if there are any values in the hashtable.
191 bool isEmpty() const;
193 // Number of slots in the property storage array in use, included deletedOffsets.
194 unsigned propertyStorageSize() const;
196 // Used to maintain a list of unused entries in the property storage.
197 void clearDeletedOffsets();
198 bool hasDeletedOffset();
199 PropertyOffset
getDeletedOffset();
200 void addDeletedOffset(PropertyOffset
);
202 PropertyOffset
nextOffset(PropertyOffset inlineCapacity
);
204 // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
205 PropertyTable
* copy(VM
&, unsigned newCapacity
);
208 size_t sizeInMemory();
209 void checkConsistency();
213 static const unsigned StructureFlags
= OverridesVisitChildren
| StructureIsImmortal
;
216 PropertyTable(VM
&, unsigned initialCapacity
);
217 PropertyTable(VM
&, const PropertyTable
&);
218 PropertyTable(VM
&, unsigned initialCapacity
, const PropertyTable
&);
220 PropertyTable(const PropertyTable
&);
221 // Used to insert a value known not to be in the table, and where we know capacity to be available.
222 void reinsert(const ValueType
& entry
);
224 // Rehash the table. Used to grow, or to recover deleted slots.
225 void rehash(unsigned newCapacity
);
227 // The capacity of the table of values is half of the size of the index.
228 unsigned tableCapacity() const;
230 // We keep an extra deleted slot after the array to make iteration work,
231 // and to use for deleted values. Index values into the array are 1-based,
232 // so this is tableCapacity() + 1.
233 // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the
234 // values array is actually 9 long (the 9th used for the deleted value/
235 // iteration guard). The 8 valid entries are numbered 1..8, so the
236 // deleted index is 9 (0 being reserved for empty).
237 unsigned deletedEntryIndex() const;
239 // Used in iterator creation/progression.
241 static T
* skipDeletedEntries(T
* valuePtr
);
243 // The table of values lies after the hash index.
245 const ValueType
* table() const;
247 // total number of used entries in the values array - by either valid entries, or deleted ones.
248 unsigned usedCount() const;
250 // The size in bytes of data needed for by the table.
253 // Calculates the appropriate table size (rounds up to a power of two).
254 static unsigned sizeForCapacity(unsigned capacity
);
256 // Check if capacity is available.
259 unsigned m_indexSize
;
260 unsigned m_indexMask
;
263 unsigned m_deletedCount
;
264 OwnPtr
< Vector
<PropertyOffset
>> m_deletedOffsets
;
266 static const unsigned MinimumTableSize
= 16;
267 static const unsigned EmptyEntryIndex
= 0;
270 inline PropertyTable::iterator
PropertyTable::begin()
272 return iterator(skipDeletedEntries(table()));
275 inline PropertyTable::iterator
PropertyTable::end()
277 return iterator(table() + usedCount());
280 inline PropertyTable::const_iterator
PropertyTable::begin() const
282 return const_iterator(skipDeletedEntries(table()));
285 inline PropertyTable::const_iterator
PropertyTable::end() const
287 return const_iterator(table() + usedCount());
290 inline PropertyTable::find_iterator
PropertyTable::find(const KeyType
& key
)
293 ASSERT(key
->isAtomic() || key
->isEmptyUnique());
294 unsigned hash
= key
->existingHash();
297 #if DUMP_PROPERTYMAP_STATS
298 ++propertyMapHashTableStats
->numFinds
;
302 unsigned entryIndex
= m_index
[hash
& m_indexMask
];
303 if (entryIndex
== EmptyEntryIndex
)
304 return std::make_pair((ValueType
*)0, hash
& m_indexMask
);
305 if (key
== table()[entryIndex
- 1].key
)
306 return std::make_pair(&table()[entryIndex
- 1], hash
& m_indexMask
);
309 step
= WTF::doubleHash(key
->existingHash()) | 1;
311 #if DUMP_PROPERTYMAP_STATS
312 ++propertyMapHashTableStats
->numCollisions
;
315 #if DUMP_PROPERTYMAP_COLLISIONS
316 dataLog("PropertyTable collision for ", key
, " (", hash
, ") with step ", step
, "\n");
317 dataLog("Collided with ", table()[entryIndex
- 1].key
, "(", table()[entryIndex
- 1].key
->existingHash(), ")\n");
324 inline PropertyTable::ValueType
* PropertyTable::get(const KeyType
& key
)
327 ASSERT(key
->isAtomic() || key
->isEmptyUnique());
332 unsigned hash
= key
->existingHash();
335 #if DUMP_PROPERTYMAP_STATS
336 ++propertyMapHashTableStats
->numLookups
;
340 unsigned entryIndex
= m_index
[hash
& m_indexMask
];
341 if (entryIndex
== EmptyEntryIndex
)
343 if (key
== table()[entryIndex
- 1].key
)
344 return &table()[entryIndex
- 1];
346 #if DUMP_PROPERTYMAP_STATS
347 ++propertyMapHashTableStats
->numLookupProbing
;
351 step
= WTF::doubleHash(key
->existingHash()) | 1;
356 inline PropertyTable::find_iterator
PropertyTable::findWithString(const KeyType
& key
)
359 ASSERT(!key
->isAtomic() && !key
->hasHash());
360 unsigned hash
= key
->hash();
363 #if DUMP_PROPERTYMAP_STATS
364 ++propertyMapHashTableStats
->numLookups
;
368 unsigned entryIndex
= m_index
[hash
& m_indexMask
];
369 if (entryIndex
== EmptyEntryIndex
)
370 return std::make_pair((ValueType
*)0, hash
& m_indexMask
);
371 const KeyType
& keyInMap
= table()[entryIndex
- 1].key
;
372 if (equal(key
, keyInMap
) && keyInMap
->isAtomic())
373 return std::make_pair(&table()[entryIndex
- 1], hash
& m_indexMask
);
375 #if DUMP_PROPERTYMAP_STATS
376 ++propertyMapHashTableStats
->numLookupProbing
;
380 step
= WTF::doubleHash(key
->existingHash()) | 1;
385 inline std::pair
<PropertyTable::find_iterator
, bool> PropertyTable::add(const ValueType
& entry
, PropertyOffset
& offset
, EffectOnPropertyOffset offsetEffect
)
387 // Look for a value with a matching key already in the array.
388 find_iterator iter
= find(entry
.key
);
390 RELEASE_ASSERT(iter
.first
->offset
<= offset
);
391 return std::make_pair(iter
, false);
394 #if DUMP_PROPERTYMAP_STATS
395 ++propertyMapHashTableStats
->numAdds
;
401 // ensure capacity is available.
403 rehash(m_keyCount
+ 1);
404 iter
= find(entry
.key
);
408 // Allocate a slot in the hashtable, and set the index to reference this.
409 unsigned entryIndex
= usedCount() + 1;
410 m_index
[iter
.second
] = entryIndex
;
411 iter
.first
= &table()[entryIndex
- 1];
416 if (offsetEffect
== PropertyOffsetMayChange
)
417 offset
= std::max(offset
, entry
.offset
);
419 RELEASE_ASSERT(offset
>= entry
.offset
);
421 return std::make_pair(iter
, true);
424 inline void PropertyTable::remove(const find_iterator
& iter
)
426 // Removing a key that doesn't exist does nothing!
430 #if DUMP_PROPERTYMAP_STATS
431 ++propertyMapHashTableStats
->numRemoves
;
434 // Replace this one element with the deleted sentinel. Also clear out
435 // the entry so we can iterate all the entries as needed.
436 m_index
[iter
.second
] = deletedEntryIndex();
437 iter
.first
->key
->deref();
438 iter
.first
->key
= PROPERTY_MAP_DELETED_ENTRY_KEY
;
440 ASSERT(m_keyCount
>= 1);
444 if (m_deletedCount
* 4 >= m_indexSize
)
448 inline void PropertyTable::remove(const KeyType
& key
)
453 // returns the number of values in the hashtable.
454 inline unsigned PropertyTable::size() const
459 inline bool PropertyTable::isEmpty() const
464 inline unsigned PropertyTable::propertyStorageSize() const
466 return size() + (m_deletedOffsets
? m_deletedOffsets
->size() : 0);
469 inline void PropertyTable::clearDeletedOffsets()
471 m_deletedOffsets
.clear();
474 inline bool PropertyTable::hasDeletedOffset()
476 return m_deletedOffsets
&& !m_deletedOffsets
->isEmpty();
479 inline PropertyOffset
PropertyTable::getDeletedOffset()
481 PropertyOffset offset
= m_deletedOffsets
->last();
482 m_deletedOffsets
->removeLast();
486 inline void PropertyTable::addDeletedOffset(PropertyOffset offset
)
488 if (!m_deletedOffsets
)
489 m_deletedOffsets
= adoptPtr(new Vector
<PropertyOffset
>);
490 m_deletedOffsets
->append(offset
);
493 inline PropertyOffset
PropertyTable::nextOffset(PropertyOffset inlineCapacity
)
495 if (hasDeletedOffset())
496 return getDeletedOffset();
498 return offsetForPropertyNumber(size(), inlineCapacity
);
501 inline PropertyTable
* PropertyTable::copy(VM
& vm
, unsigned newCapacity
)
503 ASSERT(newCapacity
>= m_keyCount
);
505 // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
506 // save rehashing all keys.
507 if (sizeForCapacity(newCapacity
) == m_indexSize
)
508 return PropertyTable::clone(vm
, *this);
509 return PropertyTable::clone(vm
, newCapacity
, *this);
513 inline size_t PropertyTable::sizeInMemory()
515 size_t result
= sizeof(PropertyTable
) + dataSize();
516 if (m_deletedOffsets
)
517 result
+= (m_deletedOffsets
->capacity() * sizeof(PropertyOffset
));
522 inline void PropertyTable::reinsert(const ValueType
& entry
)
524 #if DUMP_PROPERTYMAP_STATS
525 ++propertyMapHashTableStats
->numReinserts
;
528 // Used to insert a value known not to be in the table, and where
529 // we know capacity to be available.
531 find_iterator iter
= find(entry
.key
);
534 unsigned entryIndex
= usedCount() + 1;
535 m_index
[iter
.second
] = entryIndex
;
536 table()[entryIndex
- 1] = entry
;
541 inline void PropertyTable::rehash(unsigned newCapacity
)
543 #if DUMP_PROPERTYMAP_STATS
544 ++propertyMapHashTableStats
->numRehashes
;
547 unsigned* oldEntryIndices
= m_index
;
548 iterator iter
= this->begin();
549 iterator end
= this->end();
551 m_indexSize
= sizeForCapacity(newCapacity
);
552 m_indexMask
= m_indexSize
- 1;
555 m_index
= static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
557 for (; iter
!= end
; ++iter
) {
562 fastFree(oldEntryIndices
);
565 inline unsigned PropertyTable::tableCapacity() const { return m_indexSize
>> 1; }
567 inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
570 inline T
* PropertyTable::skipDeletedEntries(T
* valuePtr
)
572 while (valuePtr
->key
== PROPERTY_MAP_DELETED_ENTRY_KEY
)
577 inline PropertyTable::ValueType
* PropertyTable::table()
579 // The table of values lies after the hash index.
580 return reinterpret_cast<ValueType
*>(m_index
+ m_indexSize
);
583 inline const PropertyTable::ValueType
* PropertyTable::table() const
585 // The table of values lies after the hash index.
586 return reinterpret_cast<const ValueType
*>(m_index
+ m_indexSize
);
589 inline unsigned PropertyTable::usedCount() const
591 // Total number of used entries in the values array - by either valid entries, or deleted ones.
592 return m_keyCount
+ m_deletedCount
;
595 inline size_t PropertyTable::dataSize()
597 // The size in bytes of data needed for by the table.
598 return m_indexSize
* sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType
);
601 inline unsigned PropertyTable::sizeForCapacity(unsigned capacity
)
603 if (capacity
< MinimumTableSize
/ 2)
604 return MinimumTableSize
;
605 return nextPowerOf2(capacity
+ 1) * 2;
608 inline bool PropertyTable::canInsert()
610 return usedCount() < tableCapacity();
615 #endif // PropertyMapHashTable_h