1 /* Copyright (C) 2013 Wildfire Games. 2 * 3 * Permission is hereby granted, free of charge, to any person obtaining 4 * a copy of this software and associated documentation files (the 5 * "Software"), to deal in the Software without restriction, including 6 * without limitation the rights to use, copy, modify, merge, publish, 7 * distribute, sublicense, and/or sell copies of the Software, and to 8 * permit persons to whom the Software is furnished to do so, subject to 9 * the following conditions: 10 * 11 * The above copyright notice and this permission notice shall be included 12 * in all copies or substantial portions of the Software. 13 * 14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, 15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF 16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. 17 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY 18 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT, 19 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE 20 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. 21 */ 22 23 /* 24 * arena allocator (variable-size blocks, no deallocation). 25 */ 26 27 #ifndef INCLUDED_ALLOCATORS_ARENA 28 #define INCLUDED_ALLOCATORS_ARENA 29 30 #include "lib/allocators/allocator_policies.h" 31 32 namespace Allocators { 33 34 /** 35 * allocator design parameters: 36 * - O(1) allocation; 37 * - variable-size blocks; 38 * - support for deallocating all objects; 39 * - consecutive allocations are back-to-back; 40 * - no extra alignment nor padding. 41 **/ 42 template<class Storage = Storage_Fixed<> > 43 class Arena 44 { 45 NONCOPYABLE(Arena); 46 public: Arena(size_t maxSize)47 Arena(size_t maxSize) 48 : storage(maxSize) 49 { 50 DeallocateAll(); 51 } 52 RemainingBytes()53 size_t RemainingBytes() const 54 { 55 return storage.MaxCapacity() - end; 56 } 57 allocate(size_t size)58 void* allocate(size_t size) 59 { 60 return (void*)StorageAppend(storage, end, size); 61 } 62 deallocate(void * UNUSED (p),size_t UNUSED (size))63 void deallocate(void* UNUSED(p), size_t UNUSED(size)) 64 { 65 // ignored 66 } 67 DeallocateAll()68 void DeallocateAll() 69 { 70 end = 0; 71 } 72 73 // @return whether the address lies within the previously allocated range. Contains(uintptr_t address)74 bool Contains(uintptr_t address) const 75 { 76 return (address - storage.Address()) < end; 77 } 78 79 private: 80 Storage storage; 81 size_t end; 82 }; 83 84 LIB_API void TestArena(); 85 86 87 /** 88 * allocator design parameters: 89 * - grow dynamically with a fixed chunkSize 90 * - for frequent allocations of size << chunkSize 91 * - no reallocations, pointers remain valid 92 **/ 93 class DynamicArena 94 { 95 struct ArenaChunk 96 { AvailableArenaChunk97 bool Available(size_t size) const 98 { 99 return size <= (capacity - end); 100 } 101 102 // Must check Available first or this may return an invalid address AllocateArenaChunk103 uintptr_t Allocate(size_t size) 104 { 105 uintptr_t ptr = storage + end; 106 end += size; 107 return ptr; 108 } 109 110 uintptr_t storage; 111 size_t end; 112 size_t capacity; 113 ArenaChunk* next; 114 }; 115 116 NONCOPYABLE(DynamicArena); 117 public: DynamicArena(size_t chunkSize)118 DynamicArena(size_t chunkSize) : chunkSize(chunkSize), head(NULL) 119 { 120 AllocateNewChunk(); 121 } 122 ~DynamicArena()123 ~DynamicArena() 124 { 125 ArenaChunk* chunk = head; 126 while (chunk != NULL) 127 { 128 ArenaChunk* next = chunk->next; 129 free(chunk); 130 chunk = next; 131 } 132 } 133 AllocateNewChunk()134 void AllocateNewChunk() 135 { 136 // For efficiency, do a single allocation with the ArenaChunk and its storage 137 ArenaChunk* next = head; 138 head = (ArenaChunk*)malloc(sizeof(ArenaChunk) + chunkSize); 139 ENSURE(head); 140 head->storage = sizeof(ArenaChunk) + uintptr_t(head); 141 head->end = 0; 142 head->capacity = chunkSize; 143 head->next = next; 144 } 145 allocate(size_t size)146 void* allocate(size_t size) 147 { 148 if (size > chunkSize) 149 { 150 debug_warn(L"DynamicArena cannot allocate more than chunk size"); 151 throw std::bad_alloc(); 152 } 153 else if (!head->Available(size)) 154 AllocateNewChunk(); 155 156 return (void*)head->Allocate(size); 157 } 158 deallocate(void * UNUSED (p),size_t UNUSED (size))159 void deallocate(void* UNUSED(p), size_t UNUSED(size)) 160 { 161 // ignored 162 } 163 164 private: 165 166 const size_t chunkSize; 167 ArenaChunk *head; 168 }; 169 170 171 } // namespace Allocators 172 173 #endif // #ifndef INCLUDED_ALLOCATORS_ARENA 174