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/. */
7 #ifndef jit_InlineList_h
8 #define jit_InlineList_h
10 #include "mozilla/Assertions.h"
15 class InlineForwardList
;
17 class InlineForwardListIterator
;
20 class InlineForwardListNode
{
22 InlineForwardListNode() : next(nullptr) {}
23 explicit InlineForwardListNode(InlineForwardListNode
<T
>* n
) : next(n
) {}
25 InlineForwardListNode(const InlineForwardListNode
<T
>&) = delete;
28 friend class InlineForwardList
<T
>;
29 friend class InlineForwardListIterator
<T
>;
31 InlineForwardListNode
<T
>* next
;
35 class InlineForwardList
: protected InlineForwardListNode
<T
> {
36 friend class InlineForwardListIterator
<T
>;
38 using Node
= InlineForwardListNode
<T
>;
45 InlineForwardList
<T
>* thisFromConstructor() { return this; }
48 InlineForwardList() : tail_(thisFromConstructor()) {
55 using iterator
= InlineForwardListIterator
<T
>;
58 iterator
begin() const { return iterator(this); }
59 iterator
begin(Node
* item
) const { return iterator(this, item
); }
60 iterator
end() const { return iterator(nullptr); }
61 void removeAt(iterator where
) { removeAfter(where
.prev
, where
.iter
); }
62 void pushFront(Node
* t
) { insertAfter(this, t
); }
63 void pushBack(Node
* t
) {
64 MOZ_ASSERT(t
->next
== nullptr);
73 T
* result
= static_cast<T
*>(this->next
);
74 removeAfter(this, result
);
79 return static_cast<T
*>(tail_
);
81 void insertAfter(Node
* at
, Node
* item
) {
82 MOZ_ASSERT(item
->next
== nullptr);
89 item
->next
= at
->next
;
92 void removeAfter(Node
* at
, Node
* item
) {
99 MOZ_ASSERT(at
->next
== item
);
100 at
->next
= item
->next
;
101 item
->next
= nullptr;
103 void removeAndIncrement(iterator
& where
) {
104 // Do not change modifyCount_ here. The iterator can still be used
105 // after calling this method, unlike the other methods that modify
107 Node
* item
= where
.iter
;
108 where
.iter
= item
->next
;
112 MOZ_ASSERT(where
.prev
->next
== item
);
113 where
.prev
->next
= where
.iter
;
114 item
->next
= nullptr;
116 void splitAfter(Node
* at
, InlineForwardList
<T
>* to
) {
117 MOZ_ASSERT(to
->empty());
132 bool empty() const { return tail_
== this; }
134 this->next
= nullptr;
142 template <typename T
>
143 class InlineForwardListIterator
{
145 friend class InlineForwardList
<T
>;
147 using Node
= InlineForwardListNode
<T
>;
149 explicit InlineForwardListIterator(const InlineForwardList
<T
>* owner
)
150 : prev(const_cast<Node
*>(static_cast<const Node
*>(owner
))),
151 iter(owner
? owner
->next
: nullptr)
155 modifyCount_(owner
? owner
->modifyCount_
: 0)
160 InlineForwardListIterator(const InlineForwardList
<T
>* owner
, Node
* node
)
166 modifyCount_(owner
? owner
->modifyCount_
: 0)
172 InlineForwardListIterator
<T
>& operator++() {
173 MOZ_ASSERT(modifyCount_
== owner_
->modifyCount_
);
178 InlineForwardListIterator
<T
> operator++(int) {
179 InlineForwardListIterator
<T
> old(*this);
183 T
* operator*() const {
184 MOZ_ASSERT(modifyCount_
== owner_
->modifyCount_
);
185 return static_cast<T
*>(iter
);
187 T
* operator->() const {
188 MOZ_ASSERT(modifyCount_
== owner_
->modifyCount_
);
189 return static_cast<T
*>(iter
);
191 bool operator!=(const InlineForwardListIterator
<T
>& where
) const {
192 return iter
!= where
.iter
;
194 bool operator==(const InlineForwardListIterator
<T
>& where
) const {
195 return iter
== where
.iter
;
197 explicit operator bool() const { return iter
!= nullptr; }
204 const InlineForwardList
<T
>* owner_
;
209 template <typename T
>
211 template <typename T
>
212 class InlineListIterator
;
213 template <typename T
>
214 class InlineListReverseIterator
;
216 template <typename T
>
217 class InlineListNode
: public InlineForwardListNode
<T
> {
219 InlineListNode() : InlineForwardListNode
<T
>(nullptr), prev(nullptr) {}
220 InlineListNode(InlineListNode
<T
>* n
, InlineListNode
<T
>* p
)
221 : InlineForwardListNode
<T
>(n
), prev(p
) {}
223 // Move constructor. Nodes may be moved without being removed from their
224 // containing lists. For example, this allows list nodes to be safely
225 // stored in a resizable Vector -- when the Vector resizes, the new storage
226 // is initialized by this move constructor. |other| is a reference to the
227 // old node which the |this| node here is replacing.
228 InlineListNode(InlineListNode
<T
>&& other
)
229 : InlineForwardListNode
<T
>(other
.next
) {
230 InlineListNode
<T
>* newNext
= static_cast<InlineListNode
<T
>*>(other
.next
);
231 InlineListNode
<T
>* newPrev
= other
.prev
;
234 // Update the pointers in the adjacent nodes to point to this node's new
236 newNext
->prev
= this;
237 newPrev
->next
= this;
240 InlineListNode(const InlineListNode
<T
>&) = delete;
241 void operator=(const InlineListNode
<T
>&) = delete;
243 bool isInList() { return prev
!= nullptr && this->next
!= nullptr; }
246 friend class InlineList
<T
>;
247 friend class InlineListIterator
<T
>;
248 friend class InlineListReverseIterator
<T
>;
250 InlineListNode
<T
>* prev
;
253 template <typename T
>
254 class InlineList
: protected InlineListNode
<T
> {
255 using Node
= InlineListNode
<T
>;
258 InlineList() : InlineListNode
<T
>(this, this) {}
261 using iterator
= InlineListIterator
<T
>;
262 using reverse_iterator
= InlineListReverseIterator
<T
>;
265 iterator
begin() const { return iterator(static_cast<Node
*>(this->next
)); }
266 iterator
begin(Node
* t
) const { return iterator(t
); }
267 iterator
end() const { return iterator(this); }
268 reverse_iterator
rbegin() const { return reverse_iterator(this->prev
); }
269 reverse_iterator
rbegin(Node
* t
) const { return reverse_iterator(t
); }
270 reverse_iterator
rend() const { return reverse_iterator(this); }
271 void pushFront(Node
* t
) { insertAfter(this, t
); }
272 void pushFrontUnchecked(Node
* t
) { insertAfterUnchecked(this, t
); }
273 void pushBack(Node
* t
) { insertBefore(this, t
); }
274 void pushBackUnchecked(Node
* t
) { insertBeforeUnchecked(this, t
); }
276 MOZ_ASSERT(!empty());
277 T
* t
= static_cast<T
*>(this->next
);
282 MOZ_ASSERT(!empty());
283 T
* t
= static_cast<T
*>(this->prev
);
287 T
* peekBack() const {
288 iterator iter
= end();
292 void insertBefore(Node
* at
, Node
* item
) {
293 MOZ_ASSERT(item
->prev
== nullptr);
294 MOZ_ASSERT(item
->next
== nullptr);
295 insertBeforeUnchecked(at
, item
);
297 void insertBeforeUnchecked(Node
* at
, Node
* item
) {
298 Node
* atPrev
= at
->prev
;
304 void insertAfter(Node
* at
, Node
* item
) {
305 MOZ_ASSERT(item
->prev
== nullptr);
306 MOZ_ASSERT(item
->next
== nullptr);
307 insertAfterUnchecked(at
, item
);
309 void insertAfterUnchecked(Node
* at
, Node
* item
) {
310 Node
* atNext
= static_cast<Node
*>(at
->next
);
316 void remove(Node
* t
) {
317 Node
* tNext
= static_cast<Node
*>(t
->next
);
318 Node
* tPrev
= t
->prev
;
324 // Remove |old| from the list and insert |now| in its place.
325 void replace(Node
* old
, Node
* now
) {
326 MOZ_ASSERT(now
->next
== nullptr && now
->prev
== nullptr);
327 Node
* listNext
= static_cast<Node
*>(old
->next
);
328 Node
* listPrev
= old
->prev
;
329 listPrev
->next
= now
;
330 listNext
->prev
= now
;
331 now
->next
= listNext
;
332 now
->prev
= listPrev
;
336 void clear() { this->next
= this->prev
= this; }
337 bool empty() const { return begin() == end(); }
338 void takeElements(InlineList
& l
) {
339 MOZ_ASSERT(&l
!= this, "cannot takeElements from this");
340 Node
* lprev
= l
.prev
;
341 static_cast<Node
*>(l
.next
)->prev
= this;
342 lprev
->next
= this->next
;
343 static_cast<Node
*>(this->next
)->prev
= l
.prev
;
349 template <typename T
>
350 class InlineListIterator
{
352 friend class InlineList
<T
>;
354 using Node
= InlineListNode
<T
>;
356 explicit InlineListIterator(const Node
* iter
)
357 : iter(const_cast<Node
*>(iter
)) {}
360 InlineListIterator
<T
>& operator++() {
361 iter
= static_cast<Node
*>(iter
->next
);
364 InlineListIterator
<T
> operator++(int) {
365 InlineListIterator
<T
> old(*this);
369 InlineListIterator
<T
>& operator--() {
373 InlineListIterator
<T
> operator--(int) {
374 InlineListIterator
<T
> old(*this);
378 T
* operator*() const { return static_cast<T
*>(iter
); }
379 T
* operator->() const { return static_cast<T
*>(iter
); }
380 bool operator!=(const InlineListIterator
<T
>& where
) const {
381 return iter
!= where
.iter
;
383 bool operator==(const InlineListIterator
<T
>& where
) const {
384 return iter
== where
.iter
;
391 template <typename T
>
392 class InlineListReverseIterator
{
394 friend class InlineList
<T
>;
396 using Node
= InlineListNode
<T
>;
398 explicit InlineListReverseIterator(const Node
* iter
)
399 : iter(const_cast<Node
*>(iter
)) {}
402 InlineListReverseIterator
<T
>& operator++() {
406 InlineListReverseIterator
<T
> operator++(int) {
407 InlineListReverseIterator
<T
> old(*this);
411 InlineListReverseIterator
<T
>& operator--() {
412 iter
= static_cast<Node
*>(iter
->next
);
415 InlineListReverseIterator
<T
> operator--(int) {
416 InlineListReverseIterator
<T
> old(*this);
420 T
* operator*() { return static_cast<T
*>(iter
); }
421 T
* operator->() { return static_cast<T
*>(iter
); }
422 bool operator!=(const InlineListReverseIterator
<T
>& where
) const {
423 return iter
!= where
.iter
;
425 bool operator==(const InlineListReverseIterator
<T
>& where
) const {
426 return iter
== where
.iter
;
433 // This list type is more or less exactly an InlineForwardList without a
434 // sentinel node. It is useful in cases where you are doing algorithms that deal
435 // with many merging singleton lists, rather than often empty ones.
436 template <typename T
>
437 class InlineConcatListIterator
;
438 template <typename T
>
439 class InlineConcatList
{
441 using Node
= InlineConcatList
<T
>;
443 InlineConcatList
<T
>* thisFromConstructor() { return this; }
446 InlineConcatList() : next(nullptr), tail(thisFromConstructor()) {}
448 using iterator
= InlineConcatListIterator
<T
>;
450 iterator
begin() const { return iterator(this); }
452 iterator
end() const { return iterator(nullptr); }
454 void append(InlineConcatList
<T
>* adding
) {
456 MOZ_ASSERT(!tail
->next
);
457 MOZ_ASSERT(adding
->tail
);
458 MOZ_ASSERT(!adding
->tail
->next
);
462 adding
->tail
= nullptr;
466 friend class InlineConcatListIterator
<T
>;
471 template <typename T
>
472 class InlineConcatListIterator
{
474 friend class InlineConcatList
<T
>;
476 using Node
= InlineConcatList
<T
>;
478 explicit InlineConcatListIterator(const Node
* iter
)
479 : iter(const_cast<Node
*>(iter
)) {}
482 InlineConcatListIterator
<T
>& operator++() {
483 iter
= static_cast<Node
*>(iter
->next
);
486 InlineConcatListIterator
<T
> operator++(int) {
487 InlineConcatListIterator
<T
> old(*this);
491 T
* operator*() const { return static_cast<T
*>(iter
); }
492 T
* operator->() const { return static_cast<T
*>(iter
); }
493 bool operator!=(const InlineConcatListIterator
<T
>& where
) const {
494 return iter
!= where
.iter
;
496 bool operator==(const InlineConcatListIterator
<T
>& where
) const {
497 return iter
== where
.iter
;
504 template <typename T
>
505 class InlineSpaghettiStack
;
506 template <typename T
>
507 class InlineSpaghettiStackNode
;
508 template <typename T
>
509 class InlineSpaghettiStackIterator
;
511 template <typename T
>
512 class InlineSpaghettiStackNode
: public InlineForwardListNode
<T
> {
513 using Parent
= InlineForwardListNode
<T
>;
516 InlineSpaghettiStackNode() : Parent() {}
518 explicit InlineSpaghettiStackNode(InlineSpaghettiStackNode
<T
>* n
)
521 InlineSpaghettiStackNode(const InlineSpaghettiStackNode
<T
>&) = delete;
524 friend class InlineSpaghettiStack
<T
>;
525 friend class InlineSpaghettiStackIterator
<T
>;
528 template <typename T
>
529 class InlineSpaghettiStack
: protected InlineSpaghettiStackNode
<T
> {
530 friend class InlineSpaghettiStackIterator
<T
>;
532 using Node
= InlineSpaghettiStackNode
<T
>;
535 InlineSpaghettiStack() = default;
538 using iterator
= InlineSpaghettiStackIterator
<T
>;
541 iterator
begin() const { return iterator(this); }
542 iterator
end() const { return iterator(nullptr); }
545 MOZ_ASSERT(t
->next
== nullptr);
546 t
->next
= this->next
;
550 void copy(const InlineSpaghettiStack
<T
>& stack
) { this->next
= stack
.next
; }
552 bool empty() const { return this->next
== nullptr; }
555 template <typename T
>
556 class InlineSpaghettiStackIterator
{
558 friend class InlineSpaghettiStack
<T
>;
560 using Node
= InlineSpaghettiStackNode
<T
>;
562 explicit InlineSpaghettiStackIterator(const InlineSpaghettiStack
<T
>* owner
)
563 : iter(owner
? static_cast<Node
*>(owner
->next
) : nullptr) {}
566 InlineSpaghettiStackIterator
<T
>& operator++() {
567 iter
= static_cast<Node
*>(iter
->next
);
570 InlineSpaghettiStackIterator
<T
> operator++(int) {
571 InlineSpaghettiStackIterator
<T
> old(*this);
575 T
* operator*() const { return static_cast<T
*>(iter
); }
576 T
* operator->() const { return static_cast<T
*>(iter
); }
577 bool operator!=(const InlineSpaghettiStackIterator
<T
>& where
) const {
578 return iter
!= where
.iter
;
580 bool operator==(const InlineSpaghettiStackIterator
<T
>& where
) const {
581 return iter
== where
.iter
;
590 #endif /* jit_InlineList_h */