We present a lock-free algorithm for a red-black tree that supports concurrent search and modify (insert and delete) operations, using only single-word atomic instructions. Our algorithm uses the atomic compare-and-swap (CAS) and set-bit (SB) instructions, both of which are widely supported by modern processors. To our knowledge, ours is the first lock-free red-black tree that can be directly implemented on hardware, without assuming any underlying system support such as transactional memory.
展开▼
