src/jit/InlineList.h

/* -*- 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 */