Concurrent data structures and actor programming under the Matroshka model
Lawrence A. Crowl · 1988
the list and return the previous state of the history. An object represents the head of the list and addition operations apply to the object. Operations reside on the history list as element records containing a next pointer. Clients have concurrent access to the list because operations under the Matroshka model proceed concurrently unless explicitly synchronized. This algorithm relies on synchronization by a wait-free atomic swap operation on primitive reference objects. This operation swaps the reference's value with another reference indicated by the parameter. This is a fair implementation since the literature [3] commonly assumes these primitive objects and operations. object history head: reference element := nil operation addtohistory( newelem: reference element ): reference element newelem.next := newelem -- to link in self -- swap head and newelem.next head.atomicswap( reference to newelem.next ) -- now head = newelem and newelem.next = old value of head return newelem.n