libraries/source/spidermonkey/include-win32-debug/js/GCHashTable.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef GCHashTable_h
   8 #define GCHashTable_h
   9
  10 #include "mozilla/Maybe.h"
  11
  12 #include "js/GCPolicyAPI.h"
  13 #include "js/HashTable.h"
  14 #include "js/RootingAPI.h"
  15 #include "js/SweepingAPI.h"
  16 #include "js/TypeDecls.h"
  17
  18 class JSTracer;
  19
  20 namespace JS {
  21
  22 // Define a reasonable default GC policy for GC-aware Maps.
  23 template <typename Key, typename Value>
  24 struct DefaultMapSweepPolicy {
  25   static bool needsSweep(Key* key, Value* value) {
  26     return GCPolicy<Key>::needsSweep(key) || GCPolicy<Value>::needsSweep(value);
  27   }
  28
  29   static bool traceWeak(JSTracer* trc, Key* key, Value* value) {
  30     return GCPolicy<Key>::traceWeak(trc, key) &&
  31            GCPolicy<Value>::traceWeak(trc, value);
  32   }
  33 };
  34
  35 // A GCHashMap is a GC-aware HashMap, meaning that it has additional trace and
  36 // sweep methods that know how to visit all keys and values in the table.
  37 // HashMaps that contain GC pointers will generally want to use this GCHashMap
  38 // specialization instead of HashMap, because this conveniently supports tracing
  39 // keys and values, and cleaning up weak entries.
  40 //
  41 // GCHashMap::trace applies GCPolicy<T>::trace to each entry's key and value.
  42 // Most types of GC pointers already have appropriate specializations of
  43 // GCPolicy, so they should just work as keys and values. Any struct type with a
  44 // default constructor and trace and sweep functions should work as well. If you
  45 // need to define your own GCPolicy specialization, generic helpers can be found
  46 // in js/public/TracingAPI.h.
  47 //
  48 // The MapSweepPolicy template parameter controls how the table drops entries
  49 // when swept. GCHashMap::sweep applies MapSweepPolicy::needsSweep to each table
  50 // entry; if it returns true, the entry is dropped. The default MapSweepPolicy
  51 // drops the entry if either the key or value is about to be finalized,
  52 // according to its GCPolicy<T>::needsSweep method. (This default is almost
  53 // always fine: it's hard to imagine keeping such an entry around anyway.)
  54 //
  55 // Note that this HashMap only knows *how* to trace and sweep, but it does not
  56 // itself cause tracing or sweeping to be invoked. For tracing, it must be used
  57 // as Rooted<GCHashMap> or PersistentRooted<GCHashMap>, or barriered and traced
  58 // manually. For sweeping, currently it requires an explicit call to
  59 // <map>.sweep().
  60 template <typename Key, typename Value,
  61           typename HashPolicy = js::DefaultHasher<Key>,
  62           typename AllocPolicy = js::TempAllocPolicy,
  63           typename MapSweepPolicy = DefaultMapSweepPolicy<Key, Value>>
  64 class GCHashMap : public js::HashMap<Key, Value, HashPolicy, AllocPolicy> {
  65   using Base = js::HashMap<Key, Value, HashPolicy, AllocPolicy>;
  66
  67  public:
  68   explicit GCHashMap(AllocPolicy a = AllocPolicy()) : Base(std::move(a)) {}
  69   explicit GCHashMap(size_t length) : Base(length) {}
  70   GCHashMap(AllocPolicy a, size_t length) : Base(std::move(a), length) {}
  71
  72   void trace(JSTracer* trc) {
  73     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
  74       GCPolicy<Value>::trace(trc, &e.front().value(), "hashmap value");
  75       GCPolicy<Key>::trace(trc, &e.front().mutableKey(), "hashmap key");
  76     }
  77   }
  78
  79   bool needsSweep() const { return !this->empty(); }
  80
  81   void sweep() {
  82     typename Base::Enum e(*this);
  83     sweepEntries(e);
  84   }
  85
  86   void sweepEntries(typename Base::Enum& e) {
  87     for (; !e.empty(); e.popFront()) {
  88       if (MapSweepPolicy::needsSweep(&e.front().mutableKey(),
  89                                      &e.front().value())) {
  90         e.removeFront();
  91       }
  92     }
  93   }
  94
  95   void traceWeak(JSTracer* trc) {
  96     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
  97       if (!MapSweepPolicy::traceWeak(trc, &e.front().mutableKey(),
  98                                      &e.front().value())) {
  99         e.removeFront();
 100       }
 101     }
 102   }
 103
 104   // GCHashMap is movable
 105   GCHashMap(GCHashMap&& rhs) : Base(std::move(rhs)) {}
 106   void operator=(GCHashMap&& rhs) {
 107     MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
 108     Base::operator=(std::move(rhs));
 109   }
 110
 111  private:
 112   // GCHashMap is not copyable or assignable
 113   GCHashMap(const GCHashMap& hm) = delete;
 114   GCHashMap& operator=(const GCHashMap& hm) = delete;
 115 } MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS;
 116
 117 }  // namespace JS
 118
 119 namespace js {
 120
 121 // HashMap that supports rekeying.
 122 //
 123 // If your keys are pointers to something like JSObject that can be tenured or
 124 // compacted, prefer to use GCHashMap with MovableCellHasher, which takes
 125 // advantage of the Zone's stable id table to make rekeying unnecessary.
 126 template <typename Key, typename Value,
 127           typename HashPolicy = DefaultHasher<Key>,
 128           typename AllocPolicy = TempAllocPolicy,
 129           typename MapSweepPolicy = JS::DefaultMapSweepPolicy<Key, Value>>
 130 class GCRekeyableHashMap : public JS::GCHashMap<Key, Value, HashPolicy,
 131                                                 AllocPolicy, MapSweepPolicy> {
 132   using Base = JS::GCHashMap<Key, Value, HashPolicy, AllocPolicy>;
 133
 134  public:
 135   explicit GCRekeyableHashMap(AllocPolicy a = AllocPolicy())
 136       : Base(std::move(a)) {}
 137   explicit GCRekeyableHashMap(size_t length) : Base(length) {}
 138   GCRekeyableHashMap(AllocPolicy a, size_t length)
 139       : Base(std::move(a), length) {}
 140
 141   void sweep() {
 142     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
 143       Key key(e.front().key());
 144       if (MapSweepPolicy::needsSweep(&key, &e.front().value())) {
 145         e.removeFront();
 146       } else if (!HashPolicy::match(key, e.front().key())) {
 147         e.rekeyFront(key);
 148       }
 149     }
 150   }
 151
 152   void traceWeak(JSTracer* trc) {
 153     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
 154       Key key(e.front().key());
 155       if (!MapSweepPolicy::traceWeak(trc, &key, &e.front().value())) {
 156         e.removeFront();
 157       } else if (!HashPolicy::match(key, e.front().key())) {
 158         e.rekeyFront(key);
 159       }
 160     }
 161   }
 162
 163   // GCRekeyableHashMap is movable
 164   GCRekeyableHashMap(GCRekeyableHashMap&& rhs) : Base(std::move(rhs)) {}
 165   void operator=(GCRekeyableHashMap&& rhs) {
 166     MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
 167     Base::operator=(std::move(rhs));
 168   }
 169 } MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS;
 170
 171 template <typename Wrapper, typename... Args>
 172 class WrappedPtrOperations<JS::GCHashMap<Args...>, Wrapper> {
 173   using Map = JS::GCHashMap<Args...>;
 174   using Lookup = typename Map::Lookup;
 175
 176   const Map& map() const { return static_cast<const Wrapper*>(this)->get(); }
 177
 178  public:
 179   using AddPtr = typename Map::AddPtr;
 180   using Ptr = typename Map::Ptr;
 181   using Range = typename Map::Range;
 182
 183   Ptr lookup(const Lookup& l) const { return map().lookup(l); }
 184   Range all() const { return map().all(); }
 185   bool empty() const { return map().empty(); }
 186   uint32_t count() const { return map().count(); }
 187   size_t capacity() const { return map().capacity(); }
 188   bool has(const Lookup& l) const { return map().lookup(l).found(); }
 189   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 190     return map().sizeOfExcludingThis(mallocSizeOf);
 191   }
 192   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 193     return mallocSizeOf(this) + map().sizeOfExcludingThis(mallocSizeOf);
 194   }
 195 };
 196
 197 template <typename Wrapper, typename... Args>
 198 class MutableWrappedPtrOperations<JS::GCHashMap<Args...>, Wrapper>
 199     : public WrappedPtrOperations<JS::GCHashMap<Args...>, Wrapper> {
 200   using Map = JS::GCHashMap<Args...>;
 201   using Lookup = typename Map::Lookup;
 202
 203   Map& map() { return static_cast<Wrapper*>(this)->get(); }
 204
 205  public:
 206   using AddPtr = typename Map::AddPtr;
 207   struct Enum : public Map::Enum {
 208     explicit Enum(Wrapper& o) : Map::Enum(o.map()) {}
 209   };
 210   using Ptr = typename Map::Ptr;
 211   using Range = typename Map::Range;
 212
 213   void clear() { map().clear(); }
 214   void clearAndCompact() { map().clearAndCompact(); }
 215   void remove(Ptr p) { map().remove(p); }
 216   AddPtr lookupForAdd(const Lookup& l) { return map().lookupForAdd(l); }
 217
 218   template <typename KeyInput, typename ValueInput>
 219   bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) {
 220     return map().add(p, std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 221   }
 222
 223   template <typename KeyInput>
 224   bool add(AddPtr& p, KeyInput&& k) {
 225     return map().add(p, std::forward<KeyInput>(k), Map::Value());
 226   }
 227
 228   template <typename KeyInput, typename ValueInput>
 229   bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) {
 230     return map().relookupOrAdd(p, k, std::forward<KeyInput>(k),
 231                                std::forward<ValueInput>(v));
 232   }
 233
 234   template <typename KeyInput, typename ValueInput>
 235   bool put(KeyInput&& k, ValueInput&& v) {
 236     return map().put(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 237   }
 238
 239   template <typename KeyInput, typename ValueInput>
 240   bool putNew(KeyInput&& k, ValueInput&& v) {
 241     return map().putNew(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 242   }
 243 };
 244
 245 }  // namespace js
 246
 247 namespace JS {
 248
 249 // A GCHashSet is a HashSet with an additional trace method that knows
 250 // be traced to be kept alive will generally want to use this GCHashSet
 251 // specialization in lieu of HashSet.
 252 //
 253 // Most types of GC pointers can be traced with no extra infrastructure. For
 254 // structs and non-gc-pointer members, ensure that there is a specialization of
 255 // GCPolicy<T> with an appropriate trace method available to handle the custom
 256 // type. Generic helpers can be found in js/public/TracingAPI.h.
 257 //
 258 // Note that although this HashSet's trace will deal correctly with moved
 259 // elements, it does not itself know when to barrier or trace elements. To
 260 // function properly it must either be used with Rooted or barriered and traced
 261 // manually.
 262 template <typename T, typename HashPolicy = js::DefaultHasher<T>,
 263           typename AllocPolicy = js::TempAllocPolicy>
 264 class GCHashSet : public js::HashSet<T, HashPolicy, AllocPolicy> {
 265   using Base = js::HashSet<T, HashPolicy, AllocPolicy>;
 266
 267  public:
 268   explicit GCHashSet(AllocPolicy a = AllocPolicy()) : Base(std::move(a)) {}
 269   explicit GCHashSet(size_t length) : Base(length) {}
 270   GCHashSet(AllocPolicy a, size_t length) : Base(std::move(a), length) {}
 271
 272   void trace(JSTracer* trc) {
 273     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
 274       GCPolicy<T>::trace(trc, &e.mutableFront(), "hashset element");
 275     }
 276   }
 277
 278   bool needsSweep() const { return !this->empty(); }
 279
 280   void sweep() {
 281     typename Base::Enum e(*this);
 282     sweepEntries(e);
 283   }
 284
 285   void sweepEntries(typename Base::Enum& e) {
 286     for (; !e.empty(); e.popFront()) {
 287       if (GCPolicy<T>::needsSweep(&e.mutableFront())) {
 288         e.removeFront();
 289       }
 290     }
 291   }
 292
 293   void traceWeak(JSTracer* trc) {
 294     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
 295       if (!GCPolicy<T>::traceWeak(trc, &e.mutableFront())) {
 296         e.removeFront();
 297       }
 298     }
 299   }
 300
 301   // GCHashSet is movable
 302   GCHashSet(GCHashSet&& rhs) : Base(std::move(rhs)) {}
 303   void operator=(GCHashSet&& rhs) {
 304     MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
 305     Base::operator=(std::move(rhs));
 306   }
 307
 308  private:
 309   // GCHashSet is not copyable or assignable
 310   GCHashSet(const GCHashSet& hs) = delete;
 311   GCHashSet& operator=(const GCHashSet& hs) = delete;
 312 } MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS;
 313
 314 }  // namespace JS
 315
 316 namespace js {
 317
 318 template <typename Wrapper, typename... Args>
 319 class WrappedPtrOperations<JS::GCHashSet<Args...>, Wrapper> {
 320   using Set = JS::GCHashSet<Args...>;
 321
 322   const Set& set() const { return static_cast<const Wrapper*>(this)->get(); }
 323
 324  public:
 325   using Lookup = typename Set::Lookup;
 326   using AddPtr = typename Set::AddPtr;
 327   using Entry = typename Set::Entry;
 328   using Ptr = typename Set::Ptr;
 329   using Range = typename Set::Range;
 330
 331   Ptr lookup(const Lookup& l) const { return set().lookup(l); }
 332   Range all() const { return set().all(); }
 333   bool empty() const { return set().empty(); }
 334   uint32_t count() const { return set().count(); }
 335   size_t capacity() const { return set().capacity(); }
 336   bool has(const Lookup& l) const { return set().lookup(l).found(); }
 337   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 338     return set().sizeOfExcludingThis(mallocSizeOf);
 339   }
 340   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 341     return mallocSizeOf(this) + set().sizeOfExcludingThis(mallocSizeOf);
 342   }
 343 };
 344
 345 template <typename Wrapper, typename... Args>
 346 class MutableWrappedPtrOperations<JS::GCHashSet<Args...>, Wrapper>
 347     : public WrappedPtrOperations<JS::GCHashSet<Args...>, Wrapper> {
 348   using Set = JS::GCHashSet<Args...>;
 349   using Lookup = typename Set::Lookup;
 350
 351   Set& set() { return static_cast<Wrapper*>(this)->get(); }
 352
 353  public:
 354   using AddPtr = typename Set::AddPtr;
 355   using Entry = typename Set::Entry;
 356   struct Enum : public Set::Enum {
 357     explicit Enum(Wrapper& o) : Set::Enum(o.set()) {}
 358   };
 359   using Ptr = typename Set::Ptr;
 360   using Range = typename Set::Range;
 361
 362   void clear() { set().clear(); }
 363   void clearAndCompact() { set().clearAndCompact(); }
 364   [[nodiscard]] bool reserve(uint32_t len) { return set().reserve(len); }
 365   void remove(Ptr p) { set().remove(p); }
 366   void remove(const Lookup& l) { set().remove(l); }
 367   AddPtr lookupForAdd(const Lookup& l) { return set().lookupForAdd(l); }
 368
 369   template <typename TInput>
 370   void replaceKey(Ptr p, const Lookup& l, TInput&& newValue) {
 371     set().replaceKey(p, l, std::forward<TInput>(newValue));
 372   }
 373
 374   template <typename TInput>
 375   bool add(AddPtr& p, TInput&& t) {
 376     return set().add(p, std::forward<TInput>(t));
 377   }
 378
 379   template <typename TInput>
 380   bool relookupOrAdd(AddPtr& p, const Lookup& l, TInput&& t) {
 381     return set().relookupOrAdd(p, l, std::forward<TInput>(t));
 382   }
 383
 384   template <typename TInput>
 385   bool put(TInput&& t) {
 386     return set().put(std::forward<TInput>(t));
 387   }
 388
 389   template <typename TInput>
 390   bool putNew(TInput&& t) {
 391     return set().putNew(std::forward<TInput>(t));
 392   }
 393
 394   template <typename TInput>
 395   bool putNew(const Lookup& l, TInput&& t) {
 396     return set().putNew(l, std::forward<TInput>(t));
 397   }
 398 };
 399
 400 } /* namespace js */
 401
 402 namespace JS {
 403
 404 // Specialize WeakCache for GCHashMap to provide a barriered map that does not
 405 // need to be swept immediately.
 406 template <typename Key, typename Value, typename HashPolicy,
 407           typename AllocPolicy, typename MapSweepPolicy>
 408 class WeakCache<GCHashMap<Key, Value, HashPolicy, AllocPolicy, MapSweepPolicy>>
 409     : protected detail::WeakCacheBase {
 410   using Map = GCHashMap<Key, Value, HashPolicy, AllocPolicy, MapSweepPolicy>;
 411   using Self = WeakCache<Map>;
 412
 413   Map map;
 414   bool needsBarrier;
 415
 416  public:
 417   template <typename... Args>
 418   explicit WeakCache(Zone* zone, Args&&... args)
 419       : WeakCacheBase(zone),
 420         map(std::forward<Args>(args)...),
 421         needsBarrier(false) {}
 422   template <typename... Args>
 423   explicit WeakCache(JSRuntime* rt, Args&&... args)
 424       : WeakCacheBase(rt),
 425         map(std::forward<Args>(args)...),
 426         needsBarrier(false) {}
 427   ~WeakCache() { MOZ_ASSERT(!needsBarrier); }
 428
 429   bool needsSweep() override { return map.needsSweep(); }
 430
 431   size_t sweep(js::gc::StoreBuffer* sbToLock) override {
 432     size_t steps = map.count();
 433
 434     // Create an Enum and sweep the table entries.
 435     mozilla::Maybe<typename Map::Enum> e;
 436     e.emplace(map);
 437     map.sweepEntries(e.ref());
 438
 439     // Potentially take a lock while the Enum's destructor is called as this can
 440     // rehash/resize the table and access the store buffer.
 441     mozilla::Maybe<js::gc::AutoLockStoreBuffer> lock;
 442     if (sbToLock) {
 443       lock.emplace(sbToLock);
 444     }
 445     e.reset();
 446
 447     return steps;
 448   }
 449
 450   bool setNeedsIncrementalBarrier(bool needs) override {
 451     MOZ_ASSERT(needsBarrier != needs);
 452     needsBarrier = needs;
 453     return true;
 454   }
 455
 456   bool needsIncrementalBarrier() const override { return needsBarrier; }
 457
 458  private:
 459   using Entry = typename Map::Entry;
 460
 461   static bool entryNeedsSweep(const Entry& prior) {
 462     Key key(prior.key());
 463     Value value(prior.value());
 464     bool result = MapSweepPolicy::needsSweep(&key, &value);
 465     MOZ_ASSERT(prior.key() == key);      // We shouldn't update here.
 466     MOZ_ASSERT(prior.value() == value);  // We shouldn't update here.
 467     return result;
 468   }
 469
 470  public:
 471   using Lookup = typename Map::Lookup;
 472   using Ptr = typename Map::Ptr;
 473   using AddPtr = typename Map::AddPtr;
 474
 475   struct Range {
 476     explicit Range(const typename Map::Range& r) : range(r) { settle(); }
 477     Range() = default;
 478
 479     bool empty() const { return range.empty(); }
 480     const Entry& front() const { return range.front(); }
 481
 482     void popFront() {
 483       range.popFront();
 484       settle();
 485     }
 486
 487    private:
 488     typename Map::Range range;
 489
 490     void settle() {
 491       while (!empty() && entryNeedsSweep(front())) {
 492         popFront();
 493       }
 494     }
 495   };
 496
 497   struct Enum : public Map::Enum {
 498     explicit Enum(Self& cache) : Map::Enum(cache.map) {
 499       // This operation is not allowed while barriers are in place as we
 500       // may also need to enumerate the set for sweeping.
 501       MOZ_ASSERT(!cache.needsBarrier);
 502     }
 503   };
 504
 505   Ptr lookup(const Lookup& l) const {
 506     Ptr ptr = map.lookup(l);
 507     if (needsBarrier && ptr && entryNeedsSweep(*ptr)) {
 508       const_cast<Map&>(map).remove(ptr);
 509       return Ptr();
 510     }
 511     return ptr;
 512   }
 513
 514   AddPtr lookupForAdd(const Lookup& l) {
 515     AddPtr ptr = map.lookupForAdd(l);
 516     if (needsBarrier && ptr && entryNeedsSweep(*ptr)) {
 517       const_cast<Map&>(map).remove(ptr);
 518       return map.lookupForAdd(l);
 519     }
 520     return ptr;
 521   }
 522
 523   Range all() const { return Range(map.all()); }
 524
 525   bool empty() const {
 526     // This operation is not currently allowed while barriers are in place
 527     // as it would require iterating the map and the caller expects a
 528     // constant time operation.
 529     MOZ_ASSERT(!needsBarrier);
 530     return map.empty();
 531   }
 532
 533   uint32_t count() const {
 534     // This operation is not currently allowed while barriers are in place
 535     // as it would require iterating the set and the caller expects a
 536     // constant time operation.
 537     MOZ_ASSERT(!needsBarrier);
 538     return map.count();
 539   }
 540
 541   size_t capacity() const { return map.capacity(); }
 542
 543   bool has(const Lookup& l) const { return lookup(l).found(); }
 544
 545   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 546     return map.sizeOfExcludingThis(mallocSizeOf);
 547   }
 548   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 549     return mallocSizeOf(this) + map.shallowSizeOfExcludingThis(mallocSizeOf);
 550   }
 551
 552   void clear() {
 553     // This operation is not currently allowed while barriers are in place
 554     // since it doesn't make sense to clear a cache while it is being swept.
 555     MOZ_ASSERT(!needsBarrier);
 556     map.clear();
 557   }
 558
 559   void clearAndCompact() {
 560     // This operation is not currently allowed while barriers are in place
 561     // since it doesn't make sense to clear a cache while it is being swept.
 562     MOZ_ASSERT(!needsBarrier);
 563     map.clearAndCompact();
 564   }
 565
 566   void remove(Ptr p) {
 567     // This currently supports removing entries during incremental
 568     // sweeping. If we allow these tables to be swept incrementally this may
 569     // no longer be possible.
 570     map.remove(p);
 571   }
 572
 573   void remove(const Lookup& l) {
 574     Ptr p = lookup(l);
 575     if (p) {
 576       remove(p);
 577     }
 578   }
 579
 580   template <typename KeyInput, typename ValueInput>
 581   bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) {
 582     return map.add(p, std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 583   }
 584
 585   template <typename KeyInput, typename ValueInput>
 586   bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) {
 587     return map.relookupOrAdd(p, std::forward<KeyInput>(k),
 588                              std::forward<ValueInput>(v));
 589   }
 590
 591   template <typename KeyInput, typename ValueInput>
 592   bool put(KeyInput&& k, ValueInput&& v) {
 593     return map.put(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 594   }
 595
 596   template <typename KeyInput, typename ValueInput>
 597   bool putNew(KeyInput&& k, ValueInput&& v) {
 598     return map.putNew(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 599   }
 600 } JS_HAZ_NON_GC_POINTER;
 601
 602 // Specialize WeakCache for GCHashSet to provide a barriered set that does not
 603 // need to be swept immediately.
 604 template <typename T, typename HashPolicy, typename AllocPolicy>
 605 class WeakCache<GCHashSet<T, HashPolicy, AllocPolicy>>
 606     : protected detail::WeakCacheBase {
 607   using Set = GCHashSet<T, HashPolicy, AllocPolicy>;
 608   using Self = WeakCache<Set>;
 609
 610   Set set;
 611   bool needsBarrier;
 612
 613  public:
 614   using Entry = typename Set::Entry;
 615
 616   template <typename... Args>
 617   explicit WeakCache(Zone* zone, Args&&... args)
 618       : WeakCacheBase(zone),
 619         set(std::forward<Args>(args)...),
 620         needsBarrier(false) {}
 621   template <typename... Args>
 622   explicit WeakCache(JSRuntime* rt, Args&&... args)
 623       : WeakCacheBase(rt),
 624         set(std::forward<Args>(args)...),
 625         needsBarrier(false) {}
 626
 627   size_t sweep(js::gc::StoreBuffer* sbToLock) override {
 628     size_t steps = set.count();
 629
 630     // Create an Enum and sweep the table entries. It's not necessary to take
 631     // the store buffer lock yet.
 632     mozilla::Maybe<typename Set::Enum> e;
 633     e.emplace(set);
 634     set.sweepEntries(e.ref());
 635
 636     // Destroy the Enum, potentially rehashing or resizing the table. Since this
 637     // can access the store buffer, we need to take a lock for this if we're
 638     // called off main thread.
 639     mozilla::Maybe<js::gc::AutoLockStoreBuffer> lock;
 640     if (sbToLock) {
 641       lock.emplace(sbToLock);
 642     }
 643     e.reset();
 644
 645     return steps;
 646   }
 647
 648   bool needsSweep() override { return set.needsSweep(); }
 649
 650   bool setNeedsIncrementalBarrier(bool needs) override {
 651     MOZ_ASSERT(needsBarrier != needs);
 652     needsBarrier = needs;
 653     return true;
 654   }
 655
 656   bool needsIncrementalBarrier() const override { return needsBarrier; }
 657
 658  private:
 659   static bool entryNeedsSweep(const Entry& prior) {
 660     Entry entry(prior);
 661     bool result = GCPolicy<T>::needsSweep(&entry);
 662     MOZ_ASSERT(prior == entry);  // We shouldn't update here.
 663     return result;
 664   }
 665
 666  public:
 667   using Lookup = typename Set::Lookup;
 668   using Ptr = typename Set::Ptr;
 669   using AddPtr = typename Set::AddPtr;
 670
 671   struct Range {
 672     explicit Range(const typename Set::Range& r) : range(r) { settle(); }
 673     Range() = default;
 674
 675     bool empty() const { return range.empty(); }
 676     const Entry& front() const { return range.front(); }
 677
 678     void popFront() {
 679       range.popFront();
 680       settle();
 681     }
 682
 683    private:
 684     typename Set::Range range;
 685
 686     void settle() {
 687       while (!empty() && entryNeedsSweep(front())) {
 688         popFront();
 689       }
 690     }
 691   };
 692
 693   struct Enum : public Set::Enum {
 694     explicit Enum(Self& cache) : Set::Enum(cache.set) {
 695       // This operation is not allowed while barriers are in place as we
 696       // may also need to enumerate the set for sweeping.
 697       MOZ_ASSERT(!cache.needsBarrier);
 698     }
 699   };
 700
 701   Ptr lookup(const Lookup& l) const {
 702     Ptr ptr = set.lookup(l);
 703     if (needsBarrier && ptr && entryNeedsSweep(*ptr)) {
 704       const_cast<Set&>(set).remove(ptr);
 705       return Ptr();
 706     }
 707     return ptr;
 708   }
 709
 710   AddPtr lookupForAdd(const Lookup& l) {
 711     AddPtr ptr = set.lookupForAdd(l);
 712     if (needsBarrier && ptr && entryNeedsSweep(*ptr)) {
 713       const_cast<Set&>(set).remove(ptr);
 714       return set.lookupForAdd(l);
 715     }
 716     return ptr;
 717   }
 718
 719   Range all() const { return Range(set.all()); }
 720
 721   bool empty() const {
 722     // This operation is not currently allowed while barriers are in place
 723     // as it would require iterating the set and the caller expects a
 724     // constant time operation.
 725     MOZ_ASSERT(!needsBarrier);
 726     return set.empty();
 727   }
 728
 729   uint32_t count() const {
 730     // This operation is not currently allowed while barriers are in place
 731     // as it would require iterating the set and the caller expects a
 732     // constant time operation.
 733     MOZ_ASSERT(!needsBarrier);
 734     return set.count();
 735   }
 736
 737   size_t capacity() const { return set.capacity(); }
 738
 739   bool has(const Lookup& l) const { return lookup(l).found(); }
 740
 741   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 742     return set.shallowSizeOfExcludingThis(mallocSizeOf);
 743   }
 744   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 745     return mallocSizeOf(this) + set.shallowSizeOfExcludingThis(mallocSizeOf);
 746   }
 747
 748   void clear() {
 749     // This operation is not currently allowed while barriers are in place
 750     // since it doesn't make sense to clear a cache while it is being swept.
 751     MOZ_ASSERT(!needsBarrier);
 752     set.clear();
 753   }
 754
 755   void clearAndCompact() {
 756     // This operation is not currently allowed while barriers are in place
 757     // since it doesn't make sense to clear a cache while it is being swept.
 758     MOZ_ASSERT(!needsBarrier);
 759     set.clearAndCompact();
 760   }
 761
 762   void remove(Ptr p) {
 763     // This currently supports removing entries during incremental
 764     // sweeping. If we allow these tables to be swept incrementally this may
 765     // no longer be possible.
 766     set.remove(p);
 767   }
 768
 769   void remove(const Lookup& l) {
 770     Ptr p = lookup(l);
 771     if (p) {
 772       remove(p);
 773     }
 774   }
 775
 776   template <typename TInput>
 777   void replaceKey(Ptr p, const Lookup& l, TInput&& newValue) {
 778     set.replaceKey(p, l, std::forward<TInput>(newValue));
 779   }
 780
 781   template <typename TInput>
 782   bool add(AddPtr& p, TInput&& t) {
 783     return set.add(p, std::forward<TInput>(t));
 784   }
 785
 786   template <typename TInput>
 787   bool relookupOrAdd(AddPtr& p, const Lookup& l, TInput&& t) {
 788     return set.relookupOrAdd(p, l, std::forward<TInput>(t));
 789   }
 790
 791   template <typename TInput>
 792   bool put(TInput&& t) {
 793     return set.put(std::forward<TInput>(t));
 794   }
 795
 796   template <typename TInput>
 797   bool putNew(TInput&& t) {
 798     return set.putNew(std::forward<TInput>(t));
 799   }
 800
 801   template <typename TInput>
 802   bool putNew(const Lookup& l, TInput&& t) {
 803     return set.putNew(l, std::forward<TInput>(t));
 804   }
 805 } JS_HAZ_NON_GC_POINTER;
 806
 807 }  // namespace JS
 808
 809 #endif /* GCHashTable_h */