多线程读写无锁链表： 之前有没有相同的实现？ (更新)

windoze

回复 30# zylthinking

39行是常量么？没发现……
另外，39行的list->root.next和40行的head->next没看出有什么依赖关系，但我觉得如果调换次序就会出问题了。

zylthinking

回复 31# windoze

好吧， 19行是常量
   

zylthinking

windoze 发表于 2013-10-29 23:16
回复 30# zylthinking

39行是常量么？没发现……

乱序了怎么会出问题？
    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;
    }

依赖 1.
        list->root.next = next;
        head->next = head;
依赖 next != NULL

依赖 2.
list->root.next 依赖一开始的 struct lkf_node* next = head->next; 而不是  head->next = head; 赋值后的  head->next

若你说依赖2 不存在， 那么int i = 8; int k = i; i = 9 你猜 k 最终的值是哪个？

windoze

回复 33# zylthinking

38行的if检查“head->next”，然后if里面我又看到了list->root.next…………
我没仔细的看你的代码…………最讨厌看这种lock free的东西…………每次都要在纸上画半天各种顺序依赖…………
懒得猜了……谁知道有没有问题……

liuiang

，大神给大神review代码，学习了，其实是来顶楼主的。

mmqmjy

一个小bug，考虑下面的调用序列：

链表list已经插入一个节点nodeA，链表状态
list->root.next = nodeA;
nodeA->next = NULL;
list->tail = &nodeA->next;

这时调用put插入节点nodeB，只执行了第一条语句，链表的状态
list->root.next = nodeA;
nodeA->next = NULL;
nodeB->next = NULL;
list->tail = &nodeB->next;
put的最后一句*ptr = node(即nodeA->next = nodeB)还未执行，线程被挂起

这时另一个线程执行get，原链表恢复初始状态，并得到链表nodeB
nodeB->next = nodeA;
nodeA->next = NULL;
得到的新链表不完整，通过next去遍历nodeB只会返回nodeA节点，nodeB丢掉了？
而且，通过next取出nodeA使用完并释放掉内存后，前面挂起的put线程恢复后再执行最后一句就访问到了己释放的内存

PS：put应该要将node->next初始化为NULL吧，反而next最后的ptr->next = NULL有点多余

zylthinking

mmqmjy 发表于 2013-11-03 12:27
一个小bug，考虑下面的调用序列：

链表list已经插入一个节点nodeA，链表状态

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;
}

提供这个函数的目的就是为了避免调用者掉入你所说的那个坑里面， 标红部分保证了你所说的情况发生的话， 直接返回 null; 但这并不是链表循环的结束

mmqmjy

没看到你前面的例子，以为next返回null就结束了
不太符合使用习惯，稍微改一下接口就更完美了

让调用者重试确实是一个很好的替代方案
强求lock-free没必要而且实在太复杂

感谢楼主分享，赞一个

zylthinking

我去， 更新完毕居然不上浮， 人工置顶