digitalmars.D - Re: Ternary Search Trees
- bearophile <bearophileHUGS lycos.com> Apr 18 2009
This is the final version I am added to the dlibs: /******************************************** To create a memory pool of a native item, like structs. Not thread-safe. It allows to create new items (it performs block-allocations for speed), and then free them all at once (and then you can create some more). */ struct MemoryPool(T, int MAX_BLOCK_BYTES=1 << 14) { static assert(!is(T == class), "MemoryPool is designed for native data, not classes."); static assert(MAX_BLOCK_BYTES >= 1, "MemoryPool: MAX_BLOCK_BYTES must be >= 1 bytes."); struct Block { static assert(MAX_BLOCK_BYTES >= T.sizeof, "MemoryPool: MAX_BLOCK_BYTES must be bigger than a T."); static if ((T.sizeof * 5) > MAX_BLOCK_BYTES) pragma(msg, "MemoryPool: Block is very small, so probably a MemoryPool isn't useful."); T[(MAX_BLOCK_BYTES / T.sizeof)] items; } static Block*[] blocks; static T* nextFree, lastFree; // a single int that keeps the number of items used // in the last block is enough, but it may lead to a // bit slower code. /// Return pointer to a new item. Allocates memory if necessary. static T* newItem() { if (nextFree >= lastFree) { // then add new block. // this whole new block gets scanned by the GC, // even if you need only 1 item blocks.length = blocks.length + 1; blocks[$-1] = new Block; nextFree = blocks[$-1].items.ptr; lastFree = nextFree + Block.items.length; } return nextFree++; } /// Deallocate all items at once. You can then create new ones. static void freeAll() { foreach (block_ptr; blocks) delete block_ptr; blocks[] = null; blocks.length = 0; nextFree = null; lastFree = null; } // This is like free() but doesn't deallocate memory, just cleans it up so // when you create new items there's no new memory allocation, and it's // faster. But to implement this other static members seem necessary. //static void cleanMemory() { //} } // end of MemoryPool!() unittest { // tests of MemoryPool!() struct BinaryTreeNode { BinaryTreeNode* left, right; int data; string toString() { string nrepr(BinaryTreeNode* n) { return n is null ? "nil" : str(*n); } return "<" ~ str(data) ~ ", " ~ nrepr(left) ~ ", " ~ nrepr(right) ~ ">"; } } MemoryPool!(BinaryTreeNode) BinaryTreeNodePool; auto t = BinaryTreeNodePool.newItem(); t.data = 100; t.left = BinaryTreeNodePool.newItem(); t.left.data = 7; t.right = BinaryTreeNodePool.newItem(); t.right.data = 150; assert(str(*t) == "<100, <7, nil, nil>, <150, nil, nil>>"); } // end tests of MemoryPool!()
Apr 18 2009