free_list.hpp

/*
 * Copyright (c) 2019-2021, NVIDIA CORPORATION.
 *
 * 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.
 */
 
#pragma once
 
#include <algorithm>
#include <iostream>
#include <list>
 
namespace rmm::mr::detail {
 
struct block_base {
  void* ptr{};  
 
  block_base() = default;
  block_base(void* ptr) : ptr{ptr} {};
 
  [[nodiscard]] inline void* pointer() const { return ptr; }
  [[nodiscard]] inline bool is_valid() const { return pointer() != nullptr; }
 
#ifdef RMM_DEBUG_PRINT
  inline void print() const { std::cout << pointer(); }
#endif
};
 
#ifdef RMM_DEBUG_PRINT
inline std::ostream& operator<<(std::ostream& out, const block_base& block)
{
  out << block.pointer();
  return out;
}
#endif
 
template <typename BlockType, typename ListType = std::list<BlockType>>
class free_list {
 public:
  free_list()          = default;
  virtual ~free_list() = default;
 
  free_list(free_list const&) = delete;
  free_list& operator=(free_list const&) = delete;
  free_list(free_list&&)                 = delete;
  free_list& operator=(free_list&&) = delete;
 
  using block_type     = BlockType;
  using list_type      = ListType;
  using size_type      = typename list_type::size_type;
  using iterator       = typename list_type::iterator;
  using const_iterator = typename list_type::const_iterator;
 
  [[nodiscard]] iterator begin() noexcept { return blocks.begin(); }
  [[nodiscard]] const_iterator begin() const noexcept { return blocks.begin(); }
  [[nodiscard]] const_iterator cbegin() const noexcept { return blocks.cbegin(); }
 
  [[nodiscard]] iterator end() noexcept { return blocks.end(); }
  [[nodiscard]] const_iterator end() const noexcept { return blocks.end(); }
  [[nodiscard]] const_iterator cend() const noexcept { return blocks.cend(); }
 
  [[nodiscard]] size_type size() const noexcept { return blocks.size(); }
 
  [[nodiscard]] bool is_empty() const noexcept { return blocks.empty(); }
 
  void erase(const_iterator iter) { blocks.erase(iter); }
 
  void clear() noexcept { blocks.clear(); }
 
#ifdef RMM_DEBUG_PRINT
 
  void print() const
  {
    std::cout << size() << std::endl;
    for (auto const& block : blocks) {
      std::cout << block << std::endl;
    }
  }
#endif
 
 protected:
  void insert(const_iterator pos, block_type const& block) { blocks.insert(pos, block); }
 
  void splice(const_iterator pos, free_list&& other)
  {
    return blocks.splice(pos, std::move(other.blocks));
  }
 
  void push_back(const block_type& block) { blocks.push_back(block); }
 
  void push_back(block_type&& block) { blocks.push_back(std::move(block)); }
 
  void pop_front() { blocks.pop_front(); }
 
 private:
  list_type blocks;  // The internal container of blocks
};
 
}  // namespace rmm::mr::detail