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
6This file is part of Osmium (https://osmcode.org/libosmium).
7
8Copyright 2013-2022 Jochen Topf <jochen@topf.org> and others (see README).
9
10Boost Software License - Version 1.0 - August 17th, 2003
11
12Permission is hereby granted, free of charge, to any person or organization
13obtaining a copy of the software and accompanying documentation covered by
14this license (the "Software") to use, reproduce, display, distribute,
15execute, and transmit the Software, and to prepare derivative works of the
16Software, and to permit third-parties to whom the Software is furnished to
17do so, all subject to the following:
18
19The copyright notices in the Software and this entire statement, including
20the above license grant, this restriction and the following disclaimer,
21must be included in all copies of the Software, in whole or in part, and
22all derivative works of the Software, unless such copies or derivative
23works are solely in the form of machine-executable object code generated by
24a source language processor.
25
26THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
27IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
28FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT
29SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE
30FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE,
31ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
32DEALINGS IN THE SOFTWARE.
33
34*/
35
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
51namespace 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 > end(Reader &)
Definition: reader_iterator.hpp:47
InputIterator< Reader > begin(Reader &reader)
Definition: reader_iterator.hpp:43
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