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 "UString.h"
  25 #include "WriteBarrier.h"
  26 #include <wtf/HashTable.h>
  27 #include <wtf/PassOwnPtr.h>
  28 #include <wtf/Vector.h>
  29
  30
  31 #ifndef NDEBUG
  32 #define DUMP_PROPERTYMAP_STATS 0
  33 #else
  34 #define DUMP_PROPERTYMAP_STATS 0
  35 #endif
  36
  37 #if DUMP_PROPERTYMAP_STATS
  38
  39 extern int numProbes;
  40 extern int numCollisions;
  41 extern int numRehashes;
  42 extern int numRemoves;
  43
  44 #endif
  45
  46 #define PROPERTY_MAP_DELETED_ENTRY_KEY ((StringImpl*)1)
  47
  48 namespace JSC {
  49
  50 inline bool isPowerOf2(unsigned v)
  51 {
  52     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
  53
  54     return !(v & (v - 1)) && v;
  55 }
  56
  57 inline unsigned nextPowerOf2(unsigned v)
  58 {
  59     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
  60     // Devised by Sean Anderson, Sepember 14, 2001
  61
  62     v--;
  63     v |= v >> 1;
  64     v |= v >> 2;
  65     v |= v >> 4;
  66     v |= v >> 8;
  67     v |= v >> 16;
  68     v++;
  69
  70     return v;
  71 }
  72
  73 struct PropertyMapEntry {
  74     StringImpl* key;
  75     unsigned offset;
  76     unsigned attributes;
  77     WriteBarrier<JSCell> specificValue;
  78
  79     PropertyMapEntry(JSGlobalData& globalData, JSCell* owner, StringImpl* key, unsigned offset, unsigned attributes, JSCell* specificValue)
  80         : key(key)
  81         , offset(offset)
  82         , attributes(attributes)
  83         , specificValue(globalData, owner, specificValue, WriteBarrier<JSCell>::MayBeNull)
  84     {
  85     }
  86 };
  87
  88 class PropertyTable {
  89     WTF_MAKE_FAST_ALLOCATED;
  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     typedef StringImpl* KeyType;
 133     typedef PropertyMapEntry ValueType;
 134
 135     // The in order iterator provides overloaded * and -> to access the Value at the current position.
 136     typedef ordered_iterator<ValueType> iterator;
 137     typedef ordered_iterator<const ValueType> const_iterator;
 138
 139     // The find_iterator is a pair of a pointer to a Value* an the entry in the index.
 140     // If 'find' does not find an entry then iter.first will be 0, and iter.second will
 141     // give the point in m_index where an entry should be inserted.
 142     typedef std::pair<ValueType*, unsigned> find_iterator;
 143
 144     // Constructor is passed an initial capacity, a PropertyTable to copy, or both.
 145     explicit PropertyTable(unsigned initialCapacity);
 146     PropertyTable(JSGlobalData&, JSCell*, const PropertyTable&);
 147     PropertyTable(JSGlobalData&, JSCell*, unsigned initialCapacity, const PropertyTable&);
 148     ~PropertyTable();
 149
 150     // Ordered iteration methods.
 151     iterator begin();
 152     iterator end();
 153     const_iterator begin() const;
 154     const_iterator end() const;
 155
 156     // Find a value in the table.
 157     find_iterator find(const KeyType&);
 158     find_iterator findWithString(const KeyType&);
 159     // Add a value to the table
 160     std::pair<find_iterator, bool> add(const ValueType& entry);
 161     // Remove a value from the table.
 162     void remove(const find_iterator& iter);
 163     void remove(const KeyType& key);
 164
 165     // Returns the number of values in the hashtable.
 166     unsigned size() const;
 167
 168     // Checks if there are any values in the hashtable.
 169     bool isEmpty() const;
 170
 171     // Number of slots in the property storage array in use, included deletedOffsets.
 172     unsigned propertyStorageSize() const;
 173
 174     // Used to maintain a list of unused entries in the property storage.
 175     void clearDeletedOffsets();
 176     bool hasDeletedOffset();
 177     unsigned getDeletedOffset();
 178     void addDeletedOffset(unsigned offset);
 179
 180     // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
 181     PassOwnPtr<PropertyTable> copy(JSGlobalData&, JSCell* owner, unsigned newCapacity);
 182
 183 #ifndef NDEBUG
 184     size_t sizeInMemory();
 185     void checkConsistency();
 186 #endif
 187
 188 private:
 189     PropertyTable(const PropertyTable&);
 190     // Used to insert a value known not to be in the table, and where we know capacity to be available.
 191     void reinsert(const ValueType& entry);
 192
 193     // Rehash the table.  Used to grow, or to recover deleted slots.
 194     void rehash(unsigned newCapacity);
 195
 196     // The capacity of the table of values is half of the size of the index.
 197     unsigned tableCapacity() const;
 198
 199     // We keep an extra deleted slot after the array to make iteration work,
 200     // and to use for deleted values. Index values into the array are 1-based,
 201     // so this is tableCapacity() + 1.
 202     // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the
 203     // values array is actually 9 long (the 9th used for the deleted value/
 204     // iteration guard).  The 8 valid entries are numbered 1..8, so the
 205     // deleted index is 9 (0 being reserved for empty).
 206     unsigned deletedEntryIndex() const;
 207
 208     // Used in iterator creation/progression.
 209     template<typename T>
 210     static T* skipDeletedEntries(T* valuePtr);
 211
 212     // The table of values lies after the hash index.
 213     ValueType* table();
 214     const ValueType* table() const;
 215
 216     // total number of  used entries in the values array - by either valid entries, or deleted ones.
 217     unsigned usedCount() const;
 218
 219     // The size in bytes of data needed for by the table.
 220     size_t dataSize();
 221
 222     // Calculates the appropriate table size (rounds up to a power of two).
 223     static unsigned sizeForCapacity(unsigned capacity);
 224
 225     // Check if capacity is available.
 226     bool canInsert();
 227
 228     unsigned m_indexSize;
 229     unsigned m_indexMask;
 230     unsigned* m_index;
 231     unsigned m_keyCount;
 232     unsigned m_deletedCount;
 233     OwnPtr< Vector<unsigned> > m_deletedOffsets;
 234
 235     static const unsigned MinimumTableSize = 16;
 236     static const unsigned EmptyEntryIndex = 0;
 237 };
 238
 239 inline PropertyTable::PropertyTable(unsigned initialCapacity)
 240     : m_indexSize(sizeForCapacity(initialCapacity))
 241     , m_indexMask(m_indexSize - 1)
 242     , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize())))
 243     , m_keyCount(0)
 244     , m_deletedCount(0)
 245 {
 246     ASSERT(isPowerOf2(m_indexSize));
 247 }
 248
 249 inline PropertyTable::PropertyTable(JSGlobalData&, JSCell* owner, const PropertyTable& other)
 250     : m_indexSize(other.m_indexSize)
 251     , m_indexMask(other.m_indexMask)
 252     , m_index(static_cast<unsigned*>(fastMalloc(dataSize())))
 253     , m_keyCount(other.m_keyCount)
 254     , m_deletedCount(other.m_deletedCount)
 255 {
 256     ASSERT(isPowerOf2(m_indexSize));
 257
 258     memcpy(m_index, other.m_index, dataSize());
 259
 260     iterator end = this->end();
 261     for (iterator iter = begin(); iter != end; ++iter) {
 262         iter->key->ref();
 263         Heap::writeBarrier(owner, iter->specificValue.get());
 264     }
 265
 266     // Copy the m_deletedOffsets vector.
 267     Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
 268     if (otherDeletedOffsets)
 269         m_deletedOffsets = adoptPtr(new Vector<unsigned>(*otherDeletedOffsets));
 270 }
 271
 272 inline PropertyTable::PropertyTable(JSGlobalData&, JSCell* owner, unsigned initialCapacity, const PropertyTable& other)
 273     : m_indexSize(sizeForCapacity(initialCapacity))
 274     , m_indexMask(m_indexSize - 1)
 275     , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize())))
 276     , m_keyCount(0)
 277     , m_deletedCount(0)
 278 {
 279     ASSERT(isPowerOf2(m_indexSize));
 280     ASSERT(initialCapacity >= other.m_keyCount);
 281
 282     const_iterator end = other.end();
 283     for (const_iterator iter = other.begin(); iter != end; ++iter) {
 284         ASSERT(canInsert());
 285         reinsert(*iter);
 286         iter->key->ref();
 287         Heap::writeBarrier(owner, iter->specificValue.get());
 288     }
 289
 290     // Copy the m_deletedOffsets vector.
 291     Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
 292     if (otherDeletedOffsets)
 293         m_deletedOffsets = adoptPtr(new Vector<unsigned>(*otherDeletedOffsets));
 294 }
 295
 296 inline PropertyTable::~PropertyTable()
 297 {
 298     iterator end = this->end();
 299     for (iterator iter = begin(); iter != end; ++iter)
 300         iter->key->deref();
 301
 302     fastFree(m_index);
 303 }
 304
 305 inline PropertyTable::iterator PropertyTable::begin()
 306 {
 307     return iterator(skipDeletedEntries(table()));
 308 }
 309
 310 inline PropertyTable::iterator PropertyTable::end()
 311 {
 312     return iterator(table() + usedCount());
 313 }
 314
 315 inline PropertyTable::const_iterator PropertyTable::begin() const
 316 {
 317     return const_iterator(skipDeletedEntries(table()));
 318 }
 319
 320 inline PropertyTable::const_iterator PropertyTable::end() const
 321 {
 322     return const_iterator(table() + usedCount());
 323 }
 324
 325 inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
 326 {
 327     ASSERT(key);
 328     ASSERT(key->isIdentifier());
 329     unsigned hash = key->existingHash();
 330     unsigned step = 0;
 331
 332 #if DUMP_PROPERTYMAP_STATS
 333     ++numProbes;
 334 #endif
 335
 336     while (true) {
 337         unsigned entryIndex = m_index[hash & m_indexMask];
 338         if (entryIndex == EmptyEntryIndex)
 339             return std::make_pair((ValueType*)0, hash & m_indexMask);
 340         if (key == table()[entryIndex - 1].key)
 341             return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
 342
 343 #if DUMP_PROPERTYMAP_STATS
 344         ++numCollisions;
 345 #endif
 346
 347         if (!step)
 348             step = WTF::doubleHash(key->existingHash()) | 1;
 349         hash += step;
 350
 351 #if DUMP_PROPERTYMAP_STATS
 352         ++numRehashes;
 353 #endif
 354     }
 355 }
 356
 357 inline PropertyTable::find_iterator PropertyTable::findWithString(const KeyType& key)
 358 {
 359     ASSERT(key);
 360     ASSERT(!key->isIdentifier() && !key->hasHash());
 361     unsigned hash = key->hash();
 362     unsigned step = 0;
 363
 364 #if DUMP_PROPERTYMAP_STATS
 365     ++numProbes;
 366 #endif
 367
 368     while (true) {
 369         unsigned entryIndex = m_index[hash & m_indexMask];
 370         if (entryIndex == EmptyEntryIndex)
 371             return std::make_pair((ValueType*)0, hash & m_indexMask);
 372         if (equal(key, table()[entryIndex - 1].key))
 373             return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
 374
 375 #if DUMP_PROPERTYMAP_STATS
 376         ++numCollisions;
 377 #endif
 378
 379         if (!step)
 380             step = WTF::doubleHash(key->existingHash()) | 1;
 381         hash += step;
 382
 383 #if DUMP_PROPERTYMAP_STATS
 384         ++numRehashes;
 385 #endif
 386     }
 387 }
 388
 389 inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry)
 390 {
 391     // Look for a value with a matching key already in the array.
 392     find_iterator iter = find(entry.key);
 393     if (iter.first)
 394         return std::make_pair(iter, false);
 395
 396     // Ref the key
 397     entry.key->ref();
 398
 399     // ensure capacity is available.
 400     if (!canInsert()) {
 401         rehash(m_keyCount + 1);
 402         iter = find(entry.key);
 403         ASSERT(!iter.first);
 404     }
 405
 406     // Allocate a slot in the hashtable, and set the index to reference this.
 407     unsigned entryIndex = usedCount() + 1;
 408     m_index[iter.second] = entryIndex;
 409     iter.first = &table()[entryIndex - 1];
 410     *iter.first = entry;
 411
 412     ++m_keyCount;
 413     return std::make_pair(iter, true);
 414 }
 415
 416 inline void PropertyTable::remove(const find_iterator& iter)
 417 {
 418     // Removing a key that doesn't exist does nothing!
 419     if (!iter.first)
 420         return;
 421
 422 #if DUMP_PROPERTYMAP_STATS
 423     ++numRemoves;
 424 #endif
 425
 426     // Replace this one element with the deleted sentinel. Also clear out
 427     // the entry so we can iterate all the entries as needed.
 428     m_index[iter.second] = deletedEntryIndex();
 429     iter.first->key->deref();
 430     iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY;
 431
 432     ASSERT(m_keyCount >= 1);
 433     --m_keyCount;
 434     ++m_deletedCount;
 435
 436     if (m_deletedCount * 4 >= m_indexSize)
 437         rehash(m_keyCount);
 438 }
 439
 440 inline void PropertyTable::remove(const KeyType& key)
 441 {
 442     remove(find(key));
 443 }
 444
 445 // returns the number of values in the hashtable.
 446 inline unsigned PropertyTable::size() const
 447 {
 448     return m_keyCount;
 449 }
 450
 451 inline bool PropertyTable::isEmpty() const
 452 {
 453     return !m_keyCount;
 454 }
 455
 456 inline unsigned PropertyTable::propertyStorageSize() const
 457 {
 458     return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0);
 459 }
 460
 461 inline void PropertyTable::clearDeletedOffsets()
 462 {
 463     m_deletedOffsets.clear();
 464 }
 465
 466 inline bool PropertyTable::hasDeletedOffset()
 467 {
 468     return m_deletedOffsets && !m_deletedOffsets->isEmpty();
 469 }
 470
 471 inline unsigned PropertyTable::getDeletedOffset()
 472 {
 473     unsigned offset = m_deletedOffsets->last();
 474     m_deletedOffsets->removeLast();
 475     return offset;
 476 }
 477
 478 inline void PropertyTable::addDeletedOffset(unsigned offset)
 479 {
 480     if (!m_deletedOffsets)
 481         m_deletedOffsets = adoptPtr(new Vector<unsigned>);
 482     m_deletedOffsets->append(offset);
 483 }
 484
 485 inline PassOwnPtr<PropertyTable> PropertyTable::copy(JSGlobalData& globalData, JSCell* owner, unsigned newCapacity)
 486 {
 487     ASSERT(newCapacity >= m_keyCount);
 488
 489     // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
 490     // save rehashing all keys.
 491     if (sizeForCapacity(newCapacity) == m_indexSize)
 492         return adoptPtr(new PropertyTable(globalData, owner, *this));
 493     return adoptPtr(new PropertyTable(globalData, owner, newCapacity, *this));
 494 }
 495
 496 #ifndef NDEBUG
 497 inline size_t PropertyTable::sizeInMemory()
 498 {
 499     size_t result = sizeof(PropertyTable) + dataSize();
 500     if (m_deletedOffsets)
 501         result += (m_deletedOffsets->capacity() * sizeof(unsigned));
 502     return result;
 503 }
 504 #endif
 505
 506 inline void PropertyTable::reinsert(const ValueType& entry)
 507 {
 508     // Used to insert a value known not to be in the table, and where
 509     // we know capacity to be available.
 510     ASSERT(canInsert());
 511     find_iterator iter = find(entry.key);
 512     ASSERT(!iter.first);
 513
 514     unsigned entryIndex = usedCount() + 1;
 515     m_index[iter.second] = entryIndex;
 516     table()[entryIndex - 1] = entry;
 517
 518     ++m_keyCount;
 519 }
 520
 521 inline void PropertyTable::rehash(unsigned newCapacity)
 522 {
 523     unsigned* oldEntryIndices = m_index;
 524     iterator iter = this->begin();
 525     iterator end = this->end();
 526
 527     m_indexSize = sizeForCapacity(newCapacity);
 528     m_indexMask = m_indexSize - 1;
 529     m_keyCount = 0;
 530     m_deletedCount = 0;
 531     m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
 532
 533     for (; iter != end; ++iter) {
 534         ASSERT(canInsert());
 535         reinsert(*iter);
 536     }
 537
 538     fastFree(oldEntryIndices);
 539 }
 540
 541 inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; }
 542
 543 inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
 544
 545 template<typename T>
 546 inline T* PropertyTable::skipDeletedEntries(T* valuePtr)
 547 {
 548     while (valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY)
 549         ++valuePtr;
 550     return valuePtr;
 551 }
 552
 553 inline PropertyTable::ValueType* PropertyTable::table()
 554 {
 555     // The table of values lies after the hash index.
 556     return reinterpret_cast<ValueType*>(m_index + m_indexSize);
 557 }
 558
 559 inline const PropertyTable::ValueType* PropertyTable::table() const
 560 {
 561     // The table of values lies after the hash index.
 562     return reinterpret_cast<const ValueType*>(m_index + m_indexSize);
 563 }
 564
 565 inline unsigned PropertyTable::usedCount() const
 566 {
 567     // Total number of  used entries in the values array - by either valid entries, or deleted ones.
 568     return m_keyCount + m_deletedCount;
 569 }
 570
 571 inline size_t PropertyTable::dataSize()
 572 {
 573     // The size in bytes of data needed for by the table.
 574     return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType);
 575 }
 576
 577 inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
 578 {
 579     if (capacity < 8)
 580         return MinimumTableSize;
 581     return nextPowerOf2(capacity + 1) * 2;
 582 }
 583
 584 inline bool PropertyTable::canInsert()
 585 {
 586     return usedCount() < tableCapacity();
 587 }
 588
 589 } // namespace JSC
 590
 591 #endif // PropertyMapHashTable_h