Linked-list implementation of a data structure with concurrent non-blocking insert and remove operations

A non-blocking concurrent shared object representation encoded in a computer-readable medium comprising:

• a linked-list of nodes encoding of a group of zero or more values;
• and
• linearizable operations defined to implement semantics of at least insert and remove operations on the group, wherein concurrent execution of the linearizable operations is mediated using a first synchronization primitive to encode a marked node indication signifying logical deletion of a corresponding one of the values from the group, wherein the first synchronization primitive atomically examines and updates a single target, the updating being conditional on the examination,
• wherein successful completion of an insertion into the group requires, at most, one atomic update of the concurrent shared object;
• wherein successful completion of a deletion from the group requires, at most, two atomic updates of the concurrent shared object;
• and
• wherein mere traversal of the concurrent shared object is without atomic update of the concurrent shared object.

A method of managing access to a linked-list of nodes susceptible to concurrent operations on a group encoded therein, the method comprising:

• separating deletion of a value from the group into at least two functional sequences;
• the first functional sequence performing a logical deletion of the value using a synchronization primitive to mark a corresponding one of the nodes;
• and
• the second functional sequence excising the marked node from the linked-list,
• wherein the synchronization primitive atomically examines and updates a single target, the updating being conditional on the examination.

A computer program product encoded in at least one computer readable medium, the computer program product comprising:

• at least two functional sequences providing non-blocking access to a concurrent shared object, the concurrent shared object instantiable as a linked-list of nodes encoding of a group of zero or more values;
• a first of the functional sequences defined to implement semantics of an insert operation on the group;
• and
• a second of the functional sequences defined to implement semantics of a remove operation on the group,
• wherein instances of the functional sequences are linearizable and concurrent execution thereof by plural processors of a multiprocessor is mediated using a synchronization primitive to encode a marked node indication signifying logical deletion of a corresponding one of the values from the group with separate physical excision of the corresponding node, wherein the synchronization primitive atomically examines and updates a single target, the updating being conditional on the examination.

An apparatus comprising:

• plural processors;
• one or more data stores addressable by each of the plural processors;
• means for coordinating concurrent execution, by ones of the plural processors, of at least insert and remove operations on a group of zero or more values encoded in the one or more data stores, the coordinating employing a first synchronization primitive to encode an indication signifying logical deletion of a corresponding one of the values from the group and a second synchronization primitive to physically excise the node corresponding to the logically deleted value, wherein the synchronization primitives atomically examine and update their respective single targets, the updating being conditional on the examination;
• and
• means for traversing the encoded group without use of an atomic operation.