radix.h File Reference

#include <common/system.h>
#include <rcu.h>
#include <array>
#include <atomic>
#include <cstdint>
#include <memory>
#include <type_traits>

Include dependency graph for radix.h:

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Classes
struct	PassthroughAdapter< T >
struct	RadixTree< T, Adapter >
	This is a radix tree storing values identified by a unique key. More...
struct	RadixTree< T, Adapter >::RadixElement
struct	RadixTree< T, Adapter >::RadixNode

Macros
#define	SEEK_LEAF_LOOP()

Macro Definition Documentation

SEEK_LEAF_LOOP

#define SEEK_LEAF_LOOP

(

)

Value:

    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<RadixNode>(*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.decrementRefCount();                                             \
            eptr = copy->get(level--, key);                                    \
            e = eptr->load();                                                  \
            copy.release();                                                    \
        }                                                                      \
    } while (0)

Definition at line 149 of file radix.h.