Dr. Dobb's Journal - December 2007 - (Page 54)

d12gran_p5ma 10/16/07 11:18 AM Page 54 Core Technology TRANSACTIONAL PROGRAMMING Trees The tree-based containers (atomic::map and the like) are based upon an implementation of red-black trees (a standard technique for balancing trees). When an item is inserted into the data structure, it is logged on the transaction stack. When an item is deleted, it is removed from the data structure and stored on the transaction stack. Rolling back a deletion is tricky because the object must be inserted in the correct position in the tree. You cannot simply call insert() to insert the node back into the data structure because the comparators might throw, and the nodes might end up in a different order than the original. So the deleted node stores the next node in the data structure. When the deletion is rolled back, the node is reinserted immediately before the next node in the data structure. There are a few cases to consider, but the procedure can be performed reliably. Figure 2 shows how tree operations are rolled back (ignoring tree balancing). With red-back trees, the tree-balancing algorithms must be called after an insertion or a deletion, but these only perform pointer manipulation and will not throw exceptions. Rolling back a deletion is tricky because the object must be inserted in the correct position in the tree Cleanup If the program could be rolled back right to the beginning, no memory would ever be freed and eventually the program would run out of memory. So objects marked for deletion must actually be deleted at some point. This can be done when the outermost transaction has completed. At this point, there is no possibility of roll back. So the entire transaction stack is scanned for deleted objects, which are deleted, and then the transaction stack is resized to 0. If transactions are kept short, then the transaction stack will be small, and deleted objects will not be hanging around for very long. On the other hand, if the entire program is wrapped in a transaction, then the program will never free any memory! Concurrent Access Transactions in different threads should be independent. When one thread throws an exception and rolls back some containers, it should not interfere with another thread 54 Dr. Dobb’s Journal l www.ddj.com l December 2007 http://www.leadtools.com http://www.leadtools.com http://www.leadtools.com http://www.ddj.com

Table of Contents Feed for the Digital Edition of Dr. Dobb's Journal - December 2007

Dr. Dobb's Journal - December 2007 Contents Hmmmm Alia Vox Developer Diaries Developer’s Notebook Computer Books: Reading Between the Lines Conversations Query Anything with SQLite XQuery Web Maps with the Google Map API OpenALM and Its Manifesto Transactional Programming Effective Concurrency The Agile Edge Swaine’s Flames

Dr. Dobb's Journal - December 2007

For optimal viewing of this digital publication, please enable JavaScript and then refresh the page. If you would like to try to load the digital publication without using Flash Player detection, please click here.