添加到無鎖列表的尾部

Question

我使用的是在llist.h中定義的Linux內核的無鎖列表。 llist_add將添加到列表中，但它會在頭後添加新節點。我如何在常量時間內添加到列表尾部？

Answer 1

如何在常量時間內添加到列表尾部？

你不行。

llist的無鎖屬性以降低功能爲代價：只支持開始時刪除第一個元素和刪除所有元素。並且即使這種減少也不足以使其無鎖始終爲，請參閱標頭inclide/linux/llist.h開頭的說明。

其實，一些物體的無鎖屬性很少是。在大多數情況下，自旋鎖的使用是可以接受的。如果是你的情況，而不是無鎖llist，你可以使用雙鏈表list_head，受自旋鎖保護。雙鏈表存儲指向最後一個元素的指針並支持其後的添加（功能list_add_tail）。