//==-- llvm/ADT/ilist_node.h - Intrusive Linked List Helper ------*- C++ -*-==//
//
//                     The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file defines the ilist_node class template, which is a convenient
// base class for creating classes that can be used with ilists.
//
//===----------------------------------------------------------------------===//

#ifndef LLVM_ADT_ILIST_NODE_H
#define LLVM_ADT_ILIST_NODE_H

#include "llvm/ADT/ilist_node_base.h"

namespace llvm {

template<typename NodeTy>
struct ilist_traits;

struct ilist_node_access;
template <typename NodeTy, bool IsReverse = false> class ilist_iterator;
template <typename NodeTy> class ilist_sentinel;

/// Templated wrapper class.
template <typename NodeTy> class ilist_node : ilist_node_base {
  friend class ilist_base;
  friend struct ilist_node_access;
  friend struct ilist_traits<NodeTy>;
  friend class ilist_iterator<NodeTy, false>;
  friend class ilist_iterator<NodeTy, true>;
  friend class ilist_sentinel<NodeTy>;

protected:
  ilist_node() = default;

private:
  ilist_node *getPrev() {
    return static_cast<ilist_node *>(ilist_node_base::getPrev());
  }
  ilist_node *getNext() {
    return static_cast<ilist_node *>(ilist_node_base::getNext());
  }

  const ilist_node *getPrev() const {
    return static_cast<ilist_node *>(ilist_node_base::getPrev());
  }
  const ilist_node *getNext() const {
    return static_cast<ilist_node *>(ilist_node_base::getNext());
  }

  void setPrev(ilist_node *N) { ilist_node_base::setPrev(N); }
  void setNext(ilist_node *N) { ilist_node_base::setNext(N); }

public:
  ilist_iterator<NodeTy> getIterator() { return ilist_iterator<NodeTy>(*this); }
  ilist_iterator<const NodeTy> getIterator() const {
    return ilist_iterator<const NodeTy>(*this);
  }

  using ilist_node_base::isKnownSentinel;
};

/// An access class for ilist_node private API.
///
/// This gives access to the private parts of ilist nodes.  Nodes for an ilist
/// should friend this class if they inherit privately from ilist_node.
///
/// Using this class outside of the ilist implementation is unsupported.
struct ilist_node_access {
  template <typename T> static ilist_node<T> *getNodePtr(T *N) { return N; }
  template <typename T> static const ilist_node<T> *getNodePtr(const T *N) {
    return N;
  }
  template <typename T> static T *getValuePtr(ilist_node<T> *N) {
    return static_cast<T *>(N);
  }
  template <typename T> static const T *getValuePtr(const ilist_node<T> *N) {
    return static_cast<const T *>(N);
  }

  template <typename T> static ilist_node<T> *getPrev(ilist_node<T> &N) {
    return N.getPrev();
  }
  template <typename T> static ilist_node<T> *getNext(ilist_node<T> &N) {
    return N.getNext();
  }
  template <typename T>
  static const ilist_node<T> *getPrev(const ilist_node<T> &N) {
    return N.getPrev();
  }
  template <typename T>
  static const ilist_node<T> *getNext(const ilist_node<T> &N) {
    return N.getNext();
  }
};

template <typename NodeTy> class ilist_sentinel : public ilist_node<NodeTy> {
public:
  ilist_sentinel() {
    ilist_node_base::initializeSentinel();
    reset();
  }

  void reset() {
    this->setPrev(this);
    this->setNext(this);
  }

  bool empty() const { return this == this->getPrev(); }
};

/// An ilist node that can access its parent list.
///
/// Requires \c NodeTy to have \a getParent() to find the parent node, and the
/// \c ParentTy to have \a getSublistAccess() to get a reference to the list.
template <typename NodeTy, typename ParentTy>
class ilist_node_with_parent : public ilist_node<NodeTy> {
protected:
  ilist_node_with_parent() = default;

private:
  /// Forward to NodeTy::getParent().
  ///
  /// Note: do not use the name "getParent()".  We want a compile error
  /// (instead of recursion) when the subclass fails to implement \a
  /// getParent().
  const ParentTy *getNodeParent() const {
    return static_cast<const NodeTy *>(this)->getParent();
  }

public:
  /// @name Adjacent Node Accessors
  /// @{
  /// \brief Get the previous node, or \c nullptr for the list head.
  NodeTy *getPrevNode() {
    // Should be separated to a reused function, but then we couldn't use auto
    // (and would need the type of the list).
    const auto &List =
        getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
    return List.getPrevNode(*static_cast<NodeTy *>(this));
  }
  /// \brief Get the previous node, or \c nullptr for the list head.
  const NodeTy *getPrevNode() const {
    return const_cast<ilist_node_with_parent *>(this)->getPrevNode();
  }

  /// \brief Get the next node, or \c nullptr for the list tail.
  NodeTy *getNextNode() {
    // Should be separated to a reused function, but then we couldn't use auto
    // (and would need the type of the list).
    const auto &List =
        getNodeParent()->*(ParentTy::getSublistAccess((NodeTy *)nullptr));
    return List.getNextNode(*static_cast<NodeTy *>(this));
  }
  /// \brief Get the next node, or \c nullptr for the list tail.
  const NodeTy *getNextNode() const {
    return const_cast<ilist_node_with_parent *>(this)->getNextNode();
  }
  /// @}
};

} // End llvm namespace

#endif