Libosmium  2.17.0
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-2021 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 
60  buffer_is_full() :
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
121  auto_grow m_auto_grow{auto_grow::no};
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 
146  m_written -= m_committed;
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),
204  m_capacity(capacity),
205  m_written(committed),
206  m_committed(committed) {
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()),
235  m_capacity(capacity),
236  m_written(committed),
237  m_committed(committed) {
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()),
265  m_capacity(calculate_capacity(capacity)),
266  m_auto_grow(auto_grow) {
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;
474  m_committed = m_written;
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");
487  m_written = m_committed;
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 num_used_bytes = m_committed;
502  m_written = 0;
503  m_committed = 0;
504  return num_used_bytes;
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  }
568  if (m_auto_grow == auto_grow::internal && m_committed != 0) {
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* reserved_space = &m_data[m_written];
581  m_written += size;
582  return reserved_space;
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>
648  using t_iterator = osmium::memory::ItemIterator<T>;
649 
654  template <typename T>
655  using t_const_iterator = osmium::memory::ItemIterator<const T>;
656 
661  using iterator = t_iterator<osmium::OSMEntity>;
662 
667  using const_iterator = t_const_iterator<osmium::OSMEntity>;
668 
669  template <typename T>
670  ItemIteratorRange<T> select() {
671  return ItemIteratorRange<T>{m_data, m_data + m_committed};
672  }
673 
674  template <typename T>
675  ItemIteratorRange<const T> select() const {
676  return ItemIteratorRange<const T>{m_data, m_data + m_committed};
677  }
678 
687  template <typename T>
688  t_iterator<T> begin() {
689  assert(m_data && "This must be a valid buffer");
690  return t_iterator<T>(m_data, m_data + m_committed);
691  }
692 
701  iterator begin() {
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>
746  t_iterator<T> end() {
747  assert(m_data && "This must be a valid buffer");
748  return {m_data + m_committed, m_data + m_committed};
749  }
750 
759  iterator end() {
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>
765  t_const_iterator<T> cbegin() const {
766  assert(m_data && "This must be a valid buffer");
767  return {m_data, m_data + m_committed};
768  }
769 
770  const_iterator cbegin() const {
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>
789  t_const_iterator<T> cend() const {
790  assert(m_data && "This must be a valid buffer");
791  return {m_data + m_committed, m_data + m_committed};
792  }
793 
794  const_iterator cend() const {
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>
800  t_const_iterator<T> begin() const {
801  return cbegin<T>();
802  }
803 
804  const_iterator begin() const {
805  return cbegin();
806  }
807 
808  template <typename T>
809  t_const_iterator<T> end() const {
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 
827  swap(m_next_buffer, other.m_next_buffer);
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 
854  template <typename TCallbackClass>
855  void purge_removed(TCallbackClass* callback) {
856  assert(m_data && "This must be a valid buffer");
857  assert(callback);
858 
859  if (begin() == end()) {
860  return;
861  }
862 
863  iterator it_write = begin();
864 
865  iterator next;
866  for (iterator it_read = begin(); it_read != end(); it_read = next) {
867  next = std::next(it_read);
868  if (!it_read->removed()) {
869  if (it_read != it_write) {
870  assert(it_read.data() >= data());
871  assert(it_write.data() >= data());
872  const auto old_offset = static_cast<std::size_t>(it_read.data() - data());
873  const auto new_offset = static_cast<std::size_t>(it_write.data() - data());
874  callback->moving_in_buffer(old_offset, new_offset);
875  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
876  }
877  it_write.advance_once();
878  }
879  }
880 
881  assert(it_write.data() >= data());
882  m_written = static_cast<std::size_t>(it_write.data() - data());
883  m_committed = m_written;
884  }
885 
896  void purge_removed() {
897  assert(m_data && "This must be a valid buffer");
898  if (begin() == end()) {
899  return;
900  }
901 
902  iterator it_write = begin();
903 
904  iterator next;
905  for (iterator it_read = begin(); it_read != end(); it_read = next) {
906  next = std::next(it_read);
907  if (!it_read->removed()) {
908  if (it_read != it_write) {
909  assert(it_read.data() >= data());
910  assert(it_write.data() >= data());
911  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
912  }
913  it_write.advance_once();
914  }
915  }
916 
917  assert(it_write.data() >= data());
918  m_written = static_cast<std::size_t>(it_write.data() - data());
919  m_committed = m_written;
920  }
921 
922  }; // class Buffer
923 
924  inline void swap(Buffer& lhs, Buffer& rhs) {
925  lhs.swap(rhs);
926  }
927 
935  inline bool operator==(const Buffer& lhs, const Buffer& rhs) noexcept {
936  if (!lhs || !rhs) {
937  return !lhs && !rhs;
938  }
939  return lhs.data() == rhs.data() && lhs.capacity() == rhs.capacity() && lhs.committed() == rhs.committed();
940  }
941 
942  inline bool operator!=(const Buffer& lhs, const Buffer& rhs) noexcept {
943  return !(lhs == rhs);
944  }
945 
946  } // namespace memory
947 
948 } // namespace osmium
949 
950 #endif // OSMIUM_MEMORY_BUFFER_HPP
Definition: item_iterator.hpp:59
Definition: item.hpp:105
#define OSMIUM_DEPRECATED
Definition: compatibility.hpp:51
InputIterator< Reader > begin(Reader &reader)
Definition: reader_iterator.hpp:43
InputIterator< Reader > end(Reader &)
Definition: reader_iterator.hpp:47
constexpr std::size_t padded_length(std::size_t length) noexcept
Definition: item.hpp:64
@ align_bytes
Definition: item.hpp:61
Namespace for everything in the Osmium library.
Definition: assembler.hpp:53
bool operator==(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:442
bool operator!=(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:446
Definition: location.hpp:551