Trie结构，免锁插入

Question

我试图实现无锁的Trie结构，但我一直在插入节点。起初，我认为这很容易(我的trie结构不会有任何删除方法(，但即使是原子交换一个指针也可能很棘手。我只想在指针为nullptr时原子性地交换指向结构(TrieNode(的指针，以确保我不会丢失其他线程可以插入其中的其他点。

struct TrieNode{
int t =0;
std::shared_ptr<TrieNode> child{nullptr};
};
std::shared_ptr<TrieNode> root;
auto p = std::atomic_load(&root);
auto node =  std::make_shared<TrieNode>();
node->t=1;

auto tmp = std::shared_ptr<TrieNode>{nullptr};
std::cout<<std::atomic_compare_exchange_strong( &(p->child), &tmp,node)<<std::endl;
std::cout<<node->t;

有了这个代码，我得到了退出代码-1073741819(0xC0000005(。

编辑：谢谢你的光临。也许我没有具体说明我的问题，所以我想现在就解决它。经过大约10个小时的编码，我改变了一些事情。现在我使用普通指针，目前它正在工作。我现在没有测试它是否有多个线程插入单词的种族自由。我计划今天做。

const int ALPHABET_SIZE =4;
enum  Alphabet {A,T,G,C,END};
class LFTrie{
private:
struct TrieNode{
std::atomic<TrieNode*> children[ALPHABET_SIZE+1];
};
std::atomic<TrieNode*> root = new TrieNode();
public:
void Insert(std::string word){
auto p =root.load();
int index;
for(int i=0; i<=word.size();i++){
if(i==word.size())
index = END;
else
index = WhatIndex(word[i]);
auto expected = p->children[index].load();
if(!expected){
auto node = new TrieNode();
if(! p->children[index].compare_exchange_strong(expected,node))
delete node;
}
p = p->children[index];
}
}
};

现在我相信它将与插入不同单词的许多线程一起工作。是的，在这个解决方案中，如果下一个指针不为空，我将丢弃节点。很抱歉给您带来麻烦(我不是母语人士(。

Answer 1

neneneba CAS模式应该类似于：

auto expected = p->child;
while( !expected ){
if (success at CAS(&p->child, &expected, make_null_replace() ))
break;
}

如果您不注意返回值/期望值，并且测试您正在替换本地存储的null，那么您就有麻烦了。

一旦失败，您需要丢弃您创建的新节点。