Tree-like structure supporting multi-reader snapshot iteration with partial support for multiple writers. Stored records must be copy constructible and comparable.
Note: After some consideration, I've decided to work on a snapshot vector/deque implementation before returning to this project.
In the main thread:
- Create a SnapshotTree object.
- Start a number of worker threads each receiving a reference to the tree object.
- Wait for threads to complete.
In the worker threads:
- Obtain a handle for tree object access. Handles are read or write. Read handles open snapshots on the data which can be used to view the state of the tree at the time the handle was created indefinitely. Write handles can be used to read records but do not create a consistent snapshot and incur locking overhead.
- Access the tree ( either read or write ops )
- Leave the scope in which the handle object exists in. This is important for reclamation of resources used in read snaphsots and tree structure optimization operations.
There are a fixed number of handles which can be active at any time. This is a configurable parameter but ideally there should not be more than a handful of handles open per thread at any time.
Update and remove are the supported write operations. Find and iteration are supported for the read ops.
Immutability is an important property of the implementation. The idea is to use a list structure to store updates in when they are first made and to gradually incorporate data from the list structure into a sorted set like structure.
The implementation is heavily dependent on c++1y features. The arena allocator from the ArenaAlloc project ( see Kubiyak/ArenaAlloc on github ) is used for memory allocation. For convenience a recent version of arenaalloc.h from ArenaAlloc is included in this project.