Source code

Revision control

Other Tools

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