This class stores a pointer to a single value, allocated via an allocator. When the object is reassigned, the previous object is stored in the operation stack via a call to log_delete(). When the object is rolled back, value::relink() deletes the current value and inserts the previous value back into the object. When the operation stack is cleaned up, the call to value::destroy() erases previous values.

There is a specialization for integers. In this case the integer is stored within the object itself, and the previous value is stored on the operation stack. relink() assigns the value back to the previous value stored as the pointer. destroy() does nothing.

atomic::list

This is implemented as a standard doubly-linked list with the following differences:

• The list inherits from atomic::container.
• When a node is created, a call to log_insert() pushes the node onto the operation stack
• When a node is removed, a call to log_delete() pushes the node onto the operation stack.
• The destroy() method deletes a node.
• The unlink() method removes the node from the list
• The relink() method inserts the node back into the list in its original position.
• The reference type is const for non-atomic values.
• There is no swap().

atomic::vector

Atomic vectors are store an array of values. The differences to std::vector are

• The methods erase(), pop_back(), push_front(), resize(), operator=(), clear(), swap() are not provided.
• The reference type is const for non-atomic values.
• The vector inherits from atomic::container.
• When items are pushed back, the log_insert() method is called with the original size.
• When items are rolled back, the unlink() method resizes the stack back to its previous size.

atomic::map, atomic::set, atomic::multimap, atomic::multiset

These containers are all implemented around the same red-black tree implementation. The tree implementation has been modified by

• Inheriting from atomic::container.
• Changing the reference type to const for non-atomic values. This means that the "m[k]=v" operation will not work in these cases.
• When nodes are inserted, they are recorded on the transaction stack via log_insert()
• When nodes are removed, they are stored on the transaction stack via log_delete(). The "next" node in the tree is stored in the node.
• When an insert is rolled back, the unlink() method removes the node from the tree.
• When a delete is rolled back, the relink() method inserts the node immediately before the "next" node as stored in the removed node. This involves a little tree walking but is O(1) on average.
• There is no swap().

Composite operations like operator=() can be implemented in terms of simpler insertions and deletions.

atomic::shared_ptr

See the TR1 documentation.

atomic::weak_ptr

See the TR1 documentation.

Thread safety

Transactions must be strictly nested to work on a single transaction stack. Therefore having transactions running in different threads will not work.

The simplest solution - which Atomic plans to implement - is for the transactions to lock the transaction stack for the duration of the transaction. So not only do transactions provide atomicity - they also provide thread safety ("isolation") as well! 

The other solution is to implement the transaction stack on thread-local storage.  While not as safe, it means that transactions can be run concurrently.