The code below represents a lock-free ordered single-linked list, and is a modification of the algorithm proposed in this doc.
How can I improve speed of searching (lookingup) in the list maintaining lock-free capability? Any suggestions, code modifications, examples, maybe other lock-free data structures?
typedef uintptr_t marked_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
{
void *value;
uint64_t key;
marked_ptr_t next;
} Node;
typedef struct
{
marked_ptr_t bucket;
uint32_t size;
} LF_List;
void *lf_list_get(LF_List*, uint64_t);
void *lf_list_put_if_absent(LF_List*, uint64_t, void*);
int lf_list_remove(LF_List*, uint64_t);
void* lf_list_find(marked_ptr_t* head, uint64_t key, marked_ptr_t** prev, marked_ptr_t* cur, marked_ptr_t* last)
{
marked_ptr_t* tp_prev;
marked_ptr_t tp_cur, tp_last;
marked_ptr_t* tp_next;
uint64_t cur_key;
void* cur_value;
tp_prev = head;
tp_cur = *head;
tp_last = (marked_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 (key >= cur_key)
{
if(prev){*prev = tp_prev;};
if(cur){*cur = tp_cur;};
if(last){*last = tp_last;};
return key == cur_key ? cur_value : NULL;
}
tp_last = tp_cur;
tp_prev = tp_next;
tp_cur = *tp_next;
}
}
void* lf_list_get(LF_List* table, uint64_t key)
{
return lf_list_find(&table->bucket, key, NULL, NULL, NULL);
}
void* lf_list_put_if_absent(LF_List* table, uint64_t key, void* value)
{
marked_ptr_t* prev;
marked_ptr_t cur, last;
marked_ptr_t new_node;
while(1)
{
if(lf_list_find(&table->bucket, key, &prev, &cur, &last) != NULL)
{
return PTR_OF(cur)->value;
}
new_node = CONSTRUCT(calloc(1, sizeof(Node)));
PTR_OF(new_node)->value = value;
PTR_OF(new_node)->key = key;
PTR_OF(new_node)->next = *prev;
if(CAS(prev, cur, new_node) == cur)
{
INCR(&table->size, 1);
break;
} else {
free(PTR_OF(new_node));
continue;
}
}
return NULL;
}
int lf_list_remove(LF_List* table, uint64_t key)
{
marked_ptr_t cur, last;
marked_ptr_t *prev;
while(1)
{
if(lf_list_find(&table->bucket, key, &prev, &cur, &last) == NULL)
{
return 0;
}
if (CAS(prev, cur, PTR_OF(cur)->next) == cur) {
free(PTR_OF(cur));
INCR(&table->size, -1);
return 1;
} else {
continue;
}
}
return 0;
}
lf_list_find()
? Have you tested this code? Because from just a casual inspection, it doesn't look like it works. \$\endgroup\$