1 /* 2 * Copyright 2021 Google Inc. All rights reserved. 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #ifndef FLATBUFFERS_VECTOR_DOWNWARD_H_ 18 #define FLATBUFFERS_VECTOR_DOWNWARD_H_ 19 20 #include <algorithm> 21 #include <cstdint> 22 23 #include "flatbuffers/base.h" 24 #include "flatbuffers/default_allocator.h" 25 #include "flatbuffers/detached_buffer.h" 26 27 namespace flatbuffers { 28 29 // This is a minimal replication of std::vector<uint8_t> functionality, 30 // except growing from higher to lower addresses. i.e. push_back() inserts data 31 // in the lowest address in the vector. 32 // Since this vector leaves the lower part unused, we support a "scratch-pad" 33 // that can be stored there for temporary data, to share the allocated space. 34 // Essentially, this supports 2 std::vectors in a single buffer. 35 template<typename SizeT = uoffset_t> class vector_downward { 36 public: 37 explicit vector_downward(size_t initial_size, Allocator *allocator, 38 bool own_allocator, size_t buffer_minalign, 39 const SizeT max_size = FLATBUFFERS_MAX_BUFFER_SIZE) allocator_(allocator)40 : allocator_(allocator), 41 own_allocator_(own_allocator), 42 initial_size_(initial_size), 43 max_size_(max_size), 44 buffer_minalign_(buffer_minalign), 45 reserved_(0), 46 size_(0), 47 buf_(nullptr), 48 cur_(nullptr), 49 scratch_(nullptr) {} 50 vector_downward(vector_downward && other)51 vector_downward(vector_downward &&other) noexcept 52 // clang-format on 53 : allocator_(other.allocator_), 54 own_allocator_(other.own_allocator_), 55 initial_size_(other.initial_size_), 56 max_size_(other.max_size_), 57 buffer_minalign_(other.buffer_minalign_), 58 reserved_(other.reserved_), 59 size_(other.size_), 60 buf_(other.buf_), 61 cur_(other.cur_), 62 scratch_(other.scratch_) { 63 // No change in other.allocator_ 64 // No change in other.initial_size_ 65 // No change in other.buffer_minalign_ 66 other.own_allocator_ = false; 67 other.reserved_ = 0; 68 other.buf_ = nullptr; 69 other.cur_ = nullptr; 70 other.scratch_ = nullptr; 71 } 72 73 vector_downward &operator=(vector_downward &&other) noexcept { 74 // Move construct a temporary and swap idiom 75 vector_downward temp(std::move(other)); 76 swap(temp); 77 return *this; 78 } 79 ~vector_downward()80 ~vector_downward() { 81 clear_buffer(); 82 clear_allocator(); 83 } 84 reset()85 void reset() { 86 clear_buffer(); 87 clear(); 88 } 89 clear()90 void clear() { 91 if (buf_) { 92 cur_ = buf_ + reserved_; 93 } else { 94 reserved_ = 0; 95 cur_ = nullptr; 96 } 97 size_ = 0; 98 clear_scratch(); 99 } 100 clear_scratch()101 void clear_scratch() { scratch_ = buf_; } 102 clear_allocator()103 void clear_allocator() { 104 if (own_allocator_ && allocator_) { delete allocator_; } 105 allocator_ = nullptr; 106 own_allocator_ = false; 107 } 108 clear_buffer()109 void clear_buffer() { 110 if (buf_) Deallocate(allocator_, buf_, reserved_); 111 buf_ = nullptr; 112 } 113 114 // Relinquish the pointer to the caller. release_raw(size_t & allocated_bytes,size_t & offset)115 uint8_t *release_raw(size_t &allocated_bytes, size_t &offset) { 116 auto *buf = buf_; 117 allocated_bytes = reserved_; 118 offset = vector_downward::offset(); 119 120 // release_raw only relinquishes the buffer ownership. 121 // Does not deallocate or reset the allocator. Destructor will do that. 122 buf_ = nullptr; 123 clear(); 124 return buf; 125 } 126 127 // Relinquish the pointer to the caller. release()128 DetachedBuffer release() { 129 // allocator ownership (if any) is transferred to DetachedBuffer. 130 DetachedBuffer fb(allocator_, own_allocator_, buf_, reserved_, cur_, 131 size()); 132 if (own_allocator_) { 133 allocator_ = nullptr; 134 own_allocator_ = false; 135 } 136 buf_ = nullptr; 137 clear(); 138 return fb; 139 } 140 ensure_space(size_t len)141 size_t ensure_space(size_t len) { 142 FLATBUFFERS_ASSERT(cur_ >= scratch_ && scratch_ >= buf_); 143 // If the length is larger than the unused part of the buffer, we need to 144 // grow. 145 if (len > unused_buffer_size()) { reallocate(len); } 146 FLATBUFFERS_ASSERT(size() < max_size_); 147 return len; 148 } 149 make_space(size_t len)150 inline uint8_t *make_space(size_t len) { 151 if (len) { 152 ensure_space(len); 153 cur_ -= len; 154 size_ += static_cast<SizeT>(len); 155 } 156 return cur_; 157 } 158 159 // Returns nullptr if using the DefaultAllocator. get_custom_allocator()160 Allocator *get_custom_allocator() { return allocator_; } 161 162 // The current offset into the buffer. offset()163 size_t offset() const { return cur_ - buf_; } 164 165 // The total size of the vector (both the buffer and scratch parts). size()166 inline SizeT size() const { return size_; } 167 168 // The size of the buffer part of the vector that is currently unused. unused_buffer_size()169 SizeT unused_buffer_size() const { 170 return static_cast<SizeT>(cur_ - scratch_); 171 } 172 173 // The size of the scratch part of the vector. scratch_size()174 SizeT scratch_size() const { return static_cast<SizeT>(scratch_ - buf_); } 175 capacity()176 size_t capacity() const { return reserved_; } 177 data()178 uint8_t *data() const { 179 FLATBUFFERS_ASSERT(cur_); 180 return cur_; 181 } 182 scratch_data()183 uint8_t *scratch_data() const { 184 FLATBUFFERS_ASSERT(buf_); 185 return buf_; 186 } 187 scratch_end()188 uint8_t *scratch_end() const { 189 FLATBUFFERS_ASSERT(scratch_); 190 return scratch_; 191 } 192 data_at(size_t offset)193 uint8_t *data_at(size_t offset) const { return buf_ + reserved_ - offset; } 194 push(const uint8_t * bytes,size_t num)195 void push(const uint8_t *bytes, size_t num) { 196 if (num > 0) { memcpy(make_space(num), bytes, num); } 197 } 198 199 // Specialized version of push() that avoids memcpy call for small data. push_small(const T & little_endian_t)200 template<typename T> void push_small(const T &little_endian_t) { 201 make_space(sizeof(T)); 202 *reinterpret_cast<T *>(cur_) = little_endian_t; 203 } 204 scratch_push_small(const T & t)205 template<typename T> void scratch_push_small(const T &t) { 206 ensure_space(sizeof(T)); 207 *reinterpret_cast<T *>(scratch_) = t; 208 scratch_ += sizeof(T); 209 } 210 211 // fill() is most frequently called with small byte counts (<= 4), 212 // which is why we're using loops rather than calling memset. fill(size_t zero_pad_bytes)213 void fill(size_t zero_pad_bytes) { 214 make_space(zero_pad_bytes); 215 for (size_t i = 0; i < zero_pad_bytes; i++) cur_[i] = 0; 216 } 217 218 // Version for when we know the size is larger. 219 // Precondition: zero_pad_bytes > 0 fill_big(size_t zero_pad_bytes)220 void fill_big(size_t zero_pad_bytes) { 221 memset(make_space(zero_pad_bytes), 0, zero_pad_bytes); 222 } 223 pop(size_t bytes_to_remove)224 void pop(size_t bytes_to_remove) { 225 cur_ += bytes_to_remove; 226 size_ -= static_cast<SizeT>(bytes_to_remove); 227 } 228 scratch_pop(size_t bytes_to_remove)229 void scratch_pop(size_t bytes_to_remove) { scratch_ -= bytes_to_remove; } 230 swap(vector_downward & other)231 void swap(vector_downward &other) { 232 using std::swap; 233 swap(allocator_, other.allocator_); 234 swap(own_allocator_, other.own_allocator_); 235 swap(initial_size_, other.initial_size_); 236 swap(buffer_minalign_, other.buffer_minalign_); 237 swap(reserved_, other.reserved_); 238 swap(size_, other.size_); 239 swap(max_size_, other.max_size_); 240 swap(buf_, other.buf_); 241 swap(cur_, other.cur_); 242 swap(scratch_, other.scratch_); 243 } 244 swap_allocator(vector_downward & other)245 void swap_allocator(vector_downward &other) { 246 using std::swap; 247 swap(allocator_, other.allocator_); 248 swap(own_allocator_, other.own_allocator_); 249 } 250 251 private: 252 // You shouldn't really be copying instances of this class. 253 FLATBUFFERS_DELETE_FUNC(vector_downward(const vector_downward &)); 254 FLATBUFFERS_DELETE_FUNC(vector_downward &operator=(const vector_downward &)); 255 256 Allocator *allocator_; 257 bool own_allocator_; 258 size_t initial_size_; 259 260 // The maximum size the vector can be. 261 SizeT max_size_; 262 size_t buffer_minalign_; 263 size_t reserved_; 264 SizeT size_; 265 uint8_t *buf_; 266 uint8_t *cur_; // Points at location between empty (below) and used (above). 267 uint8_t *scratch_; // Points to the end of the scratchpad in use. 268 reallocate(size_t len)269 void reallocate(size_t len) { 270 auto old_reserved = reserved_; 271 auto old_size = size(); 272 auto old_scratch_size = scratch_size(); 273 reserved_ += 274 (std::max)(len, old_reserved ? old_reserved / 2 : initial_size_); 275 reserved_ = (reserved_ + buffer_minalign_ - 1) & ~(buffer_minalign_ - 1); 276 if (buf_) { 277 buf_ = ReallocateDownward(allocator_, buf_, old_reserved, reserved_, 278 old_size, old_scratch_size); 279 } else { 280 buf_ = Allocate(allocator_, reserved_); 281 } 282 cur_ = buf_ + reserved_ - old_size; 283 scratch_ = buf_ + old_scratch_size; 284 } 285 }; 286 287 } // namespace flatbuffers 288 289 #endif // FLATBUFFERS_VECTOR_DOWNWARD_H_ 290