1 /********************************************************* 2 Copyright: (C) 2008-2010 by Steven Schveighoffer. 3 All rights reserved 4 5 License: Boost Software License version 1.0 6 7 Permission is hereby granted, free of charge, to any person or organization 8 obtaining a copy of the software and accompanying documentation covered by 9 this license (the "Software") to use, reproduce, display, distribute, 10 execute, and transmit the Software, and to prepare derivative works of the 11 Software, and to permit third-parties to whom the Software is furnished to 12 do so, all subject to the following: 13 14 The copyright notices in the Software and this entire statement, including 15 the above license grant, this restriction and the following disclaimer, must 16 be included in all copies of the Software, in whole or in part, and all 17 derivative works of the Software, unless such copies or derivative works are 18 solely in the form of machine-executable object code generated by a source 19 language processor. 20 21 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 22 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 23 FITNESS FOR A PARTICULAR PURPOSE, TITLE AND NON-INFRINGEMENT. IN NO EVENT 24 SHALL THE COPYRIGHT HOLDERS OR ANYONE DISTRIBUTING THE SOFTWARE BE LIABLE 25 FOR ANY DAMAGES OR OTHER LIABILITY, WHETHER IN CONTRACT, TORT OR OTHERWISE, 26 ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 27 DEALINGS IN THE SOFTWARE. 28 29 **********************************************************/ 30 module Engine.Allocator; 31 32 version(DDoc) 33 { 34 } 35 else 36 { 37 private import core.memory; 38 private import std.c..string; 39 } 40 41 /** 42 * Allocate a chunk of elements at once, then use the chunk to return 43 * elements. This makes allocating individual elements more efficient 44 * because the GC isn't used for allocating every element, only every 45 * chunk of elements. 46 * 47 * The only requirement is that the size of V is >= size of a pointer. 48 * This is because the data V contains is used as a pointer when freeing 49 * the element. 50 * 51 * If an entire chunk of elements is freed, that chunk is then returned to 52 * the GC. 53 */ 54 struct ChunkAllocator(V, uint elemsPerChunk) 55 { 56 /** 57 * Free is needed to recycle nodes for another allocation. 58 */ 59 enum bool freeNeeded = true; 60 static if(V.sizeof < (void*).sizeof) 61 { 62 static assert(false, "Error, allocator for " ~ V.stringof ~ " failed to instantiate"); 63 } 64 65 /** 66 * This is the form used to link recyclable elements together. 67 */ 68 struct element 69 { 70 element *next; 71 } 72 73 /** 74 * A chunk of elements 75 */ 76 struct chunk 77 { 78 /** 79 * The next chunk in the chain 80 */ 81 chunk *next; 82 83 /** 84 * The previous chunk in the chain. Required for O(1) removal 85 * from the chain. 86 */ 87 chunk *prev; 88 89 /** 90 * The linked list of free elements in the chunk. This list is 91 * amended each time an element in this chunk is freed. 92 */ 93 element *freeList; 94 95 /** 96 * The number of free elements in the freeList. Used to determine 97 * whether this chunk can be given back to the GC 98 */ 99 uint numFree; 100 101 /** 102 * The elements in the chunk. 103 */ 104 V[elemsPerChunk] elems; 105 106 /** 107 * Allocate a V* from the free list. 108 */ 109 V *allocateFromFree() 110 { 111 element *x = freeList; 112 freeList = x.next; 113 // 114 // initialize the element. We do it this way to avoid triggering 115 // any copy hooks such as postblits 116 // 117 auto init = cast(ubyte[])typeid(V).init(); 118 if(init.ptr is null) // null ptr means initialize to 0 119 x.next = null; // we already know the other bytes are 0 120 else 121 { 122 auto buf = (cast(ubyte *)x)[0..(V).sizeof]; 123 buf[] = init[]; 124 } 125 numFree--; 126 return cast(V*)x; 127 } 128 129 /** 130 * deallocate a V*, send it to the free list 131 * 132 * returns true if this chunk no longer has any used elements. 133 */ 134 bool deallocate(V *v) 135 { 136 // 137 // clear the element so the GC does not interpret the element 138 // as pointing to anything else. 139 // 140 memset(v, 0, (V).sizeof); 141 element *x = cast(element *)v; 142 x.next = freeList; 143 freeList = x; 144 return (++numFree == elemsPerChunk); 145 } 146 } 147 148 /** 149 * The chain of used chunks. Used chunks have had all their elements 150 * allocated at least once. 151 */ 152 chunk *used; 153 154 /** 155 * The fresh chunk. This is only used if no elements are available in 156 * the used chain. 157 */ 158 chunk *fresh; 159 160 /** 161 * The next element in the fresh chunk. Because we don't worry about 162 * the free list in the fresh chunk, we need to keep track of the next 163 * fresh element to use. 164 */ 165 uint nextFresh; 166 167 /** 168 * Allocate a V* 169 */ 170 V* allocate() 171 { 172 if(used !is null && used.numFree > 0) 173 { 174 // 175 // allocate one element of the used list 176 // 177 V* result = used.allocateFromFree(); 178 if(used.numFree == 0) 179 // 180 // move used to the end of the list 181 // 182 used = used.next; 183 return result; 184 } 185 186 // 187 // no used elements are available, allocate out of the fresh 188 // elements 189 // 190 if(fresh is null) 191 { 192 fresh = new chunk; 193 nextFresh = 0; 194 } 195 196 V* result = &fresh.elems[nextFresh]; 197 if(++nextFresh == elemsPerChunk) 198 { 199 if(used is null) 200 { 201 used = fresh; 202 fresh.next = fresh; 203 fresh.prev = fresh; 204 } 205 else 206 { 207 // 208 // insert fresh into the used chain 209 // 210 fresh.prev = used.prev; 211 fresh.next = used; 212 fresh.prev.next = fresh; 213 fresh.next.prev = fresh; 214 if(fresh.numFree != 0) 215 { 216 // 217 // can recycle elements from fresh 218 // 219 used = fresh; 220 } 221 } 222 fresh = null; 223 } 224 return result; 225 } 226 227 /** 228 * free a V* 229 */ 230 void free(V* v) 231 { 232 // 233 // need to figure out which chunk v is in 234 // 235 chunk *cur = cast(chunk *)GC.addrOf(v); 236 237 if(cur !is fresh && cur.numFree == 0) 238 { 239 // 240 // move cur to the front of the used list, it has free nodes 241 // to be used. 242 // 243 if(cur !is used) 244 { 245 if(used !is null) 246 { 247 // 248 // first, unlink cur from its current location 249 // 250 cur.prev.next = cur.next; 251 cur.next.prev = cur.prev; 252 253 // 254 // now, insert cur before used. 255 // 256 cur.prev = used.prev; 257 cur.next = used; 258 used.prev = cur; 259 cur.prev.next = cur; 260 } 261 else 262 { 263 cur.next = cur.prev = cur; 264 } 265 used = cur; 266 } 267 } 268 269 if(cur.deallocate(v)) 270 { 271 // 272 // cur no longer has any elements in use, it can be deleted. 273 // 274 if(cur is fresh || cur.next is cur) 275 { 276 // 277 // cur is either fresh or is the only element in the 278 // used chain 279 // 280 } 281 else 282 { 283 // 284 // remove cur from list 285 // 286 if(used is cur) 287 { 288 // 289 // update used pointer 290 // 291 used = used.next; 292 } 293 cur.next.prev = cur.prev; 294 cur.prev.next = cur.next; 295 delete cur; 296 } 297 } 298 } 299 300 /** 301 * Deallocate all chunks used by this allocator. 302 */ 303 void freeAll() 304 { 305 if(fresh is null) 306 { 307 fresh = used; 308 } 309 used = null; 310 311 // 312 // keep fresh around 313 // 314 if(fresh !is null) 315 { 316 nextFresh = 0; 317 // need to re-initialize the data elements 318 auto chunkinit = cast(ubyte[])typeid(chunk).init(); 319 if(chunkinit.ptr is null) 320 // all the data is zero, just write 0s to the chunk 321 memset(fresh, 0, chunk.sizeof); 322 else 323 { 324 // copy the entire init array 325 auto buf = (cast(ubyte *)fresh)[0..chunk.sizeof]; 326 buf[] = chunkinit[]; 327 } 328 } 329 } 330 }