LOCK-FREE IMPLEMENTATION OF AN ORDERED SINGLE-WRITER MULTIPLE-READERS DATA STRUCTURE

摘要

A lock-free implementation of an ordered data structure allows updating of the data structure without disturbing the ordering relied upon for accessing the data structure. After searching and finding an element in a data structure in accordance with an update operation (i.e., an insert operation or a remove operation), values are successively copied to shift the values either up or down the data structure. If an insert operation is being performed, then the new value is eventually inserted to overwrite a duplicate value in the data structure. If a delete operation is being performed, then a value is shifted over the value to be deleted.