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