runtime/PropertyMapHashTable.h

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