Ordered doubly-linked lock-free list

I'm implementing a lock-free ordered doubly-linked list based on heavily modified paper entitled Split-Ordered Lists: Lock-Free Extensible Hash Tables by ORI SHALEV. My main concern is correctness of algorithm, secondly performance.

Is the algorithm used in the code really lock-free? How can I improve the code?

```
typedef __uint64_t uint64_t;
typedef uintptr_t node_ptr_t;
#define PTR_OF(x) ((Node*)(x))
#define CONSTRUCT(ptr) ((uintptr_t)ptr)
#define CAS(ADDR, OLDV, NEWV) __sync_val_compare_and_swap((ADDR), (OLDV), (NEWV))
#define INCR(ADDR, INCVAL) __sync_fetch_and_add((ADDR), (INCVAL))

typedef struct
{
int mark;
void *value;
uint64_t key;
node_ptr_t prev, next;
} Node;

typedef struct
{
node_ptr_t bucket;
uint32_t size;
} LF_List;

void lf_list_find(LF_List list, node_ptr_t head, uint64_t key, node_ptr_t** prev, node_ptr_t cur, node_ptr_t* last)
{
node_ptr_t* tp_prev;
node_ptr_t tp_cur, tp_last;
node_ptr_t* tp_next;

uint64_t cur_key;
void* cur_value;

while(1)
{
tp_prev = head;
tp_cur = *head;
tp_last = (node_ptr_t)NULL;

while(1)
{
if (PTR_OF(tp_cur) == NULL)
{
if(prev){*prev = tp_prev;};
if(cur){*cur = tp_cur;};
if(last){*last = tp_last;};

return NULL;
}

tp_next = &PTR_OF(tp_cur)->next;

cur_key = PTR_OF(tp_cur)->key;
cur_value = PTR_OF(tp_cur)->value;

if(*tp_prev != tp_cur)
{
break;
}

if (PTR_OF(tp_cur)->mark == 1)
{

if (PTR_OF(*tp_next) != NULL)
{
if (CAS(&PTR_OF(*tp_next)->prev, tp_cur, tp_last) != tp_cur)
{
continue;

Still not safe

I haven't run the new code yet but I can already theorize at least one possible flaw. Suppose you have the following list:

4 -> 3 -> 2 -> 1

Then suppose element 2 is deleted:

4 -> 3 -> 2 -> 1 ( = marked for deletion)

Now thread 1 iterates across the list and stops at element 2, and is about to delete it. Meanwhile, element 3 is deleted:

4 -> 3 -> 2 -> 1

Thread 2 iterates across the list and stops at element 3. Now you have two threads both trying to delete separate elements at the same time. One is trying to make 4 point to 2. The other is trying to make 3 point to 1. All sorts of bad things can happen. I'm even leaving out the part where the list is now doubly linked with prev pointers.

The reason that the research paper algorithm works is because the mark is stored within the next pointer. That way, the CAS will fail if it tries to change the pointer with the wrong mark on it. With your program, the mark is stored separately from the next pointer. Therefore, you can't atomically change both the mark and the pointer.

StackExchange Code Review Q#92598, answer score: 6