I want to implement a sparse tree in C++, using a vector; and by using the COW features of Linux, to minimize the number of physical page frames actually held.
See http://en.wikipedia.org/wiki/Copy_on_write
Since the tree is sparse, some large number of pages will be initialized to zero and never written to since only a few of the array cells are used. But under linux COW, pages allocated in the VM are never actually allocated as physical pages until a write occurs on the page in question.
Compare this with a Unix file w/ "holes" in it.
So the array may have a VM usage of 10**8 pages but only 10**4 page frames ever are allocated.
I know I can use this linux feature to implement a sparse array in C.
I am not so sure about C++.
Can anyone tell me if there is a way to achieve the same transparent allocations in C++?
P.S.
For whom it may concern:
IMPLEMENTATION DETAILS
The structs actually stored in the vector looks like this:
struct foo
{
long int payload[15]
char flags;
string label;
}
The root of the tree will have offset 0 in the array, and will be labeled "1".
Subtracting one from a label give the physical index of the corresponding array cell. Hence node 1 is stored at index 0, node 10 is stored at index 1, node 11 is stored at index 2, etc.
The address of the left child of some node labeled "X" is derived by shifting X << 1. Hence the left child of node 1 is labeled "10".
The address of the right child of some node labeled "X" is derived by shifting X << 1 and adding 1 . Hence the right child of node 1 is labeled "11".
The parent of some node "X" is derived by right shifting X >> 1. Hence the of the parent of node 10 is labeled "1".
All these operations are invariant throughout, and also reversible.
The flags variable of struct foo can be used to indicate status, as for example, if a node has any children and if so, how many.
Left shifts are zero filled on the right; right shifts are zero-filled on the left.