vox.utils.arena source code

1 /**
2 Copyright: Copyright (c) 2017-2019 Andrey Penechko.
3 License: $(WEB boost.org/LICENSE_1_0.txt, Boost License 1.0).
4 Authors: Andrey Penechko.
5 */
6 module vox.utils.arena;
7 
8 import std.stdio;
9 import std.traits : isDynamicArray;
10 
11 ///
12 struct Arena(T)
13 {
14 	import vox.utils : alignValue, max, format, to, PAGE_SIZE, paddingSize;
15 	import std.range : isInputRange;
16 
17 	// Profiling stats:
18 	//    4k - 10.00% usage (12.9s)
19 	//   64k -  0.95% usage (11.6s)
20 	//  256k -  0.28% usage (11.5s)
21 	enum COMMIT_PAGE_SIZE = 65_536;
22 
23 	T* bufPtr;
24 	/// How many items can be stored without commiting more memory (committed items)
25 	size_t capacity;
26 	/// Number of items in the buffer. length <= capacity
27 	size_t length;
28 	/// Total reserved bytes
29 	size_t reservedBytes;
30 
31 	size_t committedBytes() { return alignValue(capacity * T.sizeof, COMMIT_PAGE_SIZE); }
32 
33 	uint uintLength() { return length.to!uint; }
34 	size_t byteLength() { return length * T.sizeof; }
35 	ref T opIndex(size_t at) { return bufPtr[at]; }
36 	ref T back() { return bufPtr[length-1]; }
37 	inout(T[]) data() inout { return bufPtr[0..length]; }
38 	bool empty() { return length == 0; }
39 	T* nextPtr() { return bufPtr + length; }
40 	bool contains(void* ptr) { return cast(void*)bufPtr <= ptr && cast(T*)ptr < cast(void*)(bufPtr + length); }
41 
42 	void setBuffer(ubyte[] reservedBuffer) {
43 		setBuffer(reservedBuffer, reservedBuffer.length);
44 	}
45 	void setBuffer(ubyte[] reservedBuffer, size_t committedBytes) {
46 		bufPtr = cast(T*)reservedBuffer.ptr;
47 		assert(bufPtr, "reservedBuffer is null");
48 		reservedBytes = reservedBuffer.length;
49 		// we can lose [0; T.sizeof-1] bytes here, need to round up to multiple of allocation size when committing
50 		capacity = committedBytes / T.sizeof;
51 		length = 0;
52 	}
53 	void clear() { length = 0; }
54 
55 	T[] put(T[] items ...) {
56 		size_t initialLength = length;
57 		version(Windows) {
58 			if (capacity - length < items.length) makeSpace(items.length);
59 		}
60 		//writefln("assign %X.%s @ %s..%s+%s cap %s", bufPtr, T.sizeof, length, length, items.length, capacity);
61 		bufPtr[length..length+items.length] = items;
62 		length += items.length;
63 		return bufPtr[initialLength..length];
64 	}
65 
66 	T[] put(R)(R itemRange) if (isInputRange!R) {
67 		size_t initialLength = length;
68 		foreach(item; itemRange)
69 			put(item);
70 		return bufPtr[initialLength..length];
71 	}
72 
73 	void stealthPut(T item) {
74 		version(Windows) {
75 			if (capacity == length) makeSpace(1);
76 		}
77 		bufPtr[length] = item;
78 	}
79 
80 	/// Increases length and returns void-initialized slice to be filled by user
81 	T[] voidPut(size_t howMany) {
82 		version(Windows) {
83 			if (capacity - length < howMany) makeSpace(howMany);
84 		}
85 		length += howMany;
86 		return bufPtr[length-howMany..length];
87 	}
88 
89 	void free(T[] array) {
90 		T* endPtr = bufPtr + length;
91 		T* arrayEndPtr = array.ptr + array.length;
92 		if (endPtr == arrayEndPtr) {
93 			length -= array.length;
94 		}
95 	}
96 
97 	void unput(size_t numItems) {
98 		length -= numItems;
99 	}
100 
101 	static if (is(T == ubyte))
102 	{
103 		void put(V)(auto ref V value) if (!isDynamicArray!V) {
104 			ubyte[] ptr = voidPut(V.sizeof);
105 			ptr[] = *cast(ubyte[V.sizeof]*)&value;
106 		}
107 
108 		void pad(size_t bytes) {
109 			voidPut(bytes)[] = 0;
110 		}
111 
112 		void padUntilAligned(size_t alignment) {
113 			pad(paddingSize(length, alignment));
114 		}
115 	}
116 
117 	version(Windows)
118 	void makeSpace(size_t items) {
119 		assert(items > (capacity - length));
120 		size_t _committedBytes = committedBytes;
121 		size_t bytesToCommit = alignValue((items - (capacity - length)) * T.sizeof, COMMIT_PAGE_SIZE);
122 		bytesToCommit = max(bytesToCommit, COMMIT_PAGE_SIZE);
123 
124 		if (_committedBytes + bytesToCommit > reservedBytes) {
125 			assert(false, format("Arena.makeSpace() out of memory: reserved %s, committed bytes %s, requested %s",
126 				reservedBytes, _committedBytes, bytesToCommit));
127 		}
128 
129 		version(Windows) {
130 			import vox.utils.windows : VirtualAlloc, MEM_COMMIT, PAGE_READWRITE;
131 			void* result = VirtualAlloc(cast(ubyte*)bufPtr + _committedBytes, bytesToCommit, MEM_COMMIT, PAGE_READWRITE);
132 			if (result is null) assert(false, "Cannot commit more bytes");
133 		} else version(Posix) {
134 			// noop, mmap already committed all memory
135 		} else static assert(false, "Not implemented on this platform");
136 
137 		capacity = (_committedBytes + bytesToCommit) / T.sizeof;
138 	}
139 }