/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*- * vim: set ts=8 sts=4 et sw=4 tw=99: * This Source Code Form is subject to the terms of the Mozilla Public * License, v. 2.0. If a copy of the MPL was not distributed with this * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ #ifndef jit_InlineList_h #define jit_InlineList_h #include "jsutil.h" namespace js { template <typename T> class InlineForwardList; template <typename T> class InlineForwardListIterator; template <typename T> class InlineForwardListNode { public: InlineForwardListNode() : next(nullptr) { } explicit InlineForwardListNode(InlineForwardListNode<T>* n) : next(n) { } InlineForwardListNode(const InlineForwardListNode<T>&) = delete; protected: friend class InlineForwardList<T>; friend class InlineForwardListIterator<T>; InlineForwardListNode<T>* next; }; template <typename T> class InlineForwardList : protected InlineForwardListNode<T> { friend class InlineForwardListIterator<T>; typedef InlineForwardListNode<T> Node; Node* tail_; #ifdef DEBUG int modifyCount_; #endif InlineForwardList<T>* thisFromConstructor() { return this; } public: InlineForwardList() : tail_(thisFromConstructor()) { #ifdef DEBUG modifyCount_ = 0; #endif } public: typedef InlineForwardListIterator<T> iterator; public: iterator begin() const { return iterator(this); } iterator begin(Node* item) const { return iterator(this, item); } iterator end() const { return iterator(nullptr); } void removeAt(iterator where) { removeAfter(where.prev, where.iter); } void pushFront(Node* t) { insertAfter(this, t); } void pushBack(Node* t) { MOZ_ASSERT(t->next == nullptr); #ifdef DEBUG modifyCount_++; #endif tail_->next = t; tail_ = t; } T* popFront() { MOZ_ASSERT(!empty()); T* result = static_cast<T*>(this->next); removeAfter(this, result); return result; } T* back() const { MOZ_ASSERT(!empty()); return static_cast<T*>(tail_); } void insertAfter(Node* at, Node* item) { MOZ_ASSERT(item->next == nullptr); #ifdef DEBUG modifyCount_++; #endif if (at == tail_) tail_ = item; item->next = at->next; at->next = item; } void removeAfter(Node* at, Node* item) { #ifdef DEBUG modifyCount_++; #endif if (item == tail_) tail_ = at; MOZ_ASSERT(at->next == item); at->next = item->next; item->next = nullptr; } void removeAndIncrement(iterator &where) { // Do not change modifyCount_ here. The iterator can still be used // after calling this method, unlike the other methods that modify // the list. Node* item = where.iter; where.iter = item->next; if (item == tail_) tail_ = where.prev; MOZ_ASSERT(where.prev->next == item); where.prev->next = where.iter; item->next = nullptr; } void splitAfter(Node* at, InlineForwardList<T>* to) { MOZ_ASSERT(to->empty()); if (!at) at = this; if (at == tail_) return; #ifdef DEBUG modifyCount_++; #endif to->next = at->next; to->tail_ = tail_; tail_ = at; at->next = nullptr; } bool empty() const { return tail_ == this; } void clear() { this->next = nullptr; tail_ = this; #ifdef DEBUG modifyCount_ = 0; #endif } }; template <typename T> class InlineForwardListIterator { private: friend class InlineForwardList<T>; typedef InlineForwardListNode<T> Node; explicit InlineForwardListIterator<T>(const InlineForwardList<T>* owner) : prev(const_cast<Node*>(static_cast<const Node*>(owner))), iter(owner ? owner->next : nullptr) #ifdef DEBUG , owner_(owner), modifyCount_(owner ? owner->modifyCount_ : 0) #endif { } InlineForwardListIterator<T>(const InlineForwardList<T>* owner, Node* node) : prev(nullptr), iter(node) #ifdef DEBUG , owner_(owner), modifyCount_(owner ? owner->modifyCount_ : 0) #endif { } public: InlineForwardListIterator<T> & operator ++() { MOZ_ASSERT(modifyCount_ == owner_->modifyCount_); prev = iter; iter = iter->next; return *this; } InlineForwardListIterator<T> operator ++(int) { InlineForwardListIterator<T> old(*this); operator++(); return old; } T * operator*() const { MOZ_ASSERT(modifyCount_ == owner_->modifyCount_); return static_cast<T*>(iter); } T * operator ->() const { MOZ_ASSERT(modifyCount_ == owner_->modifyCount_); return static_cast<T*>(iter); } bool operator !=(const InlineForwardListIterator<T>& where) const { return iter != where.iter; } bool operator ==(const InlineForwardListIterator<T>& where) const { return iter == where.iter; } explicit operator bool() const { return iter != nullptr; } private: Node* prev; Node* iter; #ifdef DEBUG const InlineForwardList<T>* owner_; int modifyCount_; #endif }; template <typename T> class InlineList; template <typename T> class InlineListIterator; template <typename T> class InlineListReverseIterator; template <typename T> class InlineListNode : public InlineForwardListNode<T> { public: InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr) { } InlineListNode(InlineListNode<T>* n, InlineListNode<T>* p) : InlineForwardListNode<T>(n), prev(p) { } // Move constructor. Nodes may be moved without being removed from their // containing lists. For example, this allows list nodes to be safely // stored in a resizable Vector -- when the Vector resizes, the new storage // is initialized by this move constructor. |other| is a reference to the // old node which the |this| node here is replacing. InlineListNode(InlineListNode<T>&& other) : InlineForwardListNode<T>(other.next) { InlineListNode<T>* newNext = static_cast<InlineListNode<T>*>(other.next); InlineListNode<T>* newPrev = other.prev; prev = newPrev; // Update the pointers in the adjacent nodes to point to this node's new // location. newNext->prev = this; newPrev->next = this; } InlineListNode(const InlineListNode<T>&) = delete; void operator=(const InlineListNode<T>&) = delete; protected: friend class InlineList<T>; friend class InlineListIterator<T>; friend class InlineListReverseIterator<T>; InlineListNode<T>* prev; }; template <typename T> class InlineList : protected InlineListNode<T> { typedef InlineListNode<T> Node; public: InlineList() : InlineListNode<T>(this, this) { } public: typedef InlineListIterator<T> iterator; typedef InlineListReverseIterator<T> reverse_iterator; public: iterator begin() const { return iterator(static_cast<Node*>(this->next)); } iterator begin(Node* t) const { return iterator(t); } iterator end() const { return iterator(this); } reverse_iterator rbegin() const { return reverse_iterator(this->prev); } reverse_iterator rbegin(Node* t) const { return reverse_iterator(t); } reverse_iterator rend() const { return reverse_iterator(this); } void pushFront(Node* t) { insertAfter(this, t); } void pushFrontUnchecked(Node* t) { insertAfterUnchecked(this, t); } void pushBack(Node* t) { insertBefore(this, t); } void pushBackUnchecked(Node* t) { insertBeforeUnchecked(this, t); } T* popFront() { MOZ_ASSERT(!empty()); T* t = static_cast<T*>(this->next); remove(t); return t; } T* popBack() { MOZ_ASSERT(!empty()); T* t = static_cast<T*>(this->prev); remove(t); return t; } T* peekBack() const { iterator iter = end(); iter--; return *iter; } void insertBefore(Node* at, Node* item) { MOZ_ASSERT(item->prev == nullptr); MOZ_ASSERT(item->next == nullptr); insertBeforeUnchecked(at, item); } void insertBeforeUnchecked(Node* at, Node* item) { Node* atPrev = at->prev; item->next = at; item->prev = atPrev; atPrev->next = item; at->prev = item; } void insertAfter(Node* at, Node* item) { MOZ_ASSERT(item->prev == nullptr); MOZ_ASSERT(item->next == nullptr); insertAfterUnchecked(at, item); } void insertAfterUnchecked(Node* at, Node* item) { Node* atNext = static_cast<Node*>(at->next); item->next = atNext; item->prev = at; atNext->prev = item; at->next = item; } void remove(Node* t) { Node* tNext = static_cast<Node*>(t->next); Node* tPrev = t->prev; tPrev->next = tNext; tNext->prev = tPrev; t->next = nullptr; t->prev = nullptr; } // Remove |old| from the list and insert |now| in its place. void replace(Node* old, Node* now) { MOZ_ASSERT(now->next == nullptr && now->prev == nullptr); Node* listNext = static_cast<Node*>(old->next); Node* listPrev = old->prev; listPrev->next = now; listNext->prev = now; now->next = listNext; now->prev = listPrev; old->next = nullptr; old->prev = nullptr; } void clear() { this->next = this->prev = this; } bool empty() const { return begin() == end(); } void takeElements(InlineList& l) { MOZ_ASSERT(&l != this, "cannot takeElements from this"); Node* lprev = l.prev; static_cast<Node*>(l.next)->prev = this; lprev->next = this->next; static_cast<Node*>(this->next)->prev = l.prev; this->next = l.next; l.clear(); } }; template <typename T> class InlineListIterator { private: friend class InlineList<T>; typedef InlineListNode<T> Node; explicit InlineListIterator(const Node* iter) : iter(const_cast<Node*>(iter)) { } public: InlineListIterator<T> & operator ++() { iter = static_cast<Node*>(iter->next); return *this; } InlineListIterator<T> operator ++(int) { InlineListIterator<T> old(*this); operator++(); return old; } InlineListIterator<T> & operator --() { iter = iter->prev; return *this; } InlineListIterator<T> operator --(int) { InlineListIterator<T> old(*this); operator--(); return old; } T * operator*() const { return static_cast<T*>(iter); } T * operator ->() const { return static_cast<T*>(iter); } bool operator !=(const InlineListIterator<T>& where) const { return iter != where.iter; } bool operator ==(const InlineListIterator<T>& where) const { return iter == where.iter; } private: Node* iter; }; template <typename T> class InlineListReverseIterator { private: friend class InlineList<T>; typedef InlineListNode<T> Node; explicit InlineListReverseIterator(const Node* iter) : iter(const_cast<Node*>(iter)) { } public: InlineListReverseIterator<T> & operator ++() { iter = iter->prev; return *this; } InlineListReverseIterator<T> operator ++(int) { InlineListReverseIterator<T> old(*this); operator++(); return old; } InlineListReverseIterator<T> & operator --() { iter = static_cast<Node*>(iter->next); return *this; } InlineListReverseIterator<T> operator --(int) { InlineListReverseIterator<T> old(*this); operator--(); return old; } T * operator*() { return static_cast<T*>(iter); } T * operator ->() { return static_cast<T*>(iter); } bool operator !=(const InlineListReverseIterator<T>& where) const { return iter != where.iter; } bool operator ==(const InlineListReverseIterator<T>& where) const { return iter == where.iter; } private: Node* iter; }; /* This list type is more or less exactly an InlineForwardList without a sentinel * node. It is useful in cases where you are doing algorithms that deal with many * merging singleton lists, rather than often empty ones. */ template <typename T> class InlineConcatListIterator; template <typename T> class InlineConcatList { private: typedef InlineConcatList<T> Node; InlineConcatList<T>* thisFromConstructor() { return this; } public: InlineConcatList() : next(nullptr), tail(thisFromConstructor()) { } typedef InlineConcatListIterator<T> iterator; iterator begin() const { return iterator(this); } iterator end() const { return iterator(nullptr); } void append(InlineConcatList<T>* adding) { MOZ_ASSERT(tail); MOZ_ASSERT(!tail->next); MOZ_ASSERT(adding->tail); MOZ_ASSERT(!adding->tail->next); tail->next = adding; tail = adding->tail; adding->tail = nullptr; } protected: friend class InlineConcatListIterator<T>; Node* next; Node* tail; }; template <typename T> class InlineConcatListIterator { private: friend class InlineConcatList<T>; typedef InlineConcatList<T> Node; explicit InlineConcatListIterator(const Node* iter) : iter(const_cast<Node*>(iter)) { } public: InlineConcatListIterator<T> & operator ++() { iter = static_cast<Node*>(iter->next); return *this; } InlineConcatListIterator<T> operator ++(int) { InlineConcatListIterator<T> old(*this); operator++(); return old; } T * operator*() const { return static_cast<T*>(iter); } T * operator ->() const { return static_cast<T*>(iter); } bool operator !=(const InlineConcatListIterator<T>& where) const { return iter != where.iter; } bool operator ==(const InlineConcatListIterator<T>& where) const { return iter == where.iter; } private: Node* iter; }; template <typename T> class InlineSpaghettiStack; template <typename T> class InlineSpaghettiStackNode; template <typename T> class InlineSpaghettiStackIterator; template <typename T> class InlineSpaghettiStackNode : public InlineForwardListNode<T> { typedef InlineForwardListNode<T> Parent; public: InlineSpaghettiStackNode() : Parent() { } explicit InlineSpaghettiStackNode(InlineSpaghettiStackNode<T>* n) : Parent(n) { } InlineSpaghettiStackNode(const InlineSpaghettiStackNode<T>&) = delete; protected: friend class InlineSpaghettiStack<T>; friend class InlineSpaghettiStackIterator<T>; }; template <typename T> class InlineSpaghettiStack : protected InlineSpaghettiStackNode<T> { friend class InlineSpaghettiStackIterator<T>; typedef InlineSpaghettiStackNode<T> Node; public: InlineSpaghettiStack() { } public: typedef InlineSpaghettiStackIterator<T> iterator; public: iterator begin() const { return iterator(this); } iterator end() const { return iterator(nullptr); } void push(Node* t) { MOZ_ASSERT(t->next == nullptr); t->next = this->next; this->next = t; } void copy(const InlineSpaghettiStack<T>& stack) { this->next = stack.next; } bool empty() const { return this->next == nullptr; } }; template <typename T> class InlineSpaghettiStackIterator { private: friend class InlineSpaghettiStack<T>; typedef InlineSpaghettiStackNode<T> Node; explicit InlineSpaghettiStackIterator<T>(const InlineSpaghettiStack<T>* owner) : iter(owner ? static_cast<Node*>(owner->next) : nullptr) { } public: InlineSpaghettiStackIterator<T> & operator ++() { iter = static_cast<Node*>(iter->next); return *this; } InlineSpaghettiStackIterator<T> operator ++(int) { InlineSpaghettiStackIterator<T> old(*this); operator++(); return old; } T* operator*() const { return static_cast<T*>(iter); } T* operator ->() const { return static_cast<T*>(iter); } bool operator !=(const InlineSpaghettiStackIterator<T>& where) const { return iter != where.iter; } bool operator ==(const InlineSpaghettiStackIterator<T>& where) const { return iter == where.iter; } private: Node* iter; }; } // namespace js #endif /* jit_InlineList_h */