这是一个我自己发明的无锁链表实现
特点是多写一读情况下， 不考虑 CPU 指令的本身实现， 则是 O(1) 的， 没有任何循环


#ifndef lkf_h
#define lkf_h

typedef struct lkf_node {
    struct lkf_node* next;
} lkf_node;

typedef struct lkf_list {
    struct lkf_node root;
    struct lkf_node** tail;
} lkf_list;


#define LKF_INIT(name) {.root = {NULL}, .tail = &(name.root.next)}
#define LKF_LIST(name) \
struct lkf_list name = LKF_INIT(name)

#define INIT_LKF(name) \
do { \
    typeof(name) lkf = name; \
    lkf->root.next = NULL; \
    lkf->tail = &(lkf->root.next); \
} while (0)

static inline void lkf_node_put(struct lkf_list* list, struct lkf_node* node)
{
    node->next = NULL;
    struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
    *ptr = node;
}

static inline struct lkf_node* lkf_node_get_one(struct lkf_list* list)
{
    struct lkf_node* head = __sync_lock_test_and_set(&(list->root.next), NULL);
    if (head == NULL) {
        return NULL;
    }

    struct lkf_node* next = head->next;
    if (next != NULL) {
        list->root.next = next;
        head->next = head;
        return head;
    }

    int b = __sync_bool_compare_and_swap(&(list->tail), &(head->next), &(list->root.next));
    if (b) {
        head->next = head;
        return head;
    }

    list->root.next = head;
    return NULL;
}

static inline struct lkf_node* lkf_node_get(struct lkf_list* list)
{
    struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
    if (ptr == NULL) {
        return NULL;
    }

    struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
    *last = ptr;
    return *last;
}

static inline struct lkf_node* lkf_node_next(struct lkf_node* node)
{
    struct lkf_node* ptr = node->next;
    if (ptr == NULL || ptr->next == NULL) {
        return NULL;
    }

    if (ptr == node) {
        return ptr;
    }

    node->next = ptr->next;
    ptr->next = NULL;
    return ptr;
}

#ifdef __linux__
#include <linux/futex.h>
#include <syscall.h>

static inline void lkf_node_put_wake(struct lkf_list* list, struct lkf_node* node)
{
    node->next = NULL;
    struct lkf_node** ptr = __sync_lock_test_and_set(&(list->tail), &(node->next));
    if (ptr == &list->root.next) {
        while (-1 == syscall(__NR_futex, ptr, FUTEX_WAKE, 1, NULL, NULL, 0));
    }
    *ptr = node;
}

static inline struct lkf_node* lkf_node_get_wait(struct lkf_list* list)
{
    struct lkf_node* ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
    while (ptr == NULL) {
        syscall(__NR_futex, &list->root.next, FUTEX_WAIT, NULL, NULL, NULL, 0);
        ptr = __sync_lock_test_and_set(&(list->root.next), NULL);
    };

    struct lkf_node** last = __sync_lock_test_and_set(&(list->tail), &(list->root.next));
    *last = ptr;
    return *last;
}
#endif

#if 1
typedef struct proc_context {
    struct lkf_list list;
    int stat;
} proc_context;

static int proc_enter(struct proc_context* ctx, struct lkf_node* node)
{
    lkf_node_put(&ctx->list, node);
    int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
    if (n == 0) {
        return -1;
    }
    return 0;
}

static int proc_leave(struct proc_context* ctx)
{
    ctx->stat = 0;
    __sync_synchronize();
    if (ctx->list.tail == &ctx->list.root.next) {
        return 0;
    }

    int n = __sync_bool_compare_and_swap(&ctx->stat, 0, 1);
    if (n == 0) {
        return 0;
    }
    return -1;
}
#endif

#endif

【 在 zylthinking2 的大作中提到: 】
: 值不值一个360 T7级别
: 真是心寒了
: 难道 43 岁就真的要窝窝囊囊被人欺负？
: ...................
--
FROM 220.181.41.*