Libosmium  2.19.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-2023 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 
91  class Buffer {
92 
93  public:
94 
95  // This is needed so we can call std::back_inserter() on a Buffer.
96  using value_type = Item;
97 
98  enum class auto_grow {
99  no = 0,
100  yes = 1,
101  internal = 2
102  }; // enum class auto_grow
103 
104  private:
105 
106  std::unique_ptr<Buffer> m_next_buffer;
107  std::unique_ptr<unsigned char[]> m_memory{};
108  unsigned char* m_data = nullptr;
109  std::size_t m_capacity = 0;
110  std::size_t m_written = 0;
111  std::size_t m_committed = 0;
112 #ifndef NDEBUG
113  uint8_t m_builder_count = 0;
114 #endif
115  auto_grow m_auto_grow{auto_grow::no};
116 
117  static std::size_t calculate_capacity(std::size_t capacity) noexcept {
118  enum {
119  // The majority of all Nodes will fit into this size.
120  min_capacity = 64
121  };
122 
123  if (capacity < min_capacity) {
124  return min_capacity;
125  }
126  return padded_length(capacity);
127  }
128 
129  void grow_internal() {
130  assert(m_data && "This must be a valid buffer");
131  if (!m_memory) {
132  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
133  }
134 
135  std::unique_ptr<Buffer> old{new Buffer{std::move(m_memory), m_capacity, m_committed}};
136  m_memory = std::unique_ptr<unsigned char[]>{new unsigned char[m_capacity]};
137  m_data = m_memory.get();
138 
139  m_written -= m_committed;
140  std::copy_n(old->data() + m_committed, m_written, m_data);
141  m_committed = 0;
142 
143  old->m_next_buffer = std::move(m_next_buffer);
144  m_next_buffer = std::move(old);
145  }
146 
147  public:
148 
157  Buffer() noexcept = default;
158 
169  explicit Buffer(unsigned char* data, std::size_t size) :
170  m_data(data),
171  m_capacity(size),
172  m_written(size),
173  m_committed(size) {
174  if (size % align_bytes != 0) {
175  throw std::invalid_argument{"buffer size needs to be multiple of alignment"};
176  }
177  }
178 
191  explicit Buffer(unsigned char* data, std::size_t capacity, std::size_t committed) :
192  m_data(data),
193  m_capacity(capacity),
194  m_written(committed),
195  m_committed(committed) {
196  if (capacity % align_bytes != 0) {
197  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
198  }
199  if (committed % align_bytes != 0) {
200  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
201  }
202  if (committed > capacity) {
203  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
204  }
205  }
206 
220  explicit Buffer(std::unique_ptr<unsigned char[]> data, std::size_t capacity, std::size_t committed) :
221  m_memory(std::move(data)),
222  m_data(m_memory.get()),
223  m_capacity(capacity),
224  m_written(committed),
225  m_committed(committed) {
226  if (capacity % align_bytes != 0) {
227  throw std::invalid_argument{"buffer capacity needs to be multiple of alignment"};
228  }
229  if (committed % align_bytes != 0) {
230  throw std::invalid_argument{"buffer parameter 'committed' needs to be multiple of alignment"};
231  }
232  if (committed > capacity) {
233  throw std::invalid_argument{"buffer parameter 'committed' can not be larger than capacity"};
234  }
235  }
236 
249  explicit Buffer(std::size_t capacity, auto_grow auto_grow = auto_grow::yes) :
250  m_memory(new unsigned char[calculate_capacity(capacity)]),
251  m_data(m_memory.get()),
252  m_capacity(calculate_capacity(capacity)),
253  m_auto_grow(auto_grow) {
254  }
255 
256  // buffers can not be copied
257  Buffer(const Buffer&) = delete;
258  Buffer& operator=(const Buffer&) = delete;
259 
260  // buffers can be moved
261  Buffer(Buffer&& other) noexcept :
262  m_next_buffer(std::move(other.m_next_buffer)),
263  m_memory(std::move(other.m_memory)),
264  m_data(other.m_data),
265  m_capacity(other.m_capacity),
266  m_written(other.m_written),
267  m_committed(other.m_committed),
268 #ifndef NDEBUG
269  m_builder_count(other.m_builder_count),
270 #endif
271  m_auto_grow(other.m_auto_grow) {
272  other.m_data = nullptr;
273  other.m_capacity = 0;
274  other.m_written = 0;
275  other.m_committed = 0;
276 #ifndef NDEBUG
277  other.m_builder_count = 0;
278 #endif
279  }
280 
281  Buffer& operator=(Buffer&& other) noexcept {
282  m_next_buffer = std::move(other.m_next_buffer);
283  m_memory = std::move(other.m_memory);
284  m_data = other.m_data;
285  m_capacity = other.m_capacity;
286  m_written = other.m_written;
287  m_committed = other.m_committed;
288 #ifndef NDEBUG
289  m_builder_count = other.m_builder_count;
290 #endif
291  m_auto_grow = other.m_auto_grow;
292  other.m_data = nullptr;
293  other.m_capacity = 0;
294  other.m_written = 0;
295  other.m_committed = 0;
296 #ifndef NDEBUG
297  other.m_builder_count = 0;
298 #endif
299  return *this;
300  }
301 
302  ~Buffer() noexcept = default;
303 
304 #ifndef NDEBUG
305  void increment_builder_count() noexcept {
306  ++m_builder_count;
307  }
308 
309  void decrement_builder_count() noexcept {
310  assert(m_builder_count > 0);
311  --m_builder_count;
312  }
313 
314  uint8_t builder_count() const noexcept {
315  return m_builder_count;
316  }
317 #endif
318 
324  unsigned char* data() const noexcept {
325  assert(m_data && "This must be a valid buffer");
326  return m_data;
327  }
328 
333  std::size_t capacity() const noexcept {
334  return m_capacity;
335  }
336 
341  std::size_t committed() const noexcept {
342  return m_committed;
343  }
344 
350  std::size_t written() const noexcept {
351  return m_written;
352  }
353 
360  bool is_aligned() const noexcept {
361  assert(m_data && "This must be a valid buffer");
362  return (m_written % align_bytes == 0) && (m_committed % align_bytes == 0);
363  }
364 
380  void grow(std::size_t size) {
381  assert(m_data && "This must be a valid buffer");
382  if (!m_memory) {
383  throw std::logic_error{"Can't grow Buffer if it doesn't use internal memory management."};
384  }
385  size = calculate_capacity(size);
386  if (m_capacity < size) {
387  std::unique_ptr<unsigned char[]> memory{new unsigned char[size]};
388  std::copy_n(m_memory.get(), m_capacity, memory.get());
389  using std::swap;
390  swap(m_memory, memory);
391  m_data = m_memory.get();
392  m_capacity = size;
393  }
394  }
395 
402  bool has_nested_buffers() const noexcept {
403  return m_next_buffer != nullptr;
404  }
405 
412  std::unique_ptr<Buffer> get_last_nested() {
413  assert(has_nested_buffers());
414  Buffer* buffer = this;
415  while (buffer->m_next_buffer->has_nested_buffers()) {
416  buffer = buffer->m_next_buffer.get();
417  }
418  return std::move(buffer->m_next_buffer);
419  }
420 
433  std::size_t commit() {
434  assert(m_data && "This must be a valid buffer");
435  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
436  assert(is_aligned());
437 
438  const std::size_t offset = m_committed;
439  m_committed = m_written;
440  return offset;
441  }
442 
449  void rollback() {
450  assert(m_data && "This must be a valid buffer");
451  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
452  m_written = m_committed;
453  }
454 
464  std::size_t clear() {
465  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
466  const std::size_t num_used_bytes = m_committed;
467  m_written = 0;
468  m_committed = 0;
469  return num_used_bytes;
470  }
471 
482  template <typename T>
483  T& get(const std::size_t offset) const {
484  assert(m_data && "This must be a valid buffer");
485  assert(offset % alignof(T) == 0 && "Wrong alignment");
486  return *reinterpret_cast<T*>(&m_data[offset]);
487  }
488 
515  unsigned char* reserve_space(const std::size_t size) {
516  assert(m_data && "This must be a valid buffer");
517  // if there's still not enough space, then try growing the buffer.
518  if (m_written + size > m_capacity) {
519  if (!m_memory || m_auto_grow == auto_grow::no) {
520  throw osmium::buffer_is_full{};
521  }
522  if (m_auto_grow == auto_grow::internal && m_committed != 0) {
523  grow_internal();
524  }
525  if (m_written + size > m_capacity) {
526  // double buffer size until there is enough space
527  std::size_t new_capacity = m_capacity * 2;
528  while (m_written + size > new_capacity) {
529  new_capacity *= 2;
530  }
531  grow(new_capacity);
532  }
533  }
534  unsigned char* reserved_space = &m_data[m_written];
535  m_written += size;
536  return reserved_space;
537  }
538 
554  template <typename T>
555  T& add_item(const T& item) {
556  assert(m_data && "This must be a valid buffer");
557  unsigned char* target = reserve_space(item.padded_size());
558  std::copy_n(reinterpret_cast<const unsigned char*>(&item), item.padded_size(), target);
559  return *reinterpret_cast<T*>(target);
560  }
561 
573  void add_buffer(const Buffer& buffer) {
574  assert(m_data && "This must be a valid buffer");
575  assert(buffer && "Buffer parameter must be a valid buffer");
576  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
577  unsigned char* target = reserve_space(buffer.committed());
578  std::copy_n(buffer.data(), buffer.committed(), target);
579  }
580 
590  void push_back(const osmium::memory::Item& item) {
591  assert(m_data && "This must be a valid buffer");
592  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
593  add_item(item);
594  commit();
595  }
596 
601  template <typename T>
602  using t_iterator = osmium::memory::ItemIterator<T>;
603 
608  template <typename T>
609  using t_const_iterator = osmium::memory::ItemIterator<const T>;
610 
615  using iterator = t_iterator<osmium::OSMEntity>;
616 
621  using const_iterator = t_const_iterator<osmium::OSMEntity>;
622 
623  template <typename T>
624  ItemIteratorRange<T> select() {
625  return ItemIteratorRange<T>{m_data, m_data + m_committed};
626  }
627 
628  template <typename T>
629  ItemIteratorRange<const T> select() const {
630  return ItemIteratorRange<const T>{m_data, m_data + m_committed};
631  }
632 
641  template <typename T>
642  t_iterator<T> begin() {
643  assert(m_data && "This must be a valid buffer");
644  return t_iterator<T>(m_data, m_data + m_committed);
645  }
646 
655  iterator begin() {
656  assert(m_data && "This must be a valid buffer");
657  return {m_data, m_data + m_committed};
658  }
659 
669  template <typename T>
670  t_iterator<T> get_iterator(std::size_t offset) {
671  assert(m_data && "This must be a valid buffer");
672  assert(offset % alignof(T) == 0 && "Wrong alignment");
673  return {m_data + offset, m_data + m_committed};
674  }
675 
685  iterator get_iterator(std::size_t offset) {
686  assert(m_data && "This must be a valid buffer");
687  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
688  return {m_data + offset, m_data + m_committed};
689  }
690 
699  template <typename T>
700  t_iterator<T> end() {
701  assert(m_data && "This must be a valid buffer");
702  return {m_data + m_committed, m_data + m_committed};
703  }
704 
713  iterator end() {
714  assert(m_data && "This must be a valid buffer");
715  return {m_data + m_committed, m_data + m_committed};
716  }
717 
718  template <typename T>
719  t_const_iterator<T> cbegin() const {
720  assert(m_data && "This must be a valid buffer");
721  return {m_data, m_data + m_committed};
722  }
723 
724  const_iterator cbegin() const {
725  assert(m_data && "This must be a valid buffer");
726  return {m_data, m_data + m_committed};
727  }
728 
729  template <typename T>
730  t_const_iterator<T> get_iterator(std::size_t offset) const {
731  assert(m_data && "This must be a valid buffer");
732  assert(offset % alignof(T) == 0 && "Wrong alignment");
733  return {m_data + offset, m_data + m_committed};
734  }
735 
736  const_iterator get_iterator(std::size_t offset) const {
737  assert(m_data && "This must be a valid buffer");
738  assert(offset % alignof(OSMEntity) == 0 && "Wrong alignment");
739  return {m_data + offset, m_data + m_committed};
740  }
741 
742  template <typename T>
743  t_const_iterator<T> cend() const {
744  assert(m_data && "This must be a valid buffer");
745  return {m_data + m_committed, m_data + m_committed};
746  }
747 
748  const_iterator cend() const {
749  assert(m_data && "This must be a valid buffer");
750  return {m_data + m_committed, m_data + m_committed};
751  }
752 
753  template <typename T>
754  t_const_iterator<T> begin() const {
755  return cbegin<T>();
756  }
757 
758  const_iterator begin() const {
759  return cbegin();
760  }
761 
762  template <typename T>
763  t_const_iterator<T> end() const {
764  return cend<T>();
765  }
766 
767  const_iterator end() const {
768  return cend();
769  }
770 
774  explicit operator bool() const noexcept {
775  return m_data != nullptr;
776  }
777 
778  void swap(Buffer& other) {
779  using std::swap;
780 
781  swap(m_next_buffer, other.m_next_buffer);
782  swap(m_memory, other.m_memory);
783  swap(m_data, other.m_data);
784  swap(m_capacity, other.m_capacity);
785  swap(m_written, other.m_written);
786  swap(m_committed, other.m_committed);
787  swap(m_auto_grow, other.m_auto_grow);
788  }
789 
807  template <typename TCallbackClass>
808  void purge_removed(TCallbackClass* callback) {
809  assert(m_data && "This must be a valid buffer");
810  assert(callback);
811 
812  if (begin() == end()) {
813  return;
814  }
815 
816  iterator it_write = begin();
817 
818  iterator next;
819  for (iterator it_read = begin(); it_read != end(); it_read = next) {
820  next = std::next(it_read);
821  if (!it_read->removed()) {
822  if (it_read != it_write) {
823  assert(it_read.data() >= data());
824  assert(it_write.data() >= data());
825  const auto old_offset = static_cast<std::size_t>(it_read.data() - data());
826  const auto new_offset = static_cast<std::size_t>(it_write.data() - data());
827  callback->moving_in_buffer(old_offset, new_offset);
828  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
829  }
830  it_write.advance_once();
831  }
832  }
833 
834  assert(it_write.data() >= data());
835  m_written = static_cast<std::size_t>(it_write.data() - data());
836  m_committed = m_written;
837  }
838 
849  void purge_removed() {
850  assert(m_data && "This must be a valid buffer");
851  if (begin() == end()) {
852  return;
853  }
854 
855  iterator it_write = begin();
856 
857  iterator next;
858  for (iterator it_read = begin(); it_read != end(); it_read = next) {
859  next = std::next(it_read);
860  if (!it_read->removed()) {
861  if (it_read != it_write) {
862  assert(it_read.data() >= data());
863  assert(it_write.data() >= data());
864  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
865  }
866  it_write.advance_once();
867  }
868  }
869 
870  assert(it_write.data() >= data());
871  m_written = static_cast<std::size_t>(it_write.data() - data());
872  m_committed = m_written;
873  }
874 
875  }; // class Buffer
876 
877  inline void swap(Buffer& lhs, Buffer& rhs) {
878  lhs.swap(rhs);
879  }
880 
888  inline bool operator==(const Buffer& lhs, const Buffer& rhs) noexcept {
889  if (!lhs || !rhs) {
890  return !lhs && !rhs;
891  }
892  return lhs.data() == rhs.data() && lhs.capacity() == rhs.capacity() && lhs.committed() == rhs.committed();
893  }
894 
895  inline bool operator!=(const Buffer& lhs, const Buffer& rhs) noexcept {
896  return !(lhs == rhs);
897  }
898 
899  } // namespace memory
900 
901 } // namespace osmium
902 
903 #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:440
bool operator!=(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:444
Definition: location.hpp:555