michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- michael@0: * vim: set ts=8 sts=4 et sw=4 tw=99: michael@0: * This Source Code Form is subject to the terms of the Mozilla Public michael@0: * License, v. 2.0. If a copy of the MPL was not distributed with this michael@0: * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ michael@0: michael@0: #include "builtin/MapObject.h" michael@0: michael@0: #include "mozilla/Move.h" michael@0: michael@0: #include "jscntxt.h" michael@0: #include "jsiter.h" michael@0: #include "jsobj.h" michael@0: michael@0: #include "gc/Marking.h" michael@0: #include "js/Utility.h" michael@0: #include "vm/GlobalObject.h" michael@0: #include "vm/Interpreter.h" michael@0: michael@0: #include "jsobjinlines.h" michael@0: michael@0: using namespace js; michael@0: michael@0: using mozilla::NumberEqualsInt32; michael@0: using mozilla::Forward; michael@0: using mozilla::IsNaN; michael@0: using mozilla::Move; michael@0: using mozilla::ArrayLength; michael@0: using JS::DoubleNaNValue; michael@0: using JS::ForOfIterator; michael@0: michael@0: michael@0: /*** OrderedHashTable ****************************************************************************/ michael@0: michael@0: /* michael@0: * Define two collection templates, js::OrderedHashMap and js::OrderedHashSet. michael@0: * They are like js::HashMap and js::HashSet except that: michael@0: * michael@0: * - Iterating over an Ordered hash table visits the entries in the order in michael@0: * which they were inserted. This means that unlike a HashMap, the behavior michael@0: * of an OrderedHashMap is deterministic (as long as the HashPolicy methods michael@0: * are effect-free and consistent); the hashing is a pure performance michael@0: * optimization. michael@0: * michael@0: * - Range objects over Ordered tables remain valid even when entries are michael@0: * added or removed or the table is resized. (However in the case of michael@0: * removing entries, note the warning on class Range below.) michael@0: * michael@0: * - The API is a little different, so it's not a drop-in replacement. michael@0: * In particular, the hash policy is a little different. michael@0: * Also, the Ordered templates lack the Ptr and AddPtr types. michael@0: * michael@0: * Hash policies michael@0: * michael@0: * See the comment about "Hash policy" in HashTable.h for general features that michael@0: * hash policy classes must provide. Hash policies for OrderedHashMaps and Sets michael@0: * must additionally provide a distinguished "empty" key value and the michael@0: * following static member functions: michael@0: * bool isEmpty(const Key &); michael@0: * void makeEmpty(Key *); michael@0: */ michael@0: michael@0: namespace js { michael@0: michael@0: namespace detail { michael@0: michael@0: /* michael@0: * detail::OrderedHashTable is the underlying data structure used to implement both michael@0: * OrderedHashMap and OrderedHashSet. Programs should use one of those two michael@0: * templates rather than OrderedHashTable. michael@0: */ michael@0: template michael@0: class OrderedHashTable michael@0: { michael@0: public: michael@0: typedef typename Ops::KeyType Key; michael@0: typedef typename Ops::Lookup Lookup; michael@0: michael@0: struct Data michael@0: { michael@0: T element; michael@0: Data *chain; michael@0: michael@0: Data(const T &e, Data *c) : element(e), chain(c) {} michael@0: Data(T &&e, Data *c) : element(Move(e)), chain(c) {} michael@0: }; michael@0: michael@0: class Range; michael@0: friend class Range; michael@0: michael@0: private: michael@0: Data **hashTable; // hash table (has hashBuckets() elements) michael@0: Data *data; // data vector, an array of Data objects michael@0: // data[0:dataLength] are constructed michael@0: uint32_t dataLength; // number of constructed elements in data michael@0: uint32_t dataCapacity; // size of data, in elements michael@0: uint32_t liveCount; // dataLength less empty (removed) entries michael@0: uint32_t hashShift; // multiplicative hash shift michael@0: Range *ranges; // list of all live Ranges on this table michael@0: AllocPolicy alloc; michael@0: michael@0: public: michael@0: OrderedHashTable(AllocPolicy &ap) michael@0: : hashTable(nullptr), data(nullptr), dataLength(0), ranges(nullptr), alloc(ap) {} michael@0: michael@0: bool init() { michael@0: MOZ_ASSERT(!hashTable, "init must be called at most once"); michael@0: michael@0: uint32_t buckets = initialBuckets(); michael@0: Data **tableAlloc = static_cast(alloc.malloc_(buckets * sizeof(Data *))); michael@0: if (!tableAlloc) michael@0: return false; michael@0: for (uint32_t i = 0; i < buckets; i++) michael@0: tableAlloc[i] = nullptr; michael@0: michael@0: uint32_t capacity = uint32_t(buckets * fillFactor()); michael@0: Data *dataAlloc = static_cast(alloc.malloc_(capacity * sizeof(Data))); michael@0: if (!dataAlloc) { michael@0: alloc.free_(tableAlloc); michael@0: return false; michael@0: } michael@0: michael@0: // clear() requires that members are assigned only after all allocation michael@0: // has succeeded, and that this->ranges is left untouched. michael@0: hashTable = tableAlloc; michael@0: data = dataAlloc; michael@0: dataLength = 0; michael@0: dataCapacity = capacity; michael@0: liveCount = 0; michael@0: hashShift = HashNumberSizeBits - initialBucketsLog2(); michael@0: MOZ_ASSERT(hashBuckets() == buckets); michael@0: return true; michael@0: } michael@0: michael@0: ~OrderedHashTable() { michael@0: for (Range *r = ranges, *next; r; r = next) { michael@0: next = r->next; michael@0: r->onTableDestroyed(); michael@0: } michael@0: alloc.free_(hashTable); michael@0: freeData(data, dataLength); michael@0: } michael@0: michael@0: /* Return the number of elements in the table. */ michael@0: uint32_t count() const { return liveCount; } michael@0: michael@0: /* True if any element matches l. */ michael@0: bool has(const Lookup &l) const { michael@0: return lookup(l) != nullptr; michael@0: } michael@0: michael@0: /* Return a pointer to the element, if any, that matches l, or nullptr. */ michael@0: T *get(const Lookup &l) { michael@0: Data *e = lookup(l, prepareHash(l)); michael@0: return e ? &e->element : nullptr; michael@0: } michael@0: michael@0: /* Return a pointer to the element, if any, that matches l, or nullptr. */ michael@0: const T *get(const Lookup &l) const { michael@0: return const_cast(this)->get(l); michael@0: } michael@0: michael@0: /* michael@0: * If the table already contains an entry that matches |element|, michael@0: * replace that entry with |element|. Otherwise add a new entry. michael@0: * michael@0: * On success, return true, whether there was already a matching element or michael@0: * not. On allocation failure, return false. If this returns false, it michael@0: * means the element was not added to the table. michael@0: */ michael@0: template michael@0: bool put(ElementInput &&element) { michael@0: HashNumber h = prepareHash(Ops::getKey(element)); michael@0: if (Data *e = lookup(Ops::getKey(element), h)) { michael@0: e->element = Forward(element); michael@0: return true; michael@0: } michael@0: michael@0: if (dataLength == dataCapacity) { michael@0: // If the hashTable is more than 1/4 deleted data, simply rehash in michael@0: // place to free up some space. Otherwise, grow the table. michael@0: uint32_t newHashShift = liveCount >= dataCapacity * 0.75 ? hashShift - 1 : hashShift; michael@0: if (!rehash(newHashShift)) michael@0: return false; michael@0: } michael@0: michael@0: h >>= hashShift; michael@0: liveCount++; michael@0: Data *e = &data[dataLength++]; michael@0: new (e) Data(Forward(element), hashTable[h]); michael@0: hashTable[h] = e; michael@0: return true; michael@0: } michael@0: michael@0: /* michael@0: * If the table contains an element matching l, remove it and set *foundp michael@0: * to true. Otherwise set *foundp to false. michael@0: * michael@0: * Return true on success, false if we tried to shrink the table and hit an michael@0: * allocation failure. Even if this returns false, *foundp is set correctly michael@0: * and the matching element was removed. Shrinking is an optimization and michael@0: * it's OK for it to fail. michael@0: */ michael@0: bool remove(const Lookup &l, bool *foundp) { michael@0: // Note: This could be optimized so that removing the last entry, michael@0: // data[dataLength - 1], decrements dataLength. LIFO use cases would michael@0: // benefit. michael@0: michael@0: // If a matching entry exists, empty it. michael@0: Data *e = lookup(l, prepareHash(l)); michael@0: if (e == nullptr) { michael@0: *foundp = false; michael@0: return true; michael@0: } michael@0: michael@0: *foundp = true; michael@0: liveCount--; michael@0: Ops::makeEmpty(&e->element); michael@0: michael@0: // Update active Ranges. michael@0: uint32_t pos = e - data; michael@0: for (Range *r = ranges; r; r = r->next) michael@0: r->onRemove(pos); michael@0: michael@0: // If many entries have been removed, try to shrink the table. michael@0: if (hashBuckets() > initialBuckets() && liveCount < dataLength * minDataFill()) { michael@0: if (!rehash(hashShift + 1)) michael@0: return false; michael@0: } michael@0: return true; michael@0: } michael@0: michael@0: /* michael@0: * Remove all entries. michael@0: * michael@0: * Returns false on OOM, leaving the OrderedHashTable and any live Ranges michael@0: * in the old state. michael@0: * michael@0: * The effect on live Ranges is the same as removing all entries; in michael@0: * particular, those Ranges are still live and will see any entries added michael@0: * after a successful clear(). michael@0: */ michael@0: bool clear() { michael@0: if (dataLength != 0) { michael@0: Data **oldHashTable = hashTable; michael@0: Data *oldData = data; michael@0: uint32_t oldDataLength = dataLength; michael@0: michael@0: hashTable = nullptr; michael@0: if (!init()) { michael@0: // init() only mutates members on success; see comment above. michael@0: hashTable = oldHashTable; michael@0: return false; michael@0: } michael@0: michael@0: alloc.free_(oldHashTable); michael@0: freeData(oldData, oldDataLength); michael@0: for (Range *r = ranges; r; r = r->next) michael@0: r->onClear(); michael@0: } michael@0: michael@0: MOZ_ASSERT(hashTable); michael@0: MOZ_ASSERT(data); michael@0: MOZ_ASSERT(dataLength == 0); michael@0: MOZ_ASSERT(liveCount == 0); michael@0: return true; michael@0: } michael@0: michael@0: /* michael@0: * Ranges are used to iterate over OrderedHashTables. michael@0: * michael@0: * Suppose 'Map' is some instance of OrderedHashMap, and 'map' is a Map. michael@0: * Then you can walk all the key-value pairs like this: michael@0: * michael@0: * for (Map::Range r = map.all(); !r.empty(); r.popFront()) { michael@0: * Map::Entry &pair = r.front(); michael@0: * ... do something with pair ... michael@0: * } michael@0: * michael@0: * Ranges remain valid for the lifetime of the OrderedHashTable, even if michael@0: * entries are added or removed or the table is resized. Don't do anything michael@0: * to a Range, except destroy it, after the OrderedHashTable has been michael@0: * destroyed. (We support destroying the two objects in either order to michael@0: * humor the GC, bless its nondeterministic heart.) michael@0: * michael@0: * Warning: The behavior when the current front() entry is removed from the michael@0: * table is subtly different from js::HashTable<>::Enum::removeFront()! michael@0: * HashTable::Enum doesn't skip any entries when you removeFront() and then michael@0: * popFront(). OrderedHashTable::Range does! (This is useful for using a michael@0: * Range to implement JS Map.prototype.iterator.) michael@0: * michael@0: * The workaround is to call popFront() as soon as possible, michael@0: * before there's any possibility of modifying the table: michael@0: * michael@0: * for (Map::Range r = map.all(); !r.empty(); ) { michael@0: * Key key = r.front().key; // this won't modify map michael@0: * Value val = r.front().value; // this won't modify map michael@0: * r.popFront(); michael@0: * // ...do things that might modify map... michael@0: * } michael@0: */ michael@0: class Range michael@0: { michael@0: friend class OrderedHashTable; michael@0: michael@0: OrderedHashTable &ht; michael@0: michael@0: /* The index of front() within ht.data. */ michael@0: uint32_t i; michael@0: michael@0: /* michael@0: * The number of nonempty entries in ht.data to the left of front(). michael@0: * This is used when the table is resized or compacted. michael@0: */ michael@0: uint32_t count; michael@0: michael@0: /* michael@0: * Links in the doubly-linked list of active Ranges on ht. michael@0: * michael@0: * prevp points to the previous Range's .next field; michael@0: * or to ht.ranges if this is the first Range in the list. michael@0: * next points to the next Range; michael@0: * or nullptr if this is the last Range in the list. michael@0: * michael@0: * Invariant: *prevp == this. michael@0: */ michael@0: Range **prevp; michael@0: Range *next; michael@0: michael@0: /* michael@0: * Create a Range over all the entries in ht. michael@0: * (This is private on purpose. End users must use ht.all().) michael@0: */ michael@0: Range(OrderedHashTable &ht) : ht(ht), i(0), count(0), prevp(&ht.ranges), next(ht.ranges) { michael@0: *prevp = this; michael@0: if (next) michael@0: next->prevp = &next; michael@0: seek(); michael@0: } michael@0: michael@0: public: michael@0: Range(const Range &other) michael@0: : ht(other.ht), i(other.i), count(other.count), prevp(&ht.ranges), next(ht.ranges) michael@0: { michael@0: *prevp = this; michael@0: if (next) michael@0: next->prevp = &next; michael@0: } michael@0: michael@0: ~Range() { michael@0: *prevp = next; michael@0: if (next) michael@0: next->prevp = prevp; michael@0: } michael@0: michael@0: private: michael@0: // Prohibit copy assignment. michael@0: Range &operator=(const Range &other) MOZ_DELETE; michael@0: michael@0: void seek() { michael@0: while (i < ht.dataLength && Ops::isEmpty(Ops::getKey(ht.data[i].element))) michael@0: i++; michael@0: } michael@0: michael@0: /* michael@0: * The hash table calls this when an entry is removed. michael@0: * j is the index of the removed entry. michael@0: */ michael@0: void onRemove(uint32_t j) { michael@0: MOZ_ASSERT(valid()); michael@0: if (j < i) michael@0: count--; michael@0: if (j == i) michael@0: seek(); michael@0: } michael@0: michael@0: /* michael@0: * The hash table calls this when the table is resized or compacted. michael@0: * Since |count| is the number of nonempty entries to the left of michael@0: * front(), discarding the empty entries will not affect count, and it michael@0: * will make i and count equal. michael@0: */ michael@0: void onCompact() { michael@0: MOZ_ASSERT(valid()); michael@0: i = count; michael@0: } michael@0: michael@0: /* The hash table calls this when cleared. */ michael@0: void onClear() { michael@0: MOZ_ASSERT(valid()); michael@0: i = count = 0; michael@0: } michael@0: michael@0: bool valid() const { michael@0: return next != this; michael@0: } michael@0: michael@0: void onTableDestroyed() { michael@0: MOZ_ASSERT(valid()); michael@0: prevp = &next; michael@0: next = this; michael@0: } michael@0: michael@0: public: michael@0: bool empty() const { michael@0: MOZ_ASSERT(valid()); michael@0: return i >= ht.dataLength; michael@0: } michael@0: michael@0: /* michael@0: * Return the first element in the range. This must not be called if michael@0: * this->empty(). michael@0: * michael@0: * Warning: Removing an entry from the table also removes it from any michael@0: * live Ranges, and a Range can become empty that way, rendering michael@0: * front() invalid. If in doubt, check empty() before calling front(). michael@0: */ michael@0: T &front() { michael@0: MOZ_ASSERT(valid()); michael@0: MOZ_ASSERT(!empty()); michael@0: return ht.data[i].element; michael@0: } michael@0: michael@0: /* michael@0: * Remove the first element from this range. michael@0: * This must not be called if this->empty(). michael@0: * michael@0: * Warning: Removing an entry from the table also removes it from any michael@0: * live Ranges, and a Range can become empty that way, rendering michael@0: * popFront() invalid. If in doubt, check empty() before calling michael@0: * popFront(). michael@0: */ michael@0: void popFront() { michael@0: MOZ_ASSERT(valid()); michael@0: MOZ_ASSERT(!empty()); michael@0: MOZ_ASSERT(!Ops::isEmpty(Ops::getKey(ht.data[i].element))); michael@0: count++; michael@0: i++; michael@0: seek(); michael@0: } michael@0: michael@0: /* michael@0: * Change the key of the front entry. michael@0: * michael@0: * This calls Ops::hash on both the current key and the new key. michael@0: * Ops::hash on the current key must return the same hash code as michael@0: * when the entry was added to the table. michael@0: */ michael@0: void rekeyFront(const Key &k) { michael@0: MOZ_ASSERT(valid()); michael@0: Data &entry = ht.data[i]; michael@0: HashNumber oldHash = prepareHash(Ops::getKey(entry.element)) >> ht.hashShift; michael@0: HashNumber newHash = prepareHash(k) >> ht.hashShift; michael@0: Ops::setKey(entry.element, k); michael@0: if (newHash != oldHash) { michael@0: // Remove this entry from its old hash chain. (If this crashes michael@0: // reading nullptr, it would mean we did not find this entry on michael@0: // the hash chain where we expected it. That probably means the michael@0: // key's hash code changed since it was inserted, breaking the michael@0: // hash code invariant.) michael@0: Data **ep = &ht.hashTable[oldHash]; michael@0: while (*ep != &entry) michael@0: ep = &(*ep)->chain; michael@0: *ep = entry.chain; michael@0: michael@0: // Add it to the new hash chain. We could just insert it at the michael@0: // beginning of the chain. Instead, we do a bit of work to michael@0: // preserve the invariant that hash chains always go in reverse michael@0: // insertion order (descending memory order). No code currently michael@0: // depends on this invariant, so it's fine to kill it if michael@0: // needed. michael@0: ep = &ht.hashTable[newHash]; michael@0: while (*ep && *ep > &entry) michael@0: ep = &(*ep)->chain; michael@0: entry.chain = *ep; michael@0: *ep = &entry; michael@0: } michael@0: } michael@0: }; michael@0: michael@0: Range all() { return Range(*this); } michael@0: michael@0: /* michael@0: * Change the value of the given key. michael@0: * michael@0: * This calls Ops::hash on both the current key and the new key. michael@0: * Ops::hash on the current key must return the same hash code as michael@0: * when the entry was added to the table. michael@0: */ michael@0: void rekeyOneEntry(const Key ¤t, const Key &newKey, const T &element) { michael@0: if (current == newKey) michael@0: return; michael@0: michael@0: Data *entry = lookup(current, prepareHash(current)); michael@0: if (!entry) michael@0: return; michael@0: michael@0: HashNumber oldHash = prepareHash(current) >> hashShift; michael@0: HashNumber newHash = prepareHash(newKey) >> hashShift; michael@0: michael@0: entry->element = element; michael@0: michael@0: // Remove this entry from its old hash chain. (If this crashes michael@0: // reading nullptr, it would mean we did not find this entry on michael@0: // the hash chain where we expected it. That probably means the michael@0: // key's hash code changed since it was inserted, breaking the michael@0: // hash code invariant.) michael@0: Data **ep = &hashTable[oldHash]; michael@0: while (*ep != entry) michael@0: ep = &(*ep)->chain; michael@0: *ep = entry->chain; michael@0: michael@0: // Add it to the new hash chain. We could just insert it at the michael@0: // beginning of the chain. Instead, we do a bit of work to michael@0: // preserve the invariant that hash chains always go in reverse michael@0: // insertion order (descending memory order). No code currently michael@0: // depends on this invariant, so it's fine to kill it if michael@0: // needed. michael@0: ep = &hashTable[newHash]; michael@0: while (*ep && *ep > entry) michael@0: ep = &(*ep)->chain; michael@0: entry->chain = *ep; michael@0: *ep = entry; michael@0: } michael@0: michael@0: private: michael@0: /* Logarithm base 2 of the number of buckets in the hash table initially. */ michael@0: static uint32_t initialBucketsLog2() { return 1; } michael@0: static uint32_t initialBuckets() { return 1 << initialBucketsLog2(); } michael@0: michael@0: /* michael@0: * The maximum load factor (mean number of entries per bucket). michael@0: * It is an invariant that michael@0: * dataCapacity == floor(hashBuckets() * fillFactor()). michael@0: * michael@0: * The fill factor should be between 2 and 4, and it should be chosen so that michael@0: * the fill factor times sizeof(Data) is close to but <= a power of 2. michael@0: * This fixed fill factor was chosen to make the size of the data michael@0: * array, in bytes, close to a power of two when sizeof(T) is 16. michael@0: */ michael@0: static double fillFactor() { return 8.0 / 3.0; } michael@0: michael@0: /* michael@0: * The minimum permitted value of (liveCount / dataLength). michael@0: * If that ratio drops below this value, we shrink the table. michael@0: */ michael@0: static double minDataFill() { return 0.25; } michael@0: michael@0: static HashNumber prepareHash(const Lookup &l) { michael@0: return ScrambleHashCode(Ops::hash(l)); michael@0: } michael@0: michael@0: /* The size of hashTable, in elements. Always a power of two. */ michael@0: uint32_t hashBuckets() const { michael@0: return 1 << (HashNumberSizeBits - hashShift); michael@0: } michael@0: michael@0: static void destroyData(Data *data, uint32_t length) { michael@0: for (Data *p = data + length; p != data; ) michael@0: (--p)->~Data(); michael@0: } michael@0: michael@0: void freeData(Data *data, uint32_t length) { michael@0: destroyData(data, length); michael@0: alloc.free_(data); michael@0: } michael@0: michael@0: Data *lookup(const Lookup &l, HashNumber h) { michael@0: for (Data *e = hashTable[h >> hashShift]; e; e = e->chain) { michael@0: if (Ops::match(Ops::getKey(e->element), l)) michael@0: return e; michael@0: } michael@0: return nullptr; michael@0: } michael@0: michael@0: const Data *lookup(const Lookup &l) const { michael@0: return const_cast(this)->lookup(l, prepareHash(l)); michael@0: } michael@0: michael@0: /* This is called after rehashing the table. */ michael@0: void compacted() { michael@0: // If we had any empty entries, compacting may have moved live entries michael@0: // to the left within |data|. Notify all live Ranges of the change. michael@0: for (Range *r = ranges; r; r = r->next) michael@0: r->onCompact(); michael@0: } michael@0: michael@0: /* Compact the entries in |data| and rehash them. */ michael@0: void rehashInPlace() { michael@0: for (uint32_t i = 0, N = hashBuckets(); i < N; i++) michael@0: hashTable[i] = nullptr; michael@0: Data *wp = data, *end = data + dataLength; michael@0: for (Data *rp = data; rp != end; rp++) { michael@0: if (!Ops::isEmpty(Ops::getKey(rp->element))) { michael@0: HashNumber h = prepareHash(Ops::getKey(rp->element)) >> hashShift; michael@0: if (rp != wp) michael@0: wp->element = Move(rp->element); michael@0: wp->chain = hashTable[h]; michael@0: hashTable[h] = wp; michael@0: wp++; michael@0: } michael@0: } michael@0: MOZ_ASSERT(wp == data + liveCount); michael@0: michael@0: while (wp != end) michael@0: (--end)->~Data(); michael@0: dataLength = liveCount; michael@0: compacted(); michael@0: } michael@0: michael@0: /* michael@0: * Grow, shrink, or compact both |hashTable| and |data|. michael@0: * michael@0: * On success, this returns true, dataLength == liveCount, and there are no michael@0: * empty elements in data[0:dataLength]. On allocation failure, this michael@0: * leaves everything as it was and returns false. michael@0: */ michael@0: bool rehash(uint32_t newHashShift) { michael@0: // If the size of the table is not changing, rehash in place to avoid michael@0: // allocating memory. michael@0: if (newHashShift == hashShift) { michael@0: rehashInPlace(); michael@0: return true; michael@0: } michael@0: michael@0: size_t newHashBuckets = 1 << (HashNumberSizeBits - newHashShift); michael@0: Data **newHashTable = static_cast(alloc.malloc_(newHashBuckets * sizeof(Data *))); michael@0: if (!newHashTable) michael@0: return false; michael@0: for (uint32_t i = 0; i < newHashBuckets; i++) michael@0: newHashTable[i] = nullptr; michael@0: michael@0: uint32_t newCapacity = uint32_t(newHashBuckets * fillFactor()); michael@0: Data *newData = static_cast(alloc.malloc_(newCapacity * sizeof(Data))); michael@0: if (!newData) { michael@0: alloc.free_(newHashTable); michael@0: return false; michael@0: } michael@0: michael@0: Data *wp = newData; michael@0: for (Data *p = data, *end = data + dataLength; p != end; p++) { michael@0: if (!Ops::isEmpty(Ops::getKey(p->element))) { michael@0: HashNumber h = prepareHash(Ops::getKey(p->element)) >> newHashShift; michael@0: new (wp) Data(Move(p->element), newHashTable[h]); michael@0: newHashTable[h] = wp; michael@0: wp++; michael@0: } michael@0: } michael@0: MOZ_ASSERT(wp == newData + liveCount); michael@0: michael@0: alloc.free_(hashTable); michael@0: freeData(data, dataLength); michael@0: michael@0: hashTable = newHashTable; michael@0: data = newData; michael@0: dataLength = liveCount; michael@0: dataCapacity = newCapacity; michael@0: hashShift = newHashShift; michael@0: MOZ_ASSERT(hashBuckets() == newHashBuckets); michael@0: michael@0: compacted(); michael@0: return true; michael@0: } michael@0: michael@0: // Not copyable. michael@0: OrderedHashTable &operator=(const OrderedHashTable &) MOZ_DELETE; michael@0: OrderedHashTable(const OrderedHashTable &) MOZ_DELETE; michael@0: }; michael@0: michael@0: } // namespace detail michael@0: michael@0: template michael@0: class OrderedHashMap michael@0: { michael@0: public: michael@0: class Entry michael@0: { michael@0: template friend class detail::OrderedHashTable; michael@0: void operator=(const Entry &rhs) { michael@0: const_cast(key) = rhs.key; michael@0: value = rhs.value; michael@0: } michael@0: michael@0: void operator=(Entry &&rhs) { michael@0: MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited"); michael@0: const_cast(key) = Move(rhs.key); michael@0: value = Move(rhs.value); michael@0: } michael@0: michael@0: public: michael@0: Entry() : key(), value() {} michael@0: Entry(const Key &k, const Value &v) : key(k), value(v) {} michael@0: Entry(Entry &&rhs) : key(Move(rhs.key)), value(Move(rhs.value)) {} michael@0: michael@0: const Key key; michael@0: Value value; michael@0: }; michael@0: michael@0: private: michael@0: struct MapOps : OrderedHashPolicy michael@0: { michael@0: typedef Key KeyType; michael@0: static void makeEmpty(Entry *e) { michael@0: OrderedHashPolicy::makeEmpty(const_cast(&e->key)); michael@0: michael@0: // Clear the value. Destroying it is another possibility, but that michael@0: // would complicate class Entry considerably. michael@0: e->value = Value(); michael@0: } michael@0: static const Key &getKey(const Entry &e) { return e.key; } michael@0: static void setKey(Entry &e, const Key &k) { const_cast(e.key) = k; } michael@0: }; michael@0: michael@0: typedef detail::OrderedHashTable Impl; michael@0: Impl impl; michael@0: michael@0: public: michael@0: typedef typename Impl::Range Range; michael@0: michael@0: OrderedHashMap(AllocPolicy ap = AllocPolicy()) : impl(ap) {} michael@0: bool init() { return impl.init(); } michael@0: uint32_t count() const { return impl.count(); } michael@0: bool has(const Key &key) const { return impl.has(key); } michael@0: Range all() { return impl.all(); } michael@0: const Entry *get(const Key &key) const { return impl.get(key); } michael@0: Entry *get(const Key &key) { return impl.get(key); } michael@0: bool put(const Key &key, const Value &value) { return impl.put(Entry(key, value)); } michael@0: bool remove(const Key &key, bool *foundp) { return impl.remove(key, foundp); } michael@0: bool clear() { return impl.clear(); } michael@0: michael@0: void rekeyOneEntry(const Key ¤t, const Key &newKey) { michael@0: const Entry *e = get(current); michael@0: if (!e) michael@0: return; michael@0: return impl.rekeyOneEntry(current, newKey, Entry(newKey, e->value)); michael@0: } michael@0: }; michael@0: michael@0: template michael@0: class OrderedHashSet michael@0: { michael@0: private: michael@0: struct SetOps : OrderedHashPolicy michael@0: { michael@0: typedef const T KeyType; michael@0: static const T &getKey(const T &v) { return v; } michael@0: static void setKey(const T &e, const T &v) { const_cast(e) = v; } michael@0: }; michael@0: michael@0: typedef detail::OrderedHashTable Impl; michael@0: Impl impl; michael@0: michael@0: public: michael@0: typedef typename Impl::Range Range; michael@0: michael@0: OrderedHashSet(AllocPolicy ap = AllocPolicy()) : impl(ap) {} michael@0: bool init() { return impl.init(); } michael@0: uint32_t count() const { return impl.count(); } michael@0: bool has(const T &value) const { return impl.has(value); } michael@0: Range all() { return impl.all(); } michael@0: bool put(const T &value) { return impl.put(value); } michael@0: bool remove(const T &value, bool *foundp) { return impl.remove(value, foundp); } michael@0: bool clear() { return impl.clear(); } michael@0: michael@0: void rekeyOneEntry(const T ¤t, const T &newKey) { michael@0: return impl.rekeyOneEntry(current, newKey, newKey); michael@0: } michael@0: }; michael@0: michael@0: } // namespace js michael@0: michael@0: michael@0: /*** HashableValue *******************************************************************************/ michael@0: michael@0: bool michael@0: HashableValue::setValue(JSContext *cx, HandleValue v) michael@0: { michael@0: if (v.isString()) { michael@0: // Atomize so that hash() and operator==() are fast and infallible. michael@0: JSString *str = AtomizeString(cx, v.toString(), DoNotInternAtom); michael@0: if (!str) michael@0: return false; michael@0: value = StringValue(str); michael@0: } else if (v.isDouble()) { michael@0: double d = v.toDouble(); michael@0: int32_t i; michael@0: if (NumberEqualsInt32(d, &i)) { michael@0: // Normalize int32_t-valued doubles to int32_t for faster hashing and testing. michael@0: value = Int32Value(i); michael@0: } else if (IsNaN(d)) { michael@0: // NaNs with different bits must hash and test identically. michael@0: value = DoubleNaNValue(); michael@0: } else { michael@0: value = v; michael@0: } michael@0: } else { michael@0: value = v; michael@0: } michael@0: michael@0: JS_ASSERT(value.isUndefined() || value.isNull() || value.isBoolean() || michael@0: value.isNumber() || value.isString() || value.isObject()); michael@0: return true; michael@0: } michael@0: michael@0: HashNumber michael@0: HashableValue::hash() const michael@0: { michael@0: // HashableValue::setValue normalizes values so that the SameValue relation michael@0: // on HashableValues is the same as the == relationship on michael@0: // value.data.asBits. michael@0: return value.asRawBits(); michael@0: } michael@0: michael@0: bool michael@0: HashableValue::operator==(const HashableValue &other) const michael@0: { michael@0: // Two HashableValues are equal if they have equal bits. michael@0: bool b = (value.asRawBits() == other.value.asRawBits()); michael@0: michael@0: #ifdef DEBUG michael@0: bool same; michael@0: JS_ASSERT(SameValue(nullptr, value, other.value, &same)); michael@0: JS_ASSERT(same == b); michael@0: #endif michael@0: return b; michael@0: } michael@0: michael@0: HashableValue michael@0: HashableValue::mark(JSTracer *trc) const michael@0: { michael@0: HashableValue hv(*this); michael@0: trc->setTracingLocation((void *)this); michael@0: gc::MarkValue(trc, &hv.value, "key"); michael@0: return hv; michael@0: } michael@0: michael@0: michael@0: /*** MapIterator *********************************************************************************/ michael@0: michael@0: namespace { michael@0: michael@0: class MapIteratorObject : public JSObject michael@0: { michael@0: public: michael@0: static const Class class_; michael@0: michael@0: enum { TargetSlot, KindSlot, RangeSlot, SlotCount }; michael@0: static const JSFunctionSpec methods[]; michael@0: static MapIteratorObject *create(JSContext *cx, HandleObject mapobj, ValueMap *data, michael@0: MapObject::IteratorKind kind); michael@0: static void finalize(FreeOp *fop, JSObject *obj); michael@0: michael@0: private: michael@0: static inline bool is(HandleValue v); michael@0: inline ValueMap::Range *range(); michael@0: inline MapObject::IteratorKind kind() const; michael@0: static bool next_impl(JSContext *cx, CallArgs args); michael@0: static bool next(JSContext *cx, unsigned argc, Value *vp); michael@0: }; michael@0: michael@0: } /* anonymous namespace */ michael@0: michael@0: const Class MapIteratorObject::class_ = { michael@0: "Map Iterator", michael@0: JSCLASS_IMPLEMENTS_BARRIERS | michael@0: JSCLASS_HAS_RESERVED_SLOTS(MapIteratorObject::SlotCount), michael@0: JS_PropertyStub, /* addProperty */ michael@0: JS_DeletePropertyStub, /* delProperty */ michael@0: JS_PropertyStub, /* getProperty */ michael@0: JS_StrictPropertyStub, /* setProperty */ michael@0: JS_EnumerateStub, michael@0: JS_ResolveStub, michael@0: JS_ConvertStub, michael@0: MapIteratorObject::finalize michael@0: }; michael@0: michael@0: const JSFunctionSpec MapIteratorObject::methods[] = { michael@0: JS_SELF_HOSTED_FN("@@iterator", "IteratorIdentity", 0, 0), michael@0: JS_FN("next", next, 0, 0), michael@0: JS_FS_END michael@0: }; michael@0: michael@0: inline ValueMap::Range * michael@0: MapIteratorObject::range() michael@0: { michael@0: return static_cast(getSlot(RangeSlot).toPrivate()); michael@0: } michael@0: michael@0: inline MapObject::IteratorKind michael@0: MapIteratorObject::kind() const michael@0: { michael@0: int32_t i = getSlot(KindSlot).toInt32(); michael@0: JS_ASSERT(i == MapObject::Keys || i == MapObject::Values || i == MapObject::Entries); michael@0: return MapObject::IteratorKind(i); michael@0: } michael@0: michael@0: bool michael@0: GlobalObject::initMapIteratorProto(JSContext *cx, Handle global) michael@0: { michael@0: JSObject *base = GlobalObject::getOrCreateIteratorPrototype(cx, global); michael@0: if (!base) michael@0: return false; michael@0: Rooted proto(cx, michael@0: NewObjectWithGivenProto(cx, &MapIteratorObject::class_, base, global)); michael@0: if (!proto) michael@0: return false; michael@0: proto->setSlot(MapIteratorObject::RangeSlot, PrivateValue(nullptr)); michael@0: if (!JS_DefineFunctions(cx, proto, MapIteratorObject::methods)) michael@0: return false; michael@0: global->setReservedSlot(MAP_ITERATOR_PROTO, ObjectValue(*proto)); michael@0: return true; michael@0: } michael@0: michael@0: MapIteratorObject * michael@0: MapIteratorObject::create(JSContext *cx, HandleObject mapobj, ValueMap *data, michael@0: MapObject::IteratorKind kind) michael@0: { michael@0: Rooted global(cx, &mapobj->global()); michael@0: Rooted proto(cx, GlobalObject::getOrCreateMapIteratorPrototype(cx, global)); michael@0: if (!proto) michael@0: return nullptr; michael@0: michael@0: ValueMap::Range *range = cx->new_(data->all()); michael@0: if (!range) michael@0: return nullptr; michael@0: michael@0: JSObject *iterobj = NewObjectWithGivenProto(cx, &class_, proto, global); michael@0: if (!iterobj) { michael@0: js_delete(range); michael@0: return nullptr; michael@0: } michael@0: iterobj->setSlot(TargetSlot, ObjectValue(*mapobj)); michael@0: iterobj->setSlot(KindSlot, Int32Value(int32_t(kind))); michael@0: iterobj->setSlot(RangeSlot, PrivateValue(range)); michael@0: return static_cast(iterobj); michael@0: } michael@0: michael@0: void michael@0: MapIteratorObject::finalize(FreeOp *fop, JSObject *obj) michael@0: { michael@0: fop->delete_(obj->as().range()); michael@0: } michael@0: michael@0: bool michael@0: MapIteratorObject::is(HandleValue v) michael@0: { michael@0: return v.isObject() && v.toObject().hasClass(&class_); michael@0: } michael@0: michael@0: bool michael@0: MapIteratorObject::next_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: MapIteratorObject &thisobj = args.thisv().toObject().as(); michael@0: ValueMap::Range *range = thisobj.range(); michael@0: RootedValue value(cx); michael@0: bool done; michael@0: michael@0: if (!range || range->empty()) { michael@0: js_delete(range); michael@0: thisobj.setReservedSlot(RangeSlot, PrivateValue(nullptr)); michael@0: value.setUndefined(); michael@0: done = true; michael@0: } else { michael@0: switch (thisobj.kind()) { michael@0: case MapObject::Keys: michael@0: value = range->front().key.get(); michael@0: break; michael@0: michael@0: case MapObject::Values: michael@0: value = range->front().value; michael@0: break; michael@0: michael@0: case MapObject::Entries: { michael@0: JS::AutoValueArray<2> pair(cx); michael@0: pair[0].set(range->front().key.get()); michael@0: pair[1].set(range->front().value); michael@0: michael@0: JSObject *pairobj = NewDenseCopiedArray(cx, pair.length(), pair.begin()); michael@0: if (!pairobj) michael@0: return false; michael@0: value.setObject(*pairobj); michael@0: break; michael@0: } michael@0: } michael@0: range->popFront(); michael@0: done = false; michael@0: } michael@0: michael@0: RootedObject result(cx, CreateItrResultObject(cx, value, done)); michael@0: if (!result) michael@0: return false; michael@0: args.rval().setObject(*result); michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapIteratorObject::next(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, next_impl, args); michael@0: } michael@0: michael@0: michael@0: /*** Map *****************************************************************************************/ michael@0: michael@0: const Class MapObject::class_ = { michael@0: "Map", michael@0: JSCLASS_HAS_PRIVATE | JSCLASS_IMPLEMENTS_BARRIERS | michael@0: JSCLASS_HAS_CACHED_PROTO(JSProto_Map), michael@0: JS_PropertyStub, // addProperty michael@0: JS_DeletePropertyStub, // delProperty michael@0: JS_PropertyStub, // getProperty michael@0: JS_StrictPropertyStub, // setProperty michael@0: JS_EnumerateStub, michael@0: JS_ResolveStub, michael@0: JS_ConvertStub, michael@0: finalize, michael@0: nullptr, // call michael@0: nullptr, // hasInstance michael@0: nullptr, // construct michael@0: mark michael@0: }; michael@0: michael@0: const JSPropertySpec MapObject::properties[] = { michael@0: JS_PSG("size", size, 0), michael@0: JS_PS_END michael@0: }; michael@0: michael@0: const JSFunctionSpec MapObject::methods[] = { michael@0: JS_FN("get", get, 1, 0), michael@0: JS_FN("has", has, 1, 0), michael@0: JS_FN("set", set, 2, 0), michael@0: JS_FN("delete", delete_, 1, 0), michael@0: JS_FN("keys", keys, 0, 0), michael@0: JS_FN("values", values, 0, 0), michael@0: JS_FN("clear", clear, 0, 0), michael@0: JS_SELF_HOSTED_FN("forEach", "MapForEach", 2, 0), michael@0: JS_FS_END michael@0: }; michael@0: michael@0: static JSObject * michael@0: InitClass(JSContext *cx, Handle global, const Class *clasp, JSProtoKey key, Native construct, michael@0: const JSPropertySpec *properties, const JSFunctionSpec *methods) michael@0: { michael@0: Rooted proto(cx, global->createBlankPrototype(cx, clasp)); michael@0: if (!proto) michael@0: return nullptr; michael@0: proto->setPrivate(nullptr); michael@0: michael@0: Rooted ctor(cx, global->createConstructor(cx, construct, ClassName(key, cx), 0)); michael@0: if (!ctor || michael@0: !LinkConstructorAndPrototype(cx, ctor, proto) || michael@0: !DefinePropertiesAndBrand(cx, proto, properties, methods) || michael@0: !GlobalObject::initBuiltinConstructor(cx, global, key, ctor, proto)) michael@0: { michael@0: return nullptr; michael@0: } michael@0: return proto; michael@0: } michael@0: michael@0: JSObject * michael@0: MapObject::initClass(JSContext *cx, JSObject *obj) michael@0: { michael@0: Rooted global(cx, &obj->as()); michael@0: RootedObject proto(cx, michael@0: InitClass(cx, global, &class_, JSProto_Map, construct, properties, methods)); michael@0: if (proto) { michael@0: // Define the "entries" method. michael@0: JSFunction *fun = JS_DefineFunction(cx, proto, "entries", entries, 0, 0); michael@0: if (!fun) michael@0: return nullptr; michael@0: michael@0: // Define its alias. michael@0: RootedValue funval(cx, ObjectValue(*fun)); michael@0: if (!JS_DefineProperty(cx, proto, js_std_iterator_str, funval, 0)) michael@0: return nullptr; michael@0: } michael@0: return proto; michael@0: } michael@0: michael@0: template michael@0: static void michael@0: MarkKey(Range &r, const HashableValue &key, JSTracer *trc) michael@0: { michael@0: HashableValue newKey = key.mark(trc); michael@0: michael@0: if (newKey.get() != key.get()) { michael@0: // The hash function only uses the bits of the Value, so it is safe to michael@0: // rekey even when the object or string has been modified by the GC. michael@0: r.rekeyFront(newKey); michael@0: } michael@0: } michael@0: michael@0: void michael@0: MapObject::mark(JSTracer *trc, JSObject *obj) michael@0: { michael@0: if (ValueMap *map = obj->as().getData()) { michael@0: for (ValueMap::Range r = map->all(); !r.empty(); r.popFront()) { michael@0: MarkKey(r, r.front().key, trc); michael@0: gc::MarkValue(trc, &r.front().value, "value"); michael@0: } michael@0: } michael@0: } michael@0: michael@0: #ifdef JSGC_GENERATIONAL michael@0: struct UnbarrieredHashPolicy { michael@0: typedef Value Lookup; michael@0: static HashNumber hash(const Lookup &v) { return v.asRawBits(); } michael@0: static bool match(const Value &k, const Lookup &l) { return k == l; } michael@0: static bool isEmpty(const Value &v) { return v.isMagic(JS_HASH_KEY_EMPTY); } michael@0: static void makeEmpty(Value *vp) { vp->setMagic(JS_HASH_KEY_EMPTY); } michael@0: }; michael@0: michael@0: template michael@0: class OrderedHashTableRef : public gc::BufferableRef michael@0: { michael@0: TableType *table; michael@0: Value key; michael@0: michael@0: public: michael@0: explicit OrderedHashTableRef(TableType *t, const Value &k) : table(t), key(k) {} michael@0: michael@0: void mark(JSTracer *trc) { michael@0: JS_ASSERT(UnbarrieredHashPolicy::hash(key) == michael@0: HashableValue::Hasher::hash(*reinterpret_cast(&key))); michael@0: Value prior = key; michael@0: gc::MarkValueUnbarriered(trc, &key, "ordered hash table key"); michael@0: table->rekeyOneEntry(prior, key); michael@0: } michael@0: }; michael@0: #endif michael@0: michael@0: static void michael@0: WriteBarrierPost(JSRuntime *rt, ValueMap *map, const HashableValue &key) michael@0: { michael@0: #ifdef JSGC_GENERATIONAL michael@0: typedef OrderedHashMap UnbarrieredMap; michael@0: rt->gcStoreBuffer.putGeneric(OrderedHashTableRef( michael@0: reinterpret_cast(map), key.get())); michael@0: #endif michael@0: } michael@0: michael@0: static void michael@0: WriteBarrierPost(JSRuntime *rt, ValueSet *set, const HashableValue &key) michael@0: { michael@0: #ifdef JSGC_GENERATIONAL michael@0: typedef OrderedHashSet UnbarrieredSet; michael@0: rt->gcStoreBuffer.putGeneric(OrderedHashTableRef( michael@0: reinterpret_cast(set), key.get())); michael@0: #endif michael@0: } michael@0: michael@0: void michael@0: MapObject::finalize(FreeOp *fop, JSObject *obj) michael@0: { michael@0: if (ValueMap *map = obj->as().getData()) michael@0: fop->delete_(map); michael@0: } michael@0: michael@0: bool michael@0: MapObject::construct(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: Rooted obj(cx, NewBuiltinClassInstance(cx, &class_)); michael@0: if (!obj) michael@0: return false; michael@0: michael@0: ValueMap *map = cx->new_(cx->runtime()); michael@0: if (!map) michael@0: return false; michael@0: if (!map->init()) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: obj->setPrivate(map); michael@0: michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: if (args.hasDefined(0)) { michael@0: ForOfIterator iter(cx); michael@0: if (!iter.init(args[0])) michael@0: return false; michael@0: RootedValue pairVal(cx); michael@0: RootedObject pairObj(cx); michael@0: while (true) { michael@0: bool done; michael@0: if (!iter.next(&pairVal, &done)) michael@0: return false; michael@0: if (done) michael@0: break; michael@0: if (!pairVal.isObject()) { michael@0: JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_INVALID_MAP_ITERABLE); michael@0: return false; michael@0: } michael@0: michael@0: pairObj = &pairVal.toObject(); michael@0: if (!pairObj) michael@0: return false; michael@0: michael@0: RootedValue key(cx); michael@0: if (!JSObject::getElement(cx, pairObj, pairObj, 0, &key)) michael@0: return false; michael@0: michael@0: AutoHashableValueRooter hkey(cx); michael@0: if (!hkey.setValue(cx, key)) michael@0: return false; michael@0: michael@0: RootedValue val(cx); michael@0: if (!JSObject::getElement(cx, pairObj, pairObj, 1, &val)) michael@0: return false; michael@0: michael@0: RelocatableValue rval(val); michael@0: if (!map->put(hkey, rval)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: WriteBarrierPost(cx->runtime(), map, hkey); michael@0: } michael@0: } michael@0: michael@0: args.rval().setObject(*obj); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::is(HandleValue v) michael@0: { michael@0: return v.isObject() && v.toObject().hasClass(&class_) && v.toObject().getPrivate(); michael@0: } michael@0: michael@0: #define ARG0_KEY(cx, args, key) \ michael@0: AutoHashableValueRooter key(cx); \ michael@0: if (args.length() > 0 && !key.setValue(cx, args[0])) \ michael@0: return false michael@0: michael@0: ValueMap & michael@0: MapObject::extract(CallReceiver call) michael@0: { michael@0: JS_ASSERT(call.thisv().isObject()); michael@0: JS_ASSERT(call.thisv().toObject().hasClass(&MapObject::class_)); michael@0: return *call.thisv().toObject().as().getData(); michael@0: } michael@0: michael@0: bool michael@0: MapObject::size_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(MapObject::is(args.thisv())); michael@0: michael@0: ValueMap &map = extract(args); michael@0: JS_STATIC_ASSERT(sizeof map.count() <= sizeof(uint32_t)); michael@0: args.rval().setNumber(map.count()); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::size(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::get_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(MapObject::is(args.thisv())); michael@0: michael@0: ValueMap &map = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: michael@0: if (ValueMap::Entry *p = map.get(key)) michael@0: args.rval().set(p->value); michael@0: else michael@0: args.rval().setUndefined(); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::get(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::has_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(MapObject::is(args.thisv())); michael@0: michael@0: ValueMap &map = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: args.rval().setBoolean(map.has(key)); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::has(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::set_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(MapObject::is(args.thisv())); michael@0: michael@0: ValueMap &map = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: RelocatableValue rval(args.get(1)); michael@0: if (!map.put(key, rval)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: WriteBarrierPost(cx->runtime(), &map, key); michael@0: args.rval().setUndefined(); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::set(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::delete_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: // MapObject::mark does not mark deleted entries. Incremental GC therefore michael@0: // requires that no RelocatableValue objects pointing to heap values be michael@0: // left alive in the ValueMap. michael@0: // michael@0: // OrderedHashMap::remove() doesn't destroy the removed entry. It merely michael@0: // calls OrderedHashMap::MapOps::makeEmpty. But that is sufficient, because michael@0: // makeEmpty clears the value by doing e->value = Value(), and in the case michael@0: // of a ValueMap, Value() means RelocatableValue(), which is the same as michael@0: // RelocatableValue(UndefinedValue()). michael@0: JS_ASSERT(MapObject::is(args.thisv())); michael@0: michael@0: ValueMap &map = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: bool found; michael@0: if (!map.remove(key, &found)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: args.rval().setBoolean(found); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::delete_(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::iterator_impl(JSContext *cx, CallArgs args, IteratorKind kind) michael@0: { michael@0: Rooted mapobj(cx, &args.thisv().toObject().as()); michael@0: ValueMap &map = *mapobj->getData(); michael@0: Rooted iterobj(cx, MapIteratorObject::create(cx, mapobj, &map, kind)); michael@0: if (!iterobj) michael@0: return false; michael@0: args.rval().setObject(*iterobj); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::keys_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: return iterator_impl(cx, args, Keys); michael@0: } michael@0: michael@0: bool michael@0: MapObject::keys(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, keys_impl, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::values_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: return iterator_impl(cx, args, Values); michael@0: } michael@0: michael@0: bool michael@0: MapObject::values(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, values_impl, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::entries_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: return iterator_impl(cx, args, Entries); michael@0: } michael@0: michael@0: bool michael@0: MapObject::entries(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, entries_impl, args); michael@0: } michael@0: michael@0: bool michael@0: MapObject::clear_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: Rooted mapobj(cx, &args.thisv().toObject().as()); michael@0: if (!mapobj->getData()->clear()) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: args.rval().setUndefined(); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: MapObject::clear(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, clear_impl, args); michael@0: } michael@0: michael@0: JSObject * michael@0: js_InitMapClass(JSContext *cx, HandleObject obj) michael@0: { michael@0: return MapObject::initClass(cx, obj); michael@0: } michael@0: michael@0: michael@0: /*** SetIterator *********************************************************************************/ michael@0: michael@0: namespace { michael@0: michael@0: class SetIteratorObject : public JSObject michael@0: { michael@0: public: michael@0: static const Class class_; michael@0: michael@0: enum { TargetSlot, KindSlot, RangeSlot, SlotCount }; michael@0: static const JSFunctionSpec methods[]; michael@0: static SetIteratorObject *create(JSContext *cx, HandleObject setobj, ValueSet *data, michael@0: SetObject::IteratorKind kind); michael@0: static void finalize(FreeOp *fop, JSObject *obj); michael@0: michael@0: private: michael@0: static inline bool is(HandleValue v); michael@0: inline ValueSet::Range *range(); michael@0: inline SetObject::IteratorKind kind() const; michael@0: static bool next_impl(JSContext *cx, CallArgs args); michael@0: static bool next(JSContext *cx, unsigned argc, Value *vp); michael@0: }; michael@0: michael@0: } /* anonymous namespace */ michael@0: michael@0: const Class SetIteratorObject::class_ = { michael@0: "Set Iterator", michael@0: JSCLASS_IMPLEMENTS_BARRIERS | michael@0: JSCLASS_HAS_RESERVED_SLOTS(SetIteratorObject::SlotCount), michael@0: JS_PropertyStub, /* addProperty */ michael@0: JS_DeletePropertyStub, /* delProperty */ michael@0: JS_PropertyStub, /* getProperty */ michael@0: JS_StrictPropertyStub, /* setProperty */ michael@0: JS_EnumerateStub, michael@0: JS_ResolveStub, michael@0: JS_ConvertStub, michael@0: SetIteratorObject::finalize michael@0: }; michael@0: michael@0: const JSFunctionSpec SetIteratorObject::methods[] = { michael@0: JS_SELF_HOSTED_FN("@@iterator", "IteratorIdentity", 0, 0), michael@0: JS_FN("next", next, 0, 0), michael@0: JS_FS_END michael@0: }; michael@0: michael@0: inline ValueSet::Range * michael@0: SetIteratorObject::range() michael@0: { michael@0: return static_cast(getSlot(RangeSlot).toPrivate()); michael@0: } michael@0: michael@0: inline SetObject::IteratorKind michael@0: SetIteratorObject::kind() const michael@0: { michael@0: int32_t i = getSlot(KindSlot).toInt32(); michael@0: JS_ASSERT(i == SetObject::Values || i == SetObject::Entries); michael@0: return SetObject::IteratorKind(i); michael@0: } michael@0: michael@0: bool michael@0: GlobalObject::initSetIteratorProto(JSContext *cx, Handle global) michael@0: { michael@0: JSObject *base = GlobalObject::getOrCreateIteratorPrototype(cx, global); michael@0: if (!base) michael@0: return false; michael@0: RootedObject proto(cx, NewObjectWithGivenProto(cx, &SetIteratorObject::class_, base, global)); michael@0: if (!proto) michael@0: return false; michael@0: proto->setSlot(SetIteratorObject::RangeSlot, PrivateValue(nullptr)); michael@0: if (!JS_DefineFunctions(cx, proto, SetIteratorObject::methods)) michael@0: return false; michael@0: global->setReservedSlot(SET_ITERATOR_PROTO, ObjectValue(*proto)); michael@0: return true; michael@0: } michael@0: michael@0: SetIteratorObject * michael@0: SetIteratorObject::create(JSContext *cx, HandleObject setobj, ValueSet *data, michael@0: SetObject::IteratorKind kind) michael@0: { michael@0: Rooted global(cx, &setobj->global()); michael@0: Rooted proto(cx, GlobalObject::getOrCreateSetIteratorPrototype(cx, global)); michael@0: if (!proto) michael@0: return nullptr; michael@0: michael@0: ValueSet::Range *range = cx->new_(data->all()); michael@0: if (!range) michael@0: return nullptr; michael@0: michael@0: JSObject *iterobj = NewObjectWithGivenProto(cx, &class_, proto, global); michael@0: if (!iterobj) { michael@0: js_delete(range); michael@0: return nullptr; michael@0: } michael@0: iterobj->setSlot(TargetSlot, ObjectValue(*setobj)); michael@0: iterobj->setSlot(KindSlot, Int32Value(int32_t(kind))); michael@0: iterobj->setSlot(RangeSlot, PrivateValue(range)); michael@0: return static_cast(iterobj); michael@0: } michael@0: michael@0: void michael@0: SetIteratorObject::finalize(FreeOp *fop, JSObject *obj) michael@0: { michael@0: fop->delete_(obj->as().range()); michael@0: } michael@0: michael@0: bool michael@0: SetIteratorObject::is(HandleValue v) michael@0: { michael@0: return v.isObject() && v.toObject().is(); michael@0: } michael@0: michael@0: bool michael@0: SetIteratorObject::next_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: SetIteratorObject &thisobj = args.thisv().toObject().as(); michael@0: ValueSet::Range *range = thisobj.range(); michael@0: RootedValue value(cx); michael@0: bool done; michael@0: michael@0: if (!range || range->empty()) { michael@0: js_delete(range); michael@0: thisobj.setReservedSlot(RangeSlot, PrivateValue(nullptr)); michael@0: value.setUndefined(); michael@0: done = true; michael@0: } else { michael@0: switch (thisobj.kind()) { michael@0: case SetObject::Values: michael@0: value = range->front().get(); michael@0: break; michael@0: michael@0: case SetObject::Entries: { michael@0: JS::AutoValueArray<2> pair(cx); michael@0: pair[0].set(range->front().get()); michael@0: pair[1].set(range->front().get()); michael@0: michael@0: JSObject *pairObj = NewDenseCopiedArray(cx, 2, pair.begin()); michael@0: if (!pairObj) michael@0: return false; michael@0: value.setObject(*pairObj); michael@0: break; michael@0: } michael@0: } michael@0: range->popFront(); michael@0: done = false; michael@0: } michael@0: michael@0: RootedObject result(cx, CreateItrResultObject(cx, value, done)); michael@0: if (!result) michael@0: return false; michael@0: args.rval().setObject(*result); michael@0: michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetIteratorObject::next(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, next_impl, args); michael@0: } michael@0: michael@0: michael@0: /*** Set *****************************************************************************************/ michael@0: michael@0: const Class SetObject::class_ = { michael@0: "Set", michael@0: JSCLASS_HAS_PRIVATE | JSCLASS_IMPLEMENTS_BARRIERS | michael@0: JSCLASS_HAS_CACHED_PROTO(JSProto_Set), michael@0: JS_PropertyStub, // addProperty michael@0: JS_DeletePropertyStub, // delProperty michael@0: JS_PropertyStub, // getProperty michael@0: JS_StrictPropertyStub, // setProperty michael@0: JS_EnumerateStub, michael@0: JS_ResolveStub, michael@0: JS_ConvertStub, michael@0: finalize, michael@0: nullptr, // call michael@0: nullptr, // hasInstance michael@0: nullptr, // construct michael@0: mark michael@0: }; michael@0: michael@0: const JSPropertySpec SetObject::properties[] = { michael@0: JS_PSG("size", size, 0), michael@0: JS_PS_END michael@0: }; michael@0: michael@0: const JSFunctionSpec SetObject::methods[] = { michael@0: JS_FN("has", has, 1, 0), michael@0: JS_FN("add", add, 1, 0), michael@0: JS_FN("delete", delete_, 1, 0), michael@0: JS_FN("entries", entries, 0, 0), michael@0: JS_FN("clear", clear, 0, 0), michael@0: JS_SELF_HOSTED_FN("forEach", "SetForEach", 2, 0), michael@0: JS_FS_END michael@0: }; michael@0: michael@0: JSObject * michael@0: SetObject::initClass(JSContext *cx, JSObject *obj) michael@0: { michael@0: Rooted global(cx, &obj->as()); michael@0: RootedObject proto(cx, michael@0: InitClass(cx, global, &class_, JSProto_Set, construct, properties, methods)); michael@0: if (proto) { michael@0: // Define the "values" method. michael@0: JSFunction *fun = JS_DefineFunction(cx, proto, "values", values, 0, 0); michael@0: if (!fun) michael@0: return nullptr; michael@0: michael@0: // Define its aliases. michael@0: RootedValue funval(cx, ObjectValue(*fun)); michael@0: if (!JS_DefineProperty(cx, proto, "keys", funval, 0)) michael@0: return nullptr; michael@0: if (!JS_DefineProperty(cx, proto, js_std_iterator_str, funval, 0)) michael@0: return nullptr; michael@0: } michael@0: return proto; michael@0: } michael@0: michael@0: void michael@0: SetObject::mark(JSTracer *trc, JSObject *obj) michael@0: { michael@0: SetObject *setobj = static_cast(obj); michael@0: if (ValueSet *set = setobj->getData()) { michael@0: for (ValueSet::Range r = set->all(); !r.empty(); r.popFront()) michael@0: MarkKey(r, r.front(), trc); michael@0: } michael@0: } michael@0: michael@0: void michael@0: SetObject::finalize(FreeOp *fop, JSObject *obj) michael@0: { michael@0: SetObject *setobj = static_cast(obj); michael@0: if (ValueSet *set = setobj->getData()) michael@0: fop->delete_(set); michael@0: } michael@0: michael@0: bool michael@0: SetObject::construct(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: Rooted obj(cx, NewBuiltinClassInstance(cx, &class_)); michael@0: if (!obj) michael@0: return false; michael@0: michael@0: ValueSet *set = cx->new_(cx->runtime()); michael@0: if (!set) michael@0: return false; michael@0: if (!set->init()) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: obj->setPrivate(set); michael@0: michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: if (args.hasDefined(0)) { michael@0: RootedValue keyVal(cx); michael@0: ForOfIterator iter(cx); michael@0: if (!iter.init(args[0])) michael@0: return false; michael@0: AutoHashableValueRooter key(cx); michael@0: while (true) { michael@0: bool done; michael@0: if (!iter.next(&keyVal, &done)) michael@0: return false; michael@0: if (done) michael@0: break; michael@0: if (!key.setValue(cx, keyVal)) michael@0: return false; michael@0: if (!set->put(key)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: WriteBarrierPost(cx->runtime(), set, key); michael@0: } michael@0: } michael@0: michael@0: args.rval().setObject(*obj); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::is(HandleValue v) michael@0: { michael@0: return v.isObject() && v.toObject().hasClass(&class_) && v.toObject().getPrivate(); michael@0: } michael@0: michael@0: ValueSet & michael@0: SetObject::extract(CallReceiver call) michael@0: { michael@0: JS_ASSERT(call.thisv().isObject()); michael@0: JS_ASSERT(call.thisv().toObject().hasClass(&SetObject::class_)); michael@0: return *static_cast(call.thisv().toObject()).getData(); michael@0: } michael@0: michael@0: bool michael@0: SetObject::size_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(is(args.thisv())); michael@0: michael@0: ValueSet &set = extract(args); michael@0: JS_STATIC_ASSERT(sizeof set.count() <= sizeof(uint32_t)); michael@0: args.rval().setNumber(set.count()); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::size(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: SetObject::has_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(is(args.thisv())); michael@0: michael@0: ValueSet &set = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: args.rval().setBoolean(set.has(key)); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::has(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: SetObject::add_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(is(args.thisv())); michael@0: michael@0: ValueSet &set = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: if (!set.put(key)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: WriteBarrierPost(cx->runtime(), &set, key); michael@0: args.rval().setUndefined(); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::add(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: SetObject::delete_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: JS_ASSERT(is(args.thisv())); michael@0: michael@0: ValueSet &set = extract(args); michael@0: ARG0_KEY(cx, args, key); michael@0: bool found; michael@0: if (!set.remove(key, &found)) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: args.rval().setBoolean(found); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::delete_(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, args); michael@0: } michael@0: michael@0: bool michael@0: SetObject::iterator_impl(JSContext *cx, CallArgs args, IteratorKind kind) michael@0: { michael@0: Rooted setobj(cx, &args.thisv().toObject().as()); michael@0: ValueSet &set = *setobj->getData(); michael@0: Rooted iterobj(cx, SetIteratorObject::create(cx, setobj, &set, kind)); michael@0: if (!iterobj) michael@0: return false; michael@0: args.rval().setObject(*iterobj); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::values_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: return iterator_impl(cx, args, Values); michael@0: } michael@0: michael@0: bool michael@0: SetObject::values(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, values_impl, args); michael@0: } michael@0: michael@0: bool michael@0: SetObject::entries_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: return iterator_impl(cx, args, Entries); michael@0: } michael@0: michael@0: bool michael@0: SetObject::entries(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, entries_impl, args); michael@0: } michael@0: michael@0: bool michael@0: SetObject::clear_impl(JSContext *cx, CallArgs args) michael@0: { michael@0: Rooted setobj(cx, &args.thisv().toObject().as()); michael@0: if (!setobj->getData()->clear()) { michael@0: js_ReportOutOfMemory(cx); michael@0: return false; michael@0: } michael@0: args.rval().setUndefined(); michael@0: return true; michael@0: } michael@0: michael@0: bool michael@0: SetObject::clear(JSContext *cx, unsigned argc, Value *vp) michael@0: { michael@0: CallArgs args = CallArgsFromVp(argc, vp); michael@0: return CallNonGenericMethod(cx, is, clear_impl, args); michael@0: } michael@0: michael@0: JSObject * michael@0: js_InitSetClass(JSContext *cx, HandleObject obj) michael@0: { michael@0: return SetObject::initClass(cx, obj); michael@0: }