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& key);
 158     // Add a value to the table
 159     std::pair<find_iterator, bool> add(const ValueType& entry);
 160     // Remove a value from the table.
 161     void remove(const find_iterator& iter);
 162     void remove(const KeyType& key);
 163
 164     // Returns the number of values in the hashtable.
 165     unsigned size() const;
 166
 167     // Checks if there are any values in the hashtable.
 168     bool isEmpty() const;
 169
 170     // Number of slots in the property storage array in use, included deletedOffsets.
 171     unsigned propertyStorageSize() const;
 172
 173     // Used to maintain a list of unused entries in the property storage.
 174     void clearDeletedOffsets();
 175     bool hasDeletedOffset();
 176     unsigned getDeletedOffset();
 177     void addDeletedOffset(unsigned offset);
 178
 179     // Copy this PropertyTable, ensuring the copy has at least the capacity provided.
 180     PassOwnPtr<PropertyTable> copy(JSGlobalData&, JSCell* owner, unsigned newCapacity);
 181
 182 #ifndef NDEBUG
 183     size_t sizeInMemory();
 184     void checkConsistency();
 185 #endif
 186
 187 private:
 188     PropertyTable(const PropertyTable&);
 189     // Used to insert a value known not to be in the table, and where we know capacity to be available.
 190     void reinsert(const ValueType& entry);
 191
 192     // Rehash the table.  Used to grow, or to recover deleted slots.
 193     void rehash(unsigned newCapacity);
 194
 195     // The capacity of the table of values is half of the size of the index.
 196     unsigned tableCapacity() const;
 197
 198     // We keep an extra deleted slot after the array to make iteration work,
 199     // and to use for deleted values. Index values into the array are 1-based,
 200     // so this is tableCapacity() + 1.
 201     // For example, if m_tableSize is 16, then tableCapacity() is 8 - but the
 202     // values array is actually 9 long (the 9th used for the deleted value/
 203     // iteration guard).  The 8 valid entries are numbered 1..8, so the
 204     // deleted index is 9 (0 being reserved for empty).
 205     unsigned deletedEntryIndex() const;
 206
 207     // Used in iterator creation/progression.
 208     template<typename T>
 209     static T* skipDeletedEntries(T* valuePtr);
 210
 211     // The table of values lies after the hash index.
 212     ValueType* table();
 213     const ValueType* table() const;
 214
 215     // total number of  used entries in the values array - by either valid entries, or deleted ones.
 216     unsigned usedCount() const;
 217
 218     // The size in bytes of data needed for by the table.
 219     size_t dataSize();
 220
 221     // Calculates the appropriate table size (rounds up to a power of two).
 222     static unsigned sizeForCapacity(unsigned capacity);
 223
 224     // Check if capacity is available.
 225     bool canInsert();
 226
 227     unsigned m_indexSize;
 228     unsigned m_indexMask;
 229     unsigned* m_index;
 230     unsigned m_keyCount;
 231     unsigned m_deletedCount;
 232     OwnPtr< Vector<unsigned> > m_deletedOffsets;
 233
 234     static const unsigned MinimumTableSize = 16;
 235     static const unsigned EmptyEntryIndex = 0;
 236 };
 237
 238 inline PropertyTable::PropertyTable(unsigned initialCapacity)
 239     : m_indexSize(sizeForCapacity(initialCapacity))
 240     , m_indexMask(m_indexSize - 1)
 241     , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize())))
 242     , m_keyCount(0)
 243     , m_deletedCount(0)
 244 {
 245     ASSERT(isPowerOf2(m_indexSize));
 246 }
 247
 248 inline PropertyTable::PropertyTable(JSGlobalData&, JSCell* owner, const PropertyTable& other)
 249     : m_indexSize(other.m_indexSize)
 250     , m_indexMask(other.m_indexMask)
 251     , m_index(static_cast<unsigned*>(fastMalloc(dataSize())))
 252     , m_keyCount(other.m_keyCount)
 253     , m_deletedCount(other.m_deletedCount)
 254 {
 255     ASSERT(isPowerOf2(m_indexSize));
 256
 257     memcpy(m_index, other.m_index, dataSize());
 258
 259     iterator end = this->end();
 260     for (iterator iter = begin(); iter != end; ++iter) {
 261         iter->key->ref();
 262         Heap::writeBarrier(owner, iter->specificValue.get());
 263     }
 264
 265     // Copy the m_deletedOffsets vector.
 266     Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
 267     if (otherDeletedOffsets)
 268         m_deletedOffsets = adoptPtr(new Vector<unsigned>(*otherDeletedOffsets));
 269 }
 270
 271 inline PropertyTable::PropertyTable(JSGlobalData&, JSCell* owner, unsigned initialCapacity, const PropertyTable& other)
 272     : m_indexSize(sizeForCapacity(initialCapacity))
 273     , m_indexMask(m_indexSize - 1)
 274     , m_index(static_cast<unsigned*>(fastZeroedMalloc(dataSize())))
 275     , m_keyCount(0)
 276     , m_deletedCount(0)
 277 {
 278     ASSERT(isPowerOf2(m_indexSize));
 279     ASSERT(initialCapacity >= other.m_keyCount);
 280
 281     const_iterator end = other.end();
 282     for (const_iterator iter = other.begin(); iter != end; ++iter) {
 283         ASSERT(canInsert());
 284         reinsert(*iter);
 285         iter->key->ref();
 286         Heap::writeBarrier(owner, iter->specificValue.get());
 287     }
 288
 289     // Copy the m_deletedOffsets vector.
 290     Vector<unsigned>* otherDeletedOffsets = other.m_deletedOffsets.get();
 291     if (otherDeletedOffsets)
 292         m_deletedOffsets = adoptPtr(new Vector<unsigned>(*otherDeletedOffsets));
 293 }
 294
 295 inline PropertyTable::~PropertyTable()
 296 {
 297     iterator end = this->end();
 298     for (iterator iter = begin(); iter != end; ++iter)
 299         iter->key->deref();
 300
 301     fastFree(m_index);
 302 }
 303
 304 inline PropertyTable::iterator PropertyTable::begin()
 305 {
 306     return iterator(skipDeletedEntries(table()));
 307 }
 308
 309 inline PropertyTable::iterator PropertyTable::end()
 310 {
 311     return iterator(table() + usedCount());
 312 }
 313
 314 inline PropertyTable::const_iterator PropertyTable::begin() const
 315 {
 316     return const_iterator(skipDeletedEntries(table()));
 317 }
 318
 319 inline PropertyTable::const_iterator PropertyTable::end() const
 320 {
 321     return const_iterator(table() + usedCount());
 322 }
 323
 324 inline PropertyTable::find_iterator PropertyTable::find(const KeyType& key)
 325 {
 326     ASSERT(key);
 327     unsigned hash = key->existingHash();
 328     unsigned step = 0;
 329
 330 #if DUMP_PROPERTYMAP_STATS
 331     ++numProbes;
 332 #endif
 333
 334     while (true) {
 335         unsigned entryIndex = m_index[hash & m_indexMask];
 336         if (entryIndex == EmptyEntryIndex)
 337             return std::make_pair((ValueType*)0, hash & m_indexMask);
 338         if (key == table()[entryIndex - 1].key)
 339             return std::make_pair(&table()[entryIndex - 1], hash & m_indexMask);
 340
 341 #if DUMP_PROPERTYMAP_STATS
 342         ++numCollisions;
 343 #endif
 344
 345         if (!step)
 346             step =WTF::doubleHash(key->existingHash()) | 1;
 347         hash += step;
 348
 349 #if DUMP_PROPERTYMAP_STATS
 350         ++numRehashes;
 351 #endif
 352     }
 353 }
 354
 355 inline std::pair<PropertyTable::find_iterator, bool> PropertyTable::add(const ValueType& entry)
 356 {
 357     // Look for a value with a matching key already in the array.
 358     find_iterator iter = find(entry.key);
 359     if (iter.first)
 360         return std::make_pair(iter, false);
 361
 362     // Ref the key
 363     entry.key->ref();
 364
 365     // ensure capacity is available.
 366     if (!canInsert()) {
 367         rehash(m_keyCount + 1);
 368         iter = find(entry.key);
 369         ASSERT(!iter.first);
 370     }
 371
 372     // Allocate a slot in the hashtable, and set the index to reference this.
 373     unsigned entryIndex = usedCount() + 1;
 374     m_index[iter.second] = entryIndex;
 375     iter.first = &table()[entryIndex - 1];
 376     *iter.first = entry;
 377
 378     ++m_keyCount;
 379     return std::make_pair(iter, true);
 380 }
 381
 382 inline void PropertyTable::remove(const find_iterator& iter)
 383 {
 384     // Removing a key that doesn't exist does nothing!
 385     if (!iter.first)
 386         return;
 387
 388 #if DUMP_PROPERTYMAP_STATS
 389     ++numRemoves;
 390 #endif
 391
 392     // Replace this one element with the deleted sentinel. Also clear out
 393     // the entry so we can iterate all the entries as needed.
 394     m_index[iter.second] = deletedEntryIndex();
 395     iter.first->key->deref();
 396     iter.first->key = PROPERTY_MAP_DELETED_ENTRY_KEY;
 397
 398     ASSERT(m_keyCount >= 1);
 399     --m_keyCount;
 400     ++m_deletedCount;
 401
 402     if (m_deletedCount * 4 >= m_indexSize)
 403         rehash(m_keyCount);
 404 }
 405
 406 inline void PropertyTable::remove(const KeyType& key)
 407 {
 408     remove(find(key));
 409 }
 410
 411 // returns the number of values in the hashtable.
 412 inline unsigned PropertyTable::size() const
 413 {
 414     return m_keyCount;
 415 }
 416
 417 inline bool PropertyTable::isEmpty() const
 418 {
 419     return !m_keyCount;
 420 }
 421
 422 inline unsigned PropertyTable::propertyStorageSize() const
 423 {
 424     return size() + (m_deletedOffsets ? m_deletedOffsets->size() : 0);
 425 }
 426
 427 inline void PropertyTable::clearDeletedOffsets()
 428 {
 429     m_deletedOffsets.clear();
 430 }
 431
 432 inline bool PropertyTable::hasDeletedOffset()
 433 {
 434     return m_deletedOffsets && !m_deletedOffsets->isEmpty();
 435 }
 436
 437 inline unsigned PropertyTable::getDeletedOffset()
 438 {
 439     unsigned offset = m_deletedOffsets->last();
 440     m_deletedOffsets->removeLast();
 441     return offset;
 442 }
 443
 444 inline void PropertyTable::addDeletedOffset(unsigned offset)
 445 {
 446     if (!m_deletedOffsets)
 447         m_deletedOffsets = adoptPtr(new Vector<unsigned>);
 448     m_deletedOffsets->append(offset);
 449 }
 450
 451 inline PassOwnPtr<PropertyTable> PropertyTable::copy(JSGlobalData& globalData, JSCell* owner, unsigned newCapacity)
 452 {
 453     ASSERT(newCapacity >= m_keyCount);
 454
 455     // Fast case; if the new table will be the same m_indexSize as this one, we can memcpy it,
 456     // save rehashing all keys.
 457     if (sizeForCapacity(newCapacity) == m_indexSize)
 458         return adoptPtr(new PropertyTable(globalData, owner, *this));
 459     return adoptPtr(new PropertyTable(globalData, owner, newCapacity, *this));
 460 }
 461
 462 #ifndef NDEBUG
 463 inline size_t PropertyTable::sizeInMemory()
 464 {
 465     size_t result = sizeof(PropertyTable) + dataSize();
 466     if (m_deletedOffsets)
 467         result += (m_deletedOffsets->capacity() * sizeof(unsigned));
 468     return result;
 469 }
 470 #endif
 471
 472 inline void PropertyTable::reinsert(const ValueType& entry)
 473 {
 474     // Used to insert a value known not to be in the table, and where
 475     // we know capacity to be available.
 476     ASSERT(canInsert());
 477     find_iterator iter = find(entry.key);
 478     ASSERT(!iter.first);
 479
 480     unsigned entryIndex = usedCount() + 1;
 481     m_index[iter.second] = entryIndex;
 482     table()[entryIndex - 1] = entry;
 483
 484     ++m_keyCount;
 485 }
 486
 487 inline void PropertyTable::rehash(unsigned newCapacity)
 488 {
 489     unsigned* oldEntryIndices = m_index;
 490     iterator iter = this->begin();
 491     iterator end = this->end();
 492
 493     m_indexSize = sizeForCapacity(newCapacity);
 494     m_indexMask = m_indexSize - 1;
 495     m_keyCount = 0;
 496     m_deletedCount = 0;
 497     m_index = static_cast<unsigned*>(fastZeroedMalloc(dataSize()));
 498
 499     for (; iter != end; ++iter) {
 500         ASSERT(canInsert());
 501         reinsert(*iter);
 502     }
 503
 504     fastFree(oldEntryIndices);
 505 }
 506
 507 inline unsigned PropertyTable::tableCapacity() const { return m_indexSize >> 1; }
 508
 509 inline unsigned PropertyTable::deletedEntryIndex() const { return tableCapacity() + 1; }
 510
 511 template<typename T>
 512 inline T* PropertyTable::skipDeletedEntries(T* valuePtr)
 513 {
 514     while (valuePtr->key == PROPERTY_MAP_DELETED_ENTRY_KEY)
 515         ++valuePtr;
 516     return valuePtr;
 517 }
 518
 519 inline PropertyTable::ValueType* PropertyTable::table()
 520 {
 521     // The table of values lies after the hash index.
 522     return reinterpret_cast<ValueType*>(m_index + m_indexSize);
 523 }
 524
 525 inline const PropertyTable::ValueType* PropertyTable::table() const
 526 {
 527     // The table of values lies after the hash index.
 528     return reinterpret_cast<const ValueType*>(m_index + m_indexSize);
 529 }
 530
 531 inline unsigned PropertyTable::usedCount() const
 532 {
 533     // Total number of  used entries in the values array - by either valid entries, or deleted ones.
 534     return m_keyCount + m_deletedCount;
 535 }
 536
 537 inline size_t PropertyTable::dataSize()
 538 {
 539     // The size in bytes of data needed for by the table.
 540     return m_indexSize * sizeof(unsigned) + ((tableCapacity()) + 1) * sizeof(ValueType);
 541 }
 542
 543 inline unsigned PropertyTable::sizeForCapacity(unsigned capacity)
 544 {
 545     if (capacity < 8)
 546         return MinimumTableSize;
 547     return nextPowerOf2(capacity + 1) * 2;
 548 }
 549
 550 inline bool PropertyTable::canInsert()
 551 {
 552     return usedCount() < tableCapacity();
 553 }
 554
 555 } // namespace JSC
 556
 557 #endif // PropertyMapHashTable_h