Channels ▼


Transactional Programming


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
 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.

Related Reading

More Insights

Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.