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 ds_InlineTable_h
8 : #define ds_InlineTable_h
9 :
10 : #include "mozilla/Move.h"
11 :
12 : #include "jsalloc.h"
13 :
14 : #include "js/HashTable.h"
15 :
16 : namespace js {
17 :
18 : namespace detail {
19 :
20 : template <typename InlineEntry,
21 : typename Entry,
22 : typename Table,
23 : typename HashPolicy,
24 : typename AllocPolicy,
25 : size_t InlineEntries>
26 23 : class InlineTable
27 : {
28 : private:
29 : using TablePtr = typename Table::Ptr;
30 : using TableAddPtr = typename Table::AddPtr;
31 : using TableRange = typename Table::Range;
32 : using Lookup = typename HashPolicy::Lookup;
33 :
34 : size_t inlNext_;
35 : size_t inlCount_;
36 : InlineEntry inl_[InlineEntries];
37 : Table table_;
38 :
39 : #ifdef DEBUG
40 : template <typename Key>
41 451826 : static bool keyNonZero(const Key& key) {
42 : // Zero as tombstone means zero keys are invalid.
43 451826 : return !!key;
44 : }
45 : #endif
46 :
47 406674 : InlineEntry* inlineStart() {
48 406674 : MOZ_ASSERT(!usingTable());
49 406674 : return inl_;
50 : }
51 :
52 40726 : const InlineEntry* inlineStart() const {
53 40726 : MOZ_ASSERT(!usingTable());
54 40726 : return inl_;
55 : }
56 :
57 650472 : InlineEntry* inlineEnd() {
58 650472 : MOZ_ASSERT(!usingTable());
59 650472 : return inl_ + inlNext_;
60 : }
61 :
62 40726 : const InlineEntry* inlineEnd() const {
63 40726 : MOZ_ASSERT(!usingTable());
64 40726 : return inl_ + inlNext_;
65 : }
66 :
67 1612674 : bool usingTable() const {
68 1612674 : return inlNext_ > InlineEntries;
69 : }
70 :
71 516 : MOZ_MUST_USE bool switchToTable() {
72 516 : MOZ_ASSERT(inlNext_ == InlineEntries);
73 :
74 516 : if (table_.initialized()) {
75 485 : table_.clear();
76 : } else {
77 31 : if (!table_.init(count()))
78 0 : return false;
79 31 : MOZ_ASSERT(table_.initialized());
80 : }
81 :
82 516 : InlineEntry* end = inlineEnd();
83 12900 : for (InlineEntry* it = inlineStart(); it != end; ++it) {
84 12384 : if (it->key && !it->moveTo(table_))
85 0 : return false;
86 : }
87 :
88 516 : inlNext_ = InlineEntries + 1;
89 516 : MOZ_ASSERT(table_.count() == inlCount_);
90 516 : MOZ_ASSERT(usingTable());
91 516 : return true;
92 : }
93 :
94 : MOZ_NEVER_INLINE
95 : MOZ_MUST_USE bool switchAndAdd(const InlineEntry& entry) {
96 : if (!switchToTable())
97 : return false;
98 :
99 : return entry.putNew(table_);
100 : }
101 :
102 : public:
103 : static const size_t SizeOfInlineEntries = sizeof(InlineEntry) * InlineEntries;
104 :
105 88 : explicit InlineTable(AllocPolicy a = AllocPolicy())
106 : : inlNext_(0),
107 : inlCount_(0),
108 88 : table_(a)
109 88 : { }
110 :
111 : class Ptr
112 : {
113 : friend class InlineTable;
114 :
115 : protected:
116 : Entry entry_;
117 : TablePtr tablePtr_;
118 : InlineEntry* inlPtr_;
119 : bool isInlinePtr_;
120 :
121 11659 : explicit Ptr(TablePtr p)
122 11659 : : entry_(p.found() ? &*p : nullptr),
123 : tablePtr_(p),
124 11659 : isInlinePtr_(false)
125 11659 : { }
126 :
127 136677 : explicit Ptr(InlineEntry* inlineEntry)
128 : : entry_(inlineEntry),
129 : inlPtr_(inlineEntry),
130 136677 : isInlinePtr_(true)
131 136677 : { }
132 :
133 : void operator==(const Ptr& other);
134 :
135 : public:
136 : // Leaves Ptr uninitialized.
137 : Ptr() {
138 : #ifdef DEBUG
139 : inlPtr_ = (InlineEntry*) 0xbad;
140 : isInlinePtr_ = true;
141 : #endif
142 : }
143 :
144 : // Default copy constructor works for this structure.
145 :
146 244833 : bool found() const {
147 244833 : return isInlinePtr_ ? bool(inlPtr_) : tablePtr_.found();
148 : }
149 :
150 148630 : explicit operator bool() const {
151 148630 : return found();
152 : }
153 :
154 : bool operator==(const Ptr& other) const {
155 : MOZ_ASSERT(found() && other.found());
156 : if (isInlinePtr_ != other.isInlinePtr_)
157 : return false;
158 : if (isInlinePtr_)
159 : return inlPtr_ == other.inlPtr_;
160 : return tablePtr_ == other.tablePtr_;
161 : }
162 :
163 : bool operator!=(const Ptr& other) const {
164 : return !(*this == other);
165 : }
166 :
167 : Entry& operator*() {
168 : MOZ_ASSERT(found());
169 : return entry_;
170 : }
171 :
172 96203 : Entry* operator->() {
173 96203 : MOZ_ASSERT(found());
174 96203 : return &entry_;
175 : }
176 : };
177 :
178 : class AddPtr
179 : {
180 : friend class InlineTable;
181 :
182 : protected:
183 : Entry entry_;
184 : TableAddPtr tableAddPtr_;
185 : InlineEntry* inlAddPtr_;
186 : bool isInlinePtr_;
187 : // Indicates whether inlAddPtr is a found result or an add pointer.
188 : bool inlPtrFound_;
189 :
190 147324 : AddPtr(InlineEntry* ptr, bool found)
191 : : entry_(ptr),
192 : inlAddPtr_(ptr),
193 : isInlinePtr_(true),
194 147324 : inlPtrFound_(found)
195 147324 : {}
196 :
197 21547 : explicit AddPtr(const TableAddPtr& p)
198 30632 : : entry_(p.found() ? &*p : nullptr),
199 : tableAddPtr_(p),
200 30632 : isInlinePtr_(false)
201 21547 : { }
202 :
203 : public:
204 : AddPtr() {}
205 :
206 459383 : bool found() const {
207 459383 : return isInlinePtr_ ? inlPtrFound_ : tableAddPtr_.found();
208 : }
209 :
210 303490 : explicit operator bool() const {
211 303490 : return found();
212 : }
213 :
214 : bool operator==(const AddPtr& other) const {
215 : MOZ_ASSERT(found() && other.found());
216 : if (isInlinePtr_ != other.isInlinePtr_)
217 : return false;
218 : if (isInlinePtr_)
219 : return inlAddPtr_ == other.inlAddPtr_;
220 : return tableAddPtr_ == other.tableAddPtr_;
221 : }
222 :
223 : bool operator!=(const AddPtr& other) const {
224 : return !(*this == other);
225 : }
226 :
227 : Entry& operator*() {
228 : MOZ_ASSERT(found());
229 : return entry_;
230 : }
231 :
232 34252 : Entry* operator->() {
233 34252 : MOZ_ASSERT(found());
234 34252 : return &entry_;
235 : }
236 : };
237 :
238 115006 : size_t count() const {
239 115006 : return usingTable() ? table_.count() : inlCount_;
240 : }
241 :
242 : bool empty() const {
243 : return usingTable() ? table_.empty() : !inlCount_;
244 : }
245 :
246 42096 : void clear() {
247 42096 : inlNext_ = 0;
248 42096 : inlCount_ = 0;
249 42096 : }
250 :
251 : MOZ_ALWAYS_INLINE
252 148336 : Ptr lookup(const Lookup& l) {
253 148336 : MOZ_ASSERT(keyNonZero(l));
254 :
255 148336 : if (usingTable())
256 11659 : return Ptr(table_.lookup(l));
257 :
258 136677 : InlineEntry* end = inlineEnd();
259 509249 : for (InlineEntry* it = inlineStart(); it != end; ++it) {
260 460026 : if (it->key && HashPolicy::match(it->key, l))
261 87454 : return Ptr(it);
262 : }
263 :
264 49223 : return Ptr(nullptr);
265 : }
266 :
267 : MOZ_ALWAYS_INLINE
268 168871 : AddPtr lookupForAdd(const Lookup& l) {
269 168871 : MOZ_ASSERT(keyNonZero(l));
270 :
271 168871 : if (usingTable())
272 21547 : return AddPtr(table_.lookupForAdd(l));
273 :
274 147324 : InlineEntry* end = inlineEnd();
275 745238 : for (InlineEntry* it = inlineStart(); it != end; ++it) {
276 623081 : if (it->key && HashPolicy::match(it->key, l))
277 25167 : return AddPtr(it, true);
278 : }
279 :
280 : // The add pointer that's returned here may indicate the limit entry of
281 : // the linear space, in which case the |add| operation will initialize
282 : // the table if necessary and add the entry there.
283 122157 : return AddPtr(inlineEnd(), false);
284 : }
285 :
286 : template <typename KeyInput,
287 : typename... Args>
288 : MOZ_ALWAYS_INLINE
289 134619 : MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key, Args&&... args) {
290 134619 : MOZ_ASSERT(!p);
291 134619 : MOZ_ASSERT(keyNonZero(key));
292 :
293 134619 : if (p.isInlinePtr_) {
294 122157 : InlineEntry* addPtr = p.inlAddPtr_;
295 122157 : MOZ_ASSERT(addPtr == inlineEnd());
296 :
297 : // Switching to table mode before we add this pointer.
298 122157 : if (addPtr == inlineStart() + InlineEntries) {
299 516 : if (!switchToTable())
300 0 : return false;
301 : return table_.putNew(mozilla::Forward<KeyInput>(key),
302 516 : mozilla::Forward<Args>(args)...);
303 : }
304 :
305 121641 : MOZ_ASSERT(!p.found());
306 121641 : MOZ_ASSERT(uintptr_t(inlineEnd()) == uintptr_t(p.inlAddPtr_));
307 121641 : addPtr->update(mozilla::Forward<KeyInput>(key),
308 : mozilla::Forward<Args>(args)...);
309 121641 : ++inlCount_;
310 121641 : ++inlNext_;
311 121641 : return true;
312 : }
313 :
314 : return table_.add(p.tableAddPtr_,
315 : mozilla::Forward<KeyInput>(key),
316 12462 : mozilla::Forward<Args>(args)...);
317 : }
318 :
319 655 : void remove(Ptr& p) {
320 655 : MOZ_ASSERT(p);
321 655 : if (p.isInlinePtr_) {
322 655 : MOZ_ASSERT(inlCount_ > 0);
323 655 : MOZ_ASSERT(p.inlPtr_->key != nullptr);
324 655 : p.inlPtr_->key = nullptr;
325 655 : --inlCount_;
326 655 : return;
327 : }
328 0 : MOZ_ASSERT(table_.initialized() && usingTable());
329 0 : table_.remove(p.tablePtr_);
330 : }
331 :
332 : void remove(const Lookup& l) {
333 : if (Ptr p = lookup(l))
334 : remove(p);
335 : }
336 :
337 : class Range
338 : {
339 : friend class InlineTable;
340 :
341 : protected:
342 : TableRange tableRange_;
343 : InlineEntry* cur_;
344 : InlineEntry* end_;
345 : bool isInline_;
346 :
347 420 : explicit Range(TableRange r)
348 : : cur_(nullptr),
349 : end_(nullptr),
350 420 : isInline_(false)
351 : {
352 420 : tableRange_ = r;
353 420 : MOZ_ASSERT(!isInlineRange());
354 420 : }
355 :
356 40726 : Range(const InlineEntry* begin, const InlineEntry* end)
357 : : cur_(const_cast<InlineEntry*>(begin)),
358 : end_(const_cast<InlineEntry*>(end)),
359 40726 : isInline_(true)
360 : {
361 40726 : advancePastNulls(cur_);
362 40726 : MOZ_ASSERT(isInlineRange());
363 40726 : }
364 :
365 1065416 : bool assertInlineRangeInvariants() const {
366 1065416 : MOZ_ASSERT(uintptr_t(cur_) <= uintptr_t(end_));
367 1065416 : MOZ_ASSERT_IF(cur_ != end_, cur_->key != nullptr);
368 1065416 : return true;
369 : }
370 :
371 1242320 : bool isInlineRange() const {
372 1242320 : MOZ_ASSERT_IF(isInline_, assertInlineRangeInvariants());
373 1242320 : return isInline_;
374 : }
375 :
376 130897 : void advancePastNulls(InlineEntry* begin) {
377 130897 : InlineEntry* newCur = begin;
378 132941 : while (newCur < end_ && nullptr == newCur->key)
379 1022 : ++newCur;
380 130897 : MOZ_ASSERT(uintptr_t(newCur) <= uintptr_t(end_));
381 130897 : cur_ = newCur;
382 130897 : }
383 :
384 90171 : void bumpCurPtr() {
385 90171 : MOZ_ASSERT(isInlineRange());
386 90171 : advancePastNulls(cur_ + 1);
387 90171 : }
388 :
389 : public:
390 744940 : bool empty() const {
391 744940 : return isInlineRange() ? cur_ == end_ : tableRange_.empty();
392 : }
393 :
394 253702 : Entry front() {
395 253702 : MOZ_ASSERT(!empty());
396 253702 : if (isInlineRange())
397 205219 : return Entry(cur_);
398 48483 : return Entry(&tableRange_.front());
399 : }
400 :
401 112361 : void popFront() {
402 112361 : MOZ_ASSERT(!empty());
403 112361 : if (isInlineRange())
404 90171 : bumpCurPtr();
405 : else
406 22190 : tableRange_.popFront();
407 112361 : }
408 : };
409 :
410 41146 : Range all() const {
411 41146 : return usingTable() ? Range(table_.all()) : Range(inlineStart(), inlineEnd());
412 : }
413 : };
414 :
415 : } // namespace detail
416 :
417 : // A map with InlineEntries number of entries kept inline in an array.
418 : //
419 : // The Key type must be zeroable as zeros are used as tombstone keys.
420 : // The Value type must have a default constructor.
421 : //
422 : // The API is very much like HashMap's.
423 : template <typename Key,
424 : typename Value,
425 : size_t InlineEntries,
426 : typename HashPolicy = DefaultHasher<Key>,
427 : typename AllocPolicy = TempAllocPolicy>
428 23 : class InlineMap
429 : {
430 : using Map = HashMap<Key, Value, HashPolicy, AllocPolicy>;
431 :
432 2112 : struct InlineEntry
433 : {
434 : Key key;
435 : Value value;
436 :
437 : template <typename KeyInput, typename ValueInput>
438 121641 : void update(KeyInput&& key, ValueInput&& value) {
439 121641 : this->key = mozilla::Forward<KeyInput>(key);
440 121641 : this->value = mozilla::Forward<ValueInput>(value);
441 121641 : }
442 :
443 12384 : MOZ_MUST_USE bool moveTo(Map& map) {
444 12384 : return map.putNew(mozilla::Move(key), mozilla::Move(value));
445 : }
446 : };
447 :
448 : class Entry
449 : {
450 : using MapEntry = typename Map::Entry;
451 :
452 : MapEntry* mapEntry_;
453 : InlineEntry* inlineEntry_;
454 :
455 : public:
456 : Entry() = default;
457 :
458 81689 : explicit Entry(MapEntry* mapEntry)
459 : : mapEntry_(mapEntry),
460 81689 : inlineEntry_(nullptr)
461 81689 : { }
462 :
463 489255 : explicit Entry(InlineEntry* inlineEntry)
464 : : mapEntry_(nullptr),
465 489255 : inlineEntry_(inlineEntry)
466 489255 : { }
467 :
468 109970 : const Key& key() const {
469 109970 : MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_);
470 109970 : if (mapEntry_)
471 22064 : return mapEntry_->key();
472 87906 : return inlineEntry_->key;
473 : }
474 :
475 274198 : Value& value() {
476 274198 : MOZ_ASSERT(!!mapEntry_ != !!inlineEntry_);
477 274198 : if (mapEntry_)
478 44983 : return mapEntry_->value();
479 229215 : return inlineEntry_->value;
480 : }
481 : };
482 :
483 : using Impl = detail::InlineTable<InlineEntry, Entry,
484 : Map, HashPolicy, AllocPolicy,
485 : InlineEntries>;
486 :
487 : Impl impl_;
488 :
489 : public:
490 : using Table = Map;
491 : using Ptr = typename Impl::Ptr;
492 : using AddPtr = typename Impl::AddPtr;
493 : using Range = typename Impl::Range;
494 : using Lookup = typename HashPolicy::Lookup;
495 :
496 : static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries;
497 :
498 88 : explicit InlineMap(AllocPolicy a = AllocPolicy())
499 88 : : impl_(a)
500 88 : { }
501 :
502 114975 : size_t count() const {
503 114975 : return impl_.count();
504 : }
505 :
506 : bool empty() const {
507 : return impl_.empty();
508 : }
509 :
510 42096 : void clear() {
511 42096 : impl_.clear();
512 42096 : }
513 :
514 41146 : Range all() const {
515 41146 : return impl_.all();
516 : }
517 :
518 : MOZ_ALWAYS_INLINE
519 148336 : Ptr lookup(const Lookup& l) {
520 148336 : return impl_.lookup(l);
521 : }
522 :
523 : MOZ_ALWAYS_INLINE
524 : bool has(const Lookup& l) const {
525 : return const_cast<InlineMap*>(this)->lookup(l).found();
526 : }
527 :
528 : MOZ_ALWAYS_INLINE
529 168871 : AddPtr lookupForAdd(const Lookup& l) {
530 168871 : return impl_.lookupForAdd(l);
531 : }
532 :
533 : template <typename KeyInput, typename ValueInput>
534 : MOZ_ALWAYS_INLINE
535 134619 : MOZ_MUST_USE bool add(AddPtr& p, KeyInput&& key, ValueInput&& value) {
536 134619 : return impl_.add(p, mozilla::Forward<KeyInput>(key), mozilla::Forward<ValueInput>(value));
537 : }
538 :
539 : template <typename KeyInput, typename ValueInput>
540 : MOZ_MUST_USE bool put(KeyInput&& key, ValueInput&& value) {
541 : AddPtr p = lookupForAdd(key);
542 : if (p) {
543 : p->value() = mozilla::Forward<ValueInput>(value);
544 : return true;
545 : }
546 : return add(p, mozilla::Forward<KeyInput>(key), mozilla::Forward<ValueInput>(value));
547 : }
548 :
549 655 : void remove(Ptr& p) {
550 655 : impl_.remove(p);
551 655 : }
552 :
553 : void remove(const Lookup& l) {
554 : impl_.remove(l);
555 : }
556 : };
557 :
558 : // A set with InlineEntries number of entries kept inline in an array.
559 : //
560 : // The T type must be zeroable as zeros are used as tombstone keys.
561 : // The T type must have a default constructor.
562 : //
563 : // The API is very much like HashMap's.
564 : template <typename T,
565 : size_t InlineEntries,
566 : typename HashPolicy = DefaultHasher<T>,
567 : typename AllocPolicy = TempAllocPolicy>
568 : class InlineSet
569 : {
570 : using Set = HashSet<T, HashPolicy, AllocPolicy>;
571 :
572 : struct InlineEntry
573 : {
574 : T key;
575 :
576 : template <typename TInput>
577 : void update(TInput&& key) {
578 : this->key = mozilla::Forward<TInput>(key);
579 : }
580 :
581 : MOZ_MUST_USE bool moveTo(Set& set) {
582 : return set.putNew(mozilla::Move(key));
583 : }
584 : };
585 :
586 : class Entry
587 : {
588 : using SetEntry = typename Set::Entry;
589 :
590 : SetEntry* setEntry_;
591 : InlineEntry* inlineEntry_;
592 :
593 : public:
594 : Entry() = default;
595 :
596 : explicit Entry(const SetEntry* setEntry)
597 : : setEntry_(const_cast<SetEntry*>(setEntry)),
598 : inlineEntry_(nullptr)
599 : { }
600 :
601 : explicit Entry(InlineEntry* inlineEntry)
602 : : setEntry_(nullptr),
603 : inlineEntry_(inlineEntry)
604 : { }
605 :
606 : operator T() const {
607 : MOZ_ASSERT(!!setEntry_ != !!inlineEntry_);
608 : if (setEntry_)
609 : return *setEntry_;
610 : return inlineEntry_->key;
611 : }
612 : };
613 :
614 : using Impl = detail::InlineTable<InlineEntry, Entry,
615 : Set, HashPolicy, AllocPolicy,
616 : InlineEntries>;
617 :
618 : Impl impl_;
619 :
620 : public:
621 : using Table = Set;
622 : using Ptr = typename Impl::Ptr;
623 : using AddPtr = typename Impl::AddPtr;
624 : using Range = typename Impl::Range;
625 : using Lookup = typename HashPolicy::Lookup;
626 :
627 : static const size_t SizeOfInlineEntries = Impl::SizeOfInlineEntries;
628 :
629 : explicit InlineSet(AllocPolicy a = AllocPolicy())
630 : : impl_(a)
631 : { }
632 :
633 : size_t count() const {
634 : return impl_.count();
635 : }
636 :
637 : bool empty() const {
638 : return impl_.empty();
639 : }
640 :
641 : void clear() {
642 : impl_.clear();
643 : }
644 :
645 : Range all() const {
646 : return impl_.all();
647 : }
648 :
649 : MOZ_ALWAYS_INLINE
650 : Ptr lookup(const Lookup& l) {
651 : return impl_.lookup(l);
652 : }
653 :
654 : MOZ_ALWAYS_INLINE
655 : bool has(const Lookup& l) const {
656 : return const_cast<InlineSet*>(this)->lookup(l).found();
657 : }
658 :
659 : MOZ_ALWAYS_INLINE
660 : AddPtr lookupForAdd(const Lookup& l) {
661 : return impl_.lookupForAdd(l);
662 : }
663 :
664 : template <typename TInput>
665 : MOZ_ALWAYS_INLINE
666 : MOZ_MUST_USE bool add(AddPtr& p, TInput&& key) {
667 : return impl_.add(p, mozilla::Forward<TInput>(key));
668 : }
669 :
670 : template <typename TInput>
671 : MOZ_MUST_USE bool put(TInput&& key) {
672 : AddPtr p = lookupForAdd(key);
673 : return p ? true : add(p, mozilla::Forward<TInput>(key));
674 : }
675 :
676 : void remove(Ptr& p) {
677 : impl_.remove(p);
678 : }
679 :
680 : void remove(const Lookup& l) {
681 : impl_.remove(l);
682 : }
683 : };
684 :
685 : } // namespace js
686 :
687 : #endif // ds_InlineTable_h
|
