michael@0: /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
michael@0:  * vim: set ts=8 sts=4 et sw=4 tw=99:
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef jit_InlineList_h
michael@0: #define jit_InlineList_h
michael@0: 
michael@0: #include "jsutil.h"
michael@0: 
michael@0: namespace js {
michael@0: 
michael@0: template <typename T> class InlineForwardList;
michael@0: template <typename T> class InlineForwardListIterator;
michael@0: 
michael@0: template <typename T>
michael@0: class InlineForwardListNode
michael@0: {
michael@0:   public:
michael@0:     InlineForwardListNode() : next(nullptr)
michael@0:     { }
michael@0:     InlineForwardListNode(InlineForwardListNode<T> *n) : next(n)
michael@0:     { }
michael@0: 
michael@0:   protected:
michael@0:     friend class InlineForwardList<T>;
michael@0:     friend class InlineForwardListIterator<T>;
michael@0: 
michael@0:     InlineForwardListNode<T> *next;
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class InlineForwardList : protected InlineForwardListNode<T>
michael@0: {
michael@0:     friend class InlineForwardListIterator<T>;
michael@0: 
michael@0:     typedef InlineForwardListNode<T> Node;
michael@0: 
michael@0:     Node *tail_;
michael@0: #ifdef DEBUG
michael@0:     int modifyCount_;
michael@0: #endif
michael@0: 
michael@0:     InlineForwardList<T> *thisFromConstructor() {
michael@0:         return this;
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     InlineForwardList()
michael@0:       : tail_(thisFromConstructor())
michael@0:     {
michael@0: #ifdef DEBUG
michael@0:         modifyCount_ = 0;
michael@0: #endif
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     typedef InlineForwardListIterator<T> iterator;
michael@0: 
michael@0:   public:
michael@0:     iterator begin() const {
michael@0:         return iterator(this);
michael@0:     }
michael@0:     iterator end() const {
michael@0:         return iterator(nullptr);
michael@0:     }
michael@0:     iterator removeAt(iterator &where) {
michael@0:         iterator iter(where);
michael@0:         iter++;
michael@0:         iter.prev = where.prev;
michael@0: #ifdef DEBUG
michael@0:         iter.modifyCount_++;
michael@0: #endif
michael@0: 
michael@0:         // Once the element 'where' points at has been removed, it is no longer
michael@0:         // safe to do any operations that would touch 'iter', as the element
michael@0:         // may be added to another list, etc. This nullptr ensures that any
michael@0:         // improper uses of this function will fail quickly and loudly.
michael@0:         removeAfter(where.prev, where.iter);
michael@0:         where.prev = where.iter = nullptr;
michael@0: 
michael@0:         return iter;
michael@0:     }
michael@0:     void pushFront(Node *t) {
michael@0:         insertAfter(this, t);
michael@0:     }
michael@0:     void pushBack(Node *t) {
michael@0: #ifdef DEBUG
michael@0:         modifyCount_++;
michael@0: #endif
michael@0:         tail_->next = t;
michael@0:         t->next = nullptr;
michael@0:         tail_ = t;
michael@0:     }
michael@0:     T *popFront() {
michael@0:         JS_ASSERT(!empty());
michael@0:         T* result = static_cast<T *>(this->next);
michael@0:         removeAfter(this, result);
michael@0:         return result;
michael@0:     }
michael@0:     T *back() {
michael@0:         JS_ASSERT(!empty());
michael@0:         return static_cast<T *>(tail_);
michael@0:     }
michael@0:     void insertAfter(Node *at, Node *item) {
michael@0: #ifdef DEBUG
michael@0:         modifyCount_++;
michael@0: #endif
michael@0:         if (at == tail_)
michael@0:             tail_ = item;
michael@0:         item->next = at->next;
michael@0:         at->next = item;
michael@0:     }
michael@0:     void removeAfter(Node *at, Node *item) {
michael@0: #ifdef DEBUG
michael@0:         modifyCount_++;
michael@0: #endif
michael@0:         if (item == tail_)
michael@0:             tail_ = at;
michael@0:         JS_ASSERT(at->next == item);
michael@0:         at->next = item->next;
michael@0:     }
michael@0:     void splitAfter(Node *at, InlineForwardList<T> *to) {
michael@0:         JS_ASSERT(to->empty());
michael@0:         if (!at)
michael@0:             at = this;
michael@0:         if (at == tail_)
michael@0:             return;
michael@0: #ifdef DEBUG
michael@0:         modifyCount_++;
michael@0: #endif
michael@0:         to->next = at->next;
michael@0:         to->tail_ = tail_;
michael@0:         tail_ = at;
michael@0:         at->next = nullptr;
michael@0:     }
michael@0:     bool empty() const {
michael@0:         return tail_ == this;
michael@0:     }
michael@0:     void clear() {
michael@0:         this->next = nullptr;
michael@0:         tail_ = this;
michael@0: #ifdef DEBUG
michael@0:         modifyCount_ = 0;
michael@0: #endif
michael@0:     }
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class InlineForwardListIterator
michael@0: {
michael@0: private:
michael@0:     friend class InlineForwardList<T>;
michael@0: 
michael@0:     typedef InlineForwardListNode<T> Node;
michael@0: 
michael@0:     InlineForwardListIterator<T>(const InlineForwardList<T> *owner)
michael@0:       : prev(const_cast<Node *>(static_cast<const Node *>(owner))),
michael@0:         iter(owner ? owner->next : nullptr)
michael@0: #ifdef DEBUG
michael@0:       , owner_(owner),
michael@0:         modifyCount_(owner ? owner->modifyCount_ : 0)
michael@0: #endif
michael@0:     { }
michael@0: 
michael@0: public:
michael@0:     InlineForwardListIterator<T> & operator ++() {
michael@0:         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
michael@0:         prev = iter;
michael@0:         iter = iter->next;
michael@0:         return *this;
michael@0:     }
michael@0:     InlineForwardListIterator<T> operator ++(int) {
michael@0:         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
michael@0:         InlineForwardListIterator<T> old(*this);
michael@0:         prev = iter;
michael@0:         iter = iter->next;
michael@0:         return old;
michael@0:     }
michael@0:     T * operator *() const {
michael@0:         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     T * operator ->() const {
michael@0:         JS_ASSERT(modifyCount_ == owner_->modifyCount_);
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     bool operator !=(const InlineForwardListIterator<T> &where) const {
michael@0:         return iter != where.iter;
michael@0:     }
michael@0:     bool operator ==(const InlineForwardListIterator<T> &where) const {
michael@0:         return iter == where.iter;
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     Node *prev;
michael@0:     Node *iter;
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     const InlineForwardList<T> *owner_;
michael@0:     int modifyCount_;
michael@0: #endif
michael@0: };
michael@0: 
michael@0: template <typename T> class InlineList;
michael@0: template <typename T> class InlineListIterator;
michael@0: template <typename T> class InlineListReverseIterator;
michael@0: 
michael@0: template <typename T>
michael@0: class InlineListNode : public InlineForwardListNode<T>
michael@0: {
michael@0:   public:
michael@0:     InlineListNode() : InlineForwardListNode<T>(nullptr), prev(nullptr)
michael@0:     { }
michael@0:     InlineListNode(InlineListNode<T> *n, InlineListNode<T> *p)
michael@0:       : InlineForwardListNode<T>(n),
michael@0:         prev(p)
michael@0:     { }
michael@0: 
michael@0:   protected:
michael@0:     friend class InlineList<T>;
michael@0:     friend class InlineListIterator<T>;
michael@0:     friend class InlineListReverseIterator<T>;
michael@0: 
michael@0:     InlineListNode<T> *prev;
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class InlineList : protected InlineListNode<T>
michael@0: {
michael@0:     typedef InlineListNode<T> Node;
michael@0: 
michael@0:   public:
michael@0:     InlineList() : InlineListNode<T>(MOZ_THIS_IN_INITIALIZER_LIST(), MOZ_THIS_IN_INITIALIZER_LIST())
michael@0:     { }
michael@0: 
michael@0:   public:
michael@0:     typedef InlineListIterator<T> iterator;
michael@0:     typedef InlineListReverseIterator<T> reverse_iterator;
michael@0: 
michael@0:   public:
michael@0:     iterator begin() const {
michael@0:         return iterator(static_cast<Node *>(this->next));
michael@0:     }
michael@0:     iterator begin(Node *t) const {
michael@0:         return iterator(t);
michael@0:     }
michael@0:     iterator end() const {
michael@0:         return iterator(this);
michael@0:     }
michael@0:     reverse_iterator rbegin() const {
michael@0:         return reverse_iterator(this->prev);
michael@0:     }
michael@0:     reverse_iterator rbegin(Node *t) const {
michael@0:         return reverse_iterator(t);
michael@0:     }
michael@0:     reverse_iterator rend() const {
michael@0:         return reverse_iterator(this);
michael@0:     }
michael@0:     template <typename itertype>
michael@0:     itertype removeAt(itertype &where) {
michael@0:         itertype iter(where);
michael@0:         iter++;
michael@0: 
michael@0:         // Once the element 'where' points at has been removed, it is no longer
michael@0:         // safe to do any operations that would touch 'iter', as the element
michael@0:         // may be added to another list, etc. This nullptr ensures that any
michael@0:         // improper uses of this function will fail quickly and loudly.
michael@0:         remove(where.iter);
michael@0:         where.iter = nullptr;
michael@0: 
michael@0:         return iter;
michael@0:     }
michael@0:     void pushFront(Node *t) {
michael@0:         insertAfter(this, t);
michael@0:     }
michael@0:     void pushBack(Node *t) {
michael@0:         insertBefore(this, t);
michael@0:     }
michael@0:     T *popFront() {
michael@0:         JS_ASSERT(!empty());
michael@0:         T *t = static_cast<T *>(this->next);
michael@0:         remove(t);
michael@0:         return t;
michael@0:     }
michael@0:     T *popBack() {
michael@0:         JS_ASSERT(!empty());
michael@0:         T *t = static_cast<T *>(this->prev);
michael@0:         remove(t);
michael@0:         return t;
michael@0:     }
michael@0:     T *peekBack() const {
michael@0:         iterator iter = end();
michael@0:         iter--;
michael@0:         return *iter;
michael@0:     }
michael@0:     void insertBefore(Node *at, Node *item) {
michael@0:         item->next = at;
michael@0:         item->prev = at->prev;
michael@0:         at->prev->next = item;
michael@0:         at->prev = item;
michael@0:     }
michael@0:     void insertAfter(Node *at, Node *item) {
michael@0:         item->next = at->next;
michael@0:         item->prev = at;
michael@0:         static_cast<Node *>(at->next)->prev = item;
michael@0:         at->next = item;
michael@0:     }
michael@0:     void remove(Node *t) {
michael@0:         t->prev->next = t->next;
michael@0:         static_cast<Node *>(t->next)->prev = t->prev;
michael@0:         t->next = t->prev = nullptr;
michael@0:     }
michael@0:     void clear() {
michael@0:         this->next = this->prev = this;
michael@0:     }
michael@0:     bool empty() const {
michael@0:         return begin() == end();
michael@0:     }
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class InlineListIterator
michael@0: {
michael@0:   private:
michael@0:     friend class InlineList<T>;
michael@0: 
michael@0:     typedef InlineListNode<T> Node;
michael@0: 
michael@0:     InlineListIterator(const Node *iter)
michael@0:       : iter(const_cast<Node *>(iter))
michael@0:     { }
michael@0: 
michael@0:   public:
michael@0:     InlineListIterator<T> & operator ++() {
michael@0:         iter = static_cast<Node *>(iter->next);
michael@0:         return *this;
michael@0:     }
michael@0:     InlineListIterator<T> operator ++(int) {
michael@0:         InlineListIterator<T> old(*this);
michael@0:         iter = static_cast<Node *>(iter->next);
michael@0:         return old;
michael@0:     }
michael@0:     InlineListIterator<T> operator --(int) {
michael@0:         InlineListIterator<T> old(*this);
michael@0:         iter = iter->prev;
michael@0:         return old;
michael@0:     }
michael@0:     T * operator *() const {
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     T * operator ->() const {
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     bool operator !=(const InlineListIterator<T> &where) const {
michael@0:         return iter != where.iter;
michael@0:     }
michael@0:     bool operator ==(const InlineListIterator<T> &where) const {
michael@0:         return iter == where.iter;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     Node *iter;
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class InlineListReverseIterator
michael@0: {
michael@0:   private:
michael@0:     friend class InlineList<T>;
michael@0: 
michael@0:     typedef InlineListNode<T> Node;
michael@0: 
michael@0:     InlineListReverseIterator(const Node *iter)
michael@0:       : iter(const_cast<Node *>(iter))
michael@0:     { }
michael@0: 
michael@0:   public:
michael@0:     InlineListReverseIterator<T> & operator ++() {
michael@0:         iter = iter->prev;
michael@0:         return *this;
michael@0:     }
michael@0:     InlineListReverseIterator<T> operator ++(int) {
michael@0:         InlineListReverseIterator<T> old(*this);
michael@0:         iter = iter->prev;
michael@0:         return old;
michael@0:     }
michael@0:     T * operator *() {
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     T * operator ->() {
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     bool operator !=(const InlineListReverseIterator<T> &where) const {
michael@0:         return iter != where.iter;
michael@0:     }
michael@0:     bool operator ==(const InlineListReverseIterator<T> &where) const {
michael@0:         return iter == where.iter;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     Node *iter;
michael@0: };
michael@0: 
michael@0: /* This list type is more or less exactly an InlineForwardList without a sentinel
michael@0:  * node. It is useful in cases where you are doing algorithms that deal with many
michael@0:  * merging singleton lists, rather than often empty ones.
michael@0:  */
michael@0: template <typename T> class InlineConcatListIterator;
michael@0: template <typename T>
michael@0: class InlineConcatList
michael@0: {
michael@0:   private:
michael@0:     typedef InlineConcatList<T> Node;
michael@0: 
michael@0:     InlineConcatList<T> *thisFromConstructor() {
michael@0:         return this;
michael@0:     }
michael@0: 
michael@0:   public:
michael@0:     InlineConcatList() : next(nullptr), tail(thisFromConstructor())
michael@0:     { }
michael@0: 
michael@0:     typedef InlineConcatListIterator<T> iterator;
michael@0: 
michael@0:     iterator begin() const {
michael@0:         return iterator(this);
michael@0:     }
michael@0: 
michael@0:     iterator end() const {
michael@0:         return iterator(nullptr);
michael@0:     }
michael@0: 
michael@0:     void append(InlineConcatList<T> *adding)
michael@0:     {
michael@0:         JS_ASSERT(tail);
michael@0:         JS_ASSERT(!tail->next);
michael@0:         JS_ASSERT(adding->tail);
michael@0:         JS_ASSERT(!adding->tail->next);
michael@0: 
michael@0:         tail->next = adding;
michael@0:         tail = adding->tail;
michael@0:         adding->tail = nullptr;
michael@0:     }
michael@0: 
michael@0:   protected:
michael@0:     friend class InlineConcatListIterator<T>;
michael@0:     Node *next;
michael@0:     Node *tail;
michael@0: };
michael@0: 
michael@0: template <typename T>
michael@0: class InlineConcatListIterator
michael@0: {
michael@0:   private:
michael@0:     friend class InlineConcatList<T>;
michael@0: 
michael@0:     typedef InlineConcatList<T> Node;
michael@0: 
michael@0:     InlineConcatListIterator(const Node *iter)
michael@0:       : iter(const_cast<Node *>(iter))
michael@0:     { }
michael@0: 
michael@0:   public:
michael@0:     InlineConcatListIterator<T> & operator ++() {
michael@0:         iter = iter->next;
michael@0:         return *iter;
michael@0:     }
michael@0:     InlineConcatListIterator<T> operator ++(int) {
michael@0:         InlineConcatListIterator<T> old(*this);
michael@0:         iter = static_cast<Node *>(iter->next);
michael@0:         return old;
michael@0:     }
michael@0:     T * operator *() const {
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     T * operator ->() const {
michael@0:         return static_cast<T *>(iter);
michael@0:     }
michael@0:     bool operator !=(const InlineConcatListIterator<T> &where) const {
michael@0:         return iter != where.iter;
michael@0:     }
michael@0:     bool operator ==(const InlineConcatListIterator<T> &where) const {
michael@0:         return iter == where.iter;
michael@0:     }
michael@0: 
michael@0:   private:
michael@0:     Node *iter;
michael@0: };
michael@0: 
michael@0: } // namespace js
michael@0: 
michael@0: #endif /* jit_InlineList_h */