Libosmium  2.15.2
Fast and flexible C++ library for working with OpenStreetMap data
buffer.hpp
Go to the documentation of this file.
1 #ifndef OSMIUM_MEMORY_BUFFER_HPP
2 #define OSMIUM_MEMORY_BUFFER_HPP
3 
4 /*
5 
6 This file is part of Osmium (https://osmcode.org/libosmium).
7 
8 Copyright 2013-2019 Jochen Topf <jochen@topf.org> and others (see README).
9 
10 Boost Software License - Version 1.0 - August 17th, 2003
11 
12 Permission is hereby granted, free of charge, to any person or organization
13 obtaining a copy of the software and accompanying documentation covered by
14 this license (the "Software") to use, reproduce, display, distribute,
15 execute, and transmit the Software, and to prepare derivative works of the
16 Software, and to permit third-parties to whom the Software is furnished to
17 do so, all subject to the following:
18 
19 The copyright notices in the Software and this entire statement, including
20 the above license grant, this restriction and the following disclaimer,
21 must be included in all copies of the Software, in whole or in part, and
22 all derivative works of the Software, unless such copies or derivative
23 works are solely in the form of machine-executable object code generated by
24 a source language processor.
25 
26 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
27 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
28 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
29 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
30 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
31 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
32 DEALINGS IN THE SOFTWARE.
33 
34 */
35 
36 #include <osmium/memory/item.hpp>
38 #include <osmium/osm/entity.hpp>
40 
41 #include <algorithm>
42 #include <cassert>
43 #include <cstddef>
44 #include <cstring>
45 #include <functional>
46 #include <iterator>
47 #include <memory>
48 #include <stdexcept>
49 #include <utility>
50 
51 namespace osmium {
52 
58  struct buffer_is_full : public std::runtime_error {
59 
61  std::runtime_error{"Osmium buffer is full"} {
62  }
63 
64  }; // struct buffer_is_full
65 
69  namespace memory {
70 
97  class Buffer {
98 
99  public:
100 
101  // This is needed so we can call std::back_inserter() on a Buffer.
102  using value_type = Item;
103 
104  enum class auto_grow {
105  no = 0,
106  yes = 1,
107  internal = 2
108  }; // enum class auto_grow
109 
110  private:
111 
112  std::unique_ptr<Buffer> m_next_buffer;
113  std::unique_ptr<unsigned char[]> m_memory{};
114  unsigned char* m_data = nullptr;
115  std::size_t m_capacity = 0;
116  std::size_t m_written = 0;
117  std::size_t m_committed = 0;
118 #ifndef NDEBUG
119  uint8_t m_builder_count = 0;
120 #endif
122  std::function<void(Buffer&)> m_full;
123 
124  static std::size_t calculate_capacity(std::size_t capacity) noexcept {
125  enum {
126  // The majority of all Nodes will fit into this size.
127  min_capacity = 64
128  };
129 
130  if (capacity < min_capacity) {
131  return min_capacity;
132  }
133  return padded_length(capacity);
134  }
135 
136  void grow_internal() {
137  assert(m_data && "This must be a valid buffer");
138  if (!m_memory) {
139  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
140  }
141 
142  std::unique_ptr<Buffer> old{new Buffer{std::move(m_memory), m_capacity, m_committed}};
143  m_memory = std::unique_ptr<unsigned char[]>{new unsigned char[m_capacity]};
144  m_data = m_memory.get();
145 
147  std::copy_n(old->data() + m_committed, m_written, m_data);
148  m_committed = 0;
149 
150  old->m_next_buffer = std::move(m_next_buffer);
151  m_next_buffer = std::move(old);
152  }
153 
154  public:
155 
164  Buffer() noexcept :
165  m_next_buffer() {
166  }
167 
178  explicit Buffer(unsigned char* data, std::size_t size) :
179  m_next_buffer(),
180  m_data(data),
181  m_capacity(size),
182  m_written(size),
183  m_committed(size) {
184  if (size % align_bytes != 0) {
185  throw std::invalid_argument{"buffer size needs to be multiple of alignment"};
186  }
187  }
188 
201  explicit Buffer(unsigned char* data, std::size_t capacity, std::size_t committed) :
202  m_next_buffer(),
203  m_data(data),
207  if (capacity % align_bytes != 0) {
208  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
209  }
210  if (committed % align_bytes != 0) {
211  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
212  }
213  if (committed > capacity) {
214  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
215  }
216  }
217 
231  explicit Buffer(std::unique_ptr<unsigned char[]> data, std::size_t capacity, std::size_t committed) :
232  m_next_buffer(),
233  m_memory(std::move(data)),
234  m_data(m_memory.get()),
238  if (capacity % align_bytes != 0) {
239  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
240  }
241  if (committed % align_bytes != 0) {
242  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
243  }
244  if (committed > capacity) {
245  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
246  }
247  }
248 
261  explicit Buffer(std::size_t capacity, auto_grow auto_grow = auto_grow::yes) :
262  m_next_buffer(),
263  m_memory(new unsigned char[calculate_capacity(capacity)]),
264  m_data(m_memory.get()),
267  }
268 
269  // buffers can not be copied
270  Buffer(const Buffer&) = delete;
271  Buffer& operator=(const Buffer&) = delete;
272 
273  // buffers can be moved
274  Buffer(Buffer&& other) noexcept :
275  m_next_buffer(std::move(other.m_next_buffer)),
276  m_memory(std::move(other.m_memory)),
277  m_data(other.m_data),
278  m_capacity(other.m_capacity),
279  m_written(other.m_written),
280  m_committed(other.m_committed),
281 #ifndef NDEBUG
282  m_builder_count(other.m_builder_count),
283 #endif
284  m_auto_grow(other.m_auto_grow),
285  m_full(std::move(other.m_full)) {
286  other.m_data = nullptr;
287  other.m_capacity = 0;
288  other.m_written = 0;
289  other.m_committed = 0;
290 #ifndef NDEBUG
291  other.m_builder_count = 0;
292 #endif
293  }
294 
295  Buffer& operator=(Buffer&& other) noexcept {
296  m_next_buffer = std::move(other.m_next_buffer);
297  m_memory = std::move(other.m_memory);
298  m_data = other.m_data;
299  m_capacity = other.m_capacity;
300  m_written = other.m_written;
301  m_committed = other.m_committed;
302 #ifndef NDEBUG
303  m_builder_count = other.m_builder_count;
304 #endif
305  m_auto_grow = other.m_auto_grow;
306  m_full = std::move(other.m_full);
307  other.m_data = nullptr;
308  other.m_capacity = 0;
309  other.m_written = 0;
310  other.m_committed = 0;
311 #ifndef NDEBUG
312  other.m_builder_count = 0;
313 #endif
314  return *this;
315  }
316 
317  ~Buffer() noexcept = default;
318 
319 #ifndef NDEBUG
320  void increment_builder_count() noexcept {
321  ++m_builder_count;
322  }
323 
324  void decrement_builder_count() noexcept {
325  assert(m_builder_count > 0);
326  --m_builder_count;
327  }
328 
329  uint8_t builder_count() const noexcept {
330  return m_builder_count;
331  }
332 #endif
333 
339  unsigned char* data() const noexcept {
340  assert(m_data && "This must be a valid buffer");
341  return m_data;
342  }
343 
348  std::size_t capacity() const noexcept {
349  return m_capacity;
350  }
351 
356  std::size_t committed() const noexcept {
357  return m_committed;
358  }
359 
365  std::size_t written() const noexcept {
366  return m_written;
367  }
368 
375  bool is_aligned() const noexcept {
376  assert(m_data && "This must be a valid buffer");
377  return (m_written % align_bytes == 0) && (m_committed % align_bytes == 0);
378  }
379 
395  OSMIUM_DEPRECATED void set_full_callback(const std::function<void(Buffer&)>& full) {
396  assert(m_data && "This must be a valid buffer");
397  m_full = full;
398  }
399 
415  void grow(std::size_t size) {
416  assert(m_data && "This must be a valid buffer");
417  if (!m_memory) {
418  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
419  }
420  size = calculate_capacity(size);
421  if (m_capacity < size) {
422  std::unique_ptr<unsigned char[]> memory{new unsigned char[size]};
423  std::copy_n(m_memory.get(), m_capacity, memory.get());
424  using std::swap;
425  swap(m_memory, memory);
426  m_data = m_memory.get();
427  m_capacity = size;
428  }
429  }
430 
437  bool has_nested_buffers() const noexcept {
438  return m_next_buffer != nullptr;
439  }
440 
447  std::unique_ptr<Buffer> get_last_nested() {
448  assert(has_nested_buffers());
449  Buffer* buffer = this;
450  while (buffer->m_next_buffer->has_nested_buffers()) {
451  buffer = buffer->m_next_buffer.get();
452  }
453  return std::move(buffer->m_next_buffer);
454  }
455 
468  std::size_t commit() {
469  assert(m_data && "This must be a valid buffer");
470  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
471  assert(is_aligned());
472 
473  const std::size_t offset = m_committed;
475  return offset;
476  }
477 
484  void rollback() {
485  assert(m_data && "This must be a valid buffer");
486  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
488  }
489 
499  std::size_t clear() {
500  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
501  const std::size_t committed = m_committed;
502  m_written = 0;
503  m_committed = 0;
504  return committed;
505  }
506 
517  template <typename T>
518  T& get(const std::size_t offset) const {
519  assert(m_data && "This must be a valid buffer");
520  assert(offset % alignof(T) == 0 && "Wrong alignment");
521  return *reinterpret_cast<T*>(&m_data[offset]);
522  }
523 
557  unsigned char* reserve_space(const std::size_t size) {
558  assert(m_data && "This must be a valid buffer");
559  // try to flush the buffer empty first.
560  if (m_written + size > m_capacity && m_full) {
561  m_full(*this);
562  }
563  // if there's still not enough space, then try growing the buffer.
564  if (m_written + size > m_capacity) {
565  if (!m_memory || m_auto_grow == auto_grow::no) {
566  throw osmium::buffer_is_full{};
567  }
569  grow_internal();
570  }
571  if (m_written + size > m_capacity) {
572  // double buffer size until there is enough space
573  std::size_t new_capacity = m_capacity * 2;
574  while (m_written + size > new_capacity) {
575  new_capacity *= 2;
576  }
577  grow(new_capacity);
578  }
579  }
580  unsigned char* data = &m_data[m_written];
581  m_written += size;
582  return data;
583  }
584 
600  template <typename T>
601  T& add_item(const T& item) {
602  assert(m_data && "This must be a valid buffer");
603  unsigned char* target = reserve_space(item.padded_size());
604  std::copy_n(reinterpret_cast<const unsigned char*>(&item), item.padded_size(), target);
605  return *reinterpret_cast<T*>(target);
606  }
607 
619  void add_buffer(const Buffer& buffer) {
620  assert(m_data && "This must be a valid buffer");
621  assert(buffer && "Buffer parameter must be a valid buffer");
622  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
623  unsigned char* target = reserve_space(buffer.committed());
624  std::copy_n(buffer.data(), buffer.committed(), target);
625  }
626 
636  void push_back(const osmium::memory::Item& item) {
637  assert(m_data && "This must be a valid buffer");
638  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
639  add_item(item);
640  commit();
641  }
642 
647  template <typename T>
649 
654  template <typename T>
656 
662 
668 
669  template <typename T>
672  }
673 
674  template <typename T>
677  }
678 
687  template <typename T>
689  assert(m_data && "This must be a valid buffer");
691  }
692 
702  assert(m_data && "This must be a valid buffer");
703  return {m_data, m_data + m_committed};
704  }
705 
715  template <typename T>
716  t_iterator<T> get_iterator(std::size_t offset) {
717  assert(m_data && "This must be a valid buffer");
718  assert(offset % alignof(T) == 0 && "Wrong alignment");
719  return {m_data + offset, m_data + m_committed};
720  }
721 
731  iterator get_iterator(std::size_t offset) {
732  assert(m_data && "This must be a valid buffer");
733  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
734  return {m_data + offset, m_data + m_committed};
735  }
736 
745  template <typename T>
747  assert(m_data && "This must be a valid buffer");
748  return {m_data + m_committed, m_data + m_committed};
749  }
750 
760  assert(m_data && "This must be a valid buffer");
761  return {m_data + m_committed, m_data + m_committed};
762  }
763 
764  template <typename T>
766  assert(m_data && "This must be a valid buffer");
767  return {m_data, m_data + m_committed};
768  }
769 
771  assert(m_data && "This must be a valid buffer");
772  return {m_data, m_data + m_committed};
773  }
774 
775  template <typename T>
776  t_const_iterator<T> get_iterator(std::size_t offset) const {
777  assert(m_data && "This must be a valid buffer");
778  assert(offset % alignof(T) == 0 && "Wrong alignment");
779  return {m_data + offset, m_data + m_committed};
780  }
781 
782  const_iterator get_iterator(std::size_t offset) const {
783  assert(m_data && "This must be a valid buffer");
784  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
785  return {m_data + offset, m_data + m_committed};
786  }
787 
788  template <typename T>
790  assert(m_data && "This must be a valid buffer");
791  return {m_data + m_committed, m_data + m_committed};
792  }
793 
795  assert(m_data && "This must be a valid buffer");
796  return {m_data + m_committed, m_data + m_committed};
797  }
798 
799  template <typename T>
801  return cbegin<T>();
802  }
803 
805  return cbegin();
806  }
807 
808  template <typename T>
810  return cend<T>();
811  }
812 
813  const_iterator end() const {
814  return cend();
815  }
816 
820  explicit operator bool() const noexcept {
821  return m_data != nullptr;
822  }
823 
824  void swap(Buffer& other) {
825  using std::swap;
826 
828  swap(m_memory, other.m_memory);
829  swap(m_data, other.m_data);
830  swap(m_capacity, other.m_capacity);
831  swap(m_written, other.m_written);
832  swap(m_committed, other.m_committed);
833  swap(m_auto_grow, other.m_auto_grow);
834  swap(m_full, other.m_full);
835  }
836 
853  template <typename TCallbackClass>
854  void purge_removed(TCallbackClass* callback) {
855  assert(m_data && "This must be a valid buffer");
856  if (begin() == end()) {
857  return;
858  }
859 
860  iterator it_write = begin();
861 
862  iterator next;
863  for (iterator it_read = begin(); it_read != end(); it_read = next) {
864  next = std::next(it_read);
865  if (!it_read->removed()) {
866  if (it_read != it_write) {
867  assert(it_read.data() >= data());
868  assert(it_write.data() >= data());
869  const auto old_offset = static_cast<std::size_t>(it_read.data() - data());
870  const auto new_offset = static_cast<std::size_t>(it_write.data() - data());
871  callback->moving_in_buffer(old_offset, new_offset);
872  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
873  }
874  it_write.advance_once();
875  }
876  }
877 
878  assert(it_write.data() >= data());
879  m_written = static_cast<std::size_t>(it_write.data() - data());
881  }
882 
883  }; // class Buffer
884 
885  inline void swap(Buffer& lhs, Buffer& rhs) {
886  lhs.swap(rhs);
887  }
888 
896  inline bool operator==(const Buffer& lhs, const Buffer& rhs) noexcept {
897  if (!lhs || !rhs) {
898  return !lhs && !rhs;
899  }
900  return lhs.data() == rhs.data() && lhs.capacity() == rhs.capacity() && lhs.committed() == rhs.committed();
901  }
902 
903  inline bool operator!=(const Buffer& lhs, const Buffer& rhs) noexcept {
904  return !(lhs == rhs);
905  }
906 
907  } // namespace memory
908 
909 } // namespace osmium
910 
911 #endif // OSMIUM_MEMORY_BUFFER_HPP
Buffer(Buffer &&other) noexcept
Definition: buffer.hpp:274
void swap(Buffer &other)
Definition: buffer.hpp:824
std::size_t capacity() const noexcept
Definition: buffer.hpp:348
t_const_iterator< T > begin() const
Definition: buffer.hpp:800
~Buffer() noexcept=default
std::size_t commit()
Definition: buffer.hpp:468
#define OSMIUM_DEPRECATED
Definition: compatibility.hpp:51
bool is_aligned() const noexcept
Definition: buffer.hpp:375
iterator get_iterator(std::size_t offset)
Definition: buffer.hpp:731
Definition: item_iterator.hpp:175
void grow_internal()
Definition: buffer.hpp:136
bool operator!=(const Buffer &lhs, const Buffer &rhs) noexcept
Definition: buffer.hpp:903
t_const_iterator< T > cend() const
Definition: buffer.hpp:789
const_iterator cend() const
Definition: buffer.hpp:794
Definition: item_iterator.hpp:59
OSMIUM_DEPRECATED void set_full_callback(const std::function< void(Buffer &)> &full)
Definition: buffer.hpp:395
unsigned char * m_data
Definition: buffer.hpp:114
std::size_t m_committed
Definition: buffer.hpp:117
void increment_builder_count() noexcept
Definition: buffer.hpp:320
Definition: location.hpp:550
ItemIteratorRange< const T > select() const
Definition: buffer.hpp:675
OSMEntity is the abstract base class for the OSMObject and Changeset classes.
Definition: entity.hpp:64
void swap(Buffer &lhs, Buffer &rhs)
Definition: buffer.hpp:885
t_const_iterator< T > get_iterator(std::size_t offset) const
Definition: buffer.hpp:776
std::size_t clear()
Definition: buffer.hpp:499
static std::size_t calculate_capacity(std::size_t capacity) noexcept
Definition: buffer.hpp:124
constexpr std::size_t padded_length(std::size_t length) noexcept
Definition: item.hpp:64
std::size_t committed() const noexcept
Definition: buffer.hpp:356
std::unique_ptr< Buffer > m_next_buffer
Definition: buffer.hpp:112
Buffer(std::size_t capacity, auto_grow auto_grow=auto_grow::yes)
Definition: buffer.hpp:261
const_iterator begin() const
Definition: buffer.hpp:804
bool operator==(const Buffer &lhs, const Buffer &rhs) noexcept
Definition: buffer.hpp:896
std::size_t m_capacity
Definition: buffer.hpp:115
t_iterator< T > end()
Definition: buffer.hpp:746
Definition: item.hpp:105
uint8_t m_builder_count
Definition: buffer.hpp:119
auto_grow
Definition: buffer.hpp:104
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
T & add_item(const T &item)
Definition: buffer.hpp:601
void purge_removed(TCallbackClass *callback)
Definition: buffer.hpp:854
t_iterator< T > begin()
Definition: buffer.hpp:688
void add_buffer(const Buffer &buffer)
Definition: buffer.hpp:619
T & get(const std::size_t offset) const
Definition: buffer.hpp:518
std::size_t written() const noexcept
Definition: buffer.hpp:365
uint8_t builder_count() const noexcept
Definition: buffer.hpp:329
Buffer(unsigned char *data, std::size_t capacity, std::size_t committed)
Definition: buffer.hpp:201
Buffer(unsigned char *data, std::size_t size)
Definition: buffer.hpp:178
std::size_t m_written
Definition: buffer.hpp:116
ItemIterator< TMember > & advance_once() noexcept
Definition: item_iterator.hpp:114
unsigned char * data() const noexcept
Definition: buffer.hpp:339
Buffer() noexcept
Definition: buffer.hpp:164
void grow(std::size_t size)
Definition: buffer.hpp:415
unsigned char * reserve_space(const std::size_t size)
Definition: buffer.hpp:557
auto_grow m_auto_grow
Definition: buffer.hpp:121
void push_back(const osmium::memory::Item &item)
Definition: buffer.hpp:636
Buffer(std::unique_ptr< unsigned char[]> data, std::size_t capacity, std::size_t committed)
Definition: buffer.hpp:231
iterator end()
Definition: buffer.hpp:759
iterator begin()
Definition: buffer.hpp:701
bool has_nested_buffers() const noexcept
Definition: buffer.hpp:437
const_iterator get_iterator(std::size_t offset) const
Definition: buffer.hpp:782
Definition: buffer.hpp:97
Buffer & operator=(Buffer &&other) noexcept
Definition: buffer.hpp:295
t_const_iterator< T > cbegin() const
Definition: buffer.hpp:765
Definition: buffer.hpp:58
void decrement_builder_count() noexcept
Definition: buffer.hpp:324
const_iterator end() const
Definition: buffer.hpp:813
t_const_iterator< T > end() const
Definition: buffer.hpp:809
data_type data() noexcept
Definition: item_iterator.hpp:135
t_iterator< T > get_iterator(std::size_t offset)
Definition: buffer.hpp:716
buffer_is_full()
Definition: buffer.hpp:60
ItemIteratorRange< T > select()
Definition: buffer.hpp:670
Definition: item.hpp:61
void rollback()
Definition: buffer.hpp:484
std::unique_ptr< unsigned char[]> m_memory
Definition: buffer.hpp:113
std::unique_ptr< Buffer > get_last_nested()
Definition: buffer.hpp:447
const_iterator cbegin() const
Definition: buffer.hpp:770
std::function< void(Buffer &)> m_full
Definition: buffer.hpp:122
Buffer & operator=(const Buffer &)=delete