nxt.container.tree source code

1 module nxt.container.tree;
2 
3 /** N-ary tree that cannot shrink but only grow (in breadth and depth).
4  *
5  * Because of this a region allocator can be used for internal memory
6  * allocation.
7  *
8  * See_Also: http://forum.dlang.org/post/prsxfcmkngfwomygmthi@forum.dlang.org
9  */
10 struct GrowOnlyNaryTree(E) {
11 	alias N = Node!E;
12 
13 	/* @safe pure: */
14 public:
15 
16 	/// Create with region size in bytes.
17 	this(size_t regionSize) @trusted
18 	{
19 		_allocator = Allocator(regionSize);
20 	}
21 
22 	this(in E e, size_t regionSize) @trusted
23 	{
24 		_allocator = Allocator(regionSize);
25 		_root = _allocator.make!N(e);
26 	}
27 
28 	/// Returns: top node.
29 	inout(Node!E)* root() inout return scope
30 	{
31 		return _root;
32 	}
33 
34 private:
35 	N* _root;
36 
37 	import std.experimental.allocator : make, makeArray;
38 	import std.experimental.allocator.building_blocks.region : Region;
39 	import std.experimental.allocator.mallocator : Mallocator;
40 	alias Allocator = Region!Mallocator;
41 
42 	Allocator _allocator;
43 }
44 
45 /*@safe*/ unittest {
46 	struct X { string src; }
47 
48 	const e = X("alpha");
49 	auto tree = GrowOnlyNaryTree!X(e, 1024 * 1024);
50 	assert(tree.root.data == e);
51 
52 	/+ TODO: this should fail to compile with -dip1000 +/
53 	Node!X* dumb() {
54 		auto tree = GrowOnlyNaryTree!X(e, 1024 * 1024);
55 		return tree.root;
56 	}
57 
58 	dumb();
59 }
60 
61 /// Tree node containing `E`.
62 private struct Node(E) {
63 private:
64 	E data;
65 
66 	// allocate with pointers with std.experimental.allocator.makeArray and each
67 	// pointer with std.experimental.allocator.makeArray
68 	Node!E*[] subs;
69 }