util/include/chre/util/intrusive_list.h

/*
 * Copyright (C) 2022 The Android Open Source Project
 *
 * 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 CHRE_UTIL_INTRUSIVE_LIST_H_
#define CHRE_UTIL_INTRUSIVE_LIST_H_

#include <type_traits>
#include <utility>

#include "chre/util/intrusive_list_base.h"

#include "chre/util/container_support.h"

namespace chre {

template <typename ElementType>
struct ListNode {
  // Check if the ElementType is appropriate. Inappropriate ElementType
  // will lead to wrong behavior of the reinterpret_cast between
  // Node and ListNode that we use the retrieve item.
  static_assert(std::is_standard_layout<ElementType>::value,
                "must be std layout to alias");

  /**
   * Node that allows the linked list to link data.
   * This need to be the first member of ListNode or the reinterpret_cast
   * between Node and ListNode will fail.
   */
  intrusive_list_internal::Node node;

  /**
   * The data that the user wants to store.
   */
  ElementType item;

  /**
   * Construct a new List Node object by forwarding the arguments to
   * the constructor of ElementType.
   *
   * This breaks C++ assumptions of which constructor is called (move/copy) when
   * using assignment operator. However, in this case, it is safe to do so since
   * ListNode is not copyable (Node is not copyable).
   */
  template <typename... Args>
  ListNode(Args &&...args) : item(std::forward<Args>(args)...) {}

  ~ListNode() {
    CHRE_ASSERT(node.prev == nullptr && node.next == nullptr);
  }
};

/**
 * A container for storing data in a linked list. Note that this container does
 * not allocate any memory, the caller need to manage the memory of the
 * data/node that it wants to insert.
 *
 * Caller need to turn the data into nodes by doing ListNode<ElementType> before
 * using the linked list to manage data. This approach is preferred over the
 * more intrusive way to let user create a new node structure that inherits from
 * Node, since user will not need to worry about handling the extra node type
 * but focus on interacting with the list.
 *
 * Note that although ListNode.node is accessible to client code, user should
 * not modify them directly without using the linked list.
 *
 * Example:
 *  typedef ListNode<int> ListIntNode;
 *  ListIntNode node(10);
 *  IntrusiveList<int> myList;
 *  myList.push_back(node);
 *
 * Note that myList is declared after node so that myList will be destructed
 * before node.
 *
 * @tparam ElementType: The data type that wants to be stored using the link
 * list.
 */
template <typename ElementType>
class IntrusiveList : private intrusive_list_internal::IntrusiveListBase {
  // Check if the ListNode layout is appropriate. Inappropriate or
  // ListNode will lead to wrong behavior of the reinterpret_cast between
  // Node and ListNode that we use the retrieve item.
  static_assert(offsetof(ListNode<ElementType>, node) == 0,
                "node must be the first element");

 public:
  class Iterator {
    using Node = ::chre::intrusive_list_internal::Node;

   public:
    Iterator(Node *node) : mNode(node){};

    ListNode<ElementType> &operator*() const {
      return *reinterpret_cast<ListNode<ElementType> *>(mNode);
    }

    ListNode<ElementType> *operator->() {
      return reinterpret_cast<ListNode<ElementType> *>(mNode);
    }

    Iterator &operator++() {
      mNode = mNode->next;
      return *this;
    }

    Iterator &operator--() {
      mNode = mNode->prev;
      return *this;
    }

    bool operator==(Iterator other) const {
      return mNode == other.mNode;
    }
    bool operator!=(Iterator other) const {
      return mNode != other.mNode;
    }

   private:
    Node *mNode;
  };

  /**
   * Default construct a new Intrusive Linked List.
   */
  IntrusiveList() = default;

  /**
   * Unlink all node when destroy the Intrusive List object.
   */
  ~IntrusiveList();

  /**
   * Examines if the linked list is empty.
   *
   * @return true if the linked list has no linked node.
   */
  bool empty() const {
    return mSize == 0;
  }

  /**
   * Returns the number of nodes stored in this linked list.
   *
   * @return The number of nodes in the linked list.
   */
  size_t size() const {
    return mSize;
  }

  /**
   * Link a new node to the end of the linked list.
   *
   * @param newNode: the node to push to the pack of the linked list.
   */
  void link_back(ListNode<ElementType> *newNode);

  /**
   * Returns a reference to the first node of the linked list.
   * It is not allowed to call this on a empty list.
   *
   * @return The first node of the linked list
   */
  ListNode<ElementType> &front();
  const ListNode<ElementType> &front() const;

  /**
   * Unlink the first node from the list.
   * It is not allowed to call this on a empty list.
   * Note that this function does not free the memory of the node.
   */
  void unlink_front();

  /**
   * Returns a reference to the last node of the linked list.
   * It is not allowed to call this on a empty list.
   *
   * @return The last node of the linked list
   */
  ListNode<ElementType> &back();
  const ListNode<ElementType> &back() const;

  /**
   * Unlink the last node from the list.
   * It is not allowed to call this on a empty list.
   * Note that this function does not free the memory of the node.
   */
  void unlink_back();

  /**
   * Remove a node from its list.
   *
   * @param node: Node that need to be unlinked.
   */
  void unlink_node(ListNode<ElementType> *node);

  /**
   * Link a node after a given node.
   *
   * @param frontNode the old node that will be in front of the new node.
   * @param newNode the new node that will be link to the list.
   */
  void link_after(ListNode<ElementType> *frontNode,
                  ListNode<ElementType> *newNode);

  /**
   * @return Iterator from the beginning of the linked list.
   */
  Iterator begin() {
    return mSentinelNode.next;
  }

  /**
   * @return Iterator from the end of the linked list.
   */
  Iterator end() {
    return &mSentinelNode;
  }
};

}  // namespace chre

#include "chre/util/intrusive_list_impl.h"

#endif  // CHRE_UTIL_INTRUSIVE_LIST_H_