Libosmium  2.18.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-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 
123  static std::size_t calculate_capacity(std::size_t capacity) noexcept {
124  enum {
125  // The majority of all Nodes will fit into this size.
126  min_capacity = 64
127  };
128 
129  if (capacity < min_capacity) {
130  return min_capacity;
131  }
132  return padded_length(capacity);
133  }
134 
135  void grow_internal() {
136  assert(m_data && "This must be a valid buffer");
137  if (!m_memory) {
138  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
139  }
140 
141  std::unique_ptr<Buffer> old{new Buffer{std::move(m_memory), m_capacity, m_committed}};
142  m_memory = std::unique_ptr<unsigned char[]>{new unsigned char[m_capacity]};
143  m_data = m_memory.get();
144 
145  m_written -= m_committed;
146  std::copy_n(old->data() + m_committed, m_written, m_data);
147  m_committed = 0;
148 
149  old->m_next_buffer = std::move(m_next_buffer);
150  m_next_buffer = std::move(old);
151  }
152 
153  public:
154 
163  Buffer() noexcept = default;
164 
175  explicit Buffer(unsigned char* data, std::size_t size) :
176  m_data(data),
177  m_capacity(size),
178  m_written(size),
179  m_committed(size) {
180  if (size % align_bytes != 0) {
181  throw std::invalid_argument{"buffer size needs to be multiple of alignment"};
182  }
183  }
184 
197  explicit Buffer(unsigned char* data, std::size_t capacity, std::size_t committed) :
198  m_data(data),
199  m_capacity(capacity),
200  m_written(committed),
201  m_committed(committed) {
202  if (capacity % align_bytes != 0) {
203  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
204  }
205  if (committed % align_bytes != 0) {
206  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
207  }
208  if (committed > capacity) {
209  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
210  }
211  }
212 
226  explicit Buffer(std::unique_ptr<unsigned char[]> data, std::size_t capacity, std::size_t committed) :
227  m_memory(std::move(data)),
228  m_data(m_memory.get()),
229  m_capacity(capacity),
230  m_written(committed),
231  m_committed(committed) {
232  if (capacity % align_bytes != 0) {
233  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
234  }
235  if (committed % align_bytes != 0) {
236  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
237  }
238  if (committed > capacity) {
239  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
240  }
241  }
242 
255  explicit Buffer(std::size_t capacity, auto_grow auto_grow = auto_grow::yes) :
256  m_memory(new unsigned char[calculate_capacity(capacity)]),
257  m_data(m_memory.get()),
258  m_capacity(calculate_capacity(capacity)),
259  m_auto_grow(auto_grow) {
260  }
261 
262  // buffers can not be copied
263  Buffer(const Buffer&) = delete;
264  Buffer& operator=(const Buffer&) = delete;
265 
266  // buffers can be moved
267  Buffer(Buffer&& other) noexcept :
268  m_next_buffer(std::move(other.m_next_buffer)),
269  m_memory(std::move(other.m_memory)),
270  m_data(other.m_data),
271  m_capacity(other.m_capacity),
272  m_written(other.m_written),
273  m_committed(other.m_committed),
274 #ifndef NDEBUG
275  m_builder_count(other.m_builder_count),
276 #endif
277  m_auto_grow(other.m_auto_grow) {
278  other.m_data = nullptr;
279  other.m_capacity = 0;
280  other.m_written = 0;
281  other.m_committed = 0;
282 #ifndef NDEBUG
283  other.m_builder_count = 0;
284 #endif
285  }
286 
287  Buffer& operator=(Buffer&& other) noexcept {
288  m_next_buffer = std::move(other.m_next_buffer);
289  m_memory = std::move(other.m_memory);
290  m_data = other.m_data;
291  m_capacity = other.m_capacity;
292  m_written = other.m_written;
293  m_committed = other.m_committed;
294 #ifndef NDEBUG
295  m_builder_count = other.m_builder_count;
296 #endif
297  m_auto_grow = other.m_auto_grow;
298  other.m_data = nullptr;
299  other.m_capacity = 0;
300  other.m_written = 0;
301  other.m_committed = 0;
302 #ifndef NDEBUG
303  other.m_builder_count = 0;
304 #endif
305  return *this;
306  }
307 
308  ~Buffer() noexcept = default;
309 
310 #ifndef NDEBUG
311  void increment_builder_count() noexcept {
312  ++m_builder_count;
313  }
314 
315  void decrement_builder_count() noexcept {
316  assert(m_builder_count > 0);
317  --m_builder_count;
318  }
319 
320  uint8_t builder_count() const noexcept {
321  return m_builder_count;
322  }
323 #endif
324 
330  unsigned char* data() const noexcept {
331  assert(m_data && "This must be a valid buffer");
332  return m_data;
333  }
334 
339  std::size_t capacity() const noexcept {
340  return m_capacity;
341  }
342 
347  std::size_t committed() const noexcept {
348  return m_committed;
349  }
350 
356  std::size_t written() const noexcept {
357  return m_written;
358  }
359 
366  bool is_aligned() const noexcept {
367  assert(m_data && "This must be a valid buffer");
368  return (m_written % align_bytes == 0) && (m_committed % align_bytes == 0);
369  }
370 
386  void grow(std::size_t size) {
387  assert(m_data && "This must be a valid buffer");
388  if (!m_memory) {
389  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
390  }
391  size = calculate_capacity(size);
392  if (m_capacity < size) {
393  std::unique_ptr<unsigned char[]> memory{new unsigned char[size]};
394  std::copy_n(m_memory.get(), m_capacity, memory.get());
395  using std::swap;
396  swap(m_memory, memory);
397  m_data = m_memory.get();
398  m_capacity = size;
399  }
400  }
401 
408  bool has_nested_buffers() const noexcept {
409  return m_next_buffer != nullptr;
410  }
411 
418  std::unique_ptr<Buffer> get_last_nested() {
419  assert(has_nested_buffers());
420  Buffer* buffer = this;
421  while (buffer->m_next_buffer->has_nested_buffers()) {
422  buffer = buffer->m_next_buffer.get();
423  }
424  return std::move(buffer->m_next_buffer);
425  }
426 
439  std::size_t commit() {
440  assert(m_data && "This must be a valid buffer");
441  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
442  assert(is_aligned());
443 
444  const std::size_t offset = m_committed;
445  m_committed = m_written;
446  return offset;
447  }
448 
455  void rollback() {
456  assert(m_data && "This must be a valid buffer");
457  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
458  m_written = m_committed;
459  }
460 
470  std::size_t clear() {
471  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
472  const std::size_t num_used_bytes = m_committed;
473  m_written = 0;
474  m_committed = 0;
475  return num_used_bytes;
476  }
477 
488  template <typename T>
489  T& get(const std::size_t offset) const {
490  assert(m_data && "This must be a valid buffer");
491  assert(offset % alignof(T) == 0 && "Wrong alignment");
492  return *reinterpret_cast<T*>(&m_data[offset]);
493  }
494 
528  unsigned char* reserve_space(const std::size_t size) {
529  assert(m_data && "This must be a valid buffer");
530  // if there's still not enough space, then try growing the buffer.
531  if (m_written + size > m_capacity) {
532  if (!m_memory || m_auto_grow == auto_grow::no) {
533  throw osmium::buffer_is_full{};
534  }
535  if (m_auto_grow == auto_grow::internal && m_committed != 0) {
536  grow_internal();
537  }
538  if (m_written + size > m_capacity) {
539  // double buffer size until there is enough space
540  std::size_t new_capacity = m_capacity * 2;
541  while (m_written + size > new_capacity) {
542  new_capacity *= 2;
543  }
544  grow(new_capacity);
545  }
546  }
547  unsigned char* reserved_space = &m_data[m_written];
548  m_written += size;
549  return reserved_space;
550  }
551 
567  template <typename T>
568  T& add_item(const T& item) {
569  assert(m_data && "This must be a valid buffer");
570  unsigned char* target = reserve_space(item.padded_size());
571  std::copy_n(reinterpret_cast<const unsigned char*>(&item), item.padded_size(), target);
572  return *reinterpret_cast<T*>(target);
573  }
574 
586  void add_buffer(const Buffer& buffer) {
587  assert(m_data && "This must be a valid buffer");
588  assert(buffer && "Buffer parameter must be a valid buffer");
589  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
590  unsigned char* target = reserve_space(buffer.committed());
591  std::copy_n(buffer.data(), buffer.committed(), target);
592  }
593 
603  void push_back(const osmium::memory::Item& item) {
604  assert(m_data && "This must be a valid buffer");
605  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
606  add_item(item);
607  commit();
608  }
609 
614  template <typename T>
615  using t_iterator = osmium::memory::ItemIterator<T>;
616 
621  template <typename T>
622  using t_const_iterator = osmium::memory::ItemIterator<const T>;
623 
628  using iterator = t_iterator<osmium::OSMEntity>;
629 
634  using const_iterator = t_const_iterator<osmium::OSMEntity>;
635 
636  template <typename T>
637  ItemIteratorRange<T> select() {
638  return ItemIteratorRange<T>{m_data, m_data + m_committed};
639  }
640 
641  template <typename T>
642  ItemIteratorRange<const T> select() const {
643  return ItemIteratorRange<const T>{m_data, m_data + m_committed};
644  }
645 
654  template <typename T>
655  t_iterator<T> begin() {
656  assert(m_data && "This must be a valid buffer");
657  return t_iterator<T>(m_data, m_data + m_committed);
658  }
659 
668  iterator begin() {
669  assert(m_data && "This must be a valid buffer");
670  return {m_data, m_data + m_committed};
671  }
672 
682  template <typename T>
683  t_iterator<T> get_iterator(std::size_t offset) {
684  assert(m_data && "This must be a valid buffer");
685  assert(offset % alignof(T) == 0 && "Wrong alignment");
686  return {m_data + offset, m_data + m_committed};
687  }
688 
698  iterator get_iterator(std::size_t offset) {
699  assert(m_data && "This must be a valid buffer");
700  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
701  return {m_data + offset, m_data + m_committed};
702  }
703 
712  template <typename T>
713  t_iterator<T> end() {
714  assert(m_data && "This must be a valid buffer");
715  return {m_data + m_committed, m_data + m_committed};
716  }
717 
726  iterator end() {
727  assert(m_data && "This must be a valid buffer");
728  return {m_data + m_committed, m_data + m_committed};
729  }
730 
731  template <typename T>
732  t_const_iterator<T> cbegin() const {
733  assert(m_data && "This must be a valid buffer");
734  return {m_data, m_data + m_committed};
735  }
736 
737  const_iterator cbegin() const {
738  assert(m_data && "This must be a valid buffer");
739  return {m_data, m_data + m_committed};
740  }
741 
742  template <typename T>
743  t_const_iterator<T> get_iterator(std::size_t offset) const {
744  assert(m_data && "This must be a valid buffer");
745  assert(offset % alignof(T) == 0 && "Wrong alignment");
746  return {m_data + offset, m_data + m_committed};
747  }
748 
749  const_iterator get_iterator(std::size_t offset) const {
750  assert(m_data && "This must be a valid buffer");
751  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
752  return {m_data + offset, m_data + m_committed};
753  }
754 
755  template <typename T>
756  t_const_iterator<T> cend() const {
757  assert(m_data && "This must be a valid buffer");
758  return {m_data + m_committed, m_data + m_committed};
759  }
760 
761  const_iterator cend() const {
762  assert(m_data && "This must be a valid buffer");
763  return {m_data + m_committed, m_data + m_committed};
764  }
765 
766  template <typename T>
767  t_const_iterator<T> begin() const {
768  return cbegin<T>();
769  }
770 
771  const_iterator begin() const {
772  return cbegin();
773  }
774 
775  template <typename T>
776  t_const_iterator<T> end() const {
777  return cend<T>();
778  }
779 
780  const_iterator end() const {
781  return cend();
782  }
783 
787  explicit operator bool() const noexcept {
788  return m_data != nullptr;
789  }
790 
791  void swap(Buffer& other) {
792  using std::swap;
793 
794  swap(m_next_buffer, other.m_next_buffer);
795  swap(m_memory, other.m_memory);
796  swap(m_data, other.m_data);
797  swap(m_capacity, other.m_capacity);
798  swap(m_written, other.m_written);
799  swap(m_committed, other.m_committed);
800  swap(m_auto_grow, other.m_auto_grow);
801  }
802 
820  template <typename TCallbackClass>
821  void purge_removed(TCallbackClass* callback) {
822  assert(m_data && "This must be a valid buffer");
823  assert(callback);
824 
825  if (begin() == end()) {
826  return;
827  }
828 
829  iterator it_write = begin();
830 
831  iterator next;
832  for (iterator it_read = begin(); it_read != end(); it_read = next) {
833  next = std::next(it_read);
834  if (!it_read->removed()) {
835  if (it_read != it_write) {
836  assert(it_read.data() >= data());
837  assert(it_write.data() >= data());
838  const auto old_offset = static_cast<std::size_t>(it_read.data() - data());
839  const auto new_offset = static_cast<std::size_t>(it_write.data() - data());
840  callback->moving_in_buffer(old_offset, new_offset);
841  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
842  }
843  it_write.advance_once();
844  }
845  }
846 
847  assert(it_write.data() >= data());
848  m_written = static_cast<std::size_t>(it_write.data() - data());
849  m_committed = m_written;
850  }
851 
862  void purge_removed() {
863  assert(m_data && "This must be a valid buffer");
864  if (begin() == end()) {
865  return;
866  }
867 
868  iterator it_write = begin();
869 
870  iterator next;
871  for (iterator it_read = begin(); it_read != end(); it_read = next) {
872  next = std::next(it_read);
873  if (!it_read->removed()) {
874  if (it_read != it_write) {
875  assert(it_read.data() >= data());
876  assert(it_write.data() >= data());
877  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
878  }
879  it_write.advance_once();
880  }
881  }
882 
883  assert(it_write.data() >= data());
884  m_written = static_cast<std::size_t>(it_write.data() - data());
885  m_committed = m_written;
886  }
887 
888  }; // class Buffer
889 
890  inline void swap(Buffer& lhs, Buffer& rhs) {
891  lhs.swap(rhs);
892  }
893 
901  inline bool operator==(const Buffer& lhs, const Buffer& rhs) noexcept {
902  if (!lhs || !rhs) {
903  return !lhs && !rhs;
904  }
905  return lhs.data() == rhs.data() && lhs.capacity() == rhs.capacity() && lhs.committed() == rhs.committed();
906  }
907 
908  inline bool operator!=(const Buffer& lhs, const Buffer& rhs) noexcept {
909  return !(lhs == rhs);
910  }
911 
912  } // namespace memory
913 
914 } // namespace osmium
915 
916 #endif // OSMIUM_MEMORY_BUFFER_HPP
Definition: item_iterator.hpp:59
Definition: item.hpp:105
#define OSMIUM_EXPORT
Definition: compatibility.hpp:54
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