Mercurial > repos > rliterman > csp2

annotate CSP2/CSP2_env/env-d9b9114564458d9d-741b3de822f2aaca6c6caa4325c4afce/include/kj/arena.h @ 69:33d812a61356

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
planemo upload commit 2e9511a184a1ca667c7be0c6321a36dc4e3d116d
author jpayne
date Tue, 18 Mar 2025 17:55:14 -0400
parents
children
rev   line source
jpayne@69 1 // Copyright (c) 2013-2014 Sandstorm Development Group, Inc. and contributors
jpayne@69 2 // Licensed under the MIT License:
jpayne@69 3 //
jpayne@69 4 // Permission is hereby granted, free of charge, to any person obtaining a copy
jpayne@69 5 // of this software and associated documentation files (the "Software"), to deal
jpayne@69 6 // in the Software without restriction, including without limitation the rights
jpayne@69 7 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
jpayne@69 8 // copies of the Software, and to permit persons to whom the Software is
jpayne@69 9 // furnished to do so, subject to the following conditions:
jpayne@69 10 //
jpayne@69 11 // The above copyright notice and this permission notice shall be included in
jpayne@69 12 // all copies or substantial portions of the Software.
jpayne@69 13 //
jpayne@69 14 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
jpayne@69 15 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
jpayne@69 16 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
jpayne@69 17 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
jpayne@69 18 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
jpayne@69 19 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
jpayne@69 20 // THE SOFTWARE.
jpayne@69 21
jpayne@69 22 #pragma once
jpayne@69 23
jpayne@69 24 #include "memory.h"
jpayne@69 25 #include "array.h"
jpayne@69 26 #include "string.h"
jpayne@69 27
jpayne@69 28 KJ_BEGIN_HEADER
jpayne@69 29
jpayne@69 30 namespace kj {
jpayne@69 31
jpayne@69 32 class Arena {
jpayne@69 33 // A class which allows several objects to be allocated in contiguous chunks of memory, then
jpayne@69 34 // frees them all at once.
jpayne@69 35 //
jpayne@69 36 // Allocating from the same Arena in multiple threads concurrently is NOT safe, because making
jpayne@69 37 // it safe would require atomic operations that would slow down allocation even when
jpayne@69 38 // single-threaded. If you need to use arena allocation in a multithreaded context, consider
jpayne@69 39 // allocating thread-local arenas.
jpayne@69 40
jpayne@69 41 public:
jpayne@69 42 explicit Arena(size_t chunkSizeHint = 1024);
jpayne@69 43 // Create an Arena. `chunkSizeHint` hints at where to start when allocating chunks, but is only
jpayne@69 44 // a hint -- the Arena will, for example, allocate progressively larger chunks as time goes on,
jpayne@69 45 // in order to reduce overall allocation overhead.
jpayne@69 46
jpayne@69 47 explicit Arena(ArrayPtr<byte> scratch);
jpayne@69 48 // Allocates from the given scratch space first, only resorting to the heap when it runs out.
jpayne@69 49
jpayne@69 50 KJ_DISALLOW_COPY_AND_MOVE(Arena);
jpayne@69 51 ~Arena() noexcept(false);
jpayne@69 52
jpayne@69 53 template <typename T, typename... Params>
jpayne@69 54 T& allocate(Params&&... params);
jpayne@69 55 template <typename T>
jpayne@69 56 ArrayPtr<T> allocateArray(size_t size);
jpayne@69 57 // Allocate an object or array of type T. If T has a non-trivial destructor, that destructor
jpayne@69 58 // will be run during the Arena's destructor. Such destructors are run in opposite order of
jpayne@69 59 // allocation. Note that these methods must maintain a list of destructors to call, which has
jpayne@69 60 // overhead, but this overhead only applies if T has a non-trivial destructor.
jpayne@69 61
jpayne@69 62 template <typename T, typename... Params>
jpayne@69 63 Own<T> allocateOwn(Params&&... params);
jpayne@69 64 template <typename T>
jpayne@69 65 Array<T> allocateOwnArray(size_t size);
jpayne@69 66 template <typename T>
jpayne@69 67 ArrayBuilder<T> allocateOwnArrayBuilder(size_t capacity);
jpayne@69 68 // Allocate an object or array of type T. Destructors are executed when the returned Own<T>
jpayne@69 69 // or Array<T> goes out-of-scope, which must happen before the Arena is destroyed. This variant
jpayne@69 70 // is useful when you need to control when the destructor is called. This variant also avoids
jpayne@69 71 // the need for the Arena itself to keep track of destructors to call later, which may make it
jpayne@69 72 // slightly more efficient.
jpayne@69 73
jpayne@69 74 template <typename T>
jpayne@69 75 inline T& copy(T&& value) { return allocate<Decay<T>>(kj::fwd<T>(value)); }
jpayne@69 76 // Allocate a copy of the given value in the arena. This is just a shortcut for calling the
jpayne@69 77 // type's copy (or move) constructor.
jpayne@69 78
jpayne@69 79 StringPtr copyString(StringPtr content);
jpayne@69 80 // Make a copy of the given string inside the arena, and return a pointer to the copy.
jpayne@69 81
jpayne@69 82 private:
jpayne@69 83 struct ChunkHeader {
jpayne@69 84 ChunkHeader* next;
jpayne@69 85 byte* pos; // first unallocated byte in this chunk
jpayne@69 86 byte* end; // end of this chunk
jpayne@69 87 };
jpayne@69 88 struct ObjectHeader {
jpayne@69 89 void (*destructor)(void*);
jpayne@69 90 ObjectHeader* next;
jpayne@69 91 };
jpayne@69 92
jpayne@69 93 size_t nextChunkSize;
jpayne@69 94 ChunkHeader* chunkList = nullptr;
jpayne@69 95 ObjectHeader* objectList = nullptr;
jpayne@69 96
jpayne@69 97 ChunkHeader* currentChunk = nullptr;
jpayne@69 98
jpayne@69 99 void cleanup();
jpayne@69 100 // Run all destructors, leaving the above pointers null. If a destructor throws, the State is
jpayne@69 101 // left in a consistent state, such that if cleanup() is called again, it will pick up where
jpayne@69 102 // it left off.
jpayne@69 103
jpayne@69 104 void* allocateBytes(size_t amount, uint alignment, bool hasDisposer);
jpayne@69 105 // Allocate the given number of bytes. `hasDisposer` must be true if `setDisposer()` may be
jpayne@69 106 // called on this pointer later.
jpayne@69 107
jpayne@69 108 void* allocateBytesInternal(size_t amount, uint alignment);
jpayne@69 109 // Try to allocate the given number of bytes without taking a lock. Fails if and only if there
jpayne@69 110 // is no space left in the current chunk.
jpayne@69 111
jpayne@69 112 void setDestructor(void* ptr, void (*destructor)(void*));
jpayne@69 113 // Schedule the given destructor to be executed when the Arena is destroyed. `ptr` must be a
jpayne@69 114 // pointer previously returned by an `allocateBytes()` call for which `hasDisposer` was true.
jpayne@69 115
jpayne@69 116 template <typename T>
jpayne@69 117 static void destroyArray(void* pointer) {
jpayne@69 118 size_t elementCount = *reinterpret_cast<size_t*>(pointer);
jpayne@69 119 constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t));
jpayne@69 120 DestructorOnlyArrayDisposer::instance.disposeImpl(
jpayne@69 121 reinterpret_cast<byte*>(pointer) + prefixSize,
jpayne@69 122 sizeof(T), elementCount, elementCount, &destroyObject<T>);
jpayne@69 123 }
jpayne@69 124
jpayne@69 125 template <typename T>
jpayne@69 126 static void destroyObject(void* pointer) {
jpayne@69 127 dtor(*reinterpret_cast<T*>(pointer));
jpayne@69 128 }
jpayne@69 129 };
jpayne@69 130
jpayne@69 131 // =======================================================================================
jpayne@69 132 // Inline implementation details
jpayne@69 133
jpayne@69 134 template <typename T, typename... Params>
jpayne@69 135 T& Arena::allocate(Params&&... params) {
jpayne@69 136 T& result = *reinterpret_cast<T*>(allocateBytes(
jpayne@69 137 sizeof(T), alignof(T), !KJ_HAS_TRIVIAL_DESTRUCTOR(T)));
jpayne@69 138 if (!KJ_HAS_TRIVIAL_CONSTRUCTOR(T) || sizeof...(Params) > 0) {
jpayne@69 139 ctor(result, kj::fwd<Params>(params)...);
jpayne@69 140 }
jpayne@69 141 if (!KJ_HAS_TRIVIAL_DESTRUCTOR(T)) {
jpayne@69 142 setDestructor(&result, &destroyObject<T>);
jpayne@69 143 }
jpayne@69 144 return result;
jpayne@69 145 }
jpayne@69 146
jpayne@69 147 template <typename T>
jpayne@69 148 ArrayPtr<T> Arena::allocateArray(size_t size) {
jpayne@69 149 if (KJ_HAS_TRIVIAL_DESTRUCTOR(T)) {
jpayne@69 150 ArrayPtr<T> result =
jpayne@69 151 arrayPtr(reinterpret_cast<T*>(allocateBytes(
jpayne@69 152 sizeof(T) * size, alignof(T), false)), size);
jpayne@69 153 if (!KJ_HAS_TRIVIAL_CONSTRUCTOR(T)) {
jpayne@69 154 for (size_t i = 0; i < size; i++) {
jpayne@69 155 ctor(result[i]);
jpayne@69 156 }
jpayne@69 157 }
jpayne@69 158 return result;
jpayne@69 159 } else {
jpayne@69 160 // Allocate with a 64-bit prefix in which we store the array size.
jpayne@69 161 constexpr size_t prefixSize = kj::max(alignof(T), sizeof(size_t));
jpayne@69 162 void* base = allocateBytes(sizeof(T) * size + prefixSize, alignof(T), true);
jpayne@69 163 size_t& tag = *reinterpret_cast<size_t*>(base);
jpayne@69 164 ArrayPtr<T> result =
jpayne@69 165 arrayPtr(reinterpret_cast<T*>(reinterpret_cast<byte*>(base) + prefixSize), size);
jpayne@69 166 setDestructor(base, &destroyArray<T>);
jpayne@69 167
jpayne@69 168 if (KJ_HAS_TRIVIAL_CONSTRUCTOR(T)) {
jpayne@69 169 tag = size;
jpayne@69 170 } else {
jpayne@69 171 // In case of constructor exceptions, we need the tag to end up storing the number of objects
jpayne@69 172 // that were successfully constructed, so that they'll be properly destroyed.
jpayne@69 173 tag = 0;
jpayne@69 174 for (size_t i = 0; i < size; i++) {
jpayne@69 175 ctor(result[i]);
jpayne@69 176 tag = i + 1;
jpayne@69 177 }
jpayne@69 178 }
jpayne@69 179 return result;
jpayne@69 180 }
jpayne@69 181 }
jpayne@69 182
jpayne@69 183 template <typename T, typename... Params>
jpayne@69 184 Own<T> Arena::allocateOwn(Params&&... params) {
jpayne@69 185 T& result = *reinterpret_cast<T*>(allocateBytes(sizeof(T), alignof(T), false));
jpayne@69 186 if (!KJ_HAS_TRIVIAL_CONSTRUCTOR(T) || sizeof...(Params) > 0) {
jpayne@69 187 ctor(result, kj::fwd<Params>(params)...);
jpayne@69 188 }
jpayne@69 189 return Own<T>(&result, DestructorOnlyDisposer<T>::instance);
jpayne@69 190 }
jpayne@69 191
jpayne@69 192 template <typename T>
jpayne@69 193 Array<T> Arena::allocateOwnArray(size_t size) {
jpayne@69 194 ArrayBuilder<T> result = allocateOwnArrayBuilder<T>(size);
jpayne@69 195 for (size_t i = 0; i < size; i++) {
jpayne@69 196 result.add();
jpayne@69 197 }
jpayne@69 198 return result.finish();
jpayne@69 199 }
jpayne@69 200
jpayne@69 201 template <typename T>
jpayne@69 202 ArrayBuilder<T> Arena::allocateOwnArrayBuilder(size_t capacity) {
jpayne@69 203 return ArrayBuilder<T>(
jpayne@69 204 reinterpret_cast<T*>(allocateBytes(sizeof(T) * capacity, alignof(T), false)),
jpayne@69 205 capacity, DestructorOnlyArrayDisposer::instance);
jpayne@69 206 }
jpayne@69 207
jpayne@69 208 } // namespace kj
jpayne@69 209
jpayne@69 210 KJ_END_HEADER