js/public/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/TypeDecls.h"
  16
  17 class JSTracer;
  18
  19 namespace JS {
  20
  21 // Define a reasonable default GC policy for GC-aware Maps.
  22 template <typename Key, typename Value>
  23 struct DefaultMapEntryGCPolicy {
  24   static bool traceWeak(JSTracer* trc, Key* key, Value* value) {
  25     return GCPolicy<Key>::traceWeak(trc, key) &&
  26            GCPolicy<Value>::traceWeak(trc, value);
  27   }
  28 };
  29
  30 // A GCHashMap is a GC-aware HashMap, meaning that it has additional trace
  31 // methods that know how to visit all keys and values in the table. HashMaps
  32 // that contain GC pointers will generally want to use this GCHashMap
  33 // specialization instead of HashMap, because this conveniently supports tracing
  34 // keys and values, and cleaning up weak entries.
  35 //
  36 // GCHashMap::trace applies GCPolicy<T>::trace to each entry's key and value.
  37 // Most types of GC pointers already have appropriate specializations of
  38 // GCPolicy, so they should just work as keys and values. Any struct type with a
  39 // default constructor and trace function should work as well. If you need to
  40 // define your own GCPolicy specialization, generic helpers can be found in
  41 // js/public/TracingAPI.h.
  42 //
  43 // The MapEntryGCPolicy template parameter controls how the table drops entries
  44 // when edges are weakly held. GCHashMap::traceWeak applies the
  45 // MapEntryGCPolicy's traceWeak method to each table entry; if it returns true,
  46 // the entry is dropped. The default MapEntryGCPolicy drops the entry if either
  47 // the key or value is about to be finalized, according to its
  48 // GCPolicy<T>::traceWeak method. (This default is almost always fine: it's hard
  49 // to imagine keeping such an entry around anyway.)
  50 //
  51 // Note that this HashMap only knows *how* to trace, but it does not itself
  52 // cause tracing to be invoked. For tracing, it must be used as
  53 // Rooted<GCHashMap> or PersistentRooted<GCHashMap>, or barriered and traced
  54 // manually.
  55 template <typename Key, typename Value,
  56           typename HashPolicy = js::DefaultHasher<Key>,
  57           typename AllocPolicy = js::TempAllocPolicy,
  58           typename MapEntryGCPolicy = DefaultMapEntryGCPolicy<Key, Value>>
  59 class GCHashMap : public js::HashMap<Key, Value, HashPolicy, AllocPolicy> {
  60   using Base = js::HashMap<Key, Value, HashPolicy, AllocPolicy>;
  61
  62  public:
  63   using EntryGCPolicy = MapEntryGCPolicy;
  64
  65   explicit GCHashMap() : Base(AllocPolicy()) {}
  66   explicit GCHashMap(AllocPolicy a) : Base(std::move(a)) {}
  67   explicit GCHashMap(size_t length) : Base(length) {}
  68   GCHashMap(AllocPolicy a, size_t length) : Base(std::move(a), length) {}
  69
  70   void trace(JSTracer* trc) {
  71     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
  72       GCPolicy<Value>::trace(trc, &e.front().value(), "hashmap value");
  73       GCPolicy<Key>::trace(trc, &e.front().mutableKey(), "hashmap key");
  74     }
  75   }
  76
  77   bool traceWeak(JSTracer* trc) {
  78     typename Base::Enum e(*this);
  79     traceWeakEntries(trc, e);
  80     return !this->empty();
  81   }
  82
  83   void traceWeakEntries(JSTracer* trc, typename Base::Enum& e) {
  84     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
  85       if (!MapEntryGCPolicy::traceWeak(trc, &e.front().mutableKey(),
  86                                        &e.front().value())) {
  87         e.removeFront();
  88       }
  89     }
  90   }
  91
  92   // GCHashMap is movable
  93   GCHashMap(GCHashMap&& rhs) : Base(std::move(rhs)) {}
  94   void operator=(GCHashMap&& rhs) {
  95     MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
  96     Base::operator=(std::move(rhs));
  97   }
  98
  99  private:
 100   // GCHashMap is not copyable or assignable
 101   GCHashMap(const GCHashMap& hm) = delete;
 102   GCHashMap& operator=(const GCHashMap& hm) = delete;
 103 } MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS;
 104
 105 }  // namespace JS
 106
 107 namespace js {
 108
 109 // HashMap that supports rekeying.
 110 //
 111 // If your keys are pointers to something like JSObject that can be tenured or
 112 // compacted, prefer to use GCHashMap with StableCellHasher, which takes
 113 // advantage of the Zone's stable id table to make rekeying unnecessary.
 114 template <typename Key, typename Value,
 115           typename HashPolicy = DefaultHasher<Key>,
 116           typename AllocPolicy = TempAllocPolicy,
 117           typename MapEntryGCPolicy = JS::DefaultMapEntryGCPolicy<Key, Value>>
 118 class GCRekeyableHashMap : public JS::GCHashMap<Key, Value, HashPolicy,
 119                                                 AllocPolicy, MapEntryGCPolicy> {
 120   using Base = JS::GCHashMap<Key, Value, HashPolicy, AllocPolicy>;
 121
 122  public:
 123   explicit GCRekeyableHashMap(AllocPolicy a = AllocPolicy())
 124       : Base(std::move(a)) {}
 125   explicit GCRekeyableHashMap(size_t length) : Base(length) {}
 126   GCRekeyableHashMap(AllocPolicy a, size_t length)
 127       : Base(std::move(a), length) {}
 128
 129   bool traceWeak(JSTracer* trc) {
 130     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
 131       Key key(e.front().key());
 132       if (!MapEntryGCPolicy::traceWeak(trc, &key, &e.front().value())) {
 133         e.removeFront();
 134       } else if (!HashPolicy::match(key, e.front().key())) {
 135         e.rekeyFront(key);
 136       }
 137     }
 138     return !this->empty();
 139   }
 140
 141   // GCRekeyableHashMap is movable
 142   GCRekeyableHashMap(GCRekeyableHashMap&& rhs) : Base(std::move(rhs)) {}
 143   void operator=(GCRekeyableHashMap&& rhs) {
 144     MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
 145     Base::operator=(std::move(rhs));
 146   }
 147 } MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS;
 148
 149 template <typename Wrapper, typename... Args>
 150 class WrappedPtrOperations<JS::GCHashMap<Args...>, Wrapper> {
 151   using Map = JS::GCHashMap<Args...>;
 152   using Lookup = typename Map::Lookup;
 153
 154   const Map& map() const { return static_cast<const Wrapper*>(this)->get(); }
 155
 156  public:
 157   using AddPtr = typename Map::AddPtr;
 158   using Ptr = typename Map::Ptr;
 159   using Range = typename Map::Range;
 160
 161   Ptr lookup(const Lookup& l) const { return map().lookup(l); }
 162   Range all() const { return map().all(); }
 163   bool empty() const { return map().empty(); }
 164   uint32_t count() const { return map().count(); }
 165   size_t capacity() const { return map().capacity(); }
 166   bool has(const Lookup& l) const { return map().lookup(l).found(); }
 167   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 168     return map().sizeOfExcludingThis(mallocSizeOf);
 169   }
 170   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 171     return mallocSizeOf(this) + map().sizeOfExcludingThis(mallocSizeOf);
 172   }
 173 };
 174
 175 template <typename Wrapper, typename... Args>
 176 class MutableWrappedPtrOperations<JS::GCHashMap<Args...>, Wrapper>
 177     : public WrappedPtrOperations<JS::GCHashMap<Args...>, Wrapper> {
 178   using Map = JS::GCHashMap<Args...>;
 179   using Lookup = typename Map::Lookup;
 180
 181   Map& map() { return static_cast<Wrapper*>(this)->get(); }
 182
 183  public:
 184   using AddPtr = typename Map::AddPtr;
 185   struct Enum : public Map::Enum {
 186     explicit Enum(Wrapper& o) : Map::Enum(o.map()) {}
 187   };
 188   using Ptr = typename Map::Ptr;
 189   using Range = typename Map::Range;
 190
 191   void clear() { map().clear(); }
 192   void clearAndCompact() { map().clearAndCompact(); }
 193   void remove(Ptr p) { map().remove(p); }
 194   AddPtr lookupForAdd(const Lookup& l) { return map().lookupForAdd(l); }
 195
 196   template <typename KeyInput, typename ValueInput>
 197   bool add(AddPtr& p, KeyInput&& k, ValueInput&& v) {
 198     return map().add(p, std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 199   }
 200
 201   template <typename KeyInput>
 202   bool add(AddPtr& p, KeyInput&& k) {
 203     return map().add(p, std::forward<KeyInput>(k), Map::Value());
 204   }
 205
 206   template <typename KeyInput, typename ValueInput>
 207   bool relookupOrAdd(AddPtr& p, KeyInput&& k, ValueInput&& v) {
 208     return map().relookupOrAdd(p, k, std::forward<KeyInput>(k),
 209                                std::forward<ValueInput>(v));
 210   }
 211
 212   template <typename KeyInput, typename ValueInput>
 213   bool put(KeyInput&& k, ValueInput&& v) {
 214     return map().put(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 215   }
 216
 217   template <typename KeyInput, typename ValueInput>
 218   bool putNew(KeyInput&& k, ValueInput&& v) {
 219     return map().putNew(std::forward<KeyInput>(k), std::forward<ValueInput>(v));
 220   }
 221 };
 222
 223 }  // namespace js
 224
 225 namespace JS {
 226
 227 // A GCHashSet is a HashSet with an additional trace method that knows
 228 // be traced to be kept alive will generally want to use this GCHashSet
 229 // specialization in lieu of HashSet.
 230 //
 231 // Most types of GC pointers can be traced with no extra infrastructure. For
 232 // structs and non-gc-pointer members, ensure that there is a specialization of
 233 // GCPolicy<T> with an appropriate trace method available to handle the custom
 234 // type. Generic helpers can be found in js/public/TracingAPI.h.
 235 //
 236 // Note that although this HashSet's trace will deal correctly with moved
 237 // elements, it does not itself know when to barrier or trace elements. To
 238 // function properly it must either be used with Rooted or barriered and traced
 239 // manually.
 240 template <typename T, typename HashPolicy = js::DefaultHasher<T>,
 241           typename AllocPolicy = js::TempAllocPolicy>
 242 class GCHashSet : public js::HashSet<T, HashPolicy, AllocPolicy> {
 243   using Base = js::HashSet<T, HashPolicy, AllocPolicy>;
 244
 245  public:
 246   explicit GCHashSet(AllocPolicy a = AllocPolicy()) : Base(std::move(a)) {}
 247   explicit GCHashSet(size_t length) : Base(length) {}
 248   GCHashSet(AllocPolicy a, size_t length) : Base(std::move(a), length) {}
 249
 250   void trace(JSTracer* trc) {
 251     for (typename Base::Enum e(*this); !e.empty(); e.popFront()) {
 252       GCPolicy<T>::trace(trc, &e.mutableFront(), "hashset element");
 253     }
 254   }
 255
 256   bool traceWeak(JSTracer* trc) {
 257     typename Base::Enum e(*this);
 258     traceWeakEntries(trc, e);
 259     return !this->empty();
 260   }
 261
 262   void traceWeakEntries(JSTracer* trc, typename Base::Enum& e) {
 263     for (; !e.empty(); e.popFront()) {
 264       if (!GCPolicy<T>::traceWeak(trc, &e.mutableFront())) {
 265         e.removeFront();
 266       }
 267     }
 268   }
 269
 270   // GCHashSet is movable
 271   GCHashSet(GCHashSet&& rhs) : Base(std::move(rhs)) {}
 272   void operator=(GCHashSet&& rhs) {
 273     MOZ_ASSERT(this != &rhs, "self-move assignment is prohibited");
 274     Base::operator=(std::move(rhs));
 275   }
 276
 277  private:
 278   // GCHashSet is not copyable or assignable
 279   GCHashSet(const GCHashSet& hs) = delete;
 280   GCHashSet& operator=(const GCHashSet& hs) = delete;
 281 } MOZ_INHERIT_TYPE_ANNOTATIONS_FROM_TEMPLATE_ARGS;
 282
 283 }  // namespace JS
 284
 285 namespace js {
 286
 287 template <typename Wrapper, typename... Args>
 288 class WrappedPtrOperations<JS::GCHashSet<Args...>, Wrapper> {
 289   using Set = JS::GCHashSet<Args...>;
 290
 291   const Set& set() const { return static_cast<const Wrapper*>(this)->get(); }
 292
 293  public:
 294   using Lookup = typename Set::Lookup;
 295   using AddPtr = typename Set::AddPtr;
 296   using Entry = typename Set::Entry;
 297   using Ptr = typename Set::Ptr;
 298   using Range = typename Set::Range;
 299
 300   Ptr lookup(const Lookup& l) const { return set().lookup(l); }
 301   Range all() const { return set().all(); }
 302   bool empty() const { return set().empty(); }
 303   uint32_t count() const { return set().count(); }
 304   size_t capacity() const { return set().capacity(); }
 305   bool has(const Lookup& l) const { return set().lookup(l).found(); }
 306   size_t sizeOfExcludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 307     return set().sizeOfExcludingThis(mallocSizeOf);
 308   }
 309   size_t sizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf) const {
 310     return mallocSizeOf(this) + set().sizeOfExcludingThis(mallocSizeOf);
 311   }
 312 };
 313
 314 template <typename Wrapper, typename... Args>
 315 class MutableWrappedPtrOperations<JS::GCHashSet<Args...>, Wrapper>
 316     : public WrappedPtrOperations<JS::GCHashSet<Args...>, Wrapper> {
 317   using Set = JS::GCHashSet<Args...>;
 318   using Lookup = typename Set::Lookup;
 319
 320   Set& set() { return static_cast<Wrapper*>(this)->get(); }
 321
 322  public:
 323   using AddPtr = typename Set::AddPtr;
 324   using Entry = typename Set::Entry;
 325   struct Enum : public Set::Enum {
 326     explicit Enum(Wrapper& o) : Set::Enum(o.set()) {}
 327   };
 328   using Ptr = typename Set::Ptr;
 329   using Range = typename Set::Range;
 330
 331   void clear() { set().clear(); }
 332   void clearAndCompact() { set().clearAndCompact(); }
 333   [[nodiscard]] bool reserve(uint32_t len) { return set().reserve(len); }
 334   void remove(Ptr p) { set().remove(p); }
 335   void remove(const Lookup& l) { set().remove(l); }
 336   AddPtr lookupForAdd(const Lookup& l) { return set().lookupForAdd(l); }
 337
 338   template <typename TInput>
 339   void replaceKey(Ptr p, const Lookup& l, TInput&& newValue) {
 340     set().replaceKey(p, l, std::forward<TInput>(newValue));
 341   }
 342
 343   template <typename TInput>
 344   bool add(AddPtr& p, TInput&& t) {
 345     return set().add(p, std::forward<TInput>(t));
 346   }
 347
 348   template <typename TInput>
 349   bool relookupOrAdd(AddPtr& p, const Lookup& l, TInput&& t) {
 350     return set().relookupOrAdd(p, l, std::forward<TInput>(t));
 351   }
 352
 353   template <typename TInput>
 354   bool put(TInput&& t) {
 355     return set().put(std::forward<TInput>(t));
 356   }
 357
 358   template <typename TInput>
 359   bool putNew(TInput&& t) {
 360     return set().putNew(std::forward<TInput>(t));
 361   }
 362
 363   template <typename TInput>
 364   bool putNew(const Lookup& l, TInput&& t) {
 365     return set().putNew(l, std::forward<TInput>(t));
 366   }
 367 };
 368
 369 } /* namespace js */
 370
 371 #endif /* GCHashTable_h */