Thread-safe linked list review I want to implement a thread-safe singly linked list in C. Its nodes contain unique entries and I only need functions to add nodes (to head only), remove nodes and to locate a specific node.

I am reasonably confident of the linked-list logic (any performance tips would be greatly appreciated though), but I am more concerned with my thread-safety logic. This is my first real foray into coding a thread-safe data structure. Is it optimal? Is it overkill? Is there a more performant way to get thread-safety for this data structure?

Thread-safety definitions from header:

#define MY_SPINLOCK_INIT 0
typedef volatile int MYSpinLock;

__attribute__((always_inline))
static inline void MYSpinLockLock(MYSpinLock *lock) {
    while (__sync_lock_test_and_set(lock, 1))
        while (*lock)
            ;
}
__attribute__((always_inline))
static inline void MYSpinLockUnlock(MYSpinLock *lock) {
    __sync_lock_release(lock);
}


Struct definitions:

typedef struct {
    const void *_key;
    uintptr_t _value;
} MYEntry;

typedef struct __MYNode {
    MYEntry _entry;
    struct __MYNode *_next;
} MYNode;

typedef struct {
    MYNode *_head;
    MYSpinLock _lockLL;
} MYLinkedList;


Implementation:

#define MY_LISTLOCK_LOCK MYSpinLock *MY_macro_lock = &amp;(list-&gt;_lockLL); MYSpinLockLock(MY_macro_lock)
#define MY_LISTLOCK_UNLOCK MYSpinLockUnlock(MY_macro_lock)

MYLinkedList *MYLinkedListConstruct() {
    MYLinkedList *list = malloc(sizeof(MYLinkedList));
    list-&gt;_head = NULL;
    list-&gt;_lockLL = MY_SPINLOCK_INIT;
    return list;
}

void MYLinkedListFree(MYLinkedList *list) {
    MY_LISTLOCK_LOCK;

    MYNode *node = list-&gt;_head;
    MYNode *next;
    while (node != NULL) {
        next = node-&gt;_next;
        free(node);
        node = next;
    }

    MY_LISTLOCK_UNLOCK;
    free(list);
}

void MYLinkedListAdd(MYLinkedList *list, MYEntry *entry) {
    MY_LISTLOCK_LOCK;

    MYNode *oldHead = list-&gt;_head;
    MYNode *newHead = malloc(sizeof(MYNode));
    newHead-&gt;_entry = *entry;
    newHead-&gt;_next = oldHead;
    list-&gt;_head = newHead;

    MY_LISTLOCK_UNLOCK;
}

MYBool MYLinkedListRemoveNodeWithEntryKey(MYLinkedList *list, void *keyOfNodeToRemove) {

    if (keyOfNodeToRemove == NULL) return MYFalse;
    MY_LISTLOCK_LOCK;

    MYNode *node = list-&gt;_head;
    MYNode *prev = NULL;
    while (node != NULL) {
        // We found it, break
        if (node-&gt;_entry._key == keyOfNodeToRemove) break;

        prev = node;
        node = node-&gt;_next;
    }

    // We never found it
    if (node == NULL) {
        MY_LISTLOCK_UNLOCK;
        return MYFalse;
    }

    // We found it
    if (prev == NULL) {
        list-&gt;_head = node-&gt;_next;
        free(node);
    }
    else {
        prev-&gt;_next = node-&gt;_next;
        free(node);
    }

    MY_LISTLOCK_UNLOCK;
    return MYTrue;
}

MYNode *MYLinkedListFindNodeWithKey(MYLinkedList *list, void *keyToFind) {

    if (keyToFind == NULL) return NULL;
    MY_LISTLOCK_LOCK;

    MYNode *node = list-&gt;_head;
    while (node != NULL) {
        if (node-&gt;_entry._key == keyToFind) {
            MY_LISTLOCK_UNLOCK;
            return node;
        }
        node = node-&gt;_next;
    }

    MY_LISTLOCK_UNLOCK;
    return NULL;
}
Is there a more performant way to get thread-safety for this data structure?


It all depends on how the list will be used. Just a few examples:


Reads are more common than writes - use separate read/write locks.
Average list is short - use copy-on-write array instead of linked list.
Average list is long - use more efficient search method.
Lots of threads access list - use mutex instead of spinlock to avoid wasted cycles.
Lots of elements is added/removed in bulk - use external lock.


Have you actually measured performance in real world scenarios and identified bottlenecks? It looks like most of it is prematurely optimized.

__attribute__((always_inline))


Is this really necessary? Does it bring any measurable performance gain?

while (__sync_lock_test_and_set(lock, 1))
    while (*lock)


I do not understand this second while loop. Why are you checking the value twice?

#define MY_LISTLOCK_LOCK MYSpinLock *MY_macro_lock = &amp;(list-&gt;_lockLL); MYSpinLockLock(MY_macro_lock)
#define MY_LISTLOCK_UNLOCK MYSpinLockUnlock(MY_macro_lock)


Avoid macros which can be replaced with functions.

MYBool


Use bool from stdbool.h.