1 /// Copyright: Copyright (c) 2017-2019 Andrey Penechko. 2 /// License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0). 3 /// Authors: Andrey Penechko. 4 module vox.utils.arrayarena; 5 6 struct FreeList 7 { 8 import vox.utils : writef, writefln; 9 void* head; 10 ubyte[] get(size_t size) { 11 if (head) { 12 void** linkPtr = cast(void**)head; 13 head = linkPtr[0]; 14 return (cast(ubyte*)linkPtr)[0..size]; 15 } 16 return null; 17 } 18 void put(ubyte[] block) { 19 void** linkPtr = cast(void**)block.ptr; 20 linkPtr[0] = head; 21 head = cast(void*)block.ptr; 22 } 23 } 24 25 //version = USE_MIMALLOC; 26 27 version(USE_MIMALLOC) { 28 extern(C) void* mi_malloc(size_t size); 29 extern(C) void mi_free(void* p); 30 } 31 32 struct ArrayArena 33 { 34 import core.stdc.stdlib : malloc, free; 35 import vox.utils : max, nextPOT, Arena, bsr, isPowerOfTwo, PAGE_SIZE, writefln, format; 36 37 // arenas for buffers from 16 to 65536 bytes 38 enum NUM_ARENAS = 13; 39 enum MIN_BLOCK_BYTES = 16; 40 enum MAX_BLOCK_BYTES = 65_536; 41 42 private Arena!ubyte[NUM_ARENAS] arenas; 43 private size_t[NUM_ARENAS] arenaLengths; 44 private FreeList[NUM_ARENAS] freeLists; 45 46 void setBuffers(ubyte[] smallBuffers, ubyte[] pageBuffer) { 47 size_t sizePerArena = smallBuffers.length / NUM_ARENAS; 48 foreach(i, ref arena; arenas[0..$-1]) 49 arena.setBuffer(smallBuffers[i*sizePerArena..(i+1)*sizePerArena], 0); 50 arenas[$-1].setBuffer(pageBuffer, 0); // separate buffer for big pages 51 } 52 53 size_t byteLength() { 54 size_t total; 55 foreach(ref arena; arenas) total += arena.byteLength; 56 return total; 57 } 58 59 size_t reservedBytes() { 60 size_t total; 61 foreach(ref arena; arenas) total += arena.reservedBytes; 62 return total; 63 } 64 size_t committedBytes() { 65 size_t total; 66 foreach(ref arena; arenas) total += arena.committedBytes; 67 return total; 68 } 69 70 T[] allocArray(T)(size_t length) { 71 size_t blockSize = max(nextPOT(length * T.sizeof), MIN_BLOCK_BYTES); 72 ubyte[] newBlock = allocBlock(blockSize); 73 return (cast(T*)newBlock.ptr)[0..length]; 74 } 75 76 void freeArray(T)(ref T[] array) { 77 size_t blockSize = max(nextPOT(array.length * T.sizeof), MIN_BLOCK_BYTES); 78 ubyte* ptr = cast(ubyte*)array.ptr; 79 freeBlock(ptr[0..blockSize]); 80 array = null; 81 } 82 83 version(USE_MIMALLOC) 84 { 85 ubyte[] allocBlock(size_t size) { 86 assert(isPowerOfTwo(size)); 87 return (cast(ubyte*)mi_malloc(size))[0..size]; 88 } 89 90 void freeBlock(ubyte[] block) { 91 if (block.ptr is null) return; 92 return mi_free(block.ptr); 93 } 94 } 95 else 96 { 97 ubyte[] allocBlock(size_t size) { 98 assert(isPowerOfTwo(size)); 99 assert(size >= MIN_BLOCK_BYTES); 100 if (size > MAX_BLOCK_BYTES) { 101 return (cast(ubyte*)malloc(size))[0..size]; 102 } 103 uint index = sizeToIndex(size); 104 ubyte[] block = freeLists[index].get(size); 105 if (block) { 106 assert(arenas[index].contains(block.ptr), format("allocBlock %s, freeList get %X, %s", size, block.ptr, block.length)); 107 return block; 108 } 109 ++arenaLengths[index]; 110 ubyte[] result = arenas[index].voidPut(size); 111 return result; 112 } 113 114 void freeBlock(ubyte[] block) { 115 if (block.ptr is null) return; 116 assert(isPowerOfTwo(block.length)); 117 assert(block.length >= MIN_BLOCK_BYTES); 118 if (block.length > MAX_BLOCK_BYTES) { 119 return free(block.ptr); 120 } 121 uint index = sizeToIndex(block.length); 122 freeLists[index].put(block); 123 } 124 } 125 126 void clear() { 127 foreach(ref arena; arenas) arena.clear; 128 freeLists[] = FreeList.init; 129 arenaLengths[] = 0; 130 } 131 132 private uint sizeToIndex(size_t size) { 133 // from 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 134 // to 0 1 2 3 4 5 6 7 8 9 10 11 12 135 uint index = bsr(size) - 4; 136 return index; 137 } 138 } 139