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