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)。

编辑：感谢您的所有评论。也许我没有说明我的问题，所以我想解决它 now.After 昨天大约 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

CAS 模式应该是这样的：

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

如果您不注意 return value/expected 并测试您正在替换本地存储的 null，那您就有麻烦了。

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

Trie结构，无锁插入

Trie structure, lock-free inserting

c++

atomic

trie

lock-free

stdatomic