Libosmium  2.17.3
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-2022 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 OSMIUM_EXPORT 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 = default;
165 
176  explicit Buffer(unsigned char* data, std::size_t size) :
177  m_data(data),
178  m_capacity(size),
179  m_written(size),
180  m_committed(size) {
181  if (size % align_bytes != 0) {
182  throw std::invalid_argument{"buffer size needs to be multiple of alignment"};
183  }
184  }
185 
198  explicit Buffer(unsigned char* data, std::size_t capacity, std::size_t committed) :
199  m_data(data),
200  m_capacity(capacity),
201  m_written(committed),
202  m_committed(committed) {
203  if (capacity % align_bytes != 0) {
204  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
205  }
206  if (committed % align_bytes != 0) {
207  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
208  }
209  if (committed > capacity) {
210  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
211  }
212  }
213 
227  explicit Buffer(std::unique_ptr<unsigned char[]> data, std::size_t capacity, std::size_t committed) :
228  m_memory(std::move(data)),
229  m_data(m_memory.get()),
230  m_capacity(capacity),
231  m_written(committed),
232  m_committed(committed) {
233  if (capacity % align_bytes != 0) {
234  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
235  }
236  if (committed % align_bytes != 0) {
237  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
238  }
239  if (committed > capacity) {
240  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
241  }
242  }
243 
256  explicit Buffer(std::size_t capacity, auto_grow auto_grow = auto_grow::yes) :
257  m_memory(new unsigned char[calculate_capacity(capacity)]),
258  m_data(m_memory.get()),
259  m_capacity(calculate_capacity(capacity)),
260  m_auto_grow(auto_grow) {
261  }
262 
263  // buffers can not be copied
264  Buffer(const Buffer&) = delete;
265  Buffer& operator=(const Buffer&) = delete;
266 
267  // buffers can be moved
268  Buffer(Buffer&& other) noexcept :
269  m_next_buffer(std::move(other.m_next_buffer)),
270  m_memory(std::move(other.m_memory)),
271  m_data(other.m_data),
272  m_capacity(other.m_capacity),
273  m_written(other.m_written),
274  m_committed(other.m_committed),
275 #ifndef NDEBUG
276  m_builder_count(other.m_builder_count),
277 #endif
278  m_auto_grow(other.m_auto_grow),
279  m_full(std::move(other.m_full)) {
280  other.m_data = nullptr;
281  other.m_capacity = 0;
282  other.m_written = 0;
283  other.m_committed = 0;
284 #ifndef NDEBUG
285  other.m_builder_count = 0;
286 #endif
287  }
288 
289  Buffer& operator=(Buffer&& other) noexcept {
290  m_next_buffer = std::move(other.m_next_buffer);
291  m_memory = std::move(other.m_memory);
292  m_data = other.m_data;
293  m_capacity = other.m_capacity;
294  m_written = other.m_written;
295  m_committed = other.m_committed;
296 #ifndef NDEBUG
297  m_builder_count = other.m_builder_count;
298 #endif
299  m_auto_grow = other.m_auto_grow;
300  m_full = std::move(other.m_full);
301  other.m_data = nullptr;
302  other.m_capacity = 0;
303  other.m_written = 0;
304  other.m_committed = 0;
305 #ifndef NDEBUG
306  other.m_builder_count = 0;
307 #endif
308  return *this;
309  }
310 
311  ~Buffer() noexcept = default;
312 
313 #ifndef NDEBUG
314  void increment_builder_count() noexcept {
315  ++m_builder_count;
316  }
317 
318  void decrement_builder_count() noexcept {
319  assert(m_builder_count > 0);
320  --m_builder_count;
321  }
322 
323  uint8_t builder_count() const noexcept {
324  return m_builder_count;
325  }
326 #endif
327 
333  unsigned char* data() const noexcept {
334  assert(m_data && "This must be a valid buffer");
335  return m_data;
336  }
337 
342  std::size_t capacity() const noexcept {
343  return m_capacity;
344  }
345 
350  std::size_t committed() const noexcept {
351  return m_committed;
352  }
353 
359  std::size_t written() const noexcept {
360  return m_written;
361  }
362 
369  bool is_aligned() const noexcept {
370  assert(m_data && "This must be a valid buffer");
371  return (m_written % align_bytes == 0) && (m_committed % align_bytes == 0);
372  }
373 
389  OSMIUM_DEPRECATED void set_full_callback(const std::function<void(Buffer&)>& full) {
390  assert(m_data && "This must be a valid buffer");
391  m_full = full;
392  }
393 
409  void grow(std::size_t size) {
410  assert(m_data && "This must be a valid buffer");
411  if (!m_memory) {
412  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
413  }
414  size = calculate_capacity(size);
415  if (m_capacity < size) {
416  std::unique_ptr<unsigned char[]> memory{new unsigned char[size]};
417  std::copy_n(m_memory.get(), m_capacity, memory.get());
418  using std::swap;
419  swap(m_memory, memory);
420  m_data = m_memory.get();
421  m_capacity = size;
422  }
423  }
424 
431  bool has_nested_buffers() const noexcept {
432  return m_next_buffer != nullptr;
433  }
434 
441  std::unique_ptr<Buffer> get_last_nested() {
442  assert(has_nested_buffers());
443  Buffer* buffer = this;
444  while (buffer->m_next_buffer->has_nested_buffers()) {
445  buffer = buffer->m_next_buffer.get();
446  }
447  return std::move(buffer->m_next_buffer);
448  }
449 
462  std::size_t commit() {
463  assert(m_data && "This must be a valid buffer");
464  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
465  assert(is_aligned());
466 
467  const std::size_t offset = m_committed;
468  m_committed = m_written;
469  return offset;
470  }
471 
478  void rollback() {
479  assert(m_data && "This must be a valid buffer");
480  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
481  m_written = m_committed;
482  }
483 
493  std::size_t clear() {
494  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
495  const std::size_t num_used_bytes = m_committed;
496  m_written = 0;
497  m_committed = 0;
498  return num_used_bytes;
499  }
500 
511  template <typename T>
512  T& get(const std::size_t offset) const {
513  assert(m_data && "This must be a valid buffer");
514  assert(offset % alignof(T) == 0 && "Wrong alignment");
515  return *reinterpret_cast<T*>(&m_data[offset]);
516  }
517 
551  unsigned char* reserve_space(const std::size_t size) {
552  assert(m_data && "This must be a valid buffer");
553  // try to flush the buffer empty first.
554  if (m_written + size > m_capacity && m_full) {
555  m_full(*this);
556  }
557  // if there's still not enough space, then try growing the buffer.
558  if (m_written + size > m_capacity) {
559  if (!m_memory || m_auto_grow == auto_grow::no) {
560  throw osmium::buffer_is_full{};
561  }
562  if (m_auto_grow == auto_grow::internal && m_committed != 0) {
563  grow_internal();
564  }
565  if (m_written + size > m_capacity) {
566  // double buffer size until there is enough space
567  std::size_t new_capacity = m_capacity * 2;
568  while (m_written + size > new_capacity) {
569  new_capacity *= 2;
570  }
571  grow(new_capacity);
572  }
573  }
574  unsigned char* reserved_space = &m_data[m_written];
575  m_written += size;
576  return reserved_space;
577  }
578 
594  template <typename T>
595  T& add_item(const T& item) {
596  assert(m_data && "This must be a valid buffer");
597  unsigned char* target = reserve_space(item.padded_size());
598  std::copy_n(reinterpret_cast<const unsigned char*>(&item), item.padded_size(), target);
599  return *reinterpret_cast<T*>(target);
600  }
601 
613  void add_buffer(const Buffer& buffer) {
614  assert(m_data && "This must be a valid buffer");
615  assert(buffer && "Buffer parameter must be a valid buffer");
616  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
617  unsigned char* target = reserve_space(buffer.committed());
618  std::copy_n(buffer.data(), buffer.committed(), target);
619  }
620 
630  void push_back(const osmium::memory::Item& item) {
631  assert(m_data && "This must be a valid buffer");
632  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
633  add_item(item);
634  commit();
635  }
636 
641  template <typename T>
642  using t_iterator = osmium::memory::ItemIterator<T>;
643 
648  template <typename T>
649  using t_const_iterator = osmium::memory::ItemIterator<const T>;
650 
655  using iterator = t_iterator<osmium::OSMEntity>;
656 
661  using const_iterator = t_const_iterator<osmium::OSMEntity>;
662 
663  template <typename T>
664  ItemIteratorRange<T> select() {
665  return ItemIteratorRange<T>{m_data, m_data + m_committed};
666  }
667 
668  template <typename T>
669  ItemIteratorRange<const T> select() const {
670  return ItemIteratorRange<const T>{m_data, m_data + m_committed};
671  }
672 
681  template <typename T>
682  t_iterator<T> begin() {
683  assert(m_data && "This must be a valid buffer");
684  return t_iterator<T>(m_data, m_data + m_committed);
685  }
686 
695  iterator begin() {
696  assert(m_data && "This must be a valid buffer");
697  return {m_data, m_data + m_committed};
698  }
699 
709  template <typename T>
710  t_iterator<T> get_iterator(std::size_t offset) {
711  assert(m_data && "This must be a valid buffer");
712  assert(offset % alignof(T) == 0 && "Wrong alignment");
713  return {m_data + offset, m_data + m_committed};
714  }
715 
725  iterator get_iterator(std::size_t offset) {
726  assert(m_data && "This must be a valid buffer");
727  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
728  return {m_data + offset, m_data + m_committed};
729  }
730 
739  template <typename T>
740  t_iterator<T> end() {
741  assert(m_data && "This must be a valid buffer");
742  return {m_data + m_committed, m_data + m_committed};
743  }
744 
753  iterator end() {
754  assert(m_data && "This must be a valid buffer");
755  return {m_data + m_committed, m_data + m_committed};
756  }
757 
758  template <typename T>
759  t_const_iterator<T> cbegin() const {
760  assert(m_data && "This must be a valid buffer");
761  return {m_data, m_data + m_committed};
762  }
763 
764  const_iterator cbegin() const {
765  assert(m_data && "This must be a valid buffer");
766  return {m_data, m_data + m_committed};
767  }
768 
769  template <typename T>
770  t_const_iterator<T> get_iterator(std::size_t offset) const {
771  assert(m_data && "This must be a valid buffer");
772  assert(offset % alignof(T) == 0 && "Wrong alignment");
773  return {m_data + offset, m_data + m_committed};
774  }
775 
776  const_iterator get_iterator(std::size_t offset) const {
777  assert(m_data && "This must be a valid buffer");
778  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
779  return {m_data + offset, m_data + m_committed};
780  }
781 
782  template <typename T>
783  t_const_iterator<T> cend() const {
784  assert(m_data && "This must be a valid buffer");
785  return {m_data + m_committed, m_data + m_committed};
786  }
787 
788  const_iterator cend() const {
789  assert(m_data && "This must be a valid buffer");
790  return {m_data + m_committed, m_data + m_committed};
791  }
792 
793  template <typename T>
794  t_const_iterator<T> begin() const {
795  return cbegin<T>();
796  }
797 
798  const_iterator begin() const {
799  return cbegin();
800  }
801 
802  template <typename T>
803  t_const_iterator<T> end() const {
804  return cend<T>();
805  }
806 
807  const_iterator end() const {
808  return cend();
809  }
810 
814  explicit operator bool() const noexcept {
815  return m_data != nullptr;
816  }
817 
818  void swap(Buffer& other) {
819  using std::swap;
820 
821  swap(m_next_buffer, other.m_next_buffer);
822  swap(m_memory, other.m_memory);
823  swap(m_data, other.m_data);
824  swap(m_capacity, other.m_capacity);
825  swap(m_written, other.m_written);
826  swap(m_committed, other.m_committed);
827  swap(m_auto_grow, other.m_auto_grow);
828  swap(m_full, other.m_full);
829  }
830 
848  template <typename TCallbackClass>
849  void purge_removed(TCallbackClass* callback) {
850  assert(m_data && "This must be a valid buffer");
851  assert(callback);
852 
853  if (begin() == end()) {
854  return;
855  }
856 
857  iterator it_write = begin();
858 
859  iterator next;
860  for (iterator it_read = begin(); it_read != end(); it_read = next) {
861  next = std::next(it_read);
862  if (!it_read->removed()) {
863  if (it_read != it_write) {
864  assert(it_read.data() >= data());
865  assert(it_write.data() >= data());
866  const auto old_offset = static_cast<std::size_t>(it_read.data() - data());
867  const auto new_offset = static_cast<std::size_t>(it_write.data() - data());
868  callback->moving_in_buffer(old_offset, new_offset);
869  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
870  }
871  it_write.advance_once();
872  }
873  }
874 
875  assert(it_write.data() >= data());
876  m_written = static_cast<std::size_t>(it_write.data() - data());
877  m_committed = m_written;
878  }
879 
890  void purge_removed() {
891  assert(m_data && "This must be a valid buffer");
892  if (begin() == end()) {
893  return;
894  }
895 
896  iterator it_write = begin();
897 
898  iterator next;
899  for (iterator it_read = begin(); it_read != end(); it_read = next) {
900  next = std::next(it_read);
901  if (!it_read->removed()) {
902  if (it_read != it_write) {
903  assert(it_read.data() >= data());
904  assert(it_write.data() >= data());
905  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
906  }
907  it_write.advance_once();
908  }
909  }
910 
911  assert(it_write.data() >= data());
912  m_written = static_cast<std::size_t>(it_write.data() - data());
913  m_committed = m_written;
914  }
915 
916  }; // class Buffer
917 
918  inline void swap(Buffer& lhs, Buffer& rhs) {
919  lhs.swap(rhs);
920  }
921 
929  inline bool operator==(const Buffer& lhs, const Buffer& rhs) noexcept {
930  if (!lhs || !rhs) {
931  return !lhs && !rhs;
932  }
933  return lhs.data() == rhs.data() && lhs.capacity() == rhs.capacity() && lhs.committed() == rhs.committed();
934  }
935 
936  inline bool operator!=(const Buffer& lhs, const Buffer& rhs) noexcept {
937  return !(lhs == rhs);
938  }
939 
940  } // namespace memory
941 
942 } // namespace osmium
943 
944 #endif // OSMIUM_MEMORY_BUFFER_HPP
Definition: item_iterator.hpp:59
Definition: item.hpp:105
#define OSMIUM_DEPRECATED
Definition: compatibility.hpp:51
#define OSMIUM_EXPORT
Definition: compatibility.hpp:63
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:555