Implementation
The implementation of the Atomic Library is based around a central stack—a transaction stack—that logs each operation. Whenever an atomic container is modified, it pushes a record of the operation onto the stack.
Each operation is recorded in the struct:
struct Transaction
{
atomic::container* container;
object_pointer node;
enum { insertion, deletion } event;
};
When a transaction is entered, the constructor of atomic::transaction stores the initial size of the transaction stack. When a transaction exits, the destructor of atomic::transaction can roll back all operations (in reverse order) to the initial size of the transaction stack. The transaction::commit() method sets a flag in the transaction telling it not to roll back.
There are just two types of atomic operations—insert and delete. Other operations can be composed of insertions or deletions.
All atomic containers derive from atomic::container:
class container
{
public:
virtual ~container();
virtual void destroy(object_pointer)=0;
virtual void unlink(object_pointer)=0;
virtual void relink(object_pointer)=0;
};
When an item is inserted into a container, it logs an insertion, a pointer to the container, and a pointer to the inserted object on the transaction stack.
When an item is deleted from a container, it logs a deletion, a pointer to the container, and a pointer to the deleted object on the transaction stack. The object is not destroyed at this point in case it needs to be inserted back into the container.
Rolling Back
Rolling back is performed differently on different containers. But what is extremely important is that rolling back must not fail. Fortunately, this turns out to be possible, even for tree-based containers such as atomic::set, atomic::map, atomic::multiset, and atomic::multimap.
When an insertion is rolled back, the unlink() function is called on the container to remove the item from the data structure, and destroy() is called to delete the object.
When a deletion is rolled back, the relink() function is called on the container to insert the item back into the data structure. The deleted item must contain a hint where the item should be inserted.
