Method for efficient implementation of dynamic lock-free data structures with safe memory reclamation

Abstract

A method for safe memory reclamation for dynamic lock-free data structures employs a plurality of shared pointers, called hazard pointers, that are associated with each participating thread. Hazard pointers either have null values or point to nodes that may potentially be accessed by a thread without further verification of the validity of the local references used in their access. Each hazard pointer can be written only by its associated thread, but can be read by all threads. The method requires target lock-free algorithms to guarantee that no thread can access a dynamic node at a time when it is possibly unsafe (i.e., removed from the data structure), unless one or more of its associated hazard pointers has been pointing to the node continuously, from a time when it was not removed.

Dependencies are inferred from the claim text.