/*
* Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
*
* This library is free software; you can redistribute it and/or
* modify it under the terms of the GNU Library General Public
* License as published by the Free Software Foundation; either
* version 2 of the License, or (at your option) any later version.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
* Library General Public License for more details.
*
* You should have received a copy of the GNU Library General Public License
* along with this library; see the file COPYING.LIB. If not, write to
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
* Boston, MA 02110-1301, USA.
*
*/
#ifndef PropertyMapHashTable_h
#define PropertyMapHashTable_h
#include "UString.h"
#include "WriteBarrier.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 {
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;
WriteBarrier<JSCell> specificValue;
PropertyMapEntry(JSGlobalData& globalData, JSCell* owner, StringImpl* key, unsigned offset, unsigned attributes, JSCell* specificValue)
: key(key)
, offset(offset)
, attributes(attributes)
, specificValue(globalData, owner, 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;
}
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;
}
T* operator->()
{
return m_valuePtr;
}
ordered_iterator(T* valuePtr)
: m_valuePtr(valuePtr)
{
}
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.
explicit PropertyTable(unsigned initialCapacity);
PropertyTable(JSGlobalData&, JSCell*, const PropertyTable&);
PropertyTable(JSGlobalData&, JSCell*, 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(JSGlobalData&, JSCell* owner, unsigned newCapacity);
#ifndef NDEBUG
size_t sizeInMemory();
void checkConsistency();
#endif
private:
PropertyTable(const PropertyTable&);
// 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(JSGlobalData& globalData, JSCell* owner, 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();
writeBarrier(globalData, owner, iter->specificValue.get());
}
// Copy the m_deletedOffsets vector.
Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
if (otherDeletedOffsets)
m_deletedOffsets.set(new Vector<unsigned>(*otherDeletedOffsets));
}
inline PropertyTable::PropertyTable(JSGlobalData& globalData, JSCell* owner, 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();
writeBarrier(globalData, owner, iter->specificValue.get());
}
// 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->deref();
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(JSGlobalData& globalData, JSCell* owner, 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(globalData, owner, *this);
return new PropertyTable(globalData, owner, 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