| /* -*- 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 "mozilla/DebugOnly.h" |
| |
| #include "jsutil.h" |
| |
| namespace js { |
| |
| template <typename T> class InlineForwardList; |
| template <typename T> class InlineForwardListIterator; |
| |
| template <typename T> |
| class InlineForwardListNode |
| { |
| public: |
| InlineForwardListNode() : next(NULL) |
| { } |
| InlineForwardListNode(InlineForwardListNode<T> *n) : next(n) |
| { } |
| |
| 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_; |
| mozilla::DebugOnly<int> modifyCount_; |
| |
| InlineForwardList<T> *thisFromConstructor() { |
| return this; |
| } |
| |
| public: |
| InlineForwardList() |
| : tail_(thisFromConstructor()) |
| { |
| modifyCount_ = 0; |
| } |
| |
| public: |
| typedef InlineForwardListIterator<T> iterator; |
| |
| public: |
| iterator begin() const { |
| return iterator(this); |
| } |
| iterator end() const { |
| return iterator(NULL); |
| } |
| iterator removeAt(iterator &where) { |
| iterator iter(where); |
| iter++; |
| iter.prev = where.prev; |
| iter.modifyCount_++; |
| |
| // Once the element 'where' points at has been removed, it is no longer |
| // safe to do any operations that would touch 'iter', as the element |
| // may be added to another list, etc. This NULL ensures that any |
| // improper uses of this function will fail quickly and loudly. |
| removeAfter(where.prev, where.iter); |
| where.prev = where.iter = NULL; |
| |
| return iter; |
| } |
| void pushFront(Node *t) { |
| insertAfter(this, t); |
| } |
| void pushBack(Node *t) { |
| modifyCount_++; |
| tail_->next = t; |
| t->next = NULL; |
| tail_ = t; |
| } |
| T *popFront() { |
| JS_ASSERT(!empty()); |
| T* result = static_cast<T *>(this->next); |
| removeAfter(this, result); |
| return result; |
| } |
| void insertAfter(Node *at, Node *item) { |
| modifyCount_++; |
| if (at == tail_) |
| tail_ = item; |
| item->next = at->next; |
| at->next = item; |
| } |
| void removeAfter(Node *at, Node *item) { |
| modifyCount_++; |
| if (item == tail_) |
| tail_ = at; |
| JS_ASSERT(at->next == item); |
| at->next = item->next; |
| } |
| void splitAfter(Node *at, InlineForwardList<T> *to) { |
| JS_ASSERT(to->empty()); |
| if (!at) |
| at = this; |
| if (at == tail_) |
| return; |
| modifyCount_++; |
| to->next = at->next; |
| to->tail_ = tail_; |
| tail_ = at; |
| at->next = NULL; |
| } |
| bool empty() const { |
| return tail_ == this; |
| } |
| void clear() { |
| this->next = NULL; |
| tail_ = this; |
| modifyCount_ = 0; |
| } |
| }; |
| |
| template <typename T> |
| class InlineForwardListIterator |
| { |
| private: |
| friend class InlineForwardList<T>; |
| |
| typedef InlineForwardListNode<T> Node; |
| |
| InlineForwardListIterator<T>(const InlineForwardList<T> *owner) |
| : prev(const_cast<Node *>(static_cast<const Node *>(owner))), |
| iter(owner ? owner->next : NULL) |
| #ifdef DEBUG |
| , owner_(owner), |
| modifyCount_(owner ? owner->modifyCount_.value : 0) |
| #endif |
| { } |
| |
| public: |
| InlineForwardListIterator<T> & operator ++() { |
| JS_ASSERT(modifyCount_ == owner_->modifyCount_); |
| prev = iter; |
| iter = iter->next; |
| return *this; |
| } |
| InlineForwardListIterator<T> operator ++(int) { |
| JS_ASSERT(modifyCount_ == owner_->modifyCount_); |
| InlineForwardListIterator<T> old(*this); |
| prev = iter; |
| iter = iter->next; |
| return old; |
| } |
| T * operator *() const { |
| JS_ASSERT(modifyCount_ == owner_->modifyCount_); |
| return static_cast<T *>(iter); |
| } |
| T * operator ->() const { |
| JS_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; |
| } |
| |
| private: |
| Node *prev; |
| Node *iter; |
| |
| #ifdef DEBUG |
| const InlineForwardList<T> *owner_; |
| #endif |
| mozilla::DebugOnly<int> modifyCount_; |
| }; |
| |
| 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>(NULL), prev(NULL) |
| { } |
| InlineListNode(InlineListNode<T> *n, InlineListNode<T> *p) |
| : InlineForwardListNode<T>(n), |
| prev(p) |
| { } |
| |
| 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; |
| |
| // Silence MSVC warning C4355 |
| InlineList<T> *thisFromConstructor() { |
| return this; |
| } |
| |
| public: |
| InlineList() : InlineListNode<T>(thisFromConstructor(), thisFromConstructor()) |
| { } |
| |
| 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); |
| } |
| template <typename itertype> |
| itertype removeAt(itertype &where) { |
| itertype iter(where); |
| iter++; |
| |
| // Once the element 'where' points at has been removed, it is no longer |
| // safe to do any operations that would touch 'iter', as the element |
| // may be added to another list, etc. This NULL ensures that any |
| // improper uses of this function will fail quickly and loudly. |
| remove(where.iter); |
| where.iter = NULL; |
| |
| return iter; |
| } |
| void pushFront(Node *t) { |
| insertAfter(this, t); |
| } |
| void pushBack(Node *t) { |
| insertBefore(this, t); |
| } |
| T *popFront() { |
| JS_ASSERT(!empty()); |
| T *t = static_cast<T *>(this->next); |
| remove(t); |
| return t; |
| } |
| T *popBack() { |
| JS_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) { |
| item->next = at; |
| item->prev = at->prev; |
| at->prev->next = item; |
| at->prev = item; |
| } |
| void insertAfter(Node *at, Node *item) { |
| item->next = at->next; |
| item->prev = at; |
| static_cast<Node *>(at->next)->prev = item; |
| at->next = item; |
| } |
| void remove(Node *t) { |
| t->prev->next = t->next; |
| static_cast<Node *>(t->next)->prev = t->prev; |
| t->next = t->prev = NULL; |
| } |
| void clear() { |
| this->next = this->prev = this; |
| } |
| bool empty() const { |
| return begin() == end(); |
| } |
| }; |
| |
| template <typename T> |
| class InlineListIterator |
| { |
| private: |
| friend class InlineList<T>; |
| |
| typedef InlineListNode<T> Node; |
| |
| InlineListIterator(const Node *iter) |
| : iter(const_cast<Node *>(iter)) |
| { } |
| |
| public: |
| InlineListIterator<T> & operator ++() { |
| iter = iter->next; |
| return *iter; |
| } |
| InlineListIterator<T> operator ++(int) { |
| InlineListIterator<T> old(*this); |
| iter = static_cast<Node *>(iter->next); |
| return old; |
| } |
| InlineListIterator<T> operator --(int) { |
| InlineListIterator<T> old(*this); |
| iter = iter->prev; |
| 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; |
| |
| InlineListReverseIterator(const Node *iter) |
| : iter(const_cast<Node *>(iter)) |
| { } |
| |
| public: |
| InlineListReverseIterator<T> & operator ++() { |
| iter = iter->prev; |
| return *iter; |
| } |
| InlineListReverseIterator<T> operator ++(int) { |
| InlineListReverseIterator<T> old(*this); |
| iter = iter->prev; |
| 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; |
| }; |
| |
| } // namespace js |
| |
| #endif /* jit_InlineList_h */ |