diff --git a/src/radix.h b/src/radix.h --- a/src/radix.h +++ b/src/radix.h @@ -52,8 +52,52 @@ RadixTree() : root(RadixElement()) {} ~RadixTree() { root.load().release(); } - RadixTree(const RadixTree &) = delete; - RadixTree &operator=(const RadixTree &) = delete; + /** + * Copy semantic. + */ + RadixTree(const RadixTree &src) : RadixTree() { + { + RCULock lock; + RadixElement e = src.root.load(); + e.acquire(); + root = e; + } + + // Make sure we the writes in the tree are behind us so + // this copy won't mutate behind our back. + RCULock::synchronize(); + } + + RadixTree &operator=(const RadixTree &rhs) { + { + RCULock lock; + RadixElement e = rhs.root.load(); + e.acquire(); + root.load().release(); + root = e; + } + + // Make sure we the writes in the tree are behind us so + // this copy won't mutate behind our back. + RCULock::synchronize(); + + return *this; + } + + /** + * Move semantic. + */ + RadixTree(RadixTree &&src) : RadixTree() { *this = std::move(src); } + RadixTree &operator=(RadixTree &&rhs) { + { + RCULock lock; + RadixElement e = rhs.root.load(); + rhs.root = root.load(); + root = e; + } + + return *this; + } /** * Insert a value into the tree. @@ -93,6 +137,34 @@ return RCUPtr::acquire(ptr); } +#define SEEK_LEAF_LOOP() \ + RadixElement e = eptr->load(); \ + \ + /* Walk down the tree until we find a leaf for our node. */ \ + do { \ + while (e.isNode()) { \ + Node: \ + auto nptr = e.getNode(); \ + if (!nptr->isShared()) { \ + eptr = nptr->get(level--, key); \ + e = eptr->load(); \ + continue; \ + } \ + \ + auto copy = std::make_unique(*nptr); \ + if (!eptr->compare_exchange_strong(e, RadixElement(copy.get()))) { \ + /* We failed to insert our subtree, just try again. */ \ + continue; \ + } \ + \ + /* We have a subtree, resume normal operations from there. */ \ + e.release(); \ + eptr = copy->get(level--, key); \ + e = eptr->load(); \ + copy.release(); \ + } \ + } while (0) + /** * Remove an element from the tree. * Returns the removed element, or nullptr if there isn't one. @@ -103,14 +175,7 @@ RCULock lock; std::atomic *eptr = &root; - RadixElement e = eptr->load(); - - // Walk down the tree until we find a leaf for our node. - while (e.isNode()) { - Node: - eptr = e.getNode()->get(level--, key); - e = eptr->load(); - } + SEEK_LEAF_LOOP(); T *leaf = e.getLeaf(); if (leaf == nullptr || leaf->getId() != key) { @@ -140,14 +205,7 @@ std::atomic *eptr = &root; while (true) { - RadixElement e = eptr->load(); - - // Walk down the tree until we find a leaf for our node. - while (e.isNode()) { - Node: - eptr = e.getNode()->get(level--, key); - e = eptr->load(); - } + SEEK_LEAF_LOOP(); // If the slot is empty, try to insert right there. if (e.getLeaf() == nullptr) { @@ -183,6 +241,8 @@ } } +#undef SEEK_LEAF_LOOP + struct RadixElement { private: union { @@ -205,6 +265,14 @@ * RadixElement is designed to be a dumb wrapper. This allows any * container to release what is held by the RadixElement. */ + void acquire() { + if (isNode()) { + RCUPtr::copy(getNode()).release(); + } else { + RCUPtr::copy(getLeaf()).release(); + } + } + void release() { if (isNode()) { RadixNode *ptr = getNode(); @@ -268,12 +336,21 @@ } } - RadixNode(const RadixNode &) = delete; + RadixNode(const RadixNode &rhs) : non_atomic_children_DO_NOT_USE() { + for (size_t i = 0; i < CHILD_PER_LEVEL; i++) { + auto e = rhs.children[i].load(); + e.acquire(); + non_atomic_children_DO_NOT_USE[i] = e; + } + } + RadixNode &operator=(const RadixNode &) = delete; std::atomic *get(uint32_t level, const K &key) { return &children[(key >> (level * BITS)) & MASK]; } + + bool isShared() const { return refcount > 0; } }; // Make sure the alignment works for T and RadixElement. diff --git a/src/test/radix_tests.cpp b/src/test/radix_tests.cpp --- a/src/test/radix_tests.cpp +++ b/src/test/radix_tests.cpp @@ -307,6 +307,80 @@ CheckConstTree(mytree, false); } +BOOST_AUTO_TEST_CASE(test_cow) { + using E = TestElement; + + RadixTree mytree; + + BOOST_CHECK(mytree.insert(RCUPtr::make(0))); + BOOST_CHECK(mytree.insert(RCUPtr::make(1))); + BOOST_CHECK(mytree.insert(RCUPtr::make(2))); + BOOST_CHECK(mytree.insert(RCUPtr::make(3))); + + RadixTree copyTree = mytree; + + // The copy tree is identical. + BOOST_CHECK(copyTree.get(0)); + BOOST_CHECK(copyTree.get(1)); + BOOST_CHECK(copyTree.get(2)); + BOOST_CHECK(copyTree.get(3)); + + BOOST_CHECK(mytree.insert(RCUPtr::make(90))); + BOOST_CHECK(mytree.insert(RCUPtr::make(91))); + BOOST_CHECK(mytree.insert(RCUPtr::make(92))); + BOOST_CHECK(mytree.insert(RCUPtr::make(93))); + + // The copy was unaffected. + BOOST_CHECK(copyTree.get(0)); + BOOST_CHECK(copyTree.get(1)); + BOOST_CHECK(copyTree.get(2)); + BOOST_CHECK(copyTree.get(3)); + BOOST_CHECK(!copyTree.get(90)); + BOOST_CHECK(!copyTree.get(91)); + BOOST_CHECK(!copyTree.get(92)); + BOOST_CHECK(!copyTree.get(93)); + + copyTree = mytree; + + BOOST_CHECK(mytree.remove(0)); + BOOST_CHECK(mytree.remove(1)); + BOOST_CHECK(mytree.remove(2)); + BOOST_CHECK(mytree.remove(3)); + + // The copy was unaffected by the removals. + BOOST_CHECK(copyTree.get(0)); + BOOST_CHECK(copyTree.get(1)); + BOOST_CHECK(copyTree.get(2)); + BOOST_CHECK(copyTree.get(3)); + BOOST_CHECK(copyTree.get(90)); + BOOST_CHECK(copyTree.get(91)); + BOOST_CHECK(copyTree.get(92)); + BOOST_CHECK(copyTree.get(93)); +} + +BOOST_AUTO_TEST_CASE(test_move) { + using E = TestElement; + + RadixTree mytree; + + BOOST_CHECK(mytree.insert(RCUPtr::make(0))); + BOOST_CHECK(mytree.insert(RCUPtr::make(1))); + BOOST_CHECK(mytree.insert(RCUPtr::make(2))); + BOOST_CHECK(mytree.insert(RCUPtr::make(3))); + + RadixTree movedTree = std::move(mytree); + + BOOST_CHECK(!mytree.remove(0)); + BOOST_CHECK(!mytree.remove(1)); + BOOST_CHECK(!mytree.remove(2)); + BOOST_CHECK(!mytree.remove(3)); + + BOOST_CHECK(movedTree.remove(0)); + BOOST_CHECK(movedTree.remove(1)); + BOOST_CHECK(movedTree.remove(2)); + BOOST_CHECK(movedTree.remove(3)); +} + #define THREADS 128 #define ELEMENTS 65536