Libosmium  2.15.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-2018 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
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 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  return *reinterpret_cast<T*>(&m_data[offset]);
521  }
522 
556  unsigned char* reserve_space(const std::size_t size) {
557  assert(m_data && "This must be a valid buffer");
558  // try to flush the buffer empty first.
559  if (m_written + size > m_capacity && m_full) {
560  m_full(*this);
561  }
562  // if there's still not enough space, then try growing the buffer.
563  if (m_written + size > m_capacity) {
564  if (!m_memory || m_auto_grow == auto_grow::no) {
565  throw osmium::buffer_is_full{};
566  }
567  if (m_auto_grow == auto_grow::internal && m_committed != 0) {
568  grow_internal();
569  }
570  if (m_written + size > m_capacity) {
571  // double buffer size until there is enough space
572  std::size_t new_capacity = m_capacity * 2;
573  while (m_written + size > new_capacity) {
574  new_capacity *= 2;
575  }
576  grow(new_capacity);
577  }
578  }
579  unsigned char* data = &m_data[m_written];
580  m_written += size;
581  return data;
582  }
583 
599  template <typename T>
600  T& add_item(const T& item) {
601  assert(m_data && "This must be a valid buffer");
602  unsigned char* target = reserve_space(item.padded_size());
603  std::copy_n(reinterpret_cast<const unsigned char*>(&item), item.padded_size(), target);
604  return *reinterpret_cast<T*>(target);
605  }
606 
618  void add_buffer(const Buffer& buffer) {
619  assert(m_data && "This must be a valid buffer");
620  assert(buffer && "Buffer parameter must be a valid buffer");
621  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
622  unsigned char* target = reserve_space(buffer.committed());
623  std::copy_n(buffer.data(), buffer.committed(), target);
624  }
625 
635  void push_back(const osmium::memory::Item& item) {
636  assert(m_data && "This must be a valid buffer");
637  assert(m_builder_count == 0 && "Make sure there are no Builder objects still in scope");
638  add_item(item);
639  commit();
640  }
641 
646  template <typename T>
648 
653  template <typename T>
655 
661 
667 
668  template <typename T>
670  return ItemIteratorRange<T>{m_data, m_data + m_committed};
671  }
672 
673  template <typename T>
675  return ItemIteratorRange<const T>{m_data, m_data + m_committed};
676  }
677 
686  template <typename T>
688  assert(m_data && "This must be a valid buffer");
689  return t_iterator<T>(m_data, m_data + m_committed);
690  }
691 
701  assert(m_data && "This must be a valid buffer");
702  return {m_data, m_data + m_committed};
703  }
704 
714  template <typename T>
715  t_iterator<T> get_iterator(std::size_t offset) {
716  assert(m_data && "This must be a valid buffer");
717  return {m_data + offset, m_data + m_committed};
718  }
719 
729  iterator get_iterator(std::size_t offset) {
730  assert(m_data && "This must be a valid buffer");
731  return {m_data + offset, m_data + m_committed};
732  }
733 
742  template <typename T>
744  assert(m_data && "This must be a valid buffer");
745  return {m_data + m_committed, m_data + m_committed};
746  }
747 
757  assert(m_data && "This must be a valid buffer");
758  return {m_data + m_committed, m_data + m_committed};
759  }
760 
761  template <typename T>
763  assert(m_data && "This must be a valid buffer");
764  return {m_data, m_data + m_committed};
765  }
766 
768  assert(m_data && "This must be a valid buffer");
769  return {m_data, m_data + m_committed};
770  }
771 
772  template <typename T>
773  t_const_iterator<T> get_iterator(std::size_t offset) const {
774  assert(m_data && "This must be a valid buffer");
775  return {m_data + offset, m_data + m_committed};
776  }
777 
778  const_iterator get_iterator(std::size_t offset) const {
779  assert(m_data && "This must be a valid buffer");
780  return {m_data + offset, m_data + m_committed};
781  }
782 
783  template <typename T>
785  assert(m_data && "This must be a valid buffer");
786  return {m_data + m_committed, m_data + m_committed};
787  }
788 
790  assert(m_data && "This must be a valid buffer");
791  return {m_data + m_committed, m_data + m_committed};
792  }
793 
794  template <typename T>
796  return cbegin<T>();
797  }
798 
800  return cbegin();
801  }
802 
803  template <typename T>
805  return cend<T>();
806  }
807 
808  const_iterator end() const {
809  return cend();
810  }
811 
815  explicit operator bool() const noexcept {
816  return m_data != nullptr;
817  }
818 
819  void swap(Buffer& other) {
820  using std::swap;
821 
822  swap(m_next_buffer, other.m_next_buffer);
823  swap(m_memory, other.m_memory);
824  swap(m_data, other.m_data);
825  swap(m_capacity, other.m_capacity);
826  swap(m_written, other.m_written);
827  swap(m_committed, other.m_committed);
828  swap(m_auto_grow, other.m_auto_grow);
829  swap(m_full, other.m_full);
830  }
831 
848  template <typename TCallbackClass>
849  void purge_removed(TCallbackClass* callback) {
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  const auto old_offset = static_cast<std::size_t>(it_read.data() - data());
865  const auto new_offset = static_cast<std::size_t>(it_write.data() - data());
866  callback->moving_in_buffer(old_offset, new_offset);
867  std::memmove(it_write.data(), it_read.data(), it_read->padded_size());
868  }
869  it_write.advance_once();
870  }
871  }
872 
873  assert(it_write.data() >= data());
874  m_written = static_cast<std::size_t>(it_write.data() - data());
875  m_committed = m_written;
876  }
877 
878  }; // class Buffer
879 
880  inline void swap(Buffer& lhs, Buffer& rhs) {
881  lhs.swap(rhs);
882  }
883 
891  inline bool operator==(const Buffer& lhs, const Buffer& rhs) noexcept {
892  if (!lhs || !rhs) {
893  return !lhs && !rhs;
894  }
895  return lhs.data() == rhs.data() && lhs.capacity() == rhs.capacity() && lhs.committed() == rhs.committed();
896  }
897 
898  inline bool operator!=(const Buffer& lhs, const Buffer& rhs) noexcept {
899  return !(lhs == rhs);
900  }
901 
902  } // namespace memory
903 
904 } // namespace osmium
905 
906 #endif // OSMIUM_MEMORY_BUFFER_HPP
Buffer(Buffer &&other) noexcept
Definition: buffer.hpp:274
void swap(Buffer &other)
Definition: buffer.hpp:819
std::size_t capacity() const noexcept
Definition: buffer.hpp:348
t_const_iterator< T > begin() const
Definition: buffer.hpp:795
std::size_t commit()
Definition: buffer.hpp:468
#define OSMIUM_DEPRECATED
Definition: compatibility.hpp:50
bool is_aligned() const noexcept
Definition: buffer.hpp:375
iterator get_iterator(std::size_t offset)
Definition: buffer.hpp:729
Definition: item_iterator.hpp:175
void grow_internal()
Definition: buffer.hpp:136
t_const_iterator< T > cend() const
Definition: buffer.hpp:784
const_iterator cend() const
Definition: buffer.hpp:789
Definition: item_iterator.hpp:59
OSMIUM_DEPRECATED void set_full_callback(const std::function< void(Buffer &)> &full)
Definition: buffer.hpp:395
constexpr bool operator==(const Box &lhs, const Box &rhs) noexcept
Definition: box.hpp:212
unsigned char * m_data
Definition: buffer.hpp:114
InputIterator< Reader > end(Reader &)
Definition: reader_iterator.hpp:47
std::size_t m_committed
Definition: buffer.hpp:117
void increment_builder_count() noexcept
Definition: buffer.hpp:320
Definition: location.hpp:554
ItemIteratorRange< const T > select() const
Definition: buffer.hpp:674
void swap(Buffer &lhs, Buffer &rhs)
Definition: buffer.hpp:880
t_const_iterator< T > get_iterator(std::size_t offset) const
Definition: buffer.hpp:773
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:799
InputIterator< Reader > begin(Reader &reader)
Definition: reader_iterator.hpp:43
std::size_t m_capacity
Definition: buffer.hpp:115
t_iterator< T > end()
Definition: buffer.hpp:743
Definition: item.hpp:105
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:600
void purge_removed(TCallbackClass *callback)
Definition: buffer.hpp:849
t_iterator< T > begin()
Definition: buffer.hpp:687
void add_buffer(const Buffer &buffer)
Definition: buffer.hpp:618
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:556
auto_grow m_auto_grow
Definition: buffer.hpp:121
void push_back(const osmium::memory::Item &item)
Definition: buffer.hpp:635
Buffer(std::unique_ptr< unsigned char[]> data, std::size_t capacity, std::size_t committed)
Definition: buffer.hpp:231
iterator end()
Definition: buffer.hpp:756
iterator begin()
Definition: buffer.hpp:700
bool has_nested_buffers() const noexcept
Definition: buffer.hpp:437
const_iterator get_iterator(std::size_t offset) const
Definition: buffer.hpp:778
Definition: buffer.hpp:97
Buffer & operator=(Buffer &&other) noexcept
Definition: buffer.hpp:295
t_const_iterator< T > cbegin() const
Definition: buffer.hpp:762
Definition: buffer.hpp:58
void decrement_builder_count() noexcept
Definition: buffer.hpp:324
const_iterator end() const
Definition: buffer.hpp:808
t_const_iterator< T > end() const
Definition: buffer.hpp:804
data_type data() noexcept
Definition: item_iterator.hpp:135
t_iterator< T > get_iterator(std::size_t offset)
Definition: buffer.hpp:715
buffer_is_full()
Definition: buffer.hpp:60
ItemIteratorRange< T > select()
Definition: buffer.hpp:669
Definition: item.hpp:61
void rollback()
Definition: buffer.hpp:484
std::unique_ptr< unsigned char[]> m_memory
Definition: buffer.hpp:113
bool operator!=(const Changeset &lhs, const Changeset &rhs)
Definition: changeset.hpp:446
std::unique_ptr< Buffer > get_last_nested()
Definition: buffer.hpp:447
const_iterator cbegin() const
Definition: buffer.hpp:767
std::function< void(Buffer &)> m_full
Definition: buffer.hpp:122