diff options
Diffstat (limited to 'Source/JavaScriptCore/runtime/PropertyMapHashTable.h')
| -rw-r--r-- | Source/JavaScriptCore/runtime/PropertyMapHashTable.h | 554 |
1 files changed, 508 insertions, 46 deletions
diff --git a/Source/JavaScriptCore/runtime/PropertyMapHashTable.h b/Source/JavaScriptCore/runtime/PropertyMapHashTable.h index bd452b6..85a3818 100644 --- a/Source/JavaScriptCore/runtime/PropertyMapHashTable.h +++ b/Source/JavaScriptCore/runtime/PropertyMapHashTable.h @@ -22,69 +22,531 @@ #define PropertyMapHashTable_h #include "UString.h" +#include <wtf/HashTable.h> +#include <wtf/PassOwnPtr.h> #include <wtf/Vector.h> + +#ifndef NDEBUG +#define DUMP_PROPERTYMAP_STATS 0 +#else +#define DUMP_PROPERTYMAP_STATS 0 +#endif + +#if DUMP_PROPERTYMAP_STATS + +extern int numProbes; +extern int numCollisions; +extern int numRehashes; +extern int numRemoves; + +#endif + +#define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1) + namespace JSC { - struct PropertyMapEntry { - StringImpl* key; - unsigned offset; - unsigned attributes; - JSCell* specificValue; - unsigned index; - - PropertyMapEntry(StringImpl* key, unsigned attributes, JSCell* specificValue) - : key(key) - , offset(0) - , attributes(attributes) - , specificValue(specificValue) - , index(0) +inline bool isPowerOf2(unsigned v) +{ + // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html + + return !(v & (v - 1)) && v; +} + +inline unsigned nextPowerOf2(unsigned v) +{ + // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html + // Devised by Sean Anderson, Sepember 14, 2001 + + v--; + v |= v >> 1; + v |= v >> 2; + v |= v >> 4; + v |= v >> 8; + v |= v >> 16; + v++; + + return v; +} + +struct PropertyMapEntry { + StringImpl* key; + unsigned offset; + unsigned attributes; + JSCell* specificValue; + + PropertyMapEntry(StringImpl* key, unsigned offset, unsigned attributes, JSCell* specificValue) + : key(key) + , offset(offset) + , attributes(attributes) + , specificValue(specificValue) + { + } +}; + +class PropertyTable { + WTF_MAKE_FAST_ALLOCATED; + + // This is the implementation for 'iterator' and 'const_iterator', + // used for iterating over the table in insertion order. + template<typename T> + class ordered_iterator { + public: + ordered_iterator<T>& operator++() { + m_valuePtr = skipDeletedEntries(m_valuePtr + 1); + return *this; } - PropertyMapEntry(StringImpl* key, unsigned offset, unsigned attributes, JSCell* specificValue, unsigned index) - : key(key) - , offset(offset) - , attributes(attributes) - , specificValue(specificValue) - , index(index) + bool operator==(const ordered_iterator<T>& other) { + return m_valuePtr == other.m_valuePtr; + } + + bool operator!=(const ordered_iterator<T>& other) + { + return m_valuePtr != other.m_valuePtr; + } + + T& operator*() + { + return *m_valuePtr; } - }; - // lastIndexUsed is an ever-increasing index used to identify the order items - // were inserted into the property map. It's required that getEnumerablePropertyNames - // return the properties in the order they were added for compatibility with other - // browsers' JavaScript implementations. - struct PropertyMapHashTable { - unsigned sizeMask; - unsigned size; - unsigned keyCount; - unsigned deletedSentinelCount; - unsigned lastIndexUsed; - Vector<unsigned>* deletedOffsets; - unsigned entryIndices[1]; - - PropertyMapEntry* entries() + T* operator->() { - // The entries vector comes after the indices vector. - // The 0th item in the entries vector is not really used; it has to - // have a 0 in its key to allow the hash table lookup to handle deleted - // sentinels without any special-case code, but the other fields are unused. - return reinterpret_cast<PropertyMapEntry*>(&entryIndices[size]); + return m_valuePtr; } - static size_t allocationSize(unsigned size) + ordered_iterator(T* valuePtr) + : m_valuePtr(valuePtr) { - // We never let a hash table get more than half full, - // So the number of indices we need is the size of the hash table. - // But the number of entries is half that (plus one for the deleted sentinel). - return sizeof(PropertyMapHashTable) - + (size - 1) * sizeof(unsigned) - + (1 + size / 2) * sizeof(PropertyMapEntry); } + + private: + T* m_valuePtr; }; +public: + typedef StringImpl* KeyType; + typedef PropertyMapEntry ValueType; + + // The in order iterator provides overloaded * and -> to access the Value at the current position. + typedef ordered_iterator<ValueType> iterator; + typedef ordered_iterator<const ValueType> const_iterator; + + // The find_iterator is a pair of a pointer to a Value* an the entry in the index. + // If 'find' does not find an entry then iter.first will be 0, and iter.second will + // give the point in m_index where an entry should be inserted. + typedef std::pair<ValueType*, unsigned> find_iterator; + + // Constructor is passed an initial capacity, a PropertyTable to copy, or both. + PropertyTable(unsigned initialCapacity); + PropertyTable(const PropertyTable&); + PropertyTable(unsigned initialCapacity, const PropertyTable&); + ~PropertyTable(); + + // Ordered iteration methods. + iterator begin(); + iterator end(); + const_iterator begin() const; + const_iterator end() const; + + // Find a value in the table. + find_iterator find(const KeyType& key); + // Add a value to the table + std::pair<find_iterator, bool> add(const ValueType& entry); + // Remove a value from the table. + void remove(const find_iterator& iter); + void remove(const KeyType& key); + + // Returns the number of values in the hashtable. + unsigned size() const; + + // Checks if there are any values in the hashtable. + bool isEmpty() const; + + // Number of slots in the property storage array in use, included deletedOffsets. + unsigned propertyStorageSize() const; + + // Used to maintain a list of unused entries in the property storage. + void clearDeletedOffsets(); + bool hasDeletedOffset(); + unsigned getDeletedOffset(); + void addDeletedOffset(unsigned offset); + + // Copy this PropertyTable, ensuring the copy has at least the capacity provided. + PassOwnPtr<PropertyTable> copy(unsigned newCapacity); + +#ifndef NDEBUG + size_t sizeInMemory(); + void checkConsistency(); +#endif + +private: + // Used to insert a value known not to be in the table, and where we know capacity to be available. + void reinsert(const ValueType& entry); + + // Rehash the table. Used to grow, or to recover deleted slots. + void rehash(unsigned newCapacity); + + // The capacity of the table of values is half of the size of the index. + unsigned tableCapacity() const; + + // We keep an extra deleted slot after the array to make iteration work, + // and to use for deleted values. Index values into the array are 1-based, + // so this is tableCapacity() + 1. + // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the + // values array is actually 9 long (the 9th used for the deleted value/ + // iteration guard). The 8 valid entries are numbered 1..8, so the + // deleted index is 9 (0 being reserved for empty). + unsigned deletedEntryIndex() const; + + // Used in iterator creation/progression. + template<typename T> + static T* skipDeletedEntries(T* valuePtr); + + // The table of values lies after the hash index. + ValueType* table(); + const ValueType* table() const; + + // total number of used entries in the values array - by either valid entries, or deleted ones. + unsigned usedCount() const; + + // The size in bytes of data needed for by the table. + size_t dataSize(); + + // Calculates the appropriate table size (rounds up to a power of two). + static unsigned sizeForCapacity(unsigned capacity); + + // Check if capacity is available. + bool canInsert(); + + unsigned m_indexSize; + unsigned m_indexMask; + unsigned* m_index; + unsigned m_keyCount; + unsigned m_deletedCount; + OwnPtr< Vector<unsigned> > m_deletedOffsets; + + static const unsigned MinimumTableSize = 16; + static const unsigned EmptyEntryIndex = 0; +}; + +inline PropertyTable::PropertyTable(unsigned initialCapacity) + : m_indexSize(sizeForCapacity(initialCapacity)) + , m_indexMask(m_indexSize - 1) + , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize()))) + , m_keyCount(0) + , m_deletedCount(0) +{ + ASSERT(isPowerOf2(m_indexSize)); +} + +inline PropertyTable::PropertyTable(const PropertyTable& other) + : m_indexSize(other.m_indexSize) + , m_indexMask(other.m_indexMask) + , m_index(static_cast<unsigned*>(fastMalloc(dataSize()))) + , m_keyCount(other.m_keyCount) + , m_deletedCount(other.m_deletedCount) +{ + ASSERT(isPowerOf2(m_indexSize)); + + memcpy(m_index, other.m_index, dataSize()); + + iterator end = this->end(); + for (iterator iter = begin(); iter != end; ++iter) + iter->key->ref(); + + // Copy the m_deletedOffsets vector. + Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get(); + if (otherDeletedOffsets) + m_deletedOffsets.set(new Vector<unsigned>(*otherDeletedOffsets)); +} + +inline PropertyTable::PropertyTable(unsigned initialCapacity, const PropertyTable& other) + : m_indexSize(sizeForCapacity(initialCapacity)) + , m_indexMask(m_indexSize - 1) + , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize()))) + , m_keyCount(0) + , m_deletedCount(0) +{ + ASSERT(isPowerOf2(m_indexSize)); + ASSERT(initialCapacity >= other.m_keyCount); + + const_iterator end = other.end(); + for (const_iterator iter = other.begin(); iter != end; ++iter) { + ASSERT(canInsert()); + reinsert(*iter); + iter->key->ref(); + } + + // Copy the m_deletedOffsets vector. + Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get(); + if (otherDeletedOffsets) + m_deletedOffsets.set(new Vector<unsigned>(*otherDeletedOffsets)); +} + +inline PropertyTable::~PropertyTable() +{ + iterator end = this->end(); + for (iterator iter = begin(); iter != end; ++iter) + iter->key->ref(); + + fastFree(m_index); +} + +inline PropertyTable::iterator PropertyTable::begin() +{ + return iterator(skipDeletedEntries(table())); +} + +inline PropertyTable::iterator PropertyTable::end() +{ + return iterator(table() + usedCount()); +} + +inline PropertyTable::const_iterator PropertyTable::begin() const +{ + return const_iterator(skipDeletedEntries(table())); +} + +inline PropertyTable::const_iterator PropertyTable::end() const +{ + return const_iterator(table() + usedCount()); +} + +inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key) +{ + ASSERT(key); + unsigned hash = key->existingHash(); + unsigned step = 0; + +#if DUMP_PROPERTYMAP_STATS + ++numProbes; +#endif + + while (true) { + unsigned entryIndex = m_index[hash & m_indexMask]; + if (entryIndex == EmptyEntryIndex) + return std::make_pair((ValueType*)0, hash & m_indexMask); + if (key == table()[entryIndex - 1].key) + return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask); + +#if DUMP_PROPERTYMAP_STATS + ++numCollisions; +#endif + + if (!step) + step =WTF::doubleHash(key->existingHash()) | 1; + hash += step; + +#if DUMP_PROPERTYMAP_STATS + ++numRehashes; +#endif + } +} + +inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry) +{ + // Look for a value with a matching key already in the array. + find_iterator iter = find(entry.key); + if (iter.first) + return std::make_pair(iter, false); + + // Ref the key + entry.key->ref(); + + // ensure capacity is available. + if (!canInsert()) { + rehash(m_keyCount + 1); + iter = find(entry.key); + ASSERT(!iter.first); + } + + // Allocate a slot in the hashtable, and set the index to reference this. + unsigned entryIndex = usedCount() + 1; + m_index[iter.second] = entryIndex; + iter.first = &table()[entryIndex - 1]; + *iter.first = entry; + + ++m_keyCount; + return std::make_pair(iter, true); +} + +inline void PropertyTable::remove(const find_iterator& iter) +{ + // Removing a key that doesn't exist does nothing! + if (!iter.first) + return; + +#if DUMP_PROPERTYMAP_STATS + ++numRemoves; +#endif + + // Replace this one element with the deleted sentinel. Also clear out + // the entry so we can iterate all the entries as needed. + m_index[iter.second] = deletedEntryIndex(); + iter.first->key->deref(); + iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY; + + ASSERT(m_keyCount >= 1); + --m_keyCount; + ++m_deletedCount; + + if (m_deletedCount * 4 >= m_indexSize) + rehash(m_keyCount); +} + +inline void PropertyTable::remove(const KeyType& key) +{ + remove(find(key)); +} + +// returns the number of values in the hashtable. +inline unsigned PropertyTable::size() const +{ + return m_keyCount; +} + +inline bool PropertyTable::isEmpty() const +{ + return !m_keyCount; +} + +inline unsigned PropertyTable::propertyStorageSize() const +{ + return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0); +} + +inline void PropertyTable::clearDeletedOffsets() +{ + m_deletedOffsets.clear(); +} + +inline bool PropertyTable::hasDeletedOffset() +{ + return m_deletedOffsets && !m_deletedOffsets->isEmpty(); +} + +inline unsigned PropertyTable::getDeletedOffset() +{ + unsigned offset = m_deletedOffsets->last(); + m_deletedOffsets->removeLast(); + return offset; +} + +inline void PropertyTable::addDeletedOffset(unsigned offset) +{ + if (!m_deletedOffsets) + m_deletedOffsets.set(new Vector<unsigned>); + m_deletedOffsets->append(offset); +} + +inline PassOwnPtr<PropertyTable> PropertyTable::copy(unsigned newCapacity) +{ + ASSERT(newCapacity >= m_keyCount); + + // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it, + // save rehashing all keys. + if (sizeForCapacity(newCapacity) == m_indexSize) + return new PropertyTable(*this); + return new PropertyTable(newCapacity, *this); +} + +#ifndef NDEBUG +inline size_t PropertyTable::sizeInMemory() +{ + size_t result = sizeof(PropertyTable) + dataSize(); + if (m_deletedOffsets) + result += (m_deletedOffsets->capacity() * sizeof(unsigned)); + return result; +} +#endif + +inline void PropertyTable::reinsert(const ValueType& entry) +{ + // Used to insert a value known not to be in the table, and where + // we know capacity to be available. + ASSERT(canInsert()); + find_iterator iter = find(entry.key); + ASSERT(!iter.first); + + unsigned entryIndex = usedCount() + 1; + m_index[iter.second] = entryIndex; + table()[entryIndex - 1] = entry; + + ++m_keyCount; +} + +inline void PropertyTable::rehash(unsigned newCapacity) +{ + unsigned* oldEntryIndices = m_index; + iterator iter = this->begin(); + iterator end = this->end(); + + m_indexSize = sizeForCapacity(newCapacity); + m_indexMask = m_indexSize - 1; + m_keyCount = 0; + m_deletedCount = 0; + m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize())); + + for (; iter != end; ++iter) { + ASSERT(canInsert()); + reinsert(*iter); + } + + fastFree(oldEntryIndices); +} + +inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; } + +inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; } + +template<typename T> +inline T* PropertyTable::skipDeletedEntries(T* valuePtr) +{ + while (valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY) + ++valuePtr; + return valuePtr; +} + +inline PropertyTable::ValueType* PropertyTable::table() +{ + // The table of values lies after the hash index. + return reinterpret_cast<ValueType*>(m_index + m_indexSize); +} + +inline const PropertyTable::ValueType* PropertyTable::table() const +{ + // The table of values lies after the hash index. + return reinterpret_cast<const ValueType*>(m_index + m_indexSize); +} + +inline unsigned PropertyTable::usedCount() const +{ + // Total number of used entries in the values array - by either valid entries, or deleted ones. + return m_keyCount + m_deletedCount; +} + +inline size_t PropertyTable::dataSize() +{ + // The size in bytes of data needed for by the table. + return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType); +} + +inline unsigned PropertyTable::sizeForCapacity(unsigned capacity) +{ + if (capacity < 8) + return MinimumTableSize; + return nextPowerOf2(capacity + 1) * 2; +} + +inline bool PropertyTable::canInsert() +{ + return usedCount() < tableCapacity(); +} + } // namespace JSC #endif // PropertyMapHashTable_h |