Vince's CSV Parser
Loading...
Searching...
No Matches
block_arena.hpp
Go to the documentation of this file.
1
5#pragma once
6
7#include <algorithm>
8#include <atomic>
9#include <cassert>
10#include <memory>
11#include <utility>
12#include <vector>
13
14#include "../common.hpp"
15
16namespace csv {
17 namespace internals {
18 namespace memory {
25 template<typename T>
27 public:
28 struct Allocation {
29 Allocation() : offset(0), data(nullptr) {}
30
31 Allocation(CSVChunkIndex offset_, T* data_) : offset(offset_), data(data_) {}
32
33 CSVChunkIndex offset = 0;
34 T* data = nullptr;
35 };
36
37 explicit RawCSVBlockArena(size_t default_block_capacity, bool grow_blocks = true)
38 : default_block_capacity_(default_block_capacity == 0 ? 1 : default_block_capacity),
39 grow_blocks_(grow_blocks) {
40 this->blocks_.reserve(1);
41 }
42
43 RawCSVBlockArena(const RawCSVBlockArena&) = delete;
44 RawCSVBlockArena& operator=(const RawCSVBlockArena&) = delete;
45
47 : default_block_capacity_(other.default_block_capacity_),
48 grow_blocks_(other.grow_blocks_),
49 next_block_capacity_(other.next_block_capacity_),
50 blocks_(std::move(other.blocks_)) {
51 this->size_.store(other.size_.load(std::memory_order_acquire), std::memory_order_release);
52 this->block_count_.store(other.block_count_.load(std::memory_order_acquire), std::memory_order_release);
53 other.size_.store(0, std::memory_order_release);
54 other.block_count_.store(0, std::memory_order_release);
55 }
56
57 RawCSVBlockArena& operator=(RawCSVBlockArena&& other) noexcept {
58 if (this == &other) {
59 return *this;
60 }
61
62 this->default_block_capacity_ = other.default_block_capacity_;
63 this->grow_blocks_ = other.grow_blocks_;
64 this->next_block_capacity_ = other.next_block_capacity_;
65 this->blocks_ = std::move(other.blocks_);
66 this->size_.store(other.size_.load(std::memory_order_acquire), std::memory_order_release);
67 this->block_count_.store(other.block_count_.load(std::memory_order_acquire), std::memory_order_release);
68 other.size_.store(0, std::memory_order_release);
69 other.block_count_.store(0, std::memory_order_release);
70 return *this;
71 }
72
73 template<class... Args>
74 T& emplace_back(Args&&... args) {
75 Allocation allocation = this->allocate_contiguous(1);
76 *allocation.data = T(std::forward<Args>(args)...);
77 return *allocation.data;
78 }
79
80 Allocation allocate_contiguous(size_t count) {
81 if (count == 0) {
82 return Allocation{ this->checked_offset(this->size_.load(std::memory_order_acquire)), nullptr };
83 }
84
85 if (this->block_count_.load(std::memory_order_acquire) == 0
86 || this->current_block().used.load(std::memory_order_acquire) + count > this->current_block().capacity) {
87 this->allocate_block(count);
88 }
89
90 Block& block = this->current_block();
91 const size_t block_used = block.used.load(std::memory_order_acquire);
92 Allocation allocation{
93 this->checked_offset(block.logical_start + block_used),
94 block.values.get() + block_used
95 };
96 block.used.store(block_used + count, std::memory_order_release);
97 this->size_.fetch_add(count, std::memory_order_release);
98 return allocation;
99 }
100
101 T& operator[](size_t n) const {
102 assert(n < this->size_.load(std::memory_order_acquire));
103 const Block& block = this->find_block(n);
104 return block.values.get()[n - block.logical_start];
105 }
106
107 size_t size() const noexcept {
108 return this->size_.load(std::memory_order_acquire);
109 }
110
111 csv::string_view view(size_t offset, size_t length) const {
112 if (length == 0) {
113 return csv::string_view();
114 }
115
116 const Block& block = this->find_block(offset);
117 assert(offset + length <= block.logical_start + block.used.load(std::memory_order_acquire));
118 const size_t block_offset = offset - block.logical_start;
119 return csv::string_view(block.values.get() + block_offset, length);
120 }
121
122 void reserve_blocks(size_t count) {
123 if (count > this->blocks_.size()) {
124 this->blocks_.resize(count);
125 }
126 }
127
128 private:
129 struct Block {
130 std::unique_ptr<T[]> values;
131 size_t capacity = 0;
132 std::atomic<size_t> used{ 0 };
133 size_t logical_start = 0;
134 };
135
136 size_t default_block_capacity_;
137 bool grow_blocks_;
138 size_t next_block_capacity_ = 0;
139 std::vector<std::unique_ptr<Block>> blocks_;
140 std::atomic<size_t> size_{ 0 };
141 std::atomic<size_t> block_count_{ 0 };
142
143 CSVChunkIndex checked_offset(size_t value) const noexcept {
144 assert(value <= CSV_CHUNK_INDEX_MAX);
145 return static_cast<CSVChunkIndex>(value);
146 }
147
148 void allocate_block(size_t required_capacity) {
149 const size_t block_count = this->block_count_.load(std::memory_order_acquire);
150 if (block_count >= this->blocks_.size()) {
151 this->blocks_.resize((std::max)(size_t(1), this->blocks_.size() * 2));
152 }
153
154 const size_t baseline = this->next_block_capacity_ == 0
155 ? this->default_block_capacity_
156 : this->next_block_capacity_;
157 const size_t capacity = (std::max)(baseline, required_capacity);
158
159 if (!this->blocks_[block_count]) {
160 this->blocks_[block_count] = std::unique_ptr<Block>(new Block());
161 }
162
163 Block& block = *this->blocks_[block_count];
164 block.values = std::unique_ptr<T[]>(new T[capacity]);
165 block.capacity = capacity;
166 block.used.store(0, std::memory_order_release);
167 block.logical_start = this->size_.load(std::memory_order_acquire);
168
169 if (required_capacity > baseline) {
170 this->next_block_capacity_ = this->default_block_capacity_;
171 }
172 else if (this->grow_blocks_ && baseline < this->default_block_capacity_ * 4) {
173 this->next_block_capacity_ = baseline * 2;
174 }
175 else {
176 this->next_block_capacity_ = baseline;
177 }
178
179 this->block_count_.store(block_count + 1, std::memory_order_release);
180 }
181
182 Block& current_block() {
183 const size_t block_count = this->block_count_.load(std::memory_order_acquire);
184 return *this->blocks_[block_count - 1];
185 }
186
187 const Block& find_block(size_t offset) const {
188 size_t low = 0;
189 size_t high = this->block_count_.load(std::memory_order_acquire);
190 while (low < high) {
191 const size_t mid = low + (high - low) / 2;
192 const Block& block = *this->blocks_[mid];
193 if (offset < block.logical_start) {
194 high = mid;
195 }
196 else if (offset >= block.logical_start + block.used.load(std::memory_order_acquire)) {
197 low = mid + 1;
198 }
199 else {
200 return block;
201 }
202 }
203
204 assert(false && "RawCSVBlockArena offset out of range");
205 return *this->blocks_[this->block_count_.load(std::memory_order_acquire) - 1];
206 }
207 };
208 }
209 }
210}
Borrow a row and error state for synchronous, single-pass field access.
Variable-size block arena used for quote realization bytes.
std::uint32_t CSVChunkIndex
Type used to represent the location of a CSV byte within a larger chunk.
Definition common.hpp:419
The all encompassing namespace.
std::string_view string_view
The string_view class used by this library.
Definition common.hpp:182