source/util/ilist.h

// Copyright (c) 2017 Google Inc.
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.

#ifndef SOURCE_UTIL_ILIST_H_
#define SOURCE_UTIL_ILIST_H_

#include <cassert>
#include <memory>
#include <type_traits>
#include <vector>

#include "source/util/ilist_node.h"

namespace spvtools {
namespace utils {

// An IntrusiveList is a generic implementation of a doubly-linked list.  The
// intended convention for using this container is:
//
//      class Node : public IntrusiveNodeBase<Node> {
//        // Note that "Node", the class being defined is the template.
//        // Must have a default constructor accessible to List.
//        // Add whatever data is needed in the node
//      };
//
//      using List = IntrusiveList<Node>;
//
// You can also inherit from IntrusiveList instead of a typedef if you want to
// add more functionality.
//
// The condition on the template for IntrusiveNodeBase is there to add some type
// checking to the container.  The compiler will still allow inserting elements
// of type IntrusiveNodeBase<Node>, but that would be an error. This assumption
// allows NextNode and PreviousNode to return pointers to Node, and casting will
// not be required by the user.

template <class NodeType>
class IntrusiveList {
 public:
  static_assert(
      std::is_base_of<IntrusiveNodeBase<NodeType>, NodeType>::value,
      "The type from the node must be derived from IntrusiveNodeBase, with "
      "itself in the template.");

  // Creates an empty list.
  inline IntrusiveList();

  // Moves the contents of the given list to the list being constructed.
  IntrusiveList(IntrusiveList&&);

  // Destorys the list.  Note that the elements of the list will not be deleted,
  // but they will be removed from the list.
  virtual ~IntrusiveList();

  // Moves all of the elements in the list on the RHS to the list on the LHS.
  IntrusiveList& operator=(IntrusiveList&&);

  // Basetype for iterators so an IntrusiveList can be traversed like STL
  // containers.
  template <class T>
  class iterator_template {
   public:
    iterator_template(const iterator_template& i) : node_(i.node_) {}

    iterator_template& operator++() {
      node_ = node_->next_node_;
      return *this;
    }

    iterator_template& operator--() {
      node_ = node_->previous_node_;
      return *this;
    }

    iterator_template& operator=(const iterator_template& i) {
      node_ = i.node_;
      return *this;
    }

    T& operator*() const { return *node_; }
    T* operator->() const { return node_; }

    friend inline bool operator==(const iterator_template& lhs,
                                  const iterator_template& rhs) {
      return lhs.node_ == rhs.node_;
    }
    friend inline bool operator!=(const iterator_template& lhs,
                                  const iterator_template& rhs) {
      return !(lhs == rhs);
    }

    // Moves the nodes in |list| to the list that |this| points to.  The
    // positions of the nodes will be immediately before the element pointed to
    // by the iterator.  The return value will be an iterator pointing to the
    // first of the newly inserted elements.
    iterator_template MoveBefore(IntrusiveList* list) {
      if (list->empty()) return *this;

      NodeType* first_node = list->sentinel_.next_node_;
      NodeType* last_node = list->sentinel_.previous_node_;

      this->node_->previous_node_->next_node_ = first_node;
      first_node->previous_node_ = this->node_->previous_node_;

      last_node->next_node_ = this->node_;
      this->node_->previous_node_ = last_node;

      list->sentinel_.next_node_ = &list->sentinel_;
      list->sentinel_.previous_node_ = &list->sentinel_;

      return iterator(first_node);
    }

    // Define standard iterator types needs so this class can be
    // used with <algorithms>.
    using iterator_category = std::bidirectional_iterator_tag;
    using difference_type = std::ptrdiff_t;
    using value_type = T;
    using pointer = T*;
    using const_pointer = const T*;
    using reference = T&;
    using const_reference = const T&;
    using size_type = size_t;

   protected:
    iterator_template() = delete;
    inline iterator_template(T* node) { node_ = node; }
    T* node_;

    friend IntrusiveList;
  };

  using iterator = iterator_template<NodeType>;
  using const_iterator = iterator_template<const NodeType>;

  // Various types of iterators for the start (begin) and one past the end (end)
  // of the list.
  //
  // Decrementing |end()| iterator will give and iterator pointing to the last
  // element in the list, if one exists.
  //
  // Incrementing |end()| iterator will give |begin()|.
  //
  // Decrementing |begin()| will give |end()|.
  //
  // TODO: Not marking these functions as noexcept because Visual Studio 2013
  // does not support it.  When we no longer care about that compiler, we should
  // mark these as noexcept.
  iterator begin();
  iterator end();
  const_iterator begin() const;
  const_iterator end() const;
  const_iterator cbegin() const;
  const_iterator cend() const;

  // Appends |node| to the end of the list.  If |node| is already in a list, it
  // will be removed from that list first.
  void push_back(NodeType* node);

  // Returns true if the list is empty.
  bool empty() const;

  // Makes the current list empty.
  inline void clear();

  // Returns references to the first or last element in the list.  It is an
  // error to call these functions on an empty list.
  NodeType& front();
  NodeType& back();
  const NodeType& front() const;
  const NodeType& back() const;

  // Transfers [|first|, |last|) from |other| into the list at |where|.
  //
  // If |other| is |this|, no change is made.
  void Splice(iterator where, IntrusiveList<NodeType>* other, iterator first,
              iterator last);

 protected:
  // Doing a deep copy of the list does not make sense if the list does not own
  // the data.  It is not clear who will own the newly created data.  Making
  // copies illegal for that reason.
  IntrusiveList(const IntrusiveList&) = delete;
  IntrusiveList& operator=(const IntrusiveList&) = delete;

  // This function will assert if it finds the list containing |node| is not in
  // a valid state.
  static void Check(NodeType* node);

  // A special node used to represent both the start and end of the list,
  // without being part of the list.
  NodeType sentinel_;
};

// Implementation of IntrusiveList

template <class NodeType>
inline IntrusiveList<NodeType>::IntrusiveList() : sentinel_() {
  sentinel_.next_node_ = &sentinel_;
  sentinel_.previous_node_ = &sentinel_;
  sentinel_.is_sentinel_ = true;
}

template <class NodeType>
IntrusiveList<NodeType>::IntrusiveList(IntrusiveList&& list) : sentinel_() {
  sentinel_.next_node_ = &sentinel_;
  sentinel_.previous_node_ = &sentinel_;
  sentinel_.is_sentinel_ = true;
  list.sentinel_.ReplaceWith(&sentinel_);
}

template <class NodeType>
IntrusiveList<NodeType>::~IntrusiveList() {
  clear();
}

template <class NodeType>
IntrusiveList<NodeType>& IntrusiveList<NodeType>::operator=(
    IntrusiveList<NodeType>&& list) {
  list.sentinel_.ReplaceWith(&sentinel_);
  return *this;
}

template <class NodeType>
inline typename IntrusiveList<NodeType>::iterator
IntrusiveList<NodeType>::begin() {
  return iterator(sentinel_.next_node_);
}

template <class NodeType>
inline typename IntrusiveList<NodeType>::iterator
IntrusiveList<NodeType>::end() {
  return iterator(&sentinel_);
}

template <class NodeType>
inline typename IntrusiveList<NodeType>::const_iterator
IntrusiveList<NodeType>::begin() const {
  return const_iterator(sentinel_.next_node_);
}

template <class NodeType>
inline typename IntrusiveList<NodeType>::const_iterator
IntrusiveList<NodeType>::end() const {
  return const_iterator(&sentinel_);
}

template <class NodeType>
inline typename IntrusiveList<NodeType>::const_iterator
IntrusiveList<NodeType>::cbegin() const {
  return const_iterator(sentinel_.next_node_);
}

template <class NodeType>
inline typename IntrusiveList<NodeType>::const_iterator
IntrusiveList<NodeType>::cend() const {
  return const_iterator(&sentinel_);
}

template <class NodeType>
void IntrusiveList<NodeType>::push_back(NodeType* node) {
  node->InsertBefore(&sentinel_);
}

template <class NodeType>
bool IntrusiveList<NodeType>::empty() const {
  return sentinel_.NextNode() == nullptr;
}

template <class NodeType>
void IntrusiveList<NodeType>::clear() {
  while (!empty()) {
    front().RemoveFromList();
  }
}

template <class NodeType>
NodeType& IntrusiveList<NodeType>::front() {
  NodeType* node = sentinel_.NextNode();
  assert(node != nullptr && "Can't get the front of an empty list.");
  return *node;
}

template <class NodeType>
NodeType& IntrusiveList<NodeType>::back() {
  NodeType* node = sentinel_.PreviousNode();
  assert(node != nullptr && "Can't get the back of an empty list.");
  return *node;
}

template <class NodeType>
const NodeType& IntrusiveList<NodeType>::front() const {
  NodeType* node = sentinel_.NextNode();
  assert(node != nullptr && "Can't get the front of an empty list.");
  return *node;
}

template <class NodeType>
const NodeType& IntrusiveList<NodeType>::back() const {
  NodeType* node = sentinel_.PreviousNode();
  assert(node != nullptr && "Can't get the back of an empty list.");
  return *node;
}

template <class NodeType>
void IntrusiveList<NodeType>::Splice(iterator where,
                                     IntrusiveList<NodeType>* other,
                                     iterator first, iterator last) {
  if (first == last) return;
  if (other == this) return;

  NodeType* first_prev = first.node_->previous_node_;
  NodeType* where_next = where.node_->next_node_;

  // Attach first.
  where.node_->next_node_ = first.node_;
  first.node_->previous_node_ = where.node_;

  // Attach last.
  where_next->previous_node_ = last.node_->previous_node_;
  last.node_->previous_node_->next_node_ = where_next;

  // Fixup other.
  first_prev->next_node_ = last.node_;
  last.node_->previous_node_ = first_prev;
}

template <class NodeType>
void IntrusiveList<NodeType>::Check(NodeType* start) {
  int sentinel_count = 0;
  NodeType* p = start;
  do {
    assert(p != nullptr);
    assert(p->next_node_->previous_node_ == p);
    assert(p->previous_node_->next_node_ == p);
    if (p->is_sentinel_) sentinel_count++;
    p = p->next_node_;
  } while (p != start);
  assert(sentinel_count == 1 && "List should have exactly 1 sentinel node.");

  p = start;
  do {
    assert(p != nullptr);
    assert(p->previous_node_->next_node_ == p);
    assert(p->next_node_->previous_node_ == p);
    if (p->is_sentinel_) sentinel_count++;
    p = p->previous_node_;
  } while (p != start);
}

}  // namespace utils
}  // namespace spvtools

#endif  // SOURCE_UTIL_ILIST_H_