PMDK C++ bindings  1.8.2
This is the C++ bindings documentation for PMDK's libpmemobj.
contiguous_iterator.hpp
Go to the documentation of this file.
1 /*
2  * Copyright 2018-2021, Intel Corporation
3  *
4  * Redistribution and use in source and binary forms, with or without
5  * modification, are permitted provided that the following conditions
6  * are met:
7  *
8  * * Redistributions of source code must retain the above copyright
9  * notice, this list of conditions and the following disclaimer.
10  *
11  * * Redistributions in binary form must reproduce the above copyright
12  * notice, this list of conditions and the following disclaimer in
13  * the documentation and/or other materials provided with the
14  * distribution.
15  *
16  * * Neither the name of the copyright holder nor the names of its
17  * contributors may be used to endorse or promote products derived
18  * from this software without specific prior written permission.
19  *
20  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
21  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
22  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
23  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
24  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
25  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
26  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
27  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
28  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
30  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
31  */
32 
38 #ifndef LIBPMEMOBJ_CPP_CONTIGUOUS_ITERATOR_HPP
39 #define LIBPMEMOBJ_CPP_CONTIGUOUS_ITERATOR_HPP
40 
41 #include <algorithm>
42 #include <cassert>
43 #include <functional>
44 
46 
47 namespace pmem
48 {
49 
50 namespace detail
51 {
52 
57 template <typename Iterator, typename Reference, typename Pointer>
62  constexpr contiguous_iterator(Pointer begin) : ptr(begin)
63  {
64  }
65 
69  Reference operator*() const
70  {
71  return *ptr;
72  }
73 
77  Pointer operator->() const
78  {
79  return ptr;
80  }
81 
85  Iterator &
87  {
88  static_cast<Iterator *>(this)->change_by(1);
89  return *static_cast<Iterator *>(this);
90  }
91 
95  Iterator
97  {
98  Iterator tmp(*static_cast<Iterator *>(this));
99  static_cast<Iterator *>(this)->change_by(1);
100  return tmp;
101  }
102 
106  Iterator &
108  {
109  static_cast<Iterator *>(this)->change_by(-1);
110  return *static_cast<Iterator *>(this);
111  }
112 
116  Iterator
118  {
119  Iterator tmp(*static_cast<Iterator *>(this));
120  static_cast<Iterator *>(this)->change_by(-1);
121  return tmp;
122  }
123 
127  Iterator &
128  operator+=(std::ptrdiff_t n)
129  {
130  static_cast<Iterator *>(this)->change_by(n);
131  return *static_cast<Iterator *>(this);
132  }
133 
137  Iterator &
138  operator-=(std::ptrdiff_t n)
139  {
140  static_cast<Iterator *>(this)->change_by(-n);
141  return *static_cast<Iterator *>(this);
142  }
143 
147  Iterator
148  operator+(std::ptrdiff_t n) const
149  {
150  Iterator tmp(*static_cast<const Iterator *>(this));
151  tmp += n;
152  return tmp;
153  }
154 
158  Iterator
159  operator-(std::ptrdiff_t n) const
160  {
161  Iterator tmp(*static_cast<const Iterator *>(this));
162  tmp -= n;
163  return tmp;
164  }
165 
169  friend std::ptrdiff_t
170  operator-(const Iterator &lhs, const Iterator &rhs)
171  {
172  return lhs.ptr - rhs.ptr;
173  }
174 
178  Reference operator[](std::ptrdiff_t n)
179  {
180  return ptr[n];
181  }
182 
183  Pointer
184  get_ptr() const
185  {
186  return ptr;
187  }
188 
189 protected:
195  void
196  change_by(std::ptrdiff_t n)
197  {
198  ptr += n;
199  }
200 
201  Pointer ptr;
202 };
203 
219 template <typename T>
221  : public contiguous_iterator<range_snapshotting_iterator<T>, T &, T *> {
222  using iterator_category = std::random_access_iterator_tag;
223  using value_type = T;
224  using difference_type = std::ptrdiff_t;
225  using reference = T &;
226  using pointer = T *;
228  reference, pointer>;
229 
234  range_snapshotting_iterator(pointer ptr = nullptr,
235  pointer data = nullptr,
236  std::size_t size = 0,
237  std::size_t snapshot_size = 1)
238  : base_type(ptr),
239  data(data),
240  size(size),
241  snapshot_size(snapshot_size)
242  {
243  assert(data <= ptr);
244 
245  if (snapshot_size && ptr)
246  snapshot_range(ptr);
247  }
248 
252  operator const T *() const
253  {
254  return this->ptr;
255  }
256 
262  reference operator[](std::ptrdiff_t n)
263  {
264  detail::conditional_add_to_tx(&this->ptr[n], 1,
265  POBJ_XADD_ASSUME_INITIALIZED);
266  return base_type::operator[](n);
267  }
268 
272  friend void
274  {
275  std::swap(lhs.ptr, rhs.ptr);
276  std::swap(lhs.data, rhs.data);
277  std::swap(lhs.size, rhs.size);
278  std::swap(lhs.snapshot_size, rhs.snapshot_size);
279  }
280 
281  template <typename Iterator, typename Reference, typename Pointer>
282  friend struct contiguous_iterator;
283 
284 protected:
285  void
286  change_by(std::ptrdiff_t n)
287  {
288  conditional_snapshot_range(this->ptr, n);
290  }
291 
292 private:
293  /*
294  * Conditionally snapshot range of length snapshot_size,
295  * which contain address equal to ptr + diff.
296  */
297  void
298  conditional_snapshot_range(pointer ptr, difference_type diff)
299  {
300  if (snapshot_size == 0)
301  return;
302 
303  auto new_ptr = ptr + diff;
304 
305  /* if new pointer is outside of the array */
306  if (new_ptr < data || new_ptr >= data + size)
307  return;
308 
309  /* if new pointer is in the same range */
310  if (static_cast<std::size_t>(ptr - data) / snapshot_size ==
311  static_cast<std::size_t>(new_ptr - data) / snapshot_size)
312  return;
313 
314  snapshot_range(new_ptr);
315  }
316 
317  void
318  snapshot_range(pointer ptr)
319  {
320  /* align index to snapshot_size */
321  auto range_begin =
322  ptr - static_cast<uint64_t>(ptr - data) % snapshot_size;
323  auto range_size = snapshot_size;
324 
325  if (range_begin + range_size > data + size)
326  range_size = static_cast<uint64_t>(data + size -
327  range_begin);
328 #ifndef NDEBUG
329  verify_range(range_begin, range_size);
330 #endif
331 
332  detail::conditional_add_to_tx(range_begin, range_size,
333  POBJ_XADD_ASSUME_INITIALIZED);
334  }
335 
336 #ifndef NDEBUG
337  void
338  verify_range(pointer range_begin, uint64_t range_size)
339  {
340  auto range_offset = static_cast<uint64_t>(range_begin - data);
341 
342  assert(range_begin >= data);
343  assert(range_offset % snapshot_size == 0);
344  assert((range_offset + range_size) % snapshot_size == 0 ||
345  range_begin + range_size == data + size);
346  }
347 #endif
348 
349  pointer data;
350  std::size_t size;
351  std::size_t snapshot_size;
352 };
353 
358 template <typename T>
360  : public contiguous_iterator<basic_contiguous_iterator<T>, T &, T *> {
361  using iterator_category = std::random_access_iterator_tag;
362  using value_type = T;
363  using difference_type = std::ptrdiff_t;
364  using reference = T &;
365  using pointer = T *;
367  reference, pointer>;
368 
373  basic_contiguous_iterator(pointer ptr = nullptr) : base_type(ptr)
374  {
375  }
376 
380  operator const T *() const
381  {
382  return this->ptr;
383  }
384 
389  reference operator*() const
390  {
391  detail::conditional_add_to_tx(this->ptr, 1,
392  POBJ_XADD_ASSUME_INITIALIZED);
393  return base_type::operator*();
394  }
395 
400  pointer operator->() const
401  {
402  detail::conditional_add_to_tx(this->ptr, 1,
403  POBJ_XADD_ASSUME_INITIALIZED);
404  return base_type::operator->();
405  }
406 
412  reference operator[](std::ptrdiff_t n)
413  {
414  detail::conditional_add_to_tx(&this->ptr[n], 1,
415  POBJ_XADD_ASSUME_INITIALIZED);
416  return base_type::operator[](n);
417  }
418 
422  friend void
424  {
425  std::swap(lhs.ptr, rhs.ptr);
426  }
427 };
428 
429 } /* namespace detail */
430 
431 } /* namespace pmem */
432 
433 #endif /* LIBPMEMOBJ_CPP_CONTIGUOUS_ITERATOR_HPP */
Iterator & operator++()
Prefix increment operator.
Definition: contiguous_iterator.hpp:86
friend void swap(basic_contiguous_iterator &lhs, basic_contiguous_iterator &rhs)
Non-member swap function.
Definition: contiguous_iterator.hpp:423
Iterator operator-(std::ptrdiff_t n) const
Subtraction operator overload for integral type.
Definition: contiguous_iterator.hpp:159
reference operator[](std::ptrdiff_t n)
Element access operator.
Definition: contiguous_iterator.hpp:262
friend void swap(range_snapshotting_iterator &lhs, range_snapshotting_iterator &rhs)
Non-member swap function.
Definition: contiguous_iterator.hpp:273
Base class for iterators which satisfies RandomAccessIterator and operate on contiguous memory.
Definition: contiguous_iterator.hpp:58
Pointer operator->() const
Arrow operator.
Definition: contiguous_iterator.hpp:77
pointer operator->() const
Arrow operator which adds underlying element to a transactions.
Definition: contiguous_iterator.hpp:400
void change_by(std::ptrdiff_t n)
Function for changing underlying pointer.
Definition: contiguous_iterator.hpp:196
reference operator *() const
Dereference operator which adds dereferenced element to a transaction.
Definition: contiguous_iterator.hpp:389
reference operator[](std::ptrdiff_t n)
Element access operator.
Definition: contiguous_iterator.hpp:412
Commonly used functionality.
Non-const iterator which adds elements to a transaction in a bulk.
Definition: contiguous_iterator.hpp:220
Iterator operator+(std::ptrdiff_t n) const
Addition operator.
Definition: contiguous_iterator.hpp:148
range_snapshotting_iterator(pointer ptr=nullptr, pointer data=nullptr, std::size_t size=0, std::size_t snapshot_size=1)
Constructor taking pointer to data, pointer to the beginning of the array and snapshot_size.
Definition: contiguous_iterator.hpp:234
constexpr contiguous_iterator(Pointer begin)
Constructor taking a pointer.
Definition: contiguous_iterator.hpp:62
Default non-const iterator which adds element to a transaction on every access.
Definition: contiguous_iterator.hpp:359
Reference operator *() const
Dereference operator.
Definition: contiguous_iterator.hpp:69
basic_contiguous_iterator(pointer ptr=nullptr)
Constructor taking pointer and snapshotting function as arguments.
Definition: contiguous_iterator.hpp:373
Iterator operator++(int)
Postfix increment operator.
Definition: contiguous_iterator.hpp:96
friend std::ptrdiff_t operator-(const Iterator &lhs, const Iterator &rhs)
Subtraction operator overload Iterator type.
Definition: contiguous_iterator.hpp:170
Reference operator[](std::ptrdiff_t n)
Element access operator.
Definition: contiguous_iterator.hpp:178
A persistent version of concurrent hash map implementation Ref: https://arxiv.org/abs/1509....
Definition: allocation_flag.hpp:43
Iterator & operator--()
Prefix decrement operator.
Definition: contiguous_iterator.hpp:107
Iterator & operator+=(std::ptrdiff_t n)
Addition assignment operator.
Definition: contiguous_iterator.hpp:128
Iterator operator--(int)
Postfix decrement operator.
Definition: contiguous_iterator.hpp:117
Iterator & operator-=(std::ptrdiff_t n)
Subtraction assignment operator.
Definition: contiguous_iterator.hpp:138