24#ifndef PINEFORGE_ARRAY_HPP
25#define PINEFORGE_ARRAY_HPP
35#include <initializer_list>
54static_assert(
sizeof(
StoreHeader) == 32,
"array object header layout");
55inline constexpr std::uint64_t
kHeaderMagic = UINT64_C(0x5046415252303032);
58[[noreturn]]
void index_error(
const char*, std::int64_t, std::uint64_t,
bool missing =
false);
70 void* destination, std::size_t bytes) {
71 if (store.
read(
id, offset, destination, bytes) != bytes)
76 const void*
source, std::size_t bytes) {
77 if (store.
write(
id, offset,
source, bytes) != bytes)
81inline std::uint64_t
checked(std::int64_t raw, std::uint64_t size,
82 const char* method,
bool relative,
bool end =
false) {
83 if (raw == std::numeric_limits<std::int64_t>::min())
index_error(method, raw, size,
true);
86 const auto index = relative && raw < 0 ? raw + static_cast<std::int64_t>(size) : raw;
87 if (index < 0 || (
end ?
static_cast<std::uint64_t
>(index) > size
88 :
static_cast<std::uint64_t
>(index) >= size))
90 return static_cast<std::uint64_t
>(index);
95 static_assert(std::is_arithmetic_v<Index>,
"array index must be numeric");
96 if constexpr (std::is_floating_point_v<Index>) {
98 }
else if constexpr (std::is_unsigned_v<Index>) {
99 if (
value >
static_cast<std::uint64_t
>(std::numeric_limits<std::int64_t>::max()))
101 }
else if constexpr (!std::is_same_v<Index, bool>) {
104 return static_cast<std::int64_t
>(
value);
107template<
class T,
class =
void>
struct HasId : std::false_type {};
109struct HasId<T,
std::void_t<decltype(std::declval<T>().id)>> : std::true_type {};
113template<
class T,
class Enable =
void>
115 static_assert(std::is_trivially_copyable_v<T>,
116 "array element requires a fixed cell codec");
125 if constexpr (std::is_same_v<T, bool>) sink.b(
value);
126 else if constexpr (std::is_floating_point_v<T>) sink.d(
value);
127 else if constexpr (std::is_integral_v<T> && std::is_signed_v<T>) sink.i(
value);
128 else if constexpr (std::is_integral_v<T>) sink.u(
value);
131 static_assert(std::is_arithmetic_v<T>,
132 "structured array element needs a canonical hash codec");
158 for (std::uint64_t offset = 0; offset < bytes;) {
159 const auto take =
static_cast<std::size_t
>(
160 std::min<std::uint64_t>(
sizeof buffer, bytes - offset));
162 sink.bytes(buffer, take);
168template<
class U>
struct ElementCodec<
ScriptArray<U>, void>;
177 static_assert(std::is_trivially_copyable_v<Cell>,
"array cells must be byte-addressable");
188 static constexpr std::uint64_t max_elements() {
189 constexpr auto byte_limit =
190 (std::numeric_limits<std::uint64_t>::max() -
sizeof(Header)) /
sizeof(Cell);
191 constexpr auto index_limit =
192 static_cast<std::uint64_t
>(std::numeric_limits<std::int64_t>::max());
193 return byte_limit < index_limit ? byte_limit : index_limit;
196 static std::uint64_t rounded_capacity(std::uint64_t count) {
199 const auto bytes = count *
sizeof(Cell);
200 const auto limit = std::numeric_limits<std::uint64_t>::max();
201 if (bytes > limit - (page - 1))
return count;
202 const auto capacity = ((bytes + page - 1) / page * page) /
sizeof(Cell);
203 return std::min(
capacity, max_elements());
206 static std::uint64_t offset(std::uint64_t index) {
207 return sizeof(Header) + index *
sizeof(Cell);
210 Header header()
const {
217 value.capacity > max_elements())
222 void write_header(
const Header& value) {
226 Cell read_cell(std::uint64_t index)
const {
232 void write_cell(std::uint64_t index,
const Cell& value) {
236 T value_at(std::uint64_t index)
const {
return Codec::decode(*store_, read_cell(index)); }
238 void set_at(std::uint64_t index,
const T& value) {
240 const Cell previous = read_cell(index);
241 write_cell(index, next);
245 void grow(std::uint64_t needed) {
246 const auto before = header();
247 if (needed <= before.capacity)
return;
251 const auto doubled = before.capacity <= max_elements() / 2
252 ? before.capacity * 2 : max_elements();
253 reserve(std::max(needed, doubled));
256 void push_cell(
const Cell& cell) {
261 write_cell(h.size, cell);
266 T remove_at(std::uint64_t index) {
268 const Cell removed = read_cell(index);
272 for (std::uint64_t i = index + 1; i < h.size; ++i)
273 write_cell(i - 1, read_cell(i));
274 write_cell(h.size - 1, Cell{});
281 void insert_at(std::uint64_t index,
const T& value) {
287 for (
auto i = h.size; i > index; --i) write_cell(i, read_cell(i - 1));
288 write_cell(index, next);
294 ScriptArray result(destination);
295 result.reserve(
size());
296 const auto n =
size();
297 for (std::uint64_t i = 0; i < n; ++i)
298 result.push_cell(
Codec::clone(*store_, read_cell(i), destination));
299 const auto id = result.id_;
300 result.owner_ =
false;
306 ScriptArray borrowed(
store,
id, Borrow{});
311 void dispose() noexcept {
314 destroy_tree(*store_, id_);
322 void assign(
const ScriptArray& other) {
323 if (
this == &other || (store_ == other.store_ && id_ == other.id_))
return;
324 if (store_ ==
nullptr) {
325 if (other.store_ ==
nullptr)
return;
326 store_ = other.store_;
327 id_ = other.clone_into(*store_);
335 for (std::uint64_t i = 0, n = other.size(); i < n; ++i)
336 push_cell(
Codec::clone(*other.store_, other.read_cell(i), *store_));
350 id_ =
store.create(
sizeof(Header),
alignof(Header));
355 : ScriptArray(
store) {
357 for (std::uint64_t i = 0; i < count; ++i)
push_back(initial);
361 ScriptArray result(
store);
368 for (
const auto& value : values) result.push_back(value);
373 if (other.store_ !=
nullptr) {
374 store_ = other.store_;
375 id_ = other.clone_into(*store_);
379 ScriptArray&
operator=(
const ScriptArray& other) { assign(other);
return *
this; }
382 : store_(other.store_), id_(other.id_), owner_(other.owner_) {
383 other.store_ =
nullptr;
385 other.owner_ =
false;
389 if (
this == &other)
return *
this;
390 if (store_ ==
nullptr) {
391 store_ = other.store_;
393 owner_ = other.owner_;
394 other.store_ =
nullptr;
396 other.owner_ =
false;
398 const bool same_root = store_ == other.store_ && id_ == other.id_;
401 if (!same_root && other.owner_) other.clear();
414 bool alive()
const {
return store_ !=
nullptr && store_->alive(id_); }
415 std::uint64_t
size()
const {
return store_ ==
nullptr ? 0 : header().size; }
416 std::uint64_t
capacity()
const {
return store_ ==
nullptr ? 0 : header().capacity; }
421 template<
class Index>
422 T
get(Index index)
const {
423 if constexpr (std::is_floating_point_v<Index>)
424 if (std::isnan(index) || index < 0)
return na<T>();
425 if constexpr (std::is_signed_v<Index>)
426 if (index < 0)
return na<T>();
430 template<
class Index>
431 void set(Index index,
const T& value) {
432 if constexpr (std::is_floating_point_v<Index>)
433 if (std::isnan(index) || index < 0)
return;
434 if constexpr (std::is_signed_v<Index>)
435 if (index < 0)
return;
442 void set_i(std::int64_t index,
const T& value) {
448 template<
class Index>
450 const auto n =
size();
454 template<
class Index>
456 const auto n =
size();
460 template<
class Index>
462 const auto n =
size();
466 template<
class Index>
470 template<
class Index>
471 void set_v6(Index index,
const T& value) {
474 template<
class Index>
479 template<
class Function>
480 void mutate(std::int64_t index, Function&& function) {
482 T value = value_at(at);
483 std::forward<Function>(function)(value);
489 if (count <= h.capacity)
return;
490 const auto next = rounded_capacity(count);
491 if (!store_->resize(id_, offset(next)))
498 const auto h = header();
505 template<
class Index>
506 void insert(Index index,
const T& value) {
507 const auto n =
size();
510 insert_at(at, value);
512 template<
class Index>
514 const auto n =
size();
517 insert_at(at, value);
527 return value_at(
size() - 1);
531 return remove_at(
size() - 1);
539 if (store_ ==
nullptr)
return;
542 for (std::uint64_t i = 0; i < h.size; ++i)
Codec::destroy(*store_, read_cell(i));
548 const auto n = other.
size();
549 const auto old =
size();
552 for (std::uint64_t i = 0; i < n; ++i)
553 push_cell(
Codec::clone(*other.store_, other.read_cell(i), *store_));
557 void fill(
const T& value) {
fill(value, 0,
static_cast<std::int64_t
>(
size())); }
562 template<
class From,
class To>
564 const auto n =
size();
569 for (
auto i =
first; i <
last; ++i) set_at(i, value);
572 template<
class From,
class To>
574 const auto n =
size();
582 result.push_cell(
Codec::clone(*store_, read_cell(i), *store_));
587 const auto n =
size();
588 for (std::uint64_t i = 0; i < n / 2; ++i) {
589 const Cell saved = read_cell(i);
590 write_cell(i, read_cell(n - i - 1));
591 write_cell(n - i - 1, saved);
601 const auto n =
size();
603 for (std::uint64_t i = 0; i < n; ++i)
Codec::hash(*store_, read_cell(i), sink);
607namespace detail::script_array {
614 return value.clone_into(store);
619 typename ScriptArray<U>::Borrow{});
620 return borrowed.
copy();
625 typename ScriptArray<U>::Borrow{});
626 return borrowed.clone_into(target);
629 ScriptArray<U>::destroy_tree(store, child);
637 typename ScriptArray<U>::Borrow{});
650 std::unique_ptr<detail::o1::Tx> tx_;
656 auto scope = std::move(tx_);
657 if (scope) scope->commit();
660 auto scope = std::move(tx_);
661 if (scope) scope->rollback();
663 bool active() const noexcept {
return static_cast<bool>(tx_); }
ScriptArrayTransaction(const ScriptArrayTransaction &)=delete
ScriptArrayTransaction(detail::o1::Store &store)
ScriptArrayTransaction & operator=(const ScriptArrayTransaction &)=delete
bool active() const noexcept
ScriptArray(const ScriptArray &other)
void set_i(std::int64_t index, const T &value)
void fill(const T &value, From from, To to)
void push(const T &value)
T remove_raw(Index index)
detail::o1::Store & store() const
static ScriptArray from(detail::o1::Store &store, std::initializer_list< T > values)
ScriptArray slice(From from, To to) const
detail::o1::Id id() const noexcept
T get_v6(Index index) const
void mutate(std::int64_t index, Function &&function)
static constexpr std::size_t element_bytes
void unshift(const T &value)
T remove_i(std::int64_t index)
void append(const ScriptArray &other)
static ScriptArray preallocated(detail::o1::Store &store, std::uint64_t capacity)
std::uint64_t size() const
ScriptArray & operator=(const ScriptArray &other)
void concat(const ScriptArray &other)
bool store_backed() const noexcept
void set_v6(Index index, const T &value)
ScriptArray & operator=(ScriptArray &&other)
ScriptArray(detail::o1::Store &store)
void reserve(std::uint64_t count)
T get_i(std::int64_t index) const
ScriptArray alias() const
T get_raw(Index index) const
ScriptArray(detail::o1::Store &store, std::uint64_t count, const T &initial=na< T >())
void fill(const T &value, From from)
void set(Index index, const T &value)
void hash_into(Sink &sink) const
std::uint64_t capacity() const
void set_raw(Index index, const T &value)
static constexpr std::size_t payload_page_bytes
ScriptArray(ScriptArray &&other) noexcept
void insert_raw(Index index, const T &value)
static constexpr std::size_t header_bytes
void fill(const T &value)
void push_back(const T &value)
void insert(Index index, const T &value)
virtual std::size_t write(Id, std::uint64_t off, const void *src, std::size_t n)=0
virtual std::uint64_t size(Id) const =0
virtual std::size_t read(Id, std::uint64_t off, void *dst, std::size_t n) const =0
virtual bool alive(Id) const =0
virtual void release(Id)=0
void empty_array_error(const char *)
o1::Id store_string(o1::Store &, const std::string &)
std::int64_t checked_index_double(double, std::uint64_t, const char *)
o1::Id clone_bytes(const o1::Store &, o1::Id, o1::Store &)
std::int64_t index_integer(Index value, std::uint64_t size, const char *method)
void write_exact(o1::Store &store, o1::Id id, std::uint64_t offset, const void *source, std::size_t bytes)
void invariant(const char *)
void index_error_double(const char *, double, std::uint64_t)
void inverted_range_error(const char *)
void index_error(const char *, std::int64_t, std::uint64_t, bool missing=false)
std::string load_string(const o1::Store &, o1::Id)
constexpr std::uint64_t kPayloadPageBytes
std::uint64_t checked(std::int64_t raw, std::uint64_t size, const char *method, bool relative, bool end=false)
constexpr std::uint64_t kHeaderMagic
void read_exact(const o1::Store &store, o1::Id id, std::uint64_t offset, void *destination, std::size_t bytes)
bool is_na(const Line &h)
static Cell clone(const o1::Store &source, Cell child, o1::Store &target)
static constexpr bool owns_objects
static void hash(const o1::Store &store, Cell child, Sink &sink)
static ScriptArray< U > decode(const o1::Store &store, Cell child)
static Cell encode(o1::Store &store, const ScriptArray< U > &value)
static void destroy(o1::Store &store, Cell child)
static std::string decode(const o1::Store &store, Cell value)
static Cell encode(o1::Store &store, const std::string &value)
static void destroy(o1::Store &store, Cell value)
static constexpr bool owns_objects
static void hash(const o1::Store &store, Cell value, Sink &sink)
static Cell clone(const o1::Store &source, Cell value, o1::Store &target)
static T decode(const o1::Store &, const Cell &value)
static Cell encode(o1::Store &, const T &value)
static constexpr bool owns_objects
static void hash(const o1::Store &, const Cell &value, Sink &sink)
static void destroy(o1::Store &, const Cell &)
static Cell clone(const o1::Store &, const Cell &value, o1::Store &)