runtime/PropertyMapHashTable.h

   1 /*
   2  *  Copyright (C) 2004, 2005, 2006, 2007, 2008 Apple Inc. All rights reserved.
   3  *
   4  *  This library is free software; you can redistribute it and/or
   5  *  modify it under the terms of the GNU Library General Public
   6  *  License as published by the Free Software Foundation; either
   7  *  version 2 of the License, or (at your option) any later version.
   8  *
   9  *  This library is distributed in the hope that it will be useful,
  10  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  *  Library General Public License for more details.
  13  *
  14  *  You should have received a copy of the GNU Library General Public License
  15  *  along with this library; see the file COPYING.LIB.  If not, write to
  16  *  the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  *  Boston, MA 02110-1301, USA.
  18  *
  19  */
  20
  21 #ifndef PropertyMapHashTable_h
  22 #define PropertyMapHashTable_h
  23
  24 #include "PropertyOffset.h"
  25 #include "Structure.h"
  26 #include "WriteBarrier.h"
  27 #include <wtf/HashTable.h>
  28 #include <wtf/MathExtras.h>
  29 #include <wtf/PassOwnPtr.h>
  30 #include <wtf/Vector.h>
  31 #include <wtf/text/StringImpl.h>
  32
  33
  34 #ifndef NDEBUG
  35 #define DUMP_PROPERTYMAP_STATS 0
  36 #else
  37 #define DUMP_PROPERTYMAP_STATS 0
  38 #endif
  39
  40 #if DUMP_PROPERTYMAP_STATS
  41
  42 extern int numProbes;
  43 extern int numCollisions;
  44 extern int numRehashes;
  45 extern int numRemoves;
  46
  47 #endif
  48
  49 #define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1)
  50
  51 namespace JSC {
  52
  53 inline bool isPowerOf2(unsigned v)
  54 {
  55     return hasOneBitSet(v);
  56 }
  57
  58 inline unsigned nextPowerOf2(unsigned v)
  59 {
  60     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
  61     // Devised by Sean Anderson, Sepember 14, 2001
  62
  63     v--;
  64     v |= v >> 1;
  65     v |= v >> 2;
  66     v |= v >> 4;
  67     v |= v >> 8;
  68     v |= v >> 16;
  69     v++;
  70
  71     return v;
  72 }
  73
  74 struct PropertyMapEntry {
  75     StringImpl* key;
  76     PropertyOffset offset;
  77     unsigned attributes;
  78     WriteBarrier<JSCell> specificValue;
  79
  80     PropertyMapEntry(VM& vm, JSCell* owner, StringImpl* key, PropertyOffset offset, unsigned attributes, JSCell* specificValue)
  81         : key(key)
  82         , offset(offset)
  83         , attributes(attributes)
  84         , specificValue(vm, owner, specificValue, WriteBarrier<JSCell>::MayBeNull)
  85     {
  86     }
  87 };
  88
  89 class PropertyTable : public JSCell {
  90
  91     // This is the implementation for 'iterator' and 'const_iterator',
  92     // used for iterating over the table in insertion order.
  93     template<typename T>
  94     class ordered_iterator {
  95     public:
  96         ordered_iterator<T>& operator++()
  97         {
  98             m_valuePtr = skipDeletedEntries(m_valuePtr + 1);
  99             return *this;
 100         }
 101
 102         bool operator==(const ordered_iterator<T>& other)
 103         {
 104             return m_valuePtr == other.m_valuePtr;
 105         }
 106
 107         bool operator!=(const ordered_iterator<T>& other)
 108         {
 109             return m_valuePtr != other.m_valuePtr;
 110         }
 111
 112         T& operator*()
 113         {
 114             return *m_valuePtr;
 115         }
 116
 117         T* operator->()
 118         {
 119             return m_valuePtr;
 120         }
 121
 122         ordered_iterator(T* valuePtr)
 123             : m_valuePtr(valuePtr)
 124         {
 125         }
 126
 127     private:
 128         T* m_valuePtr;
 129     };
 130
 131 public:
 132     static const bool needsDestruction = true;
 133     static const bool hasImmortalStructure = true;
 134     static void destroy(JSCell*);
 135
 136     static JS_EXPORTDATA const ClassInfo s_info;
 137
 138     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
 139     {
 140         return Structure::create(vm, globalObject, prototype, TypeInfo(CompoundType, OverridesVisitChildren), &s_info);
 141     }
 142
 143     static void visitChildren(JSCell*, SlotVisitor&);
 144
 145     typedef StringImpl* KeyType;
 146     typedef PropertyMapEntry ValueType;
 147
 148     // The in order iterator provides overloaded * and -> to access the Value at the current position.
 149     typedef ordered_iterator<ValueType> iterator;
 150     typedef ordered_iterator<const ValueType> const_iterator;
 151
 152     // The find_iterator is a pair of a pointer to a Value* an the entry in the index.
 153     // If 'find' does not find an entry then iter.first will be 0, and iter.second will
 154     // give the point in m_index where an entry should be inserted.
 155     typedef std::pair<ValueType*, unsigned> find_iterator;
 156
 157     // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
 158     static PropertyTable* create(VM&, unsigned initialCapacity);
 159     static PropertyTable* clone(VM&, JSCell* owner, const PropertyTable&);
 160     static PropertyTable* clone(VM&, JSCell* owner, unsigned initialCapacity, const PropertyTable&);
 161     ~PropertyTable();
 162
 163     // Ordered iteration methods.
 164     iterator begin();
 165     iterator end();
 166     const_iterator begin() const;
 167     const_iterator end() const;
 168
 169     // Find a value in the table.
 170     find_iterator find(const KeyType&);
 171     find_iterator findWithString(const KeyType&);
 172     // Add a value to the table
 173     enum EffectOnPropertyOffset { PropertyOffsetMayChange, PropertyOffsetMustNotChange };
 174     std::pair<find_iterator, bool> add(const ValueType& entry, PropertyOffset&, EffectOnPropertyOffset);
 175     // Remove a value from the table.
 176     void remove(const find_iterator& iter);
 177     void remove(const KeyType& key);
 178
 179     // Returns the number of values in the hashtable.
 180     unsigned size() const;
 181
 182     // Checks if there are any values in the hashtable.
 183     bool isEmpty() const;
 184
 185     // Number of slots in the property storage array in use, included deletedOffsets.
 186     unsigned propertyStorageSize() const;
 187
 188     // Used to maintain a list of unused entries in the property storage.
 189     void clearDeletedOffsets();
 190     bool hasDeletedOffset();
 191     PropertyOffset getDeletedOffset();
 192     void addDeletedOffset(PropertyOffset);
 193
 194     PropertyOffset nextOffset(PropertyOffset inlineCapacity);
 195
 196     // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
 197     PropertyTable* copy(VM&, JSCell* owner, unsigned newCapacity);
 198
 199 #ifndef NDEBUG
 200     size_t sizeInMemory();
 201     void checkConsistency();
 202 #endif
 203
 204 private:
 205     PropertyTable(VM&, unsigned initialCapacity);
 206     PropertyTable(VM&, JSCell*, const PropertyTable&);
 207     PropertyTable(VM&, JSCell*, unsigned initialCapacity, const PropertyTable&);
 208
 209     PropertyTable(const PropertyTable&);
 210     // Used to insert a value known not to be in the table, and where we know capacity to be available.
 211     void reinsert(const ValueType& entry);
 212
 213     // Rehash the table.  Used to grow, or to recover deleted slots.
 214     void rehash(unsigned newCapacity);
 215
 216     // The capacity of the table of values is half of the size of the index.
 217     unsigned tableCapacity() const;
 218
 219     // We keep an extra deleted slot after the array to make iteration work,
 220     // and to use for deleted values. Index values into the array are 1-based,
 221     // so this is tableCapacity() + 1.
 222     // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the
 223     // values array is actually 9 long (the 9th used for the deleted value/
 224     // iteration guard).  The 8 valid entries are numbered 1..8, so the
 225     // deleted index is 9 (0 being reserved for empty).
 226     unsigned deletedEntryIndex() const;
 227
 228     // Used in iterator creation/progression.
 229     template<typename T>
 230     static T* skipDeletedEntries(T* valuePtr);
 231
 232     // The table of values lies after the hash index.
 233     ValueType* table();
 234     const ValueType* table() const;
 235
 236     // total number of  used entries in the values array - by either valid entries, or deleted ones.
 237     unsigned usedCount() const;
 238
 239     // The size in bytes of data needed for by the table.
 240     size_t dataSize();
 241
 242     // Calculates the appropriate table size (rounds up to a power of two).
 243     static unsigned sizeForCapacity(unsigned capacity);
 244
 245     // Check if capacity is available.
 246     bool canInsert();
 247
 248     unsigned m_indexSize;
 249     unsigned m_indexMask;
 250     unsigned* m_index;
 251     unsigned m_keyCount;
 252     unsigned m_deletedCount;
 253     OwnPtr< Vector<PropertyOffset> > m_deletedOffsets;
 254
 255     static const unsigned MinimumTableSize = 8;
 256     static const unsigned EmptyEntryIndex = 0;
 257 };
 258
 259 inline PropertyTable::iterator PropertyTable::begin()
 260 {
 261     return iterator(skipDeletedEntries(table()));
 262 }
 263
 264 inline PropertyTable::iterator PropertyTable::end()
 265 {
 266     return iterator(table() + usedCount());
 267 }
 268
 269 inline PropertyTable::const_iterator PropertyTable::begin() const
 270 {
 271     return const_iterator(skipDeletedEntries(table()));
 272 }
 273
 274 inline PropertyTable::const_iterator PropertyTable::end() const
 275 {
 276     return const_iterator(table() + usedCount());
 277 }
 278
 279 inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
 280 {
 281     ASSERT(key);
 282     ASSERT(key->isIdentifier() || key->isEmptyUnique());
 283     unsigned hash = key->existingHash();
 284     unsigned step = 0;
 285
 286 #if DUMP_PROPERTYMAP_STATS
 287     ++numProbes;
 288 #endif
 289
 290     while (true) {
 291         unsigned entryIndex = m_index[hash & m_indexMask];
 292         if (entryIndex == EmptyEntryIndex)
 293             return std::make_pair((ValueType*)0, hash & m_indexMask);
 294         if (key == table()[entryIndex - 1].key)
 295             return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
 296
 297 #if DUMP_PROPERTYMAP_STATS
 298         ++numCollisions;
 299 #endif
 300
 301         if (!step)
 302             step = WTF::doubleHash(key->existingHash()) | 1;
 303         hash += step;
 304
 305 #if DUMP_PROPERTYMAP_STATS
 306         ++numRehashes;
 307 #endif
 308     }
 309 }
 310
 311 inline PropertyTable::find_iterator PropertyTable::findWithString(const KeyType& key)
 312 {
 313     ASSERT(key);
 314     ASSERT(!key->isIdentifier() && !key->hasHash());
 315     unsigned hash = key->hash();
 316     unsigned step = 0;
 317
 318 #if DUMP_PROPERTYMAP_STATS
 319     ++numProbes;
 320 #endif
 321
 322     while (true) {
 323         unsigned entryIndex = m_index[hash & m_indexMask];
 324         if (entryIndex == EmptyEntryIndex)
 325             return std::make_pair((ValueType*)0, hash & m_indexMask);
 326         const KeyType& keyInMap = table()[entryIndex - 1].key;
 327         if (equal(key, keyInMap) && keyInMap->isIdentifier())
 328             return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
 329
 330 #if DUMP_PROPERTYMAP_STATS
 331         ++numCollisions;
 332 #endif
 333
 334         if (!step)
 335             step = WTF::doubleHash(key->existingHash()) | 1;
 336         hash += step;
 337
 338 #if DUMP_PROPERTYMAP_STATS
 339         ++numRehashes;
 340 #endif
 341     }
 342 }
 343
 344 inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry, PropertyOffset& offset, EffectOnPropertyOffset offsetEffect)
 345 {
 346     // Look for a value with a matching key already in the array.
 347     find_iterator iter = find(entry.key);
 348     if (iter.first) {
 349         RELEASE_ASSERT(iter.first->offset <= offset);
 350         return std::make_pair(iter, false);
 351     }
 352
 353     // Ref the key
 354     entry.key->ref();
 355
 356     // ensure capacity is available.
 357     if (!canInsert()) {
 358         rehash(m_keyCount + 1);
 359         iter = find(entry.key);
 360         ASSERT(!iter.first);
 361     }
 362
 363     // Allocate a slot in the hashtable, and set the index to reference this.
 364     unsigned entryIndex = usedCount() + 1;
 365     m_index[iter.second] = entryIndex;
 366     iter.first = &table()[entryIndex - 1];
 367     *iter.first = entry;
 368
 369     ++m_keyCount;
 370
 371     if (offsetEffect == PropertyOffsetMayChange)
 372         offset = std::max(offset, entry.offset);
 373     else
 374         RELEASE_ASSERT(offset >= entry.offset);
 375
 376     return std::make_pair(iter, true);
 377 }
 378
 379 inline void PropertyTable::remove(const find_iterator& iter)
 380 {
 381     // Removing a key that doesn't exist does nothing!
 382     if (!iter.first)
 383         return;
 384
 385 #if DUMP_PROPERTYMAP_STATS
 386     ++numRemoves;
 387 #endif
 388
 389     // Replace this one element with the deleted sentinel. Also clear out
 390     // the entry so we can iterate all the entries as needed.
 391     m_index[iter.second] = deletedEntryIndex();
 392     iter.first->key->deref();
 393     iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY;
 394
 395     ASSERT(m_keyCount >= 1);
 396     --m_keyCount;
 397     ++m_deletedCount;
 398
 399     if (m_deletedCount * 4 >= m_indexSize)
 400         rehash(m_keyCount);
 401 }
 402
 403 inline void PropertyTable::remove(const KeyType& key)
 404 {
 405     remove(find(key));
 406 }
 407
 408 // returns the number of values in the hashtable.
 409 inline unsigned PropertyTable::size() const
 410 {
 411     return m_keyCount;
 412 }
 413
 414 inline bool PropertyTable::isEmpty() const
 415 {
 416     return !m_keyCount;
 417 }
 418
 419 inline unsigned PropertyTable::propertyStorageSize() const
 420 {
 421     return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0);
 422 }
 423
 424 inline void PropertyTable::clearDeletedOffsets()
 425 {
 426     m_deletedOffsets.clear();
 427 }
 428
 429 inline bool PropertyTable::hasDeletedOffset()
 430 {
 431     return m_deletedOffsets && !m_deletedOffsets->isEmpty();
 432 }
 433
 434 inline PropertyOffset PropertyTable::getDeletedOffset()
 435 {
 436     PropertyOffset offset = m_deletedOffsets->last();
 437     m_deletedOffsets->removeLast();
 438     return offset;
 439 }
 440
 441 inline void PropertyTable::addDeletedOffset(PropertyOffset offset)
 442 {
 443     if (!m_deletedOffsets)
 444         m_deletedOffsets = adoptPtr(new Vector<PropertyOffset>);
 445     m_deletedOffsets->append(offset);
 446 }
 447
 448 inline PropertyOffset PropertyTable::nextOffset(PropertyOffset inlineCapacity)
 449 {
 450     if (hasDeletedOffset())
 451         return getDeletedOffset();
 452
 453     return offsetForPropertyNumber(size(), inlineCapacity);
 454 }
 455
 456 inline PropertyTable* PropertyTable::copy(VM& vm, JSCell* owner, unsigned newCapacity)
 457 {
 458     ASSERT(newCapacity >= m_keyCount);
 459
 460     // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
 461     // save rehashing all keys.
 462     if (sizeForCapacity(newCapacity) == m_indexSize)
 463         return PropertyTable::clone(vm, owner, *this);
 464     return PropertyTable::clone(vm, owner, newCapacity, *this);
 465 }
 466
 467 #ifndef NDEBUG
 468 inline size_t PropertyTable::sizeInMemory()
 469 {
 470     size_t result = sizeof(PropertyTable) + dataSize();
 471     if (m_deletedOffsets)
 472         result += (m_deletedOffsets->capacity() * sizeof(PropertyOffset));
 473     return result;
 474 }
 475 #endif
 476
 477 inline void PropertyTable::reinsert(const ValueType& entry)
 478 {
 479     // Used to insert a value known not to be in the table, and where
 480     // we know capacity to be available.
 481     ASSERT(canInsert());
 482     find_iterator iter = find(entry.key);
 483     ASSERT(!iter.first);
 484
 485     unsigned entryIndex = usedCount() + 1;
 486     m_index[iter.second] = entryIndex;
 487     table()[entryIndex - 1] = entry;
 488
 489     ++m_keyCount;
 490 }
 491
 492 inline void PropertyTable::rehash(unsigned newCapacity)
 493 {
 494     unsigned* oldEntryIndices = m_index;
 495     iterator iter = this->begin();
 496     iterator end = this->end();
 497
 498     m_indexSize = sizeForCapacity(newCapacity);
 499     m_indexMask = m_indexSize - 1;
 500     m_keyCount = 0;
 501     m_deletedCount = 0;
 502     m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
 503
 504     for (; iter != end; ++iter) {
 505         ASSERT(canInsert());
 506         reinsert(*iter);
 507     }
 508
 509     fastFree(oldEntryIndices);
 510 }
 511
 512 inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; }
 513
 514 inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
 515
 516 template<typename T>
 517 inline T* PropertyTable::skipDeletedEntries(T* valuePtr)
 518 {
 519     while (valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY)
 520         ++valuePtr;
 521     return valuePtr;
 522 }
 523
 524 inline PropertyTable::ValueType* PropertyTable::table()
 525 {
 526     // The table of values lies after the hash index.
 527     return reinterpret_cast<ValueType*>(m_index + m_indexSize);
 528 }
 529
 530 inline const PropertyTable::ValueType* PropertyTable::table() const
 531 {
 532     // The table of values lies after the hash index.
 533     return reinterpret_cast<const ValueType*>(m_index + m_indexSize);
 534 }
 535
 536 inline unsigned PropertyTable::usedCount() const
 537 {
 538     // Total number of  used entries in the values array - by either valid entries, or deleted ones.
 539     return m_keyCount + m_deletedCount;
 540 }
 541
 542 inline size_t PropertyTable::dataSize()
 543 {
 544     // The size in bytes of data needed for by the table.
 545     return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType);
 546 }
 547
 548 inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
 549 {
 550     if (capacity < MinimumTableSize / 2)
 551         return MinimumTableSize;
 552     return nextPowerOf2(capacity + 1) * 2;
 553 }
 554
 555 inline bool PropertyTable::canInsert()
 556 {
 557     return usedCount() < tableCapacity();
 558 }
 559
 560 } // namespace JSC
 561
 562 #endif // PropertyMapHashTable_h