JavaScriptCore/kjs/property_map.cpp - WebKit - Git at Google

 /*
  *  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.
  *
  */

 #include "config.h"
 #include "property_map.h"

 #include "object.h"
 #include "protect.h"
 #include "PropertyNameArray.h"
 #include <algorithm>
 #include <wtf/Assertions.h>
 #include <wtf/FastMalloc.h>
 #include <wtf/HashTable.h>
 #include <wtf/Vector.h>

 using std::max;
 using WTF::doubleHash;

 #ifndef NDEBUG
 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
 #define DUMP_PROPERTYMAP_STATS 0
 #else
 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
 #define DUMP_PROPERTYMAP_STATS 0
 #endif

 #define USE_SINGLE_ENTRY 1

 // 2/28/2006 ggaren: command-line JS iBench says that USE_SINGLE_ENTRY is a
 // 3.2% performance boost.

 namespace KJS {

 // Choose a number for the following so that most property maps are smaller,
 // but it's not going to blow out the stack to allocate this number of pointers.
 static const int smallMapThreshold = 1024;

 // The point at which the function call overhead of the qsort implementation
 // becomes small compared to the inefficiency of insertion sort.
 static const unsigned tinyMapThreshold = 20;

 #if DUMP_PROPERTYMAP_STATS

 static int numProbes;
 static int numCollisions;
 static int numRehashes;
 static int numRemoves;

 struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };

 static PropertyMapStatisticsExitLogger logger;

 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
 {
     printf("\nKJS::PropertyMap statistics\n\n");
     printf("%d probes\n", numProbes);
     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
     printf("%d rehashes\n", numRehashes);
     printf("%d removes\n", numRemoves);
 }

 #endif

 struct PropertyMapEntry {
     UString::Rep* key;
     JSValue* value;
     unsigned attributes;
     unsigned index;

     PropertyMapEntry(UString::Rep* k, JSValue* v, int a)
         : key(k), value(v), attributes(a), index(0)
     {
     }
 };

 // 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;
     unsigned entryIndicies[1];

     PropertyMapEntry* entries()
     {
         // 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*>(&entryIndicies[size]);
     }

     static size_t allocationSize(unsigned size)
     {
         // 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);
     }
 };

 static const unsigned emptyEntryIndex = 0;
 static const unsigned deletedSentinelIndex = 1;

 SavedProperties::SavedProperties()
     : count(0)
 {
 }

 SavedProperties::~SavedProperties()
 {
 }

 #if !DO_PROPERTYMAP_CONSTENCY_CHECK

 inline void PropertyMap::checkConsistency()
 {
 }

 #endif

 PropertyMap::~PropertyMap()
 {
     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (m_singleEntryKey)
             m_singleEntryKey->deref();
 #endif
         return;
     }

     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; i++) {
         if (UString::Rep* key = m_u.table->entries()[i].key)
             key->deref();
     }
     fastFree(m_u.table);
 }

 void PropertyMap::clear()
 {
     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (m_singleEntryKey) {
             m_singleEntryKey->deref();
             m_singleEntryKey = 0;
         }
 #endif
         return;
     }

     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; i++) {
         if (UString::Rep* key = m_u.table->entries()[i].key)
             key->deref();
     }
     for (unsigned i = 0; i < m_u.table->size; i++)
         m_u.table->entryIndicies[i] = emptyEntryIndex;
     m_u.table->keyCount = 0;
     m_u.table->deletedSentinelCount = 0;
 }

 JSValue* PropertyMap::get(const Identifier& name, unsigned& attributes) const
 {
     ASSERT(!name.isNull());

     UString::Rep* rep = name._ustring.rep();

     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (rep == m_singleEntryKey) {
             attributes = m_singleEntryAttributes;
             return m_u.singleEntryValue;
         }
 #endif
         return 0;
     }

     unsigned i = rep->computedHash();

 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
 #endif

     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     if (entryIndex == emptyEntryIndex)
         return 0;

     if (rep == m_u.table->entries()[entryIndex - 1].key) {
         attributes = m_u.table->entries()[entryIndex - 1].attributes;
         return m_u.table->entries()[entryIndex - 1].value;
     }

 #if DUMP_PROPERTYMAP_STATS
     ++numCollisions;
 #endif

     unsigned k = 1 | doubleHash(rep->computedHash());

     while (1) {
         i += k;

 #if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif

         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
         if (entryIndex == emptyEntryIndex)
             return 0;

         if (rep == m_u.table->entries()[entryIndex - 1].key) {
             attributes = m_u.table->entries()[entryIndex - 1].attributes;
             return m_u.table->entries()[entryIndex - 1].value;
         }
     }
 }

 JSValue* PropertyMap::get(const Identifier& name) const
 {
     ASSERT(!name.isNull());

     UString::Rep* rep = name._ustring.rep();

     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (rep == m_singleEntryKey)
             return m_u.singleEntryValue;
 #endif
         return 0;
     }

     unsigned i = rep->computedHash();

 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
 #endif

     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     if (entryIndex == emptyEntryIndex)
         return 0;

     if (rep == m_u.table->entries()[entryIndex - 1].key)
         return m_u.table->entries()[entryIndex - 1].value;

 #if DUMP_PROPERTYMAP_STATS
     ++numCollisions;
 #endif

     unsigned k = 1 | doubleHash(rep->computedHash());

     while (1) {
         i += k;

 #if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif

         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
         if (entryIndex == emptyEntryIndex)
             return 0;

         if (rep == m_u.table->entries()[entryIndex - 1].key)
             return m_u.table->entries()[entryIndex - 1].value;
     }
 }

 JSValue** PropertyMap::getLocation(const Identifier& name)
 {
     ASSERT(!name.isNull());

     UString::Rep* rep = name._ustring.rep();

     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (rep == m_singleEntryKey)
             return &m_u.singleEntryValue;
 #endif
         return 0;
     }

     unsigned i = rep->computedHash();

 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
 #endif

     unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
     if (entryIndex == emptyEntryIndex)
         return 0;

     if (rep == m_u.table->entries()[entryIndex - 1].key)
         return &m_u.table->entries()[entryIndex - 1].value;

 #if DUMP_PROPERTYMAP_STATS
     ++numCollisions;
 #endif

     unsigned k = 1 | doubleHash(rep->computedHash());

     while (1) {
         i += k;

 #if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif

         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
         if (entryIndex == emptyEntryIndex)
             return 0;

         if (rep == m_u.table->entries()[entryIndex - 1].key)
             return &m_u.table->entries()[entryIndex - 1].value;
     }
 }

 void PropertyMap::put(const Identifier& name, JSValue* value, unsigned attributes, bool checkReadOnly)
 {
     ASSERT(!name.isNull());
     ASSERT(value);

     checkConsistency();

     UString::Rep* rep = name._ustring.rep();

 #if USE_SINGLE_ENTRY
     if (!m_usingTable) {
         if (!m_singleEntryKey) {
             rep->ref();
             m_singleEntryKey = rep;
             m_u.singleEntryValue = value;
             m_singleEntryAttributes = static_cast<short>(attributes);
             checkConsistency();
             return;
         }
         if (rep == m_singleEntryKey && !(checkReadOnly && (m_singleEntryAttributes & ReadOnly))) {
             m_u.singleEntryValue = value;
             return;
         }
     }
 #endif

     if (!m_usingTable || (m_u.table->keyCount + m_u.table->deletedSentinelCount) * 2 >= m_u.table->size)
         expand();

     // FIXME: Consider a fast case for tables with no deleted sentinels.

     unsigned i = rep->computedHash();
     unsigned k = 0;
     bool foundDeletedElement = false;
     unsigned deletedElementIndex = 0; // initialize to make the compiler happy

 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
 #endif

     while (1) {
         unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
         if (entryIndex == emptyEntryIndex)
             break;

         if (m_u.table->entries()[entryIndex - 1].key == rep) {
             if (checkReadOnly && (m_u.table->entries()[entryIndex - 1].attributes & ReadOnly))
                 return;
             // Put a new value in an existing hash table entry.
             m_u.table->entries()[entryIndex - 1].value = value;
             // Attributes are intentionally not updated.
             return;
         } else if (entryIndex == deletedSentinelIndex) {
             // If we find a deleted-element sentinel, remember it for use later.
             if (!foundDeletedElement) {
                 foundDeletedElement = true;
                 deletedElementIndex = i;
             }
         }

         if (k == 0) {
             k = 1 | doubleHash(rep->computedHash());
 #if DUMP_PROPERTYMAP_STATS
             ++numCollisions;
 #endif
         }

         i += k;

 #if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }

     // Figure out which entry to use.
     unsigned entryIndex = m_u.table->keyCount + m_u.table->deletedSentinelCount + 2;
     if (foundDeletedElement) {
         i = deletedElementIndex;
         --m_u.table->deletedSentinelCount;

         // Since we're not making the table bigger, we can't use the entry one past
         // the end that we were planning on using, so search backwards for the empty
         // slot that we can use. We know it will be there because we did at least one
         // deletion in the past that left an entry empty.
         while (m_u.table->entries()[--entryIndex - 1].key)
             ;
     }


     // Create a new hash table entry.
     m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;

     // Create a new hash table entry.
     rep->ref();
     m_u.table->entries()[entryIndex - 1].key = rep;
     m_u.table->entries()[entryIndex - 1].value = value;
     m_u.table->entries()[entryIndex - 1].attributes = attributes;
     m_u.table->entries()[entryIndex - 1].index = ++m_u.table->lastIndexUsed;
     ++m_u.table->keyCount;

     checkConsistency();
 }

 void PropertyMap::insert(const Entry& entry)
 {
     ASSERT(m_u.table);

     unsigned i = entry.key->computedHash();
     unsigned k = 0;

 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
 #endif

     while (1) {
         unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
         if (entryIndex == emptyEntryIndex)
             break;

         if (k == 0) {
             k = 1 | doubleHash(entry.key->computedHash());
 #if DUMP_PROPERTYMAP_STATS
             ++numCollisions;
 #endif
         }

         i += k;

 #if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }

     unsigned entryIndex = m_u.table->keyCount + 2;
     m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
     m_u.table->entries()[entryIndex - 1] = entry;
     ++m_u.table->keyCount;
 }

 void PropertyMap::expand()
 {
     if (!m_usingTable)
         createTable();
     else
         rehash(m_u.table->size * 2);
 }

 void PropertyMap::rehash()
 {
     ASSERT(m_usingTable);
     ASSERT(m_u.table);
     ASSERT(m_u.table->size);
     rehash(m_u.table->size);
 }

 void PropertyMap::createTable()
 {
     const unsigned newTableSize = 16;

     ASSERT(!m_usingTable);

     checkConsistency();

 #if USE_SINGLE_ENTRY
     JSValue* oldSingleEntryValue = m_u.singleEntryValue;
 #endif

     m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
     m_u.table->size = newTableSize;
     m_u.table->sizeMask = newTableSize - 1;
     m_usingTable = true;

 #if USE_SINGLE_ENTRY
     if (m_singleEntryKey) {
         insert(Entry(m_singleEntryKey, oldSingleEntryValue, m_singleEntryAttributes));
         m_singleEntryKey = 0;
     }
 #endif

     checkConsistency();
 }

 void PropertyMap::rehash(unsigned newTableSize)
 {
     ASSERT(!m_singleEntryKey);
     ASSERT(m_u.table);
     ASSERT(m_usingTable);

     checkConsistency();

     Table* oldTable = m_u.table;

     m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
     m_u.table->size = newTableSize;
     m_u.table->sizeMask = newTableSize - 1;

     unsigned lastIndexUsed = 0;
     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; ++i) {
         if (oldTable->entries()[i].key) {
             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
             insert(oldTable->entries()[i]);
         }
     }
     m_u.table->lastIndexUsed = lastIndexUsed;

     fastFree(oldTable);

     checkConsistency();
 }

 void PropertyMap::remove(const Identifier& name)
 {
     ASSERT(!name.isNull());

     checkConsistency();

     UString::Rep* rep = name._ustring.rep();

     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (rep == m_singleEntryKey) {
             m_singleEntryKey->deref();
             m_singleEntryKey = 0;
             checkConsistency();
         }
 #endif
         return;
     }

 #if DUMP_PROPERTYMAP_STATS
     ++numProbes;
     ++numRemoves;
 #endif

     // Find the thing to remove.
     unsigned i = rep->computedHash();
     unsigned k = 0;
     unsigned entryIndex;
     UString::Rep* key = 0;
     while (1) {
         entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
         if (entryIndex == emptyEntryIndex)
             return;

         key = m_u.table->entries()[entryIndex - 1].key;
         if (rep == key)
             break;

         if (k == 0) {
             k = 1 | doubleHash(rep->computedHash());
 #if DUMP_PROPERTYMAP_STATS
             ++numCollisions;
 #endif
         }

         i += k;

 #if DUMP_PROPERTYMAP_STATS
         ++numRehashes;
 #endif
     }

     // Replace this one element with the deleted sentinel. Also clear out
     // the entry so we can iterate all the entries as needed.
     m_u.table->entryIndicies[i & m_u.table->sizeMask] = deletedSentinelIndex;
     key->deref();
     m_u.table->entries()[entryIndex - 1].key = 0;
     m_u.table->entries()[entryIndex - 1].value = jsUndefined();
     m_u.table->entries()[entryIndex - 1].attributes = 0;
     ASSERT(m_u.table->keyCount >= 1);
     --m_u.table->keyCount;
     ++m_u.table->deletedSentinelCount;

     if (m_u.table->deletedSentinelCount * 4 >= m_u.table->size)
         rehash();

     checkConsistency();
 }

 void PropertyMap::mark() const
 {
     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (m_singleEntryKey) {
             JSValue* v = m_u.singleEntryValue;
             if (!v->marked())
                 v->mark();
         }
 #endif
         return;
     }

     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; i++) {
         JSValue* v = m_u.table->entries()[i].value;
         if (!v->marked())
             v->mark();
     }
 }

 static int comparePropertyMapEntryIndices(const void* a, const void* b)
 {
     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
     if (ia < ib)
         return -1;
     if (ia > ib)
         return +1;
     return 0;
 }

 bool PropertyMap::containsGettersOrSetters() const
 {
     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         return !!(m_singleEntryAttributes & GetterSetter);
 #else
         return false;
 #endif
     }

     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; i++) {
         if (m_u.table->entries()[i].attributes & GetterSetter)
             return true;
     }

     return false;
 }

 void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
 {
     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         UString::Rep* key = m_singleEntryKey;
         if (key && !(m_singleEntryAttributes & DontEnum))
             propertyNames.add(Identifier(key));
 #endif
         return;
     }

     if (m_u.table->keyCount < tinyMapThreshold) {
         Entry* a[tinyMapThreshold];
         int i = 0;
         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
         for (unsigned k = 1; k <= entryCount; k++) {
             if (m_u.table->entries()[k].key && !(m_u.table->entries()[k].attributes & DontEnum)) {
                 Entry* value = &m_u.table->entries()[k];
                 int j;
                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
                     a[j + 1] = a[j];
                 a[j + 1] = value;
                 ++i;
             }
         }
         for (int k = 0; k < i; ++k)
             propertyNames.add(Identifier(a[k]->key));
         return;
     }

     // Allocate a buffer to use to sort the keys.
     Vector<Entry*, smallMapThreshold> sortedEnumerables(m_u.table->keyCount);

     // Get pointers to the enumerable entries in the buffer.
     Entry** p = sortedEnumerables.data();
     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; i++) {
         if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & DontEnum))
             *p++ = &m_u.table->entries()[i];
     }

     // Sort the entries by index.
     qsort(sortedEnumerables.data(), p - sortedEnumerables.data(), sizeof(Entry*), comparePropertyMapEntryIndices);

     // Put the keys of the sorted entries into the list.
     for (Entry** q = sortedEnumerables.data(); q != p; ++q)
         propertyNames.add(Identifier(q[0]->key));
 }

 void PropertyMap::save(SavedProperties& s) const
 {
     unsigned count = 0;

     if (!m_usingTable) {
 #if USE_SINGLE_ENTRY
         if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly | Function)))
             ++count;
 #endif
     } else {
         unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
         for (unsigned i = 1; i <= entryCount; ++i)
             if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
                 ++count;
     }

     s.properties.clear();
     s.count = count;

     if (count == 0)
         return;

     s.properties.set(new SavedProperty[count]);

     SavedProperty* prop = s.properties.get();

 #if USE_SINGLE_ENTRY
     if (!m_usingTable) {
         prop->init(m_singleEntryKey, m_u.singleEntryValue, m_singleEntryAttributes);
         return;
     }
 #endif

     // Save in the right order so we don't lose the order.
     // Another possibility would be to save the indices.

     // Allocate a buffer to use to sort the keys.
     Vector<Entry*, smallMapThreshold> sortedEntries(count);

     // Get pointers to the entries in the buffer.
     Entry** p = sortedEntries.data();
     unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
     for (unsigned i = 1; i <= entryCount; ++i) {
         if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly | Function)))
             *p++ = &m_u.table->entries()[i];
     }
     ASSERT(p == sortedEntries.data() + count);

     // Sort the entries by index.
     qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry*), comparePropertyMapEntryIndices);

     // Put the sorted entries into the saved properties list.
     for (Entry** q = sortedEntries.data(); q != p; ++q, ++prop) {
         Entry* e = *q;
         prop->init(e->key, e->value, e->attributes);
     }
 }

 void PropertyMap::restore(const SavedProperties& p)
 {
     for (unsigned i = 0; i != p.count; ++i)
         put(Identifier(p.properties[i].name()), p.properties[i].value(), p.properties[i].attributes());
 }

 #if DO_PROPERTYMAP_CONSTENCY_CHECK

 void PropertyMap::checkConsistency()
 {
     if (!m_usingTable)
         return;

     ASSERT(m_u.table->size >= 16);
     ASSERT(m_u.table->sizeMask);
     ASSERT(m_u.table->size == m_u.table->sizeMask + 1);
     ASSERT(!(m_u.table->size & m_u.table->sizeMask));

     ASSERT(m_u.table->keyCount <= m_u.table->size / 2);
     ASSERT(m_u.table->deletedSentinelCount <= m_u.table->size / 4);

     ASSERT(m_u.table->keyCount + m_u.table->deletedSentinelCount <= m_u.table->size / 2);

     unsigned indexCount = 0;
     unsigned deletedIndexCount = 0;
     for (unsigned a = 0; a != m_u.table->size; ++a) {
         unsigned entryIndex = m_u.table->entryIndicies[a];
         if (entryIndex == emptyEntryIndex)
             continue;
         if (entryIndex == deletedSentinelIndex) {
             ++deletedIndexCount;
             continue;
         }
         ASSERT(entryIndex > deletedSentinelIndex);
         ASSERT(entryIndex - 1 <= m_u.table->keyCount + m_u.table->deletedSentinelCount);
         ++indexCount;

         for (unsigned b = a + 1; b != m_u.table->size; ++b)
             ASSERT(m_u.table->entryIndicies[b] != entryIndex);
     }
     ASSERT(indexCount == m_u.table->keyCount);
     ASSERT(deletedIndexCount == m_u.table->deletedSentinelCount);

     ASSERT(m_u.table->entries()[0].key == 0);

     unsigned nonEmptyEntryCount = 0;
     for (unsigned c = 1; c <= m_u.table->keyCount + m_u.table->deletedSentinelCount; ++c) {
         UString::Rep* rep = m_u.table->entries()[c].key;
         if (!rep) {
             ASSERT(m_u.table->entries()[c].value->isUndefined());
             continue;
         }
         ++nonEmptyEntryCount;
         unsigned i = rep->computedHash();
         unsigned k = 0;
         unsigned entryIndex;
         while (1) {
             entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
             ASSERT(entryIndex != emptyEntryIndex);
             if (rep == m_u.table->entries()[entryIndex - 1].key)
                 break;
             if (k == 0)
                 k = 1 | doubleHash(rep->computedHash());
             i += k;
         }
         ASSERT(entryIndex == c + 1);
     }

     ASSERT(nonEmptyEntryCount == m_u.table->keyCount);
 }

 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK

 } // namespace KJS
	/*
	* 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.
	*
	*/

	#include "config.h"
	#include "property_map.h"

	#include "object.h"
	#include "protect.h"
	#include "PropertyNameArray.h"
	#include <algorithm>
	#include <wtf/Assertions.h>
	#include <wtf/FastMalloc.h>
	#include <wtf/HashTable.h>
	#include <wtf/Vector.h>

	using std::max;
	using WTF::doubleHash;

	#ifndef NDEBUG
	#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
	#define DUMP_PROPERTYMAP_STATS 0
	#else
	#define DO_PROPERTYMAP_CONSTENCY_CHECK 0
	#define DUMP_PROPERTYMAP_STATS 0
	#endif

	#define USE_SINGLE_ENTRY 1

	// 2/28/2006 ggaren: command-line JS iBench says that USE_SINGLE_ENTRY is a
	// 3.2% performance boost.

	namespace KJS {

	// Choose a number for the following so that most property maps are smaller,
	// but it's not going to blow out the stack to allocate this number of pointers.
	static const int smallMapThreshold = 1024;

	// The point at which the function call overhead of the qsort implementation
	// becomes small compared to the inefficiency of insertion sort.
	static const unsigned tinyMapThreshold = 20;

	#if DUMP_PROPERTYMAP_STATS

	static int numProbes;
	static int numCollisions;
	static int numRehashes;
	static int numRemoves;

	struct PropertyMapStatisticsExitLogger { ~PropertyMapStatisticsExitLogger(); };

	static PropertyMapStatisticsExitLogger logger;

	PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
	{
	printf("\nKJS::PropertyMap statistics\n\n");
	printf("%d probes\n", numProbes);
	printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
	printf("%d rehashes\n", numRehashes);
	printf("%d removes\n", numRemoves);
	}

	#endif

	struct PropertyMapEntry {
	UString::Rep* key;
	JSValue* value;
	unsigned attributes;
	unsigned index;

	PropertyMapEntry(UString::Rep* k, JSValue* v, int a)
	: key(k), value(v), attributes(a), index(0)
	{
	}
	};

	// 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;
	unsigned entryIndicies[1];

	PropertyMapEntry* entries()
	{
	// 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*>(&entryIndicies[size]);
	}

	static size_t allocationSize(unsigned size)
	{
	// 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);
	}
	};

	static const unsigned emptyEntryIndex = 0;
	static const unsigned deletedSentinelIndex = 1;

	SavedProperties::SavedProperties()
	: count(0)
	{
	}

	SavedProperties::~SavedProperties()
	{
	}

	#if !DO_PROPERTYMAP_CONSTENCY_CHECK

	inline void PropertyMap::checkConsistency()
	{
	}

	#endif

	PropertyMap::~PropertyMap()
	{
	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (m_singleEntryKey)
	m_singleEntryKey->deref();
	#endif
	return;
	}

	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; i++) {
	if (UString::Rep* key = m_u.table->entries()[i].key)
	key->deref();
	}
	fastFree(m_u.table);
	}

	void PropertyMap::clear()
	{
	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (m_singleEntryKey) {
	m_singleEntryKey->deref();
	m_singleEntryKey = 0;
	}
	#endif
	return;
	}

	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; i++) {
	if (UString::Rep* key = m_u.table->entries()[i].key)
	key->deref();
	}
	for (unsigned i = 0; i < m_u.table->size; i++)
	m_u.table->entryIndicies[i] = emptyEntryIndex;
	m_u.table->keyCount = 0;
	m_u.table->deletedSentinelCount = 0;
	}

	JSValue* PropertyMap::get(const Identifier& name, unsigned& attributes) const
	{
	ASSERT(!name.isNull());

	UString::Rep* rep = name._ustring.rep();

	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (rep == m_singleEntryKey) {
	attributes = m_singleEntryAttributes;
	return m_u.singleEntryValue;
	}
	#endif
	return 0;
	}

	unsigned i = rep->computedHash();

	#if DUMP_PROPERTYMAP_STATS
	++numProbes;
	#endif

	unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return 0;

	if (rep == m_u.table->entries()[entryIndex - 1].key) {
	attributes = m_u.table->entries()[entryIndex - 1].attributes;
	return m_u.table->entries()[entryIndex - 1].value;
	}

	#if DUMP_PROPERTYMAP_STATS
	++numCollisions;
	#endif

	unsigned k = 1 \| doubleHash(rep->computedHash());

	while (1) {
	i += k;

	#if DUMP_PROPERTYMAP_STATS
	++numRehashes;
	#endif

	entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return 0;

	if (rep == m_u.table->entries()[entryIndex - 1].key) {
	attributes = m_u.table->entries()[entryIndex - 1].attributes;
	return m_u.table->entries()[entryIndex - 1].value;
	}
	}
	}

	JSValue* PropertyMap::get(const Identifier& name) const
	{
	ASSERT(!name.isNull());

	UString::Rep* rep = name._ustring.rep();

	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (rep == m_singleEntryKey)
	return m_u.singleEntryValue;
	#endif
	return 0;
	}

	unsigned i = rep->computedHash();

	#if DUMP_PROPERTYMAP_STATS
	++numProbes;
	#endif

	unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return 0;

	if (rep == m_u.table->entries()[entryIndex - 1].key)
	return m_u.table->entries()[entryIndex - 1].value;

	#if DUMP_PROPERTYMAP_STATS
	++numCollisions;
	#endif

	unsigned k = 1 \| doubleHash(rep->computedHash());

	while (1) {
	i += k;

	#if DUMP_PROPERTYMAP_STATS
	++numRehashes;
	#endif

	entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return 0;

	if (rep == m_u.table->entries()[entryIndex - 1].key)
	return m_u.table->entries()[entryIndex - 1].value;
	}
	}

	JSValue** PropertyMap::getLocation(const Identifier& name)
	{
	ASSERT(!name.isNull());

	UString::Rep* rep = name._ustring.rep();

	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (rep == m_singleEntryKey)
	return &m_u.singleEntryValue;
	#endif
	return 0;
	}

	unsigned i = rep->computedHash();

	#if DUMP_PROPERTYMAP_STATS
	++numProbes;
	#endif

	unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return 0;

	if (rep == m_u.table->entries()[entryIndex - 1].key)
	return &m_u.table->entries()[entryIndex - 1].value;

	#if DUMP_PROPERTYMAP_STATS
	++numCollisions;
	#endif

	unsigned k = 1 \| doubleHash(rep->computedHash());

	while (1) {
	i += k;

	#if DUMP_PROPERTYMAP_STATS
	++numRehashes;
	#endif

	entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return 0;

	if (rep == m_u.table->entries()[entryIndex - 1].key)
	return &m_u.table->entries()[entryIndex - 1].value;
	}
	}

	void PropertyMap::put(const Identifier& name, JSValue* value, unsigned attributes, bool checkReadOnly)
	{
	ASSERT(!name.isNull());
	ASSERT(value);

	checkConsistency();

	UString::Rep* rep = name._ustring.rep();

	#if USE_SINGLE_ENTRY
	if (!m_usingTable) {
	if (!m_singleEntryKey) {
	rep->ref();
	m_singleEntryKey = rep;
	m_u.singleEntryValue = value;
	m_singleEntryAttributes = static_cast<short>(attributes);
	checkConsistency();
	return;
	}
	if (rep == m_singleEntryKey && !(checkReadOnly && (m_singleEntryAttributes & ReadOnly))) {
	m_u.singleEntryValue = value;
	return;
	}
	}
	#endif

	if (!m_usingTable \|\| (m_u.table->keyCount + m_u.table->deletedSentinelCount) * 2 >= m_u.table->size)
	expand();

	// FIXME: Consider a fast case for tables with no deleted sentinels.

	unsigned i = rep->computedHash();
	unsigned k = 0;
	bool foundDeletedElement = false;
	unsigned deletedElementIndex = 0; // initialize to make the compiler happy

	#if DUMP_PROPERTYMAP_STATS
	++numProbes;
	#endif

	while (1) {
	unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	break;

	if (m_u.table->entries()[entryIndex - 1].key == rep) {
	if (checkReadOnly && (m_u.table->entries()[entryIndex - 1].attributes & ReadOnly))
	return;
	// Put a new value in an existing hash table entry.
	m_u.table->entries()[entryIndex - 1].value = value;
	// Attributes are intentionally not updated.
	return;
	} else if (entryIndex == deletedSentinelIndex) {
	// If we find a deleted-element sentinel, remember it for use later.
	if (!foundDeletedElement) {
	foundDeletedElement = true;
	deletedElementIndex = i;
	}
	}

	if (k == 0) {
	k = 1 \| doubleHash(rep->computedHash());
	#if DUMP_PROPERTYMAP_STATS
	++numCollisions;
	#endif
	}

	i += k;

	#if DUMP_PROPERTYMAP_STATS
	++numRehashes;
	#endif
	}

	// Figure out which entry to use.
	unsigned entryIndex = m_u.table->keyCount + m_u.table->deletedSentinelCount + 2;
	if (foundDeletedElement) {
	i = deletedElementIndex;
	--m_u.table->deletedSentinelCount;

	// Since we're not making the table bigger, we can't use the entry one past
	// the end that we were planning on using, so search backwards for the empty
	// slot that we can use. We know it will be there because we did at least one
	// deletion in the past that left an entry empty.
	while (m_u.table->entries()[--entryIndex - 1].key)
	;
	}


	// Create a new hash table entry.
	m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;

	// Create a new hash table entry.
	rep->ref();
	m_u.table->entries()[entryIndex - 1].key = rep;
	m_u.table->entries()[entryIndex - 1].value = value;
	m_u.table->entries()[entryIndex - 1].attributes = attributes;
	m_u.table->entries()[entryIndex - 1].index = ++m_u.table->lastIndexUsed;
	++m_u.table->keyCount;

	checkConsistency();
	}

	void PropertyMap::insert(const Entry& entry)
	{
	ASSERT(m_u.table);

	unsigned i = entry.key->computedHash();
	unsigned k = 0;

	#if DUMP_PROPERTYMAP_STATS
	++numProbes;
	#endif

	while (1) {
	unsigned entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	break;

	if (k == 0) {
	k = 1 \| doubleHash(entry.key->computedHash());
	#if DUMP_PROPERTYMAP_STATS
	++numCollisions;
	#endif
	}

	i += k;

	#if DUMP_PROPERTYMAP_STATS
	++numRehashes;
	#endif
	}

	unsigned entryIndex = m_u.table->keyCount + 2;
	m_u.table->entryIndicies[i & m_u.table->sizeMask] = entryIndex;
	m_u.table->entries()[entryIndex - 1] = entry;
	++m_u.table->keyCount;
	}

	void PropertyMap::expand()
	{
	if (!m_usingTable)
	createTable();
	else
	rehash(m_u.table->size * 2);
	}

	void PropertyMap::rehash()
	{
	ASSERT(m_usingTable);
	ASSERT(m_u.table);
	ASSERT(m_u.table->size);
	rehash(m_u.table->size);
	}

	void PropertyMap::createTable()
	{
	const unsigned newTableSize = 16;

	ASSERT(!m_usingTable);

	checkConsistency();

	#if USE_SINGLE_ENTRY
	JSValue* oldSingleEntryValue = m_u.singleEntryValue;
	#endif

	m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
	m_u.table->size = newTableSize;
	m_u.table->sizeMask = newTableSize - 1;
	m_usingTable = true;

	#if USE_SINGLE_ENTRY
	if (m_singleEntryKey) {
	insert(Entry(m_singleEntryKey, oldSingleEntryValue, m_singleEntryAttributes));
	m_singleEntryKey = 0;
	}
	#endif

	checkConsistency();
	}

	void PropertyMap::rehash(unsigned newTableSize)
	{
	ASSERT(!m_singleEntryKey);
	ASSERT(m_u.table);
	ASSERT(m_usingTable);

	checkConsistency();

	Table* oldTable = m_u.table;

	m_u.table = static_cast<Table*>(fastZeroedMalloc(Table::allocationSize(newTableSize)));
	m_u.table->size = newTableSize;
	m_u.table->sizeMask = newTableSize - 1;

	unsigned lastIndexUsed = 0;
	unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; ++i) {
	if (oldTable->entries()[i].key) {
	lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
	insert(oldTable->entries()[i]);
	}
	}
	m_u.table->lastIndexUsed = lastIndexUsed;

	fastFree(oldTable);

	checkConsistency();
	}

	void PropertyMap::remove(const Identifier& name)
	{
	ASSERT(!name.isNull());

	checkConsistency();

	UString::Rep* rep = name._ustring.rep();

	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (rep == m_singleEntryKey) {
	m_singleEntryKey->deref();
	m_singleEntryKey = 0;
	checkConsistency();
	}
	#endif
	return;
	}

	#if DUMP_PROPERTYMAP_STATS
	++numProbes;
	++numRemoves;
	#endif

	// Find the thing to remove.
	unsigned i = rep->computedHash();
	unsigned k = 0;
	unsigned entryIndex;
	UString::Rep* key = 0;
	while (1) {
	entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	if (entryIndex == emptyEntryIndex)
	return;

	key = m_u.table->entries()[entryIndex - 1].key;
	if (rep == key)
	break;

	if (k == 0) {
	k = 1 \| doubleHash(rep->computedHash());
	#if DUMP_PROPERTYMAP_STATS
	++numCollisions;
	#endif
	}

	i += k;

	#if DUMP_PROPERTYMAP_STATS
	++numRehashes;
	#endif
	}

	// Replace this one element with the deleted sentinel. Also clear out
	// the entry so we can iterate all the entries as needed.
	m_u.table->entryIndicies[i & m_u.table->sizeMask] = deletedSentinelIndex;
	key->deref();
	m_u.table->entries()[entryIndex - 1].key = 0;
	m_u.table->entries()[entryIndex - 1].value = jsUndefined();
	m_u.table->entries()[entryIndex - 1].attributes = 0;
	ASSERT(m_u.table->keyCount >= 1);
	--m_u.table->keyCount;
	++m_u.table->deletedSentinelCount;

	if (m_u.table->deletedSentinelCount * 4 >= m_u.table->size)
	rehash();

	checkConsistency();
	}

	void PropertyMap::mark() const
	{
	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (m_singleEntryKey) {
	JSValue* v = m_u.singleEntryValue;
	if (!v->marked())
	v->mark();
	}
	#endif
	return;
	}

	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; i++) {
	JSValue* v = m_u.table->entries()[i].value;
	if (!v->marked())
	v->mark();
	}
	}

	static int comparePropertyMapEntryIndices(const void* a, const void* b)
	{
	unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
	unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
	if (ia < ib)
	return -1;
	if (ia > ib)
	return +1;
	return 0;
	}

	bool PropertyMap::containsGettersOrSetters() const
	{
	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	return !!(m_singleEntryAttributes & GetterSetter);
	#else
	return false;
	#endif
	}

	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; i++) {
	if (m_u.table->entries()[i].attributes & GetterSetter)
	return true;
	}

	return false;
	}

	void PropertyMap::getEnumerablePropertyNames(PropertyNameArray& propertyNames) const
	{
	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	UString::Rep* key = m_singleEntryKey;
	if (key && !(m_singleEntryAttributes & DontEnum))
	propertyNames.add(Identifier(key));
	#endif
	return;
	}

	if (m_u.table->keyCount < tinyMapThreshold) {
	Entry* a[tinyMapThreshold];
	int i = 0;
	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned k = 1; k <= entryCount; k++) {
	if (m_u.table->entries()[k].key && !(m_u.table->entries()[k].attributes & DontEnum)) {
	Entry* value = &m_u.table->entries()[k];
	int j;
	for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
	a[j + 1] = a[j];
	a[j + 1] = value;
	++i;
	}
	}
	for (int k = 0; k < i; ++k)
	propertyNames.add(Identifier(a[k]->key));
	return;
	}

	// Allocate a buffer to use to sort the keys.
	Vector<Entry*, smallMapThreshold> sortedEnumerables(m_u.table->keyCount);

	// Get pointers to the enumerable entries in the buffer.
	Entry** p = sortedEnumerables.data();
	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; i++) {
	if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & DontEnum))
	*p++ = &m_u.table->entries()[i];
	}

	// Sort the entries by index.
	qsort(sortedEnumerables.data(), p - sortedEnumerables.data(), sizeof(Entry*), comparePropertyMapEntryIndices);

	// Put the keys of the sorted entries into the list.
	for (Entry** q = sortedEnumerables.data(); q != p; ++q)
	propertyNames.add(Identifier(q[0]->key));
	}

	void PropertyMap::save(SavedProperties& s) const
	{
	unsigned count = 0;

	if (!m_usingTable) {
	#if USE_SINGLE_ENTRY
	if (m_singleEntryKey && !(m_singleEntryAttributes & (ReadOnly \| Function)))
	++count;
	#endif
	} else {
	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; ++i)
	if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly \| Function)))
	++count;
	}

	s.properties.clear();
	s.count = count;

	if (count == 0)
	return;

	s.properties.set(new SavedProperty[count]);

	SavedProperty* prop = s.properties.get();

	#if USE_SINGLE_ENTRY
	if (!m_usingTable) {
	prop->init(m_singleEntryKey, m_u.singleEntryValue, m_singleEntryAttributes);
	return;
	}
	#endif

	// Save in the right order so we don't lose the order.
	// Another possibility would be to save the indices.

	// Allocate a buffer to use to sort the keys.
	Vector<Entry*, smallMapThreshold> sortedEntries(count);

	// Get pointers to the entries in the buffer.
	Entry** p = sortedEntries.data();
	unsigned entryCount = m_u.table->keyCount + m_u.table->deletedSentinelCount;
	for (unsigned i = 1; i <= entryCount; ++i) {
	if (m_u.table->entries()[i].key && !(m_u.table->entries()[i].attributes & (ReadOnly \| Function)))
	*p++ = &m_u.table->entries()[i];
	}
	ASSERT(p == sortedEntries.data() + count);

	// Sort the entries by index.
	qsort(sortedEntries.data(), p - sortedEntries.data(), sizeof(Entry*), comparePropertyMapEntryIndices);

	// Put the sorted entries into the saved properties list.
	for (Entry** q = sortedEntries.data(); q != p; ++q, ++prop) {
	Entry* e = *q;
	prop->init(e->key, e->value, e->attributes);
	}
	}

	void PropertyMap::restore(const SavedProperties& p)
	{
	for (unsigned i = 0; i != p.count; ++i)
	put(Identifier(p.properties[i].name()), p.properties[i].value(), p.properties[i].attributes());
	}

	#if DO_PROPERTYMAP_CONSTENCY_CHECK

	void PropertyMap::checkConsistency()
	{
	if (!m_usingTable)
	return;

	ASSERT(m_u.table->size >= 16);
	ASSERT(m_u.table->sizeMask);
	ASSERT(m_u.table->size == m_u.table->sizeMask + 1);
	ASSERT(!(m_u.table->size & m_u.table->sizeMask));

	ASSERT(m_u.table->keyCount <= m_u.table->size / 2);
	ASSERT(m_u.table->deletedSentinelCount <= m_u.table->size / 4);

	ASSERT(m_u.table->keyCount + m_u.table->deletedSentinelCount <= m_u.table->size / 2);

	unsigned indexCount = 0;
	unsigned deletedIndexCount = 0;
	for (unsigned a = 0; a != m_u.table->size; ++a) {
	unsigned entryIndex = m_u.table->entryIndicies[a];
	if (entryIndex == emptyEntryIndex)
	continue;
	if (entryIndex == deletedSentinelIndex) {
	++deletedIndexCount;
	continue;
	}
	ASSERT(entryIndex > deletedSentinelIndex);
	ASSERT(entryIndex - 1 <= m_u.table->keyCount + m_u.table->deletedSentinelCount);
	++indexCount;

	for (unsigned b = a + 1; b != m_u.table->size; ++b)
	ASSERT(m_u.table->entryIndicies[b] != entryIndex);
	}
	ASSERT(indexCount == m_u.table->keyCount);
	ASSERT(deletedIndexCount == m_u.table->deletedSentinelCount);

	ASSERT(m_u.table->entries()[0].key == 0);

	unsigned nonEmptyEntryCount = 0;
	for (unsigned c = 1; c <= m_u.table->keyCount + m_u.table->deletedSentinelCount; ++c) {
	UString::Rep* rep = m_u.table->entries()[c].key;
	if (!rep) {
	ASSERT(m_u.table->entries()[c].value->isUndefined());
	continue;
	}
	++nonEmptyEntryCount;
	unsigned i = rep->computedHash();
	unsigned k = 0;
	unsigned entryIndex;
	while (1) {
	entryIndex = m_u.table->entryIndicies[i & m_u.table->sizeMask];
	ASSERT(entryIndex != emptyEntryIndex);
	if (rep == m_u.table->entries()[entryIndex - 1].key)
	break;
	if (k == 0)
	k = 1 \| doubleHash(rep->computedHash());
	i += k;
	}
	ASSERT(entryIndex == c + 1);
	}

	ASSERT(nonEmptyEntryCount == m_u.table->keyCount);
	}

	#endif // DO_PROPERTYMAP_CONSTENCY_CHECK

	} // namespace KJS