diff options
Diffstat (limited to 'source/core')
| -rw-r--r-- | source/core/slang-blob-builder.cpp | 473 | ||||
| -rw-r--r-- | source/core/slang-blob-builder.h | 352 | ||||
| -rw-r--r-- | source/core/slang-internally-linked-list.cpp | 2 | ||||
| -rw-r--r-- | source/core/slang-internally-linked-list.h | 126 | ||||
| -rw-r--r-- | source/core/slang-memory-arena.h | 11 | ||||
| -rw-r--r-- | source/core/slang-relative-ptr.cpp | 2 | ||||
| -rw-r--r-- | source/core/slang-relative-ptr.h | 97 | ||||
| -rw-r--r-- | source/core/slang-riff.h | 68 |
8 files changed, 1064 insertions, 67 deletions
diff --git a/source/core/slang-blob-builder.cpp b/source/core/slang-blob-builder.cpp new file mode 100644 index 000000000..10dd4003e --- /dev/null +++ b/source/core/slang-blob-builder.cpp @@ -0,0 +1,473 @@ +// slang-blob-builder.cpp +#include "slang-blob-builder.h" + +namespace Slang +{ + +// +// BlobBuilder +// + +BlobBuilder::BlobBuilder() + : _arena(4096) +{ +} + +void BlobBuilder::writeTo(Stream* stream) +{ + // First we scan through all the chunks to set their + // absolute offsets, which enables us to compute the + // correct values for relative pointers when we write + // them out. + // + SLANG_MAYBE_UNUSED + Size sizeComputed = _calcSizeAndSetCachedChunkOffsets(); + + // Now we can scan through the chunks again and write + // the bytes of each of their shards. + // + SLANG_MAYBE_UNUSED + Size sizeWritten = _writeChunksTo(stream); + + SLANG_ASSERT(sizeComputed == sizeWritten); +} + +Size BlobBuilder::_calcSizeAndSetCachedChunkOffsets() +{ + Size totalSize = 0; + for (auto chunk : _chunks) + { + auto chunkPrefixSize = chunk->getPrefixSize(); + auto chunkContentSize = chunk->getContentSize(); + auto chunkAlignment = chunk->getAlignment(); + + // We add the size of the chunk prefix (if any) *before* + // aligning the current offset. Doing it this way + // means that sometimes the prefix can fit "for free" + // in space that would otherwise be padding. + // + // For example, if the current `totalSize` is 4, the + // `chunkAlignment` is 16, and the `chunkPrefixSize` is 8, + // then the sequence will be: + // + // * Add `totalSize += chunkPrefixSize`, resulting in a `totalSize` + // of 12. + // + // * Round the `totalSize` up to the `chunkAlignment`, to compute + // a `chunkOffset` of 16. + // + // The result is that the chunk's content starts at offset 16, + // and the prefix can occupy the 8 bytes before that (so the + // prefix is at offset 8). + // + // In the best case this approach can save a few bytes here or + // there when `chunkAlignment` is larger than the `chunkPrefixSize`, + // and in the worst case it does no harm. + + totalSize += chunkPrefixSize; + auto chunkOffset = roundUpToAlignment(totalSize, chunkAlignment); + + chunk->_setCachedOffset(chunkOffset); + + totalSize = chunkOffset + chunkContentSize; + } + return totalSize; +} + +Size BlobBuilder::_writeChunksTo(Stream* stream) +{ + Size totalSize = 0; + for (auto chunk : _chunks) + { + auto chunkPrefixSize = chunk->getPrefixSize(); + auto chunkContentSize = chunk->getContentSize(); + auto chunkOffset = chunk->_getCachedOffset(); + + SLANG_ASSERT( + chunkOffset == roundUpToAlignment(totalSize + chunkPrefixSize, chunk->getAlignment())); + + auto paddingSize = chunkOffset - totalSize; + + // The "padding" before the chunk's content also + // includes the space reserved for the chunk's prefix. + // + // We can thus subtract the prefix size from the number + // of pad bytes to write. + + SLANG_ASSERT(paddingSize >= chunkPrefixSize); + paddingSize -= chunkPrefixSize; + + while (paddingSize--) + { + Byte padding = 0; + stream->write(&padding, sizeof(padding)); + } + + // The `ChunkBuilder::_writeTo()` call will write the + // prefix *and* the chunk content, so it is appropriate + // to call it here even when the total number of bytes + // written to the stream is not equal to the `chunkOffset` + // (because in that case the total bytes written so far + // should be `chunkOffset - chunkPrefixSize`). + // + chunk->_writeTo(stream); + + totalSize = chunkOffset + chunkContentSize; + } + + return totalSize; +} + +void BlobBuilder::writeToBlob(ISlangBlob** outBlob) +{ + OwnedMemoryStream stream(FileAccess::Write); + writeTo(&stream); + + List<uint8_t> data; + stream.swapContents(data); + + *outBlob = ListBlob::moveCreate(data).detach(); +} + +ChunkBuilder* BlobBuilder::createUnparentedChunk() +{ + auto chunk = new (_arena) ChunkBuilder(this); + return chunk; +} + +void BlobBuilder::addChunk(ChunkBuilder* chunk) +{ + // TODO(tfoley): it would be good to have a way to assert + // that the chunk has not already been added. + + _chunks.add(chunk); +} + +ChunkBuilder* BlobBuilder::addChunk() +{ + auto chunk = new (_arena) ChunkBuilder(this); + _chunks.add(chunk); + return chunk; +} + +ChunkBuilder* BlobBuilder::addChunkAfter(ChunkBuilder* existingChunk) +{ + auto newChunk = new (_arena) ChunkBuilder(this); + _chunks.insertAfter(existingChunk, newChunk); + return newChunk; +} + +// +// ChunkBuilder +// + +void ChunkBuilder::setAlignmentToAtLeast(Size alignment) +{ + SLANG_ASSERT(alignment > 0); + SLANG_ASSERT(isPowerOfTwo(alignment)); + + _contentAlignment = std::max(_contentAlignment, alignment); +} + +void ChunkBuilder::writePaddingToAlignTo(Size alignment) +{ + setAlignmentToAtLeast(alignment); + + auto alignedSize = roundUpToAlignment(_contentSize, alignment); + + auto requiredPaddingSize = alignedSize - _contentSize; + + while (requiredPaddingSize) + { + Byte padByte = 0; + writeData(&padByte, sizeof(padByte)); + requiredPaddingSize -= sizeof(padByte); + } +} + +ChunkBuilder::ChunkBuilder(BlobBuilder* parentBlob) + : _parentBlob(parentBlob) +{ +} + +Size ChunkBuilder::getContentSize() const +{ + return _contentSize; +} + +Size ChunkBuilder::getPrefixSize() const +{ + if (!_prefixShard) + return 0; + + return _prefixShard->getSize(); +} + +Size ChunkBuilder::getAlignment() const +{ + return _contentAlignment; +} + + +void ChunkBuilder::writeData(void const* data, Size size) +{ + // Adding no data should be a no-op. + // + if (size == 0) + return; + + + // The most interesting implementation detail here + // is that we will try to detect cases where we + // can re-use an existing `ShardBuilder` by adding the data + // to the end of that shard's allocation. + // + // This is only possible because of the way that + // we are using a single `MemoryArena` to allocate + // everything, which makes it possible that the + // next address the arena would return for an allocation + // of `size` bytes is the same as the ending address + // of the payload for the last shard of this chunk. + // + auto& arena = getParentBlob()->_getArena(); + + // We start by checking if this chunk already has + // a last shard that we could consider appending to. + // + auto lastShard = _childShards.getLast(); + if (lastShard && lastShard->_kind == ShardBuilder::Kind::Data) + { + // If there is a last shard, then we can compute + // the end address of its payload, and see if + // it is the same as the cursor of the arena + // we are allocating from. + // + auto payload = lastShard->_data.ptr; + auto payloadSize = lastShard->_size; + auto payloadEnd = (Byte*)payload + payloadSize; + if (payloadEnd == arena.getCursor()) + { + // Now that we've confirmed that the shard's + // payload ends at an address the arena could + // conceivably allocate from, we need to ask + // the arena to allocate `size` bytes from + // the current block it is using, and see if + // doing so succeeds. + // + if (arena.allocateCurrentUnaligned(size)) + { + // At this point, we've confirmed that we + // are in our special case, and the relevant + // bytes have been allocated from the arena. + // + // Now we can simply write the new data at + // what used to be the end address for the + // shard's payload, and adjust its state + // to account for the new allocation. + // + ::memcpy(payloadEnd, data, size); + + lastShard->_size = payloadSize + size; + _contentSize += size; + return; + } + } + } + + // If the special case above doesn't apply, we simply + // allocate a new shard to hold the data that was + // passed in. + // + auto shard = _createDataShard(data, size); + _childShards.add(shard); + _contentSize += size; +} + +void ChunkBuilder::addContentsOf(ChunkBuilder* otherChunk) +{ + auto otherPrefixShard = otherChunk->_prefixShard; + auto otherChunkSize = otherChunk->getContentSize(); + auto otherChunkAlignment = otherChunk->getAlignment(); + auto otherChunkShards = otherChunk->_childShards; + + otherChunk->_prefixShard = nullptr; + otherChunk->_contentSize = 0; + otherChunk->_contentAlignment = 1; + otherChunk->_childShards = InternallyLinkedList<ShardBuilder>(); + + if (otherPrefixShard) + { + // If the other chunk included a prefix, then + // it only makes sense to append it in the case + // where *this* chunk is completely empty. + + SLANG_ASSERT(!_prefixShard); + SLANG_ASSERT(!_childShards.getFirst()); + _prefixShard = otherPrefixShard; + } + + writePaddingToAlignTo(otherChunkAlignment); + _childShards.append(otherChunkShards); + _contentSize += otherChunkSize; +} + +ChunkBuilder* ChunkBuilder::addChunkAfter() +{ + return getParentBlob()->addChunkAfter(this); +} + +void ChunkBuilder::_writeRelativePtr(ChunkBuilder* targetChunk, Size ptrSize) +{ + SLANG_ASSERT(ptrSize != 0); + SLANG_ASSERT(ptrSize <= sizeof(UInt64)); + + writePaddingToAlignTo(ptrSize); + + if (!targetChunk) + { + UInt64 value = 0; + writeData(&value, ptrSize); + return; + } + + auto shard = _createRelativePtrShard(targetChunk, ptrSize); + _childShards.add(shard); + _contentSize += ptrSize; +} + +void ChunkBuilder::_addPrefixRelativePtr(ChunkBuilder* targetChunk, Size ptrSize) +{ + SLANG_ASSERT(targetChunk != nullptr); + SLANG_ASSERT(ptrSize != 0); + + SLANG_ASSERT(!_prefixShard); + + setAlignmentToAtLeast(ptrSize); + + auto shard = _createRelativePtrShard(targetChunk, ptrSize); + _prefixShard = shard; +} + +void ChunkBuilder::addPrefixData(void const* data, Size size) +{ + SLANG_ASSERT(data != nullptr); + SLANG_ASSERT(size != 0); + + SLANG_ASSERT(!_prefixShard); + + setAlignmentToAtLeast(size); + + auto shard = _createDataShard(data, size); + _prefixShard = shard; +} + +ShardBuilder* ChunkBuilder::_createDataShard(void const* data, Size size) +{ + auto& arena = getParentBlob()->_getArena(); + auto shard = new (arena) ShardBuilder(ShardBuilder::Kind::Data); + + auto shardData = arena.allocateUnaligned(size); + ::memcpy(shardData, data, size); + + shard->_data.ptr = shardData; + shard->_size = size; + + return shard; +} + +ShardBuilder* ChunkBuilder::_createRelativePtrShard(ChunkBuilder* targetChunk, Size ptrSize) +{ + auto& arena = getParentBlob()->_getArena(); + auto shard = new (arena) ShardBuilder(ShardBuilder::Kind::RelativePtr); + + shard->_relativePtr.targetChunk = targetChunk; + shard->_size = ptrSize; + + return shard; +} + +void ChunkBuilder::_writeTo(Stream* stream) +{ + auto chunkOffset = _getCachedOffset(); + + if (_prefixShard) + { + // Note that the prefix is written *before* the + // starting offset of the chunk's content, so we + // compute the appropriate offset to pass down. + // + auto prefixSize = _prefixShard->getSize(); + auto prefixOffset = chunkOffset - prefixSize; + + _prefixShard->_writeTo(stream, prefixOffset); + } + + auto shardOffset = chunkOffset; + for (auto shard : _childShards) + { + shard->_writeTo(stream, shardOffset); + shardOffset += shard->getSize(); + } + SLANG_ASSERT(shardOffset == chunkOffset + getContentSize()); +} + + +// +// ShardBuilder +// + +ShardBuilder::ShardBuilder(Kind kind) + : _kind(kind) +{ +} + +void ShardBuilder::_writeTo(Stream* stream, Size inSelfOffset) +{ + switch (_kind) + { + case Kind::Data: + { + stream->write(_data.ptr, _size); + } + break; + + case Kind::RelativePtr: + { + auto targetChunk = _relativePtr.targetChunk; + SLANG_ASSERT(targetChunk); + + auto selfOffset = intptr_t(inSelfOffset); + auto targetOffset = intptr_t(targetChunk->_getCachedOffset()); + + intptr_t relativeOffset = targetOffset - selfOffset; + + switch (_size) + { + case sizeof(Int32): + { + auto value = Int32(relativeOffset); + stream->write(&value, sizeof(value)); + } + break; + + case sizeof(Int64): + { + auto value = Int64(relativeOffset); + stream->write(&value, sizeof(value)); + } + break; + + default: + SLANG_UNEXPECTED("unsupported relative pointer size"); + break; + } + } + break; + + default: + SLANG_UNEXPECTED("unknown Fossil::ShardBuilder::Kind"); + break; + } +} + +} // namespace Slang diff --git a/source/core/slang-blob-builder.h b/source/core/slang-blob-builder.h new file mode 100644 index 000000000..0b59ee7ab --- /dev/null +++ b/source/core/slang-blob-builder.h @@ -0,0 +1,352 @@ +// slang-blob-builder.h +#ifndef SLANG_BLOB_BUILDER_H +#define SLANG_BLOB_BUILDER_H + +// This file provides utilities for building "blobs" of data +// where, for purposes, a blob is a contiguous sequence of +// bytes where the interpretation *of* those bytes depends +// only on the bytes themselves, and not other factors like +// the in-memory address of the blob, or the address/contents +// of memory not in the blob. +// +// Superficially, the task seems simple: just maintain a +// dynamically-sized array of bytes and append to it until +// you're done. If that's what you need, you're probably +// better off just using an `OwnedMemoryStream`. +// +// The utilities in this file deal with the case where you +// want to build some kind of offset-based data structure, +// so that parts of the blob will store byte offsets to +// other parts, while also being able to build parts of +// that structure "out of order", so that the final offset +// of a particular piece of data in the blob may not be +// known until everything *before* it has been fully built. + +#include "slang-basic.h" +#include "slang-internally-linked-list.h" +#include "slang-io.h" +#include "slang-memory-arena.h" + +namespace Slang +{ + +inline constexpr bool isPowerOfTwo(Size value) +{ + return value > 0 && (value - 1 & value) == 0; +} + +inline constexpr Size roundUpToAlignment(Size size, Size alignment) +{ + SLANG_ASSERT(isPowerOfTwo(alignment)); + + auto alignmentMask = Size(alignment) - 1; + return (size + alignmentMask) & ~alignmentMask; +} + +class ShardBuilder; +class ChunkBuilder; +struct BlobBuilder; + + +/// A utility type for composing a binary blob. +/// +/// A blob builder allows a blob to be composed as a sequence of discrete +/// chunks, allowing chunks to be added and written to in any order. +/// +/// Chunks can contain (relative) pointers to one another, with the correct +/// relative offsets being computed as part of writing the entire blob out. +/// +struct BlobBuilder +{ +public: + /// Construct an empty blob builder. + BlobBuilder(); + + /// Write the contents of the blob to the given `stream`. + void writeTo(Stream* stream); + + /// Create a copy of the contents of the blob and assign to `outBlob`. + void writeToBlob(ISlangBlob** outBlob); + + /// Add a new empty chunk to the end of the blob. + ChunkBuilder* addChunk(); + + /// Add a new empty chunk after the given `chunk`. + ChunkBuilder* addChunkAfter(ChunkBuilder* chunk); + + /// Create a chunk that is not initially part of the blob. + /// + /// The contents of the returned chunk will only become + /// part of the full blob if `addChunk()` is called later, + /// *or* if the contents of the new chunk are moved into + /// another chunk that gets added. + /// + ChunkBuilder* createUnparentedChunk(); + + /// Add a chunk to the blob that was initially not part of the blob. + void addChunk(ChunkBuilder* chunk); + +private: + InternallyLinkedList<ChunkBuilder> _chunks; + MemoryArena _arena; + + friend class ChunkBuilder; + friend class ShardBuilder; + MemoryArena& _getArena() { return _arena; } + + Size _calcSizeAndSetCachedChunkOffsets(); + Size _writeChunksTo(Stream* stream); +}; + +/// A chunk is a logically contiguous unit, such that data can +/// only ever be appended to it. As a result, offsets that are +/// relative to the start of a chunk are meaningful, and can be +/// used to encode relative offsets for pointers. +/// +/// Every `ChunkBuilder` is owned by its parent `BlobBuilder`. +/// A pointer to a `ChunkBuilder` will only be valid during the +/// lifetime of the parent `BlobBuilder`. +/// +/// Conceptually, a `ChunkBuilder` has the following: +/// +/// * A minimum *alignment* in bytes (initially 1) +/// +/// * Zero or more bytes of *content* data (initially empty) +/// +/// * An optional *prefix* consisting of zero or more bytes (initially absent) +/// +/// The content may be a mix of raw data (e.g., added via `writeData()`), +/// relative pointers to other chunks (`writeRelativePtr()`) and padding +/// bytes (`writePaddingToAlignTo()`). +/// +/// The prefix may only be either a single relative pointer, or a +/// single range of raw data bytes. +/// +/// When the parent blob written out as a flat buffer of bytes, the +/// following are guaranteed: +/// +/// * The content of the chunk will be a contiguous range of bytes +/// starting at some offset, and will not overlap any other chunks. +/// +/// * The byte offset where the chunk contents start will be a multiple +/// of the chunk's minimum alignment. +/// +/// * The bytes of the prefix (if any) will immediately precede the +/// bytes of the content. +/// +class ChunkBuilder : public InternallyLinkedList<ChunkBuilder>::Node +{ +public: + /// Get the blob builder that this chunk belongs to. + BlobBuilder* getParentBlob() const { return _parentBlob; } + + /// Get the required alignment of this chunk. + /// + /// The minimum alignment for a chunk starts at 1, + /// and may be increased by operations such as + /// `setAlignmentToAtLeast()` and `writePaddingToAlinTo()`. + /// + Size getAlignment() const; + + /// Potentially increases the required alignment of this chunk. + /// + /// If the alignment of the chunk is less than `alignment`, + /// then it will be increased to `alignment`. + /// + /// The `alignment` passed in must be a power of two. + /// + void setAlignmentToAtLeast(Size alignment); + + /// Get the size in bytes of the content of this chunk. + /// + /// Note that the size is not necessarily a multiple of the + /// alignment of the chunk. + /// + Size getContentSize() const; + + /// Write data into the chunk. + /// + /// The chunk will retain a copy of the data passed in, + /// so the `data` pointer only needs to be valid for + /// the duration of the call. + /// + /// Note that this operation does *not* adjust the + /// alignment of the chunk in any way. + /// + /// The data must only contain types that can be copied + /// bit-for-bit, and that do not depend on addresses + /// in meory. In particular no pointers (absolute or + /// relative) should be written. + /// + void writeData(void const* data, Size size); + + /// Append padding bytes to this chunk until its content size + /// is a multiple of `alignment`. + /// + /// May also increase the alignment of the chunk, as if + /// calling `setAlignmentToAtLeast(alignment)`. + /// + /// The padding bytes will all be zero. + /// + void writePaddingToAlignTo(Size alignment); + + /// Write a relative pointer to the given `targetChunk`. + /// + /// The type parameter `T` is used to determine the size + /// of the relative pointer (should be either 4 or 8 bytes). + /// + /// The bytes that eventually get written will contain + /// the computed offset of `targetChunk` minus the computed + /// offset of the first byte of the relative pointer itself. + /// + /// Acts as is `writePaddingToAlignTo(sizeof(T))` were + /// called immediately before. + /// + template<typename T> + void writeRelativePtr(ChunkBuilder* targetChunk) + { + _writeRelativePtr(targetChunk, sizeof(T)); + } + + /// Append the contents of another chunk to this one. + /// + /// This *moves* all of the contents of `chunk` into `this`. + /// After the operation completes `chunk` will be an empty + /// chunk with one-byte alignment. + /// + /// This operation is useful when accumulating data that + /// needs to be appended to the chunk, but where the correct + /// alignment for that data is not yet known; a use can + /// effectively create a temporary "sub-chunk" and then append + /// it to the main chunk once its correct alignment is known. + /// + void addContentsOf(ChunkBuilder* chunk); + + /// Get the size in bytes of the prefix of this chunk, if any. + /// + /// The prefix will be written so that the *end* offset of the + /// prefix data is the same as the starting offset of the + /// chunk's content. + /// + Size getPrefixSize() const; + + /// Add a prefix to this chunk, consisting of raw data. + /// + /// This chunk must not already have a prefix. + /// + void addPrefixData(void const* data, Size size); + + /// Add a prefix to this chunk, consisting of a relative pointer. + /// + /// This chunk must not already have a prefix. + /// + /// Updates the alignment of the chunk as if making a call to + /// `setAlignmentToAtLeast(sizeof(T))`. + /// + template<typename T> + void addPrefixRelativePtr(ChunkBuilder* targetChunk) + { + _addPrefixRelativePtr(targetChunk, sizeof(T)); + } + + /// Insert a new chunk into the blob, immediately after this chunk. + /// + ChunkBuilder* addChunkAfter(); + +private: + ChunkBuilder() = delete; + ChunkBuilder(ChunkBuilder const&) = delete; + ChunkBuilder(ChunkBuilder&&) = delete; + + friend struct BlobBuilder; + friend class ShardBuilder; + + ChunkBuilder(BlobBuilder* parentBlob); + + Size _contentSize = 0; + Size _contentAlignment = 1; + + InternallyLinkedList<ShardBuilder> _childShards; + BlobBuilder* _parentBlob = nullptr; + + Size _cachedOffset = ~Size(0); + Size _getCachedOffset() { return _cachedOffset; } + void _setCachedOffset(Size offset) { _cachedOffset = offset; } + + void _writeRelativePtr(ChunkBuilder* targetChunk, Size ptrSize); + + ShardBuilder* _createDataShard(void const* data, Size size); + ShardBuilder* _createRelativePtrShard(ChunkBuilder* targetChunk, Size ptrSize); + + ShardBuilder* _prefixShard = nullptr; + + void _writeTo(Stream* stream); + + void _addPrefixRelativePtr(ChunkBuilder* targetChunk, Size ptrSize); +}; + +/// A shard is a unit of contiguously-allocated data that makes +/// up part of a chunk. +/// +/// Shards are *not* meant to be directly manipulated by users; +/// they are an implementation detail of `ChunkBuilder`. +/// +/// Every `ShardBuilder` is owned by its parent `ChunkBuilder`. +/// A pointer to a `ShardBuilder` will only be valid during the +/// lifetime of the parent `ChunkBuilder`. +/// +class ShardBuilder : public InternallyLinkedList<ShardBuilder>::Node +{ +public: + // There are two kinds of shards that may appear in a chunk: + // + // * Shards that hold plain data that will be part of the + // serialized chunk. + // + // * Shards that represent a relative pointer to some chunk, + // which cannot have their exact binary value determined + // until the offsets of chunk/shards have been finalized. + + enum class Kind + { + Data, + RelativePtr, + }; + + Size getSize() const { return _size; } + +private: + ShardBuilder() = delete; + ShardBuilder(ShardBuilder const&) = delete; + ShardBuilder(ShardBuilder&&) = delete; + + friend class ChunkBuilder; + ShardBuilder(Kind kind); + + void _writeTo(Stream* stream, Size selfOffset); + + /// Kind of this shard (data or relative pointer) + Kind _kind = Kind::Data; + + union + { + /// Used when `_kind == Kind::Data` + struct + { + void const* ptr; + } _data; + + /// Used when `_kind == Kind::RelativePtr` + struct + { + ChunkBuilder* targetChunk; + } _relativePtr; + }; + + // Size of this shard in bytes. + Size _size = 0; +}; + +} // namespace Slang + +#endif diff --git a/source/core/slang-internally-linked-list.cpp b/source/core/slang-internally-linked-list.cpp new file mode 100644 index 000000000..27bbd77b0 --- /dev/null +++ b/source/core/slang-internally-linked-list.cpp @@ -0,0 +1,2 @@ +// slang-internally-linked-list.cpp +#include "slang-internally-linked-list.h" diff --git a/source/core/slang-internally-linked-list.h b/source/core/slang-internally-linked-list.h new file mode 100644 index 000000000..168885531 --- /dev/null +++ b/source/core/slang-internally-linked-list.h @@ -0,0 +1,126 @@ +// slang-internally-linked-list.h +#ifndef SLANG_INTERNALLY_LINKED_LIST_H +#define SLANG_INTERNALLY_LINKED_LIST_H + +// This file provides support for the idiom of a linked +// list of values where the "next" pointer is stored in +// the values themselves (thus requiring no additional +// allocation for list nodes, at the price of any given +// value only being able to appear in a single list). + +#include "slang-basic.h" + +namespace Slang +{ + +/// A linked list where the elements are themselves the nodes. +/// +/// The type parameter `T` should be a type that publicly +/// inherits from `InternallyLinkedList<T>::Node`. +/// +template<typename T> +struct InternallyLinkedList +{ +public: + struct Node + { + public: + Node() {} + + private: + friend struct InternallyLinkedList<T>; + T* _next = nullptr; + }; + + struct Iterator + { + public: + Iterator() {} + + Iterator(T* node) + : _node(node) + { + } + + T* operator*() const { return _node; } + + void operator++() { _node = static_cast<Node const*>(_node)->_next; } + + bool operator!=(Iterator const& that) const { return _node != that._node; } + + private: + T* _node = nullptr; + }; + + Iterator begin() { return Iterator(_first); } + + Iterator end() { return Iterator(); } + + T* getFirst() const { return _first; } + + T* getLast() const { return _last; } + + void add(T* element) + { + SLANG_ASSERT(element != nullptr); + if (!_last) + { + SLANG_ASSERT(_first == nullptr); + + _first = element; + _last = element; + } + else + { + SLANG_ASSERT(_first != nullptr); + + _last->_next = element; + _last = element; + } + } + + void insertAfter(T* existingElement, T* newElement) + { + SLANG_ASSERT(existingElement != nullptr); + SLANG_ASSERT(newElement != nullptr); + if (existingElement == _last) + { + add(newElement); + } + else + { + newElement->_next = existingElement->_next; + existingElement->_next = newElement; + } + } + + void append(InternallyLinkedList<T> const& other) + { + if (!other._first) + { + } + else if (!_last) + { + _first = other._first; + _last = other._last; + } + else + { + SLANG_ASSERT(_first != nullptr); + + _last->_next = other._first; + _last = other._last; + } + } + +private: + T* _first = nullptr; + T* _last = nullptr; +}; + +template<typename T> +using InternallyLinkedListNode = InternallyLinkedList<T>::Node; + +} // namespace Slang + +#endif diff --git a/source/core/slang-memory-arena.h b/source/core/slang-memory-arena.h index 03631befe..714918b9a 100644 --- a/source/core/slang-memory-arena.h +++ b/source/core/slang-memory-arena.h @@ -476,4 +476,15 @@ SLANG_FORCE_INLINE void operator delete(void* memory, Slang::MemoryArena& arena) SLANG_UNUSED(arena); } +SLANG_FORCE_INLINE void* operator new[](size_t size, Slang::MemoryArena& arena) +{ + return arena.allocate(size); +} + +SLANG_FORCE_INLINE void operator delete[](void* memory, Slang::MemoryArena& arena) +{ + SLANG_UNUSED(memory); + SLANG_UNUSED(arena); +} + #endif // SLANG_MEMORY_ARENA_H diff --git a/source/core/slang-relative-ptr.cpp b/source/core/slang-relative-ptr.cpp new file mode 100644 index 000000000..0c4da2c6e --- /dev/null +++ b/source/core/slang-relative-ptr.cpp @@ -0,0 +1,2 @@ +// slang-relative-ptr.cpp +#include "slang-relative-ptr.h" diff --git a/source/core/slang-relative-ptr.h b/source/core/slang-relative-ptr.h new file mode 100644 index 000000000..6c4bc942c --- /dev/null +++ b/source/core/slang-relative-ptr.h @@ -0,0 +1,97 @@ +// slang-relative-ptr.h +#ifndef SLANG_RELATIVE_PTR_H +#define SLANG_RELATIVE_PTR_H + +// This file implements a smart pointer type `RelativePtr<T>` +// that, rather than storing the actual *address* of a value +// of type `T`, stores the relative offset (in bytes) between +// the target `T*` and the address of the `RelativePtr<T>` +// itself. +// +// This kind of pointer representation can be useful when +// implementing "memory-mappable" data structures that can +// still conveniently represent complicated object graphs. + +#include "slang-basic.h" + +namespace Slang +{ +namespace detail +{ +struct RelativePtr32Traits +{ + using Offset = Int32; + using UOffset = UInt32; +}; + +struct RelativePtr64Traits +{ + using Offset = Int64; + using UOffset = UInt64; +}; +} // namespace detail + +template<typename T, typename Traits> +struct RelativePtr +{ +public: + using This = RelativePtr<T, Traits>; + using Value = T; + using RawPtr = T*; + using Offset = typename Traits::Offset; + using UOffset = typename Traits::UOffset; + + RelativePtr() = default; + RelativePtr(RelativePtr const& ptr) { set(ptr); } + RelativePtr(RelativePtr&& ptr) { set(ptr); } + RelativePtr(T* ptr) { set(ptr); } + + void operator=(RelativePtr const& ptr) { set(ptr); } + void operator=(RelativePtr&& ptr) { set(ptr); } + void operator=(T* ptr) { set(ptr); } + + T* get() const + { + if (_offset == 0) + { + return nullptr; + } + + intptr_t thisAddr = intptr_t(this); + intptr_t targetAddr = thisAddr + intptr_t(_offset); + + return (T*)(targetAddr); + } + + void set(T* ptr) + { + if (ptr == nullptr) + { + _offset = 0; + return; + } + + intptr_t thisAddr = intptr_t(this); + intptr_t targetAddr = intptr_t(ptr); + intptr_t offsetVal = targetAddr - thisAddr; + + _offset = Offset(offsetVal); + SLANG_ASSERT(intptr_t(_offset) == offsetVal); + } + + operator T*() const { return get(); } + T* operator->() const { return get(); } + +private: + Offset _offset = 0; +}; + +template<typename T> +using RelativePtr32 = RelativePtr<T, detail::RelativePtr32Traits>; + +template<typename T> +using RelativePtr64 = RelativePtr<T, detail::RelativePtr64Traits>; + +} // namespace Slang + +#endif diff --git a/source/core/slang-riff.h b/source/core/slang-riff.h index 20b1d7c66..9459c8a55 100644 --- a/source/core/slang-riff.h +++ b/source/core/slang-riff.h @@ -16,6 +16,7 @@ // #include "slang-basic.h" +#include "slang-internally-linked-list.h" #include "slang-memory-arena.h" #include "slang-stream.h" #include "slang-writer.h" @@ -564,73 +565,6 @@ T const* as(Chunk const* chunk) return static_cast<T const*>(chunk); } -/// A linked list where the elements are themselves the nodes. -/// -template<typename T> -struct InternallyLinkedList -{ -public: - struct Node - { - public: - Node() {} - - private: - friend struct InternallyLinkedList<T>; - T* _next = nullptr; - }; - - struct Iterator - { - public: - Iterator() {} - - Iterator(T* node) - : _node(node) - { - } - - T* operator*() const { return _node; } - - void operator++() { _node = static_cast<Node const*>(_node)->_next; } - - bool operator!=(Iterator const& that) const { return _node != that._node; } - - private: - T* _node = nullptr; - }; - - Iterator begin() { return Iterator(_first); } - - Iterator end() { return Iterator(); } - - T* getFirst() const { return _first; } - - T* getLast() const { return _last; } - - void add(T* element) - { - if (!_last) - { - SLANG_ASSERT(_first == nullptr); - - _first = element; - _last = element; - } - else - { - SLANG_ASSERT(_first != nullptr); - - _last->_next = element; - _last = element; - } - } - -private: - T* _first = nullptr; - T* _last = nullptr; -}; - /// A builder for a chunk in a RIFF. class ChunkBuilder : public InternallyLinkedList<ChunkBuilder>::Node { |