Trie structure, lock-free inserting

Question

I tried to implement lock free Trie structure, but I am stuck on inserting nodes. At first I believed it was easy (my trie structure would not have any delete methods) but even swapping one pointer atomically can be tricky. I want to swap pointer to point to structure(TrieNode) atomically only when it was nullptr so as to be sure that I do not lose other nods that other thread could insert inbetween.

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;

With this code I get exit code -1073741819 (0xC0000005).

EDIT: Thank you for all your coments. Maybe I did not specify my problem so I want to address it now.After around 10 hours of coding last day I changed few things. Now I use ordinarry pointers and for now it is working. I did not test it for now if its race free with multiple threads inserting words. I plan to do it today.

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

Now I believe it will work with many threads inserting different words . And yes, in this solution I discard node if there next pointer is not null. Sorry for the trouble (I am not native speaker).

Answer 1

CAS pattern should be something like:

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

if you aren't paying attention to the return value/expected and testing that you are replacing null, stored locally, you are in trouble.

On failure, you need to throw away the new node you made.