BTW - I think a found a race condition that causes find to incorrectly return false. Consider the following scenario:
Thread A removes an entry with key k1 which is stored directly in the cell. The cell's head points to an add_item with key k2, so thread A first updates the cell's state to reflect that the item that contained k1 is now invalid, then it copies key and value from the add_item into the item where k1 used to be, then updates the cell's state again to reflect that the item is now again valid before removing the add_item from the linked list. Now thread B is concurrently calling find with k2. It could happen that thread B finds k2 in the item marked as invalid. Now assume that the reload of the cell's state is executed before the update by thread A that restores the bit to mark the item as valid, i.e., the reload returns the same value. Then thread B would (incorrectly) assume that k2 is currently getting removed and return false. IMHO instead of returning early, find has to ignore items marked as invalid and continue the search. If the find is faster than the remove, we would find the matching add_item; if the remove is faster, the find would encounter an updated state and restart. What do you think? -- --- You received this message because you are subscribed to the Google Groups "Scalable Synchronization Algorithms" group. To unsubscribe from this group and stop receiving emails from it, send an email to lock-free+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/lock-free/b5a981db-322f-43dd-8ee5-2f09acc0c0a9%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
