Method and Data Structure for Concurrent Bi-Directional Traversal and Manipulation of a Doubly Linked List
Original Publication Date: 2004-Feb-05
Included in the Prior Art Database: 2004-Feb-05
A method is presented to allow iterators to concurrently traverse a doubly linked list in either direction without deadlocking. Each item in the list is protected by its own lock. Two types of iterators are described. Stable iterators hold locks and cannot have data at their current position altered by other iterators, but they can only move forward. Non-stable iterators release locks after each operation and can have data at their current position altered by other iterators, but they allow bi-directional traversal. When the list is modified at or near the current position of a non-stable iterator, the iterator must be adjusted to maintain its correct position and state. Stable iterators can be converted to non-stable iterators and vice versa.