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 jit_InlineList_h
8 : #define jit_InlineList_h
9 :
10 : #include "jsutil.h"
11 :
12 : namespace js {
13 :
14 : template <typename T> class InlineForwardList;
15 : template <typename T> class InlineForwardListIterator;
16 :
17 : template <typename T>
18 : class InlineForwardListNode
19 : {
20 : public:
21 55031 : InlineForwardListNode() : next(nullptr)
22 55031 : { }
23 123608 : explicit InlineForwardListNode(InlineForwardListNode<T>* n) : next(n)
24 123608 : { }
25 :
26 : InlineForwardListNode(const InlineForwardListNode<T>&) = delete;
27 :
28 : protected:
29 : friend class InlineForwardList<T>;
30 : friend class InlineForwardListIterator<T>;
31 :
32 : InlineForwardListNode<T>* next;
33 : };
34 :
35 : template <typename T>
36 : class InlineForwardList : protected InlineForwardListNode<T>
37 : {
38 : friend class InlineForwardListIterator<T>;
39 :
40 : typedef InlineForwardListNode<T> Node;
41 :
42 : Node* tail_;
43 : #ifdef DEBUG
44 : int modifyCount_;
45 : #endif
46 :
47 17906 : InlineForwardList<T>* thisFromConstructor() {
48 17906 : return this;
49 : }
50 :
51 : public:
52 17906 : InlineForwardList()
53 17906 : : tail_(thisFromConstructor())
54 : {
55 : #ifdef DEBUG
56 17906 : modifyCount_ = 0;
57 : #endif
58 17906 : }
59 :
60 : public:
61 : typedef InlineForwardListIterator<T> iterator;
62 :
63 : public:
64 158027 : iterator begin() const {
65 158027 : return iterator(this);
66 : }
67 134 : iterator begin(Node* item) const {
68 134 : return iterator(this, item);
69 : }
70 40378 : iterator end() const {
71 40378 : return iterator(nullptr);
72 : }
73 4548 : void removeAt(iterator where) {
74 4548 : removeAfter(where.prev, where.iter);
75 4548 : }
76 40155 : void pushFront(Node* t) {
77 40155 : insertAfter(this, t);
78 40155 : }
79 15556 : void pushBack(Node* t) {
80 15556 : MOZ_ASSERT(t->next == nullptr);
81 : #ifdef DEBUG
82 15556 : modifyCount_++;
83 : #endif
84 15556 : tail_->next = t;
85 15556 : tail_ = t;
86 15556 : }
87 18091 : T* popFront() {
88 18091 : MOZ_ASSERT(!empty());
89 18091 : T* result = static_cast<T*>(this->next);
90 18091 : removeAfter(this, result);
91 18091 : return result;
92 : }
93 21090 : T* back() const {
94 21090 : MOZ_ASSERT(!empty());
95 21090 : return static_cast<T*>(tail_);
96 : }
97 41167 : void insertAfter(Node* at, Node* item) {
98 41167 : MOZ_ASSERT(item->next == nullptr);
99 : #ifdef DEBUG
100 41167 : modifyCount_++;
101 : #endif
102 41167 : if (at == tail_)
103 15255 : tail_ = item;
104 41167 : item->next = at->next;
105 41167 : at->next = item;
106 41167 : }
107 22639 : void removeAfter(Node* at, Node* item) {
108 : #ifdef DEBUG
109 22639 : modifyCount_++;
110 : #endif
111 22639 : if (item == tail_)
112 4708 : tail_ = at;
113 22639 : MOZ_ASSERT(at->next == item);
114 22639 : at->next = item->next;
115 22639 : item->next = nullptr;
116 22639 : }
117 9225 : void removeAndIncrement(iterator &where) {
118 : // Do not change modifyCount_ here. The iterator can still be used
119 : // after calling this method, unlike the other methods that modify
120 : // the list.
121 9225 : Node* item = where.iter;
122 9225 : where.iter = item->next;
123 9225 : if (item == tail_)
124 1193 : tail_ = where.prev;
125 9225 : MOZ_ASSERT(where.prev->next == item);
126 9225 : where.prev->next = where.iter;
127 9225 : item->next = nullptr;
128 9225 : }
129 : void splitAfter(Node* at, InlineForwardList<T>* to) {
130 : MOZ_ASSERT(to->empty());
131 : if (!at)
132 : at = this;
133 : if (at == tail_)
134 : return;
135 : #ifdef DEBUG
136 : modifyCount_++;
137 : #endif
138 : to->next = at->next;
139 : to->tail_ = tail_;
140 : tail_ = at;
141 : at->next = nullptr;
142 : }
143 89802 : bool empty() const {
144 89802 : return tail_ == this;
145 : }
146 : void clear() {
147 : this->next = nullptr;
148 : tail_ = this;
149 : #ifdef DEBUG
150 : modifyCount_ = 0;
151 : #endif
152 : }
153 : };
154 :
155 : template <typename T>
156 : class InlineForwardListIterator
157 : {
158 : private:
159 : friend class InlineForwardList<T>;
160 :
161 : typedef InlineForwardListNode<T> Node;
162 :
163 198405 : explicit InlineForwardListIterator<T>(const InlineForwardList<T>* owner)
164 : : prev(const_cast<Node*>(static_cast<const Node*>(owner))),
165 198405 : iter(owner ? owner->next : nullptr)
166 : #ifdef DEBUG
167 : , owner_(owner),
168 396810 : modifyCount_(owner ? owner->modifyCount_ : 0)
169 : #endif
170 198405 : { }
171 :
172 134 : InlineForwardListIterator<T>(const InlineForwardList<T>* owner, Node* node)
173 : : prev(nullptr),
174 : iter(node)
175 : #ifdef DEBUG
176 : , owner_(owner),
177 134 : modifyCount_(owner ? owner->modifyCount_ : 0)
178 : #endif
179 134 : { }
180 :
181 : public:
182 265946 : InlineForwardListIterator<T> & operator ++() {
183 265946 : MOZ_ASSERT(modifyCount_ == owner_->modifyCount_);
184 265946 : prev = iter;
185 265946 : iter = iter->next;
186 265946 : return *this;
187 : }
188 259210 : InlineForwardListIterator<T> operator ++(int) {
189 259210 : InlineForwardListIterator<T> old(*this);
190 259210 : operator++();
191 259210 : return old;
192 : }
193 633646 : T * operator*() const {
194 633646 : MOZ_ASSERT(modifyCount_ == owner_->modifyCount_);
195 633646 : return static_cast<T*>(iter);
196 : }
197 589852 : T * operator ->() const {
198 589852 : MOZ_ASSERT(modifyCount_ == owner_->modifyCount_);
199 589852 : return static_cast<T*>(iter);
200 : }
201 44704 : bool operator !=(const InlineForwardListIterator<T>& where) const {
202 44704 : return iter != where.iter;
203 : }
204 1 : bool operator ==(const InlineForwardListIterator<T>& where) const {
205 1 : return iter == where.iter;
206 : }
207 370376 : explicit operator bool() const {
208 370376 : return iter != nullptr;
209 : }
210 :
211 : private:
212 : Node* prev;
213 : Node* iter;
214 :
215 : #ifdef DEBUG
216 : const InlineForwardList<T>* owner_;
217 : int modifyCount_;
218 : #endif
219 : };
220 :
221 : template <typename T> class InlineList;
222 : template <typename T> class InlineListIterator;
223 : template <typename T> class InlineListReverseIterator;
224 :
225 : template <typename T>
226 : class InlineListNode : public InlineForwardListNode<T>
227 : {
228 : public:
229 72376 : InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr)
230 72376 : { }
231 50939 : InlineListNode(InlineListNode<T>* n, InlineListNode<T>* p)
232 : : InlineForwardListNode<T>(n),
233 50939 : prev(p)
234 50939 : { }
235 :
236 : // Move constructor. Nodes may be moved without being removed from their
237 : // containing lists. For example, this allows list nodes to be safely
238 : // stored in a resizable Vector -- when the Vector resizes, the new storage
239 : // is initialized by this move constructor. |other| is a reference to the
240 : // old node which the |this| node here is replacing.
241 294 : InlineListNode(InlineListNode<T>&& other)
242 294 : : InlineForwardListNode<T>(other.next)
243 : {
244 294 : InlineListNode<T>* newNext = static_cast<InlineListNode<T>*>(other.next);
245 294 : InlineListNode<T>* newPrev = other.prev;
246 294 : prev = newPrev;
247 :
248 : // Update the pointers in the adjacent nodes to point to this node's new
249 : // location.
250 294 : newNext->prev = this;
251 294 : newPrev->next = this;
252 294 : }
253 :
254 : InlineListNode(const InlineListNode<T>&) = delete;
255 : void operator=(const InlineListNode<T>&) = delete;
256 :
257 392 : bool isInList() {
258 392 : return prev != nullptr && this->next != nullptr;
259 : }
260 :
261 : protected:
262 : friend class InlineList<T>;
263 : friend class InlineListIterator<T>;
264 : friend class InlineListReverseIterator<T>;
265 :
266 : InlineListNode<T>* prev;
267 : };
268 :
269 : template <typename T>
270 : class InlineList : protected InlineListNode<T>
271 : {
272 : typedef InlineListNode<T> Node;
273 :
274 : public:
275 50939 : InlineList() : InlineListNode<T>(this, this)
276 50939 : { }
277 :
278 : public:
279 : typedef InlineListIterator<T> iterator;
280 : typedef InlineListReverseIterator<T> reverse_iterator;
281 :
282 : public:
283 982191 : iterator begin() const {
284 982191 : return iterator(static_cast<Node*>(this->next));
285 : }
286 14668 : iterator begin(Node* t) const {
287 14668 : return iterator(t);
288 : }
289 4055195 : iterator end() const {
290 4055195 : return iterator(this);
291 : }
292 1059417 : reverse_iterator rbegin() const {
293 1059417 : return reverse_iterator(this->prev);
294 : }
295 19838 : reverse_iterator rbegin(Node* t) const {
296 19838 : return reverse_iterator(t);
297 : }
298 138959 : reverse_iterator rend() const {
299 138959 : return reverse_iterator(this);
300 : }
301 2208 : void pushFront(Node* t) {
302 2208 : insertAfter(this, t);
303 2208 : }
304 141469 : void pushFrontUnchecked(Node* t) {
305 141469 : insertAfterUnchecked(this, t);
306 141469 : }
307 67541 : void pushBack(Node* t) {
308 67541 : insertBefore(this, t);
309 67541 : }
310 : void pushBackUnchecked(Node* t) {
311 : insertBeforeUnchecked(this, t);
312 : }
313 : T* popFront() {
314 : MOZ_ASSERT(!empty());
315 : T* t = static_cast<T*>(this->next);
316 : remove(t);
317 : return t;
318 : }
319 38171 : T* popBack() {
320 38171 : MOZ_ASSERT(!empty());
321 38171 : T* t = static_cast<T*>(this->prev);
322 38171 : remove(t);
323 38171 : return t;
324 : }
325 19231 : T* peekBack() const {
326 19231 : iterator iter = end();
327 19231 : iter--;
328 19231 : return *iter;
329 : }
330 69302 : void insertBefore(Node* at, Node* item) {
331 69302 : MOZ_ASSERT(item->prev == nullptr);
332 69302 : MOZ_ASSERT(item->next == nullptr);
333 69302 : insertBeforeUnchecked(at, item);
334 69302 : }
335 69302 : void insertBeforeUnchecked(Node* at, Node* item) {
336 69302 : Node* atPrev = at->prev;
337 69302 : item->next = at;
338 69302 : item->prev = atPrev;
339 69302 : atPrev->next = item;
340 69302 : at->prev = item;
341 69302 : }
342 2258 : void insertAfter(Node* at, Node* item) {
343 2258 : MOZ_ASSERT(item->prev == nullptr);
344 2258 : MOZ_ASSERT(item->next == nullptr);
345 2258 : insertAfterUnchecked(at, item);
346 2258 : }
347 143727 : void insertAfterUnchecked(Node* at, Node* item) {
348 143727 : Node* atNext = static_cast<Node*>(at->next);
349 143727 : item->next = atNext;
350 143727 : item->prev = at;
351 143727 : atNext->prev = item;
352 143727 : at->next = item;
353 143727 : }
354 62488 : void remove(Node* t) {
355 62488 : Node* tNext = static_cast<Node*>(t->next);
356 62488 : Node* tPrev = t->prev;
357 62488 : tPrev->next = tNext;
358 62488 : tNext->prev = tPrev;
359 62488 : t->next = nullptr;
360 62488 : t->prev = nullptr;
361 62488 : }
362 : // Remove |old| from the list and insert |now| in its place.
363 473 : void replace(Node* old, Node* now) {
364 473 : MOZ_ASSERT(now->next == nullptr && now->prev == nullptr);
365 473 : Node* listNext = static_cast<Node*>(old->next);
366 473 : Node* listPrev = old->prev;
367 473 : listPrev->next = now;
368 473 : listNext->prev = now;
369 473 : now->next = listNext;
370 473 : now->prev = listPrev;
371 473 : old->next = nullptr;
372 473 : old->prev = nullptr;
373 473 : }
374 2850 : void clear() {
375 2850 : this->next = this->prev = this;
376 2850 : }
377 747435 : bool empty() const {
378 747435 : return begin() == end();
379 : }
380 2173 : void takeElements(InlineList& l) {
381 2173 : MOZ_ASSERT(&l != this, "cannot takeElements from this");
382 2173 : Node* lprev = l.prev;
383 2173 : static_cast<Node*>(l.next)->prev = this;
384 2173 : lprev->next = this->next;
385 2173 : static_cast<Node*>(this->next)->prev = l.prev;
386 2173 : this->next = l.next;
387 2173 : l.clear();
388 2173 : }
389 : };
390 :
391 : template <typename T>
392 : class InlineListIterator
393 : {
394 : private:
395 : friend class InlineList<T>;
396 :
397 : typedef InlineListNode<T> Node;
398 :
399 5051777 : explicit InlineListIterator(const Node* iter)
400 5051777 : : iter(const_cast<Node*>(iter))
401 5051777 : { }
402 :
403 : public:
404 1238828 : InlineListIterator<T> & operator ++() {
405 1238828 : iter = static_cast<Node*>(iter->next);
406 1238828 : return *this;
407 : }
408 1019940 : InlineListIterator<T> operator ++(int) {
409 1019940 : InlineListIterator<T> old(*this);
410 1019940 : operator++();
411 1019940 : return old;
412 : }
413 19231 : InlineListIterator<T> & operator --() {
414 19231 : iter = iter->prev;
415 19231 : return *this;
416 : }
417 19231 : InlineListIterator<T> operator --(int) {
418 19231 : InlineListIterator<T> old(*this);
419 19231 : operator--();
420 19231 : return old;
421 : }
422 3312843 : T * operator*() const {
423 3312843 : return static_cast<T*>(iter);
424 : }
425 950097 : T * operator ->() const {
426 950097 : return static_cast<T*>(iter);
427 : }
428 3372510 : bool operator !=(const InlineListIterator<T>& where) const {
429 3372510 : return iter != where.iter;
430 : }
431 748475 : bool operator ==(const InlineListIterator<T>& where) const {
432 748475 : return iter == where.iter;
433 : }
434 :
435 : private:
436 : Node* iter;
437 : };
438 :
439 : template <typename T>
440 : class InlineListReverseIterator
441 : {
442 : private:
443 : friend class InlineList<T>;
444 :
445 : typedef InlineListNode<T> Node;
446 :
447 1218212 : explicit InlineListReverseIterator(const Node* iter)
448 1218212 : : iter(const_cast<Node*>(iter))
449 1218212 : { }
450 :
451 : public:
452 129043 : InlineListReverseIterator<T> & operator ++() {
453 129043 : iter = iter->prev;
454 129043 : return *this;
455 : }
456 127336 : InlineListReverseIterator<T> operator ++(int) {
457 127336 : InlineListReverseIterator<T> old(*this);
458 127336 : operator++();
459 127336 : return old;
460 : }
461 0 : InlineListReverseIterator<T> & operator --() {
462 0 : iter = static_cast<Node*>(iter->next);
463 0 : return *this;
464 : }
465 : InlineListReverseIterator<T> operator --(int) {
466 : InlineListReverseIterator<T> old(*this);
467 : operator--();
468 : return old;
469 : }
470 136195 : T * operator*() {
471 136195 : return static_cast<T*>(iter);
472 : }
473 1127683 : T * operator ->() {
474 1127683 : return static_cast<T*>(iter);
475 : }
476 138790 : bool operator !=(const InlineListReverseIterator<T>& where) const {
477 138790 : return iter != where.iter;
478 : }
479 173 : bool operator ==(const InlineListReverseIterator<T>& where) const {
480 173 : return iter == where.iter;
481 : }
482 :
483 : private:
484 : Node* iter;
485 : };
486 :
487 : /* This list type is more or less exactly an InlineForwardList without a sentinel
488 : * node. It is useful in cases where you are doing algorithms that deal with many
489 : * merging singleton lists, rather than often empty ones.
490 : */
491 : template <typename T> class InlineConcatListIterator;
492 : template <typename T>
493 : class InlineConcatList
494 : {
495 : private:
496 : typedef InlineConcatList<T> Node;
497 :
498 : InlineConcatList<T>* thisFromConstructor() {
499 : return this;
500 : }
501 :
502 : public:
503 : InlineConcatList() : next(nullptr), tail(thisFromConstructor())
504 : { }
505 :
506 : typedef InlineConcatListIterator<T> iterator;
507 :
508 : iterator begin() const {
509 : return iterator(this);
510 : }
511 :
512 : iterator end() const {
513 : return iterator(nullptr);
514 : }
515 :
516 : void append(InlineConcatList<T>* adding)
517 : {
518 : MOZ_ASSERT(tail);
519 : MOZ_ASSERT(!tail->next);
520 : MOZ_ASSERT(adding->tail);
521 : MOZ_ASSERT(!adding->tail->next);
522 :
523 : tail->next = adding;
524 : tail = adding->tail;
525 : adding->tail = nullptr;
526 : }
527 :
528 : protected:
529 : friend class InlineConcatListIterator<T>;
530 : Node* next;
531 : Node* tail;
532 : };
533 :
534 : template <typename T>
535 : class InlineConcatListIterator
536 : {
537 : private:
538 : friend class InlineConcatList<T>;
539 :
540 : typedef InlineConcatList<T> Node;
541 :
542 : explicit InlineConcatListIterator(const Node* iter)
543 : : iter(const_cast<Node*>(iter))
544 : { }
545 :
546 : public:
547 : InlineConcatListIterator<T> & operator ++() {
548 : iter = static_cast<Node*>(iter->next);
549 : return *this;
550 : }
551 : InlineConcatListIterator<T> operator ++(int) {
552 : InlineConcatListIterator<T> old(*this);
553 : operator++();
554 : return old;
555 : }
556 : T * operator*() const {
557 : return static_cast<T*>(iter);
558 : }
559 : T * operator ->() const {
560 : return static_cast<T*>(iter);
561 : }
562 : bool operator !=(const InlineConcatListIterator<T>& where) const {
563 : return iter != where.iter;
564 : }
565 : bool operator ==(const InlineConcatListIterator<T>& where) const {
566 : return iter == where.iter;
567 : }
568 :
569 : private:
570 : Node* iter;
571 : };
572 :
573 : template <typename T> class InlineSpaghettiStack;
574 : template <typename T> class InlineSpaghettiStackNode;
575 : template <typename T> class InlineSpaghettiStackIterator;
576 :
577 : template <typename T>
578 : class InlineSpaghettiStackNode : public InlineForwardListNode<T>
579 : {
580 : typedef InlineForwardListNode<T> Parent;
581 :
582 : public:
583 9083 : InlineSpaghettiStackNode() : Parent()
584 9083 : { }
585 :
586 : explicit InlineSpaghettiStackNode(InlineSpaghettiStackNode<T>* n)
587 : : Parent(n)
588 : { }
589 :
590 : InlineSpaghettiStackNode(const InlineSpaghettiStackNode<T>&) = delete;
591 :
592 : protected:
593 : friend class InlineSpaghettiStack<T>;
594 : friend class InlineSpaghettiStackIterator<T>;
595 : };
596 :
597 : template <typename T>
598 : class InlineSpaghettiStack : protected InlineSpaghettiStackNode<T>
599 : {
600 : friend class InlineSpaghettiStackIterator<T>;
601 :
602 : typedef InlineSpaghettiStackNode<T> Node;
603 :
604 : public:
605 8996 : InlineSpaghettiStack()
606 8996 : { }
607 :
608 : public:
609 : typedef InlineSpaghettiStackIterator<T> iterator;
610 :
611 : public:
612 2032 : iterator begin() const {
613 2032 : return iterator(this);
614 : }
615 213 : iterator end() const {
616 213 : return iterator(nullptr);
617 : }
618 :
619 87 : void push(Node* t) {
620 87 : MOZ_ASSERT(t->next == nullptr);
621 87 : t->next = this->next;
622 87 : this->next = t;
623 87 : }
624 :
625 571 : void copy(const InlineSpaghettiStack<T>& stack) {
626 571 : this->next = stack.next;
627 571 : }
628 :
629 653 : bool empty() const {
630 653 : return this->next == nullptr;
631 : }
632 : };
633 :
634 : template <typename T>
635 : class InlineSpaghettiStackIterator
636 : {
637 : private:
638 : friend class InlineSpaghettiStack<T>;
639 :
640 : typedef InlineSpaghettiStackNode<T> Node;
641 :
642 2245 : explicit InlineSpaghettiStackIterator<T>(const InlineSpaghettiStack<T>* owner)
643 2245 : : iter(owner ? static_cast<Node*>(owner->next) : nullptr)
644 2245 : { }
645 :
646 : public:
647 681 : InlineSpaghettiStackIterator<T> & operator ++() {
648 681 : iter = static_cast<Node*>(iter->next);
649 681 : return *this;
650 : }
651 : InlineSpaghettiStackIterator<T> operator ++(int) {
652 : InlineSpaghettiStackIterator<T> old(*this);
653 : operator++();
654 : return old;
655 : }
656 : T* operator*() const {
657 : return static_cast<T*>(iter);
658 : }
659 751 : T* operator ->() const {
660 751 : return static_cast<T*>(iter);
661 : }
662 311 : bool operator !=(const InlineSpaghettiStackIterator<T>& where) const {
663 311 : return iter != where.iter;
664 : }
665 583 : bool operator ==(const InlineSpaghettiStackIterator<T>& where) const {
666 583 : return iter == where.iter;
667 : }
668 :
669 : private:
670 : Node* iter;
671 : };
672 :
673 : } // namespace js
674 :
675 : #endif /* jit_InlineList_h */
|
