free_list.hpp
1 /*
2  * Copyright (c) 2019-2021, NVIDIA CORPORATION.
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  * http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 #pragma once
18 
19 #include <algorithm>
20 #include <iostream>
21 #include <list>
22 
23 namespace rmm::mr::detail {
24 
25 struct block_base {
26  void* ptr{};
27 
28  block_base() = default;
29  block_base(void* ptr) : ptr{ptr} {};
30 
32  [[nodiscard]] inline void* pointer() const { return ptr; }
34  [[nodiscard]] inline bool is_valid() const { return pointer() != nullptr; }
35 
36 #ifdef RMM_DEBUG_PRINT
37  inline void print() const { std::cout << pointer(); }
39 #endif
40 };
41 
42 #ifdef RMM_DEBUG_PRINT
43 inline std::ostream& operator<<(std::ostream& out, const block_base& block)
45 {
46  out << block.pointer();
47  return out;
48 }
49 #endif
50 
64 template <typename BlockType, typename ListType = std::list<BlockType>>
65 class free_list {
66  public:
67  free_list() = default;
68  virtual ~free_list() = default;
69 
70  free_list(free_list const&) = delete;
71  free_list& operator=(free_list const&) = delete;
72  free_list(free_list&&) = delete;
73  free_list& operator=(free_list&&) = delete;
74 
75  using block_type = BlockType;
76  using list_type = ListType;
77  using size_type = typename list_type::size_type;
78  using iterator = typename list_type::iterator;
79  using const_iterator = typename list_type::const_iterator;
80 
82  [[nodiscard]] iterator begin() noexcept { return blocks.begin(); }
84  [[nodiscard]] const_iterator begin() const noexcept { return blocks.begin(); }
86  [[nodiscard]] const_iterator cbegin() const noexcept { return blocks.cbegin(); }
87 
89  [[nodiscard]] iterator end() noexcept { return blocks.end(); }
91  [[nodiscard]] const_iterator end() const noexcept { return blocks.end(); }
93  [[nodiscard]] const_iterator cend() const noexcept { return blocks.cend(); }
94 
100  [[nodiscard]] size_type size() const noexcept { return blocks.size(); }
101 
108  [[nodiscard]] bool is_empty() const noexcept { return blocks.empty(); }
109 
115  void erase(const_iterator iter) { blocks.erase(iter); }
116 
121  void clear() noexcept { blocks.clear(); }
122 
123 #ifdef RMM_DEBUG_PRINT
124 
127  void print() const
128  {
129  std::cout << size() << std::endl;
130  for (auto const& block : blocks) {
131  std::cout << block << std::endl;
132  }
133  }
134 #endif
135 
136  protected:
143  void insert(const_iterator pos, block_type const& block) { blocks.insert(pos, block); }
144 
151  void splice(const_iterator pos, free_list&& other)
152  {
153  return blocks.splice(pos, std::move(other.blocks));
154  }
155 
161  void push_back(const block_type& block) { blocks.push_back(block); }
162 
168  void push_back(block_type&& block) { blocks.push_back(std::move(block)); }
169 
176  void pop_front() { blocks.pop_front(); }
177 
178  private:
179  list_type blocks; // The internal container of blocks
180 };
181 
182 } // namespace rmm::mr::detail
rmm::mr::detail::free_list::cend
const_iterator cend() const noexcept
beginning of the free list
Definition: free_list.hpp:93
rmm::mr::detail::free_list::cbegin
const_iterator cbegin() const noexcept
beginning of the free list
Definition: free_list.hpp:86
rmm::mr::detail::free_list::end
const_iterator end() const noexcept
beginning of the free list
Definition: free_list.hpp:91
rmm::mr::detail::free_list::begin
iterator begin() noexcept
beginning of the free list
Definition: free_list.hpp:82
rmm::mr::detail::free_list::erase
void erase(const_iterator iter)
Removes the block indicated by iter from the free list.
Definition: free_list.hpp:115
rmm::mr::detail::free_list
Base class defining an interface for a list of free memory blocks.
Definition: free_list.hpp:65
rmm::mr::detail::free_list::push_back
void push_back(block_type &&block)
Appends the given block to the end of the free list. b is moved to the new element.
Definition: free_list.hpp:168
rmm::mr::detail::block_base::is_valid
bool is_valid() const
Returns true if this block is valid (non-null), false otherwise.
Definition: free_list.hpp:34
rmm::mr::detail::free_list::size
size_type size() const noexcept
The size of the free list in blocks.
Definition: free_list.hpp:100
rmm::mr::detail::block
A simple block structure specifying the size and location of a block of memory, with a flag indicatin...
Definition: coalescing_free_list.hpp:36
rmm::mr::detail::free_list::end
iterator end() noexcept
end of the free list
Definition: free_list.hpp:89
rmm::mr::detail::free_list::push_back
void push_back(const block_type &block)
Appends the given block to the end of the free list.
Definition: free_list.hpp:161
rmm::mr::detail::block_base::pointer
void * pointer() const
Returns the raw pointer for this block.
Definition: free_list.hpp:32
rmm::mr::detail::block_base::ptr
void * ptr
Raw memory pointer.
Definition: free_list.hpp:26
rmm::mr::detail::free_list::is_empty
bool is_empty() const noexcept
checks whether the free_list is empty.
Definition: free_list.hpp:108
rmm::mr::detail::free_list::pop_front
void pop_front()
Removes the first element of the free list. If there are no elements in the free list,...
Definition: free_list.hpp:176
rmm::mr::detail::free_list::insert
void insert(const_iterator pos, block_type const &block)
Insert a block in the free list before the specified position.
Definition: free_list.hpp:143
rmm::mr::detail::free_list::begin
const_iterator begin() const noexcept
beginning of the free list
Definition: free_list.hpp:84
rmm::mr::detail::free_list::clear
void clear() noexcept
Erase all blocks from the free_list.
Definition: free_list.hpp:121
rmm::mr::detail::block_base
Definition: free_list.hpp:25
rmm::mr::detail::free_list::splice
void splice(const_iterator pos, free_list &&other)
Inserts a list of blocks in the free list before the specified position.
Definition: free_list.hpp:151