| // Copyright 2018 The Fuchsia Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #pragma once |
| |
| #include <assert.h> |
| #include <stddef.h> |
| #include <stdint.h> |
| #include <string.h> |
| #include <algorithm> |
| #include <iosfwd> |
| #include <string> |
| #include <type_traits> |
| #include <vector> |
| #include "optional.h" |
| |
| namespace overnet { |
| |
| // Describes the extent of padding both before and after a slice. |
| struct Border { |
| size_t prefix; |
| size_t suffix; |
| |
| static Border Prefix(size_t size) { return Border{size, 0}; } |
| static Border Suffix(size_t size) { return Border{0, size}; } |
| static Border None() { return Border{0, 0}; } |
| |
| Border WithAddedPrefix(size_t size) const { |
| return Border{prefix + size, suffix}; |
| } |
| |
| Border WithAddedSuffix(size_t size) const { |
| return Border{size, suffix + size}; |
| } |
| |
| size_t Total() const { return prefix + suffix; } |
| }; |
| |
| class Slice final { |
| public: |
| static constexpr size_t kSmallSliceMaxLength = 3 * sizeof(void*) - 1; |
| union Data { |
| Data() {} |
| Data(void* control, const uint8_t* begin, const uint8_t* end) |
| : general{control, begin, end} {} |
| struct { |
| void* control; |
| const uint8_t* begin; |
| const uint8_t* end; |
| } general; |
| struct { |
| uint8_t length; |
| uint8_t bytes[kSmallSliceMaxLength]; |
| } small; |
| }; |
| |
| struct VTable { |
| const uint8_t* (*begin)(const Data* data); |
| const uint8_t* (*end)(const Data* data); |
| size_t (*length)(const Data* data); |
| void (*ref)(Data* data); |
| void (*unref)(Data* data); |
| void (*trim)(Data* data, size_t trim_left, size_t trim_right); |
| uint8_t* (*maybe_add_borders)(const Data* data, Border border, |
| Data* new_slice_data); |
| const char* name; |
| }; |
| |
| Slice(const VTable* vtable, void* control, const uint8_t* begin, |
| const uint8_t* end) |
| : vtable_(vtable), data_(control, begin, end) {} |
| |
| Slice() : Slice(&Static<>::small_vtable_) { data_.small.length = 0; } |
| |
| ~Slice() { vtable_->unref(&data_); } |
| |
| Slice(const Slice& other) : vtable_(other.vtable_), data_(other.data_) { |
| vtable_->ref(&data_); |
| } |
| |
| Slice(Slice&& other) : vtable_(other.vtable_), data_(other.data_) { |
| other.vtable_ = &Static<>::small_vtable_; |
| other.data_.small.length = 0; |
| } |
| |
| Slice& operator=(const Slice& other) { |
| Slice(other).Swap(this); |
| return *this; |
| } |
| |
| Slice& operator=(Slice&& other) { |
| Swap(&other); |
| return *this; |
| } |
| |
| void Swap(Slice* other) { |
| std::swap(vtable_, other->vtable_); |
| std::swap(data_, other->data_); |
| } |
| |
| static Optional<Slice> JoinIfSameUnderlyingMemory(const Slice& a, |
| const Slice& b) { |
| if (a.vtable_ != b.vtable_) { |
| return Nothing; |
| } |
| |
| if (a.end() != b.begin()) { |
| return Nothing; |
| } |
| |
| if (a.data_.general.control != b.data_.general.control) { |
| return Nothing; |
| } |
| |
| Slice out(a.vtable_, a.data_.general.control, a.begin(), b.end()); |
| out.vtable_->ref(&out.data_); |
| return out; |
| } |
| |
| const uint8_t* begin() const { return vtable_->begin(&data_); } |
| const uint8_t* end() const { return vtable_->end(&data_); } |
| size_t length() const { return vtable_->length(&data_); } |
| |
| void Trim(size_t left, size_t right) { vtable_->trim(&data_, left, right); } |
| void TrimBegin(size_t trim_bytes) { Trim(trim_bytes, 0); } |
| void TrimEnd(size_t trim_bytes) { Trim(0, trim_bytes); } |
| |
| Slice FromOffset(size_t offset) const { |
| Slice out(*this); |
| out.TrimBegin(offset); |
| return out; |
| } |
| |
| Slice ToOffset(size_t offset) const { |
| Slice out(*this); |
| out.TrimEnd(length() - offset); |
| return out; |
| } |
| |
| Slice FromPointer(const uint8_t* internal_pointer) const { |
| assert(internal_pointer >= begin() && internal_pointer <= end()); |
| return FromOffset(internal_pointer - begin()); |
| } |
| |
| Slice TakeUntilOffset(size_t offset) { |
| auto out = ToOffset(offset); |
| TrimBegin(offset); |
| return out; |
| } |
| |
| Slice TakeUntilPointer(const uint8_t* internal_pointer) { |
| assert(internal_pointer >= begin() && internal_pointer <= end()); |
| return TakeUntilOffset(internal_pointer - begin()); |
| } |
| |
| Slice TakeFromOffset(size_t offset) { |
| auto out = FromOffset(offset); |
| TrimEnd(length() - offset); |
| return out; |
| } |
| |
| Slice Cut(size_t from_offset, size_t to_offset) { |
| Slice copy(*this); |
| copy.Trim(from_offset, copy.length() - to_offset); |
| return copy; |
| } |
| |
| static Slice Join(std::initializer_list<Slice> slices, |
| Border desired_border = Border::None()) { |
| return Join(slices.begin(), slices.end(), desired_border); |
| } |
| |
| template <class IT> |
| static Slice Join(IT begin, IT end, Border desired_border = Border::None()) { |
| if (begin == end) |
| return Slice(); |
| if (std::next(begin) == end) |
| return *begin; |
| |
| size_t total_length = 0; |
| for (auto it = begin; it != end; ++it) { |
| total_length += it->length(); |
| } |
| |
| return Slice::WithInitializerAndBorders( |
| total_length, desired_border, [begin, end](uint8_t* out) { |
| size_t offset = 0; |
| for (auto it = begin; it != end; ++it) { |
| memcpy(out + offset, it->begin(), it->length()); |
| offset += it->length(); |
| } |
| }); |
| } |
| |
| template <class F> |
| Slice WithPrefix(size_t length, F initializer) const { |
| return WithBorders(Border::Prefix(length), initializer); |
| } |
| |
| template <class F> |
| Slice WithBorders(Border border, F initializer) const { |
| Data new_slice_data; |
| if (uint8_t* prefix = |
| vtable_->maybe_add_borders(&data_, border, &new_slice_data)) { |
| initializer(prefix); |
| return Slice{vtable_, new_slice_data}; |
| } else { |
| size_t own_length = this->length(); |
| const uint8_t* begin = this->begin(); |
| return WithInitializer(own_length + border.prefix + border.suffix, |
| [add_prefix = border.prefix, own_length, |
| initializer, begin](uint8_t* p) { |
| memcpy(p + add_prefix, begin, own_length); |
| initializer(p); |
| }); |
| } |
| } |
| |
| template <class F> |
| Slice MutateUnique(F f) const { |
| return WithBorders(Border::None(), f); |
| } |
| |
| std::string AsStdString() const { return std::string(begin(), end()); } |
| |
| bool StartsWith(const Slice& prefix) const; |
| |
| ///////////////////////////////////////////////////////////////////////////// |
| // Factory functions |
| |
| static Slice FromStaticString(const char* s) { |
| auto bs = reinterpret_cast<const uint8_t*>(s); |
| return Slice(&Static<>::const_vtable_, nullptr, bs, bs + strlen(s)); |
| } |
| |
| template <class I> |
| static Slice ReferencingContainer(I begin, I end) { |
| return Slice(&Static<>::const_vtable_, nullptr, |
| static_cast<const uint8_t*>(begin), |
| static_cast<const uint8_t*>(end)); |
| } |
| |
| static Slice FromCopiedBuffer(const void* data, size_t length) { |
| return WithInitializer( |
| length, [data, length](void* p) { memcpy(p, data, length); }); |
| } |
| |
| template <class C> |
| static Slice FromContainer(const C& c) { |
| auto begin = c.begin(); |
| auto end = c.end(); |
| return WithInitializer(end - begin, [begin, end](uint8_t* p) { |
| for (auto i = begin; i != end; ++i) { |
| *p++ = *i; |
| } |
| }); |
| } |
| |
| static Slice FromContainer(std::initializer_list<uint8_t> c) { |
| auto begin = c.begin(); |
| auto end = c.end(); |
| return WithInitializer(end - begin, [begin, end](uint8_t* p) { |
| for (auto i = begin; i != end; ++i) { |
| *p++ = *i; |
| } |
| }); |
| } |
| |
| template <class F> |
| static Slice WithInitializerAndBorders(size_t length, Border border, |
| F&& initializer) { |
| if (length <= kSmallSliceMaxLength) { |
| // Ignore prefix/suffix request if this is small enough (we'll maybe |
| // allocate later, but that's ok - we didn't here). |
| Slice s(&Static<>::small_vtable_); |
| s.data_.small.length = length; |
| std::forward<F>(initializer)(s.data_.small.bytes); |
| return s; |
| } else { |
| auto* block = BHNew(length + border.prefix + border.suffix); |
| std::forward<F>(initializer)(block->bytes + border.prefix); |
| return Slice(&Static<>::block_vtable_, block, |
| block->bytes + border.prefix, |
| block->bytes + border.prefix + length); |
| } |
| } |
| |
| template <class F> |
| static Slice WithInitializer(size_t length, F&& initializer) { |
| return WithInitializerAndBorders(length, Border::None(), |
| std::forward<F>(initializer)); |
| } |
| |
| static Slice RepeatedChar(size_t count, char c) { |
| return WithInitializer(count, [count, c](uint8_t* p) { |
| for (size_t i = 0; i < count; i++) { |
| p[i] = static_cast<uint8_t>(c); |
| } |
| }); |
| } |
| |
| // Given an object that conforms to the Writer interface (has size_t |
| // wire_length() and Write(uint8_t* out)), create a slice containing the |
| // serialized object |
| template <class... W> |
| static Slice FromWriters(const W&... w) { |
| uint64_t total_length = 0; |
| (void)std::initializer_list<int>{(total_length += w.wire_length(), 0)...}; |
| return WithInitializer(total_length, [&w...](uint8_t* bytes) { |
| uint8_t* p = bytes; |
| (void)std::initializer_list<int>{(p = w.Write(p), 0)...}; |
| }); |
| } |
| |
| // Given an object of type T that has a T::Writer interface, generate a slice |
| template <class T> |
| static Slice FromWritable(const T& t) { |
| typename T::Writer writer(&t); |
| return FromWriters(writer); |
| } |
| |
| private: |
| // Leaves data_ uninitialized |
| Slice(const VTable* vtable) : vtable_(vtable) {} |
| |
| Slice(const VTable* vtable, Data data) : vtable_(vtable), data_(data) {} |
| |
| const VTable* vtable_; |
| Data data_; |
| |
| static void NoOpRef(Data*) {} |
| |
| static const uint8_t* GeneralBegin(const Data* data) { |
| return data->general.begin; |
| } |
| static const uint8_t* GeneralEnd(const Data* data) { |
| return data->general.end; |
| } |
| static size_t GeneralLength(const Data* data) { |
| return data->general.end - data->general.begin; |
| } |
| static void GeneralTrim(Data* data, size_t trim_left, size_t trim_right) { |
| data->general.begin += trim_left; |
| data->general.end -= trim_right; |
| } |
| |
| static const uint8_t* SmallBegin(const Data* data) { |
| return data->small.bytes; |
| } |
| static const uint8_t* SmallEnd(const Data* data) { |
| return data->small.bytes + data->small.length; |
| } |
| static size_t SmallLength(const Data* data) { return data->small.length; } |
| static void SmallTrim(Data* data, size_t trim_left, size_t trim_right) { |
| data->small.length -= trim_right + trim_left; |
| if (trim_left) { |
| memmove(data->small.bytes, data->small.bytes + trim_left, |
| data->small.length); |
| } |
| } |
| static uint8_t* SmallAddBorders(const Data* data, Border border, |
| Data* new_slice_data) { |
| if (data->small.length + border.prefix + border.suffix < |
| kSmallSliceMaxLength) { |
| new_slice_data->small.length = |
| data->small.length + border.prefix + border.suffix; |
| memcpy(new_slice_data->small.bytes + border.prefix, data->small.bytes, |
| data->small.length); |
| return new_slice_data->small.bytes; |
| } |
| return nullptr; |
| } |
| |
| struct BlockHeader { |
| int refs; |
| size_t block_length; |
| uint8_t bytes[0]; |
| }; |
| static BlockHeader* BHNew(size_t length) { |
| auto* out = static_cast<BlockHeader*>(malloc(sizeof(BlockHeader) + length)); |
| out->block_length = length; |
| out->refs = 1; |
| return out; |
| } |
| static void BHRef(Data* data) { |
| static_cast<BlockHeader*>(data->general.control)->refs++; |
| } |
| static void BHUnref(Data* data) { |
| if (0 == --static_cast<BlockHeader*>(data->general.control)->refs) { |
| free(data->general.control); |
| } |
| } |
| static uint8_t* BHAddBorders(const Data* data, Border border, |
| Data* new_slice_data) { |
| auto* hdr = static_cast<BlockHeader*>(data->general.control); |
| if (hdr->refs != 1) |
| return nullptr; |
| assert(data->general.begin - hdr->bytes >= 0); |
| if (static_cast<size_t>(data->general.begin - hdr->bytes) >= |
| border.prefix && |
| static_cast<size_t>(hdr->bytes + hdr->block_length - |
| data->general.end) >= border.suffix) { |
| hdr->refs++; |
| *new_slice_data = Data(hdr, data->general.begin - border.prefix, |
| data->general.end + border.suffix); |
| return const_cast<uint8_t*>(new_slice_data->general.begin); |
| } |
| return nullptr; |
| } |
| |
| static uint8_t* NoAddBorders(const Data* data, Border border, |
| Data* new_slice_data) { |
| return nullptr; |
| } |
| |
| template <int I = 0> |
| struct Static { |
| static const VTable small_vtable_; |
| static const VTable const_vtable_; |
| static const VTable block_vtable_; |
| }; |
| }; |
| |
| template <int I> |
| const Slice::VTable Slice::Static<I>::small_vtable_ = { |
| // begin |
| SmallBegin, |
| // end |
| SmallEnd, |
| // length |
| SmallLength, |
| // ref |
| NoOpRef, |
| // unref |
| NoOpRef, |
| // trim |
| SmallTrim, |
| // maybe_add_borders |
| SmallAddBorders, |
| // name |
| "small_vtable"}; |
| |
| template <int I> |
| const Slice::VTable Slice::Static<I>::const_vtable_ = { |
| // begin |
| GeneralBegin, |
| // end |
| GeneralEnd, |
| // length |
| GeneralLength, |
| // ref |
| NoOpRef, |
| // unref |
| NoOpRef, |
| // trim |
| GeneralTrim, |
| // maybe_add_borders |
| NoAddBorders, |
| // name |
| "small_vtable"}; |
| |
| template <int I> |
| const Slice::VTable Slice::Static<I>::block_vtable_ = { |
| // begin |
| GeneralBegin, |
| // end |
| GeneralEnd, |
| // length |
| GeneralLength, |
| // ref |
| BHRef, |
| // unref |
| BHUnref, |
| // trim |
| GeneralTrim, |
| // maybe_add_borders |
| BHAddBorders, |
| // name |
| "block_vtable"}; |
| |
| struct Chunk final { |
| uint64_t offset; |
| bool end_of_message; |
| Slice slice; |
| |
| void TrimBegin(size_t trim_bytes) { |
| slice.TrimBegin(trim_bytes); |
| offset += trim_bytes; |
| } |
| |
| void TrimEnd(size_t trim_bytes) { |
| slice.TrimEnd(trim_bytes); |
| if (trim_bytes != 0) |
| end_of_message = false; |
| } |
| |
| Chunk TakeUntilSliceOffset(size_t slice_offset) { |
| Chunk out{offset, false, slice.TakeUntilOffset(slice_offset)}; |
| offset += slice_offset; |
| return out; |
| } |
| |
| Chunk TakeFromSliceOffset(size_t slice_offset) { |
| Chunk out{offset + slice_offset, end_of_message, |
| slice.TakeFromOffset(slice_offset)}; |
| end_of_message = false; |
| return out; |
| } |
| |
| static Optional<Chunk> JoinIfSameUnderlyingMemory(const Chunk& a, |
| const Chunk& b) { |
| if (a.offset + a.slice.length() != b.offset) { |
| return Nothing; |
| } |
| |
| return Slice::JoinIfSameUnderlyingMemory(a.slice, b.slice) |
| .Map([offset = a.offset, |
| end_of_message = b.end_of_message](Slice slice) { |
| return Chunk{offset, end_of_message, std::move(slice)}; |
| }); |
| } |
| }; |
| |
| inline bool operator==(const Slice& a, const Slice& b) { |
| if (a.length() != b.length()) |
| return false; |
| return 0 == memcmp(a.begin(), b.begin(), a.length()); |
| } |
| |
| inline bool operator!=(const Slice& a, const Slice& b) { return !(a == b); } |
| |
| inline bool operator==(const Chunk& a, const Chunk& b) { |
| return a.offset == b.offset && a.slice == b.slice; |
| } |
| |
| inline bool Slice::StartsWith(const Slice& prefix) const { |
| if (length() < prefix.length()) { |
| return false; |
| } |
| return ToOffset(prefix.length()) == prefix; |
| } |
| |
| std::ostream& operator<<(std::ostream& out, const Border& border); |
| std::ostream& operator<<(std::ostream& out, const Slice& slice); |
| std::ostream& operator<<(std::ostream& out, const std::vector<Slice>& slices); |
| std::ostream& operator<<(std::ostream& out, const Chunk& chunk); |
| |
| } // namespace overnet |