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