source/util/pooled_linked_list.h

// Copyright (c) 2021 The Khronos Group 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_POOLED_LINKED_LIST_H_
#define SOURCE_UTIL_POOLED_LINKED_LIST_H_

#include <cstdint>
#include <vector>

namespace spvtools {
namespace utils {

// Shared storage of nodes for PooledLinkedList.
template <typename T>
class PooledLinkedListNodes {
 public:
  struct Node {
    Node(T e, int32_t n = -1) : element(e), next(n) {}

    T element = {};
    int32_t next = -1;
  };

  PooledLinkedListNodes() = default;
  PooledLinkedListNodes(const PooledLinkedListNodes&) = delete;
  PooledLinkedListNodes& operator=(const PooledLinkedListNodes&) = delete;

  PooledLinkedListNodes(PooledLinkedListNodes&& that) {
    *this = std::move(that);
  }

  PooledLinkedListNodes& operator=(PooledLinkedListNodes&& that) {
    vec_ = std::move(that.vec_);
    free_nodes_ = that.free_nodes_;
    return *this;
  }

  size_t total_nodes() { return vec_.size(); }
  size_t free_nodes() { return free_nodes_; }
  size_t used_nodes() { return total_nodes() - free_nodes(); }

 private:
  template <typename ListT>
  friend class PooledLinkedList;

  Node& at(int32_t index) { return vec_[index]; }
  const Node& at(int32_t index) const { return vec_[index]; }

  int32_t insert(T element) {
    int32_t index = int32_t(vec_.size());
    vec_.emplace_back(element);
    return index;
  }

  std::vector<Node> vec_;
  size_t free_nodes_ = 0;
};

// Implements a linked-list where list nodes come from a shared pool. This is
// meant to be used in scenarios where it is desirable to avoid many small
// allocations.
//
// Instead of pointers, the list uses indices to allow the underlying storage
// to be modified without needing to modify the list. When removing elements
// from the list, nodes are not deleted or recycled: to reclaim unused space,
// perform a sequence of |move_nodes| operations into a temporary pool, which
// then is moved into the old pool.
//
// This does *not* attempt to implement a full stl-compatible interface.
template <typename T>
class PooledLinkedList {
 public:
  using NodePool = PooledLinkedListNodes<T>;
  using Node = typename NodePool::Node;

  PooledLinkedList() = delete;
  PooledLinkedList(NodePool* nodes) : nodes_(nodes) {}

  // Shared iterator implementation (for iterator and const_iterator).
  template <typename ElementT, typename PoolT>
  class iterator_base {
   public:
    iterator_base(const iterator_base& i)
        : nodes_(i.nodes_), index_(i.index_) {}

    iterator_base& operator++() {
      index_ = nodes_->at(index_).next;
      return *this;
    }

    iterator_base& operator=(const iterator_base& i) {
      nodes_ = i.nodes_;
      index_ = i.index_;
      return *this;
    }

    ElementT& operator*() const { return nodes_->at(index_).element; }
    ElementT* operator->() const { return &nodes_->at(index_).element; }

    friend inline bool operator==(const iterator_base& lhs,
                                  const iterator_base& rhs) {
      return lhs.nodes_ == rhs.nodes_ && lhs.index_ == rhs.index_;
    }
    friend inline bool operator!=(const iterator_base& lhs,
                                  const iterator_base& rhs) {
      return lhs.nodes_ != rhs.nodes_ || lhs.index_ != rhs.index_;
    }

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

   private:
    friend PooledLinkedList;

    iterator_base(PoolT* pool, int32_t index) : nodes_(pool), index_(index) {}

    PoolT* nodes_;
    int32_t index_ = -1;
  };

  using iterator = iterator_base<T, std::vector<Node>>;
  using const_iterator = iterator_base<const T, const std::vector<Node>>;

  bool empty() const { return head_ == -1; }

  T& front() { return nodes_->at(head_).element; }
  T& back() { return nodes_->at(tail_).element; }
  const T& front() const { return nodes_->at(head_).element; }
  const T& back() const { return nodes_->at(tail_).element; }

  iterator begin() { return iterator(&nodes_->vec_, head_); }
  iterator end() { return iterator(&nodes_->vec_, -1); }
  const_iterator begin() const { return const_iterator(&nodes_->vec_, head_); }
  const_iterator end() const { return const_iterator(&nodes_->vec_, -1); }

  // Inserts |element| at the back of the list.
  void push_back(T element) {
    int32_t new_tail = nodes_->insert(element);
    if (head_ == -1) {
      head_ = new_tail;
      tail_ = new_tail;
    } else {
      nodes_->at(tail_).next = new_tail;
      tail_ = new_tail;
    }
  }

  // Removes the first occurrence of |element| from the list.
  // Returns if |element| was removed.
  bool remove_first(T element) {
    int32_t* prev_next = &head_;
    for (int32_t prev_index = -1, index = head_; index != -1; /**/) {
      auto& node = nodes_->at(index);
      if (node.element == element) {
        // Snip from of the list, optionally fixing up tail pointer.
        if (tail_ == index) {
          assert(node.next == -1);
          tail_ = prev_index;
        }
        *prev_next = node.next;
        nodes_->free_nodes_++;
        return true;
      } else {
        prev_next = &node.next;
      }
      prev_index = index;
      index = node.next;
    }
    return false;
  }

  // Returns the PooledLinkedListNodes that owns this list's nodes.
  NodePool* pool() { return nodes_; }

  // Moves the nodes in this list into |new_pool|, providing a way to compact
  // storage and reclaim unused space.
  //
  // Upon completing a sequence of |move_nodes| calls, you must ensure you
  // retain ownership of the new storage your lists point to. Example usage:
  //
  //    unique_ptr<NodePool> new_pool = ...;
  //    for (PooledLinkedList& list : lists) {
  //        list.move_to(new_pool);
  //    }
  //    my_pool_ = std::move(new_pool);
  void move_nodes(NodePool* new_pool) {
    // Be sure to construct the list in the same order, instead of simply
    // doing a sequence of push_backs.
    int32_t prev_entry = -1;
    int32_t nodes_freed = 0;
    for (int32_t index = head_; index != -1; nodes_freed++) {
      const auto& node = nodes_->at(index);
      int32_t this_entry = new_pool->insert(node.element);
      index = node.next;
      if (prev_entry == -1) {
        head_ = this_entry;
      } else {
        new_pool->at(prev_entry).next = this_entry;
      }
      prev_entry = this_entry;
    }
    tail_ = prev_entry;
    // Update our old pool's free count, now we're a member of the new pool.
    nodes_->free_nodes_ += nodes_freed;
    nodes_ = new_pool;
  }

 private:
  NodePool* nodes_;
  int32_t head_ = -1;
  int32_t tail_ = -1;
};

}  // namespace utils
}  // namespace spvtools

#endif  // SOURCE_UTIL_POOLED_LINKED_LIST_H_