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

d12gran_p5ma 10/15/07 11:31 AM Page 53 virtual virtual virtual virtual }; ~container(); void destroy(object_pointer)=0; void unlink(object_pointer)=0; void relink(object_pointer)=0; 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. 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. Lists atomic::list is implemented as a doubly linked list of nodes, just like std::list would be implemented. When an item is inserted into the list, the node containing the item is logged on the transaction stack. When an item is deleted, it is removed from the data structure and stored on the transaction stack. To roll back a delete, the left and right pointers point to live nodes, giving the correct place in the list to insert the node. There is no possibility of an exception being thrown because roll back only requires pointer manipulation, not any memory allocation. To roll back an insertion, the list node is removed and deleted (which will not throw). Figure 1 shows how list operations can be rolled back. (a) {1,2,3} 1 2 3 top (b) Transaction stack insertion {4,1,2,3} 4 1 2 3 top (c) Transaction stack insertion deletion {4,1,2} 3 4 1 2 Accelerate up to x20: Visual Studio builds Make-Based Builds Data Builds R&D Scripts Custom Applications IncrediBuild is an easy-to-use platform for accelerating Windowsbased processes using advanced Grid Computing technology technology. top (d) Transaction stack insertion {4,1,2,3} 4 1 2 3 (e) {1,2,3} 1 2 3 Download FREE, fully-functional 30-day trial: Figure 1: Operations on atomic::list : (a) Initial list; (b) list after push_front(4); (c) list after pop_back(); (d) list after rolling back step (c); (e) the list after rolling back step (b). http://www.xoreax.com December 2007 l www.ddj.com l Dr. Dobb’s Journal 53 http://www.xoreax.com http://www.xoreax.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.