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