The implementation is based around a transaction stack that records each change to a container. Each change is recorded in a struct

struct Transaction

{

    TransactionalContainer *container;

    void *object;

    enum Action { created, deleted, none } action;

};

When a container adds an item, it calls the function log_insert(), which pushes an operation onto the transaction- stack, with action=created, container=the container holding the item, and object=the node of the item being inserted.

When a container removes an item, it calls log_delete(), which pushes an operation onto the transaction-stack, with action=deleted, container=the container containing the item, and object=the node that was deleted. The deleted item is not actually deleted at this point in case it needs to be reinserted back into the container on roll-back. The container makes sure that the deleted object holds enough context to be inserted back into the container in the right position if need be.

Containers inherit from the atomic::container class:

class container

{

public:

    virtual ~container();

    virtual void destroy(void*)=0;

    virtual void unlink(void*)=0;

    virtual void relink(void*)=0;

};

When an insertion operation is rolled back, the transaction manager calls container->unlink() to remove the item from the container, and then container->destroy() to destroy the object.

When a deletion operation is rolled back, the transaction manager calls container->relink() which inserts the item back into the container.

When the outermost transaction has been finished, the transaction stack can be emptied. This scans the transaction stack, and calls container->destroy() for all delete operations. Containers can no longer be rolled back after a cleanup has occurred.

Cleanup means that objects are not kept for longer than necessary, and that the memory used by deleted items is deallocated so that the program will not run out of memory. In fact if transactions are short, there is very little memory overhead at all.