duckdb::Node48 Class Reference

Collaboration diagram for duckdb::Node48:

Public Member Functions
	Node48 (const Node48 &)=delete
Node48 &	operator= (const Node48 &)=delete
void	ReplaceChild (const uint8_t byte, const Node child)
	Replace the child at byte.
NodeChildren	ExtractChildren (ArenaAllocator &arena)

Static Public Member Functions
static NodeHandle< Node48 >	New (ART &art, Node &node)
	Get a new Node48 handle and initialize the Node48.
static void	InsertChild (ART &art, Node &node, const uint8_t byte, const Node child)
	Insert a child at byte.
static void	DeleteChild (ART &art, Node &node, const uint8_t byte)
	Delete the child at byte.
template<class F , class NODE >
static void	Iterator (NODE &n, F &&lambda)
template<class NODE >
static unsafe_optional_ptr< Node >	GetChild (NODE &n, const uint8_t byte, const bool unsafe=false)
template<class NODE >
static unsafe_optional_ptr< Node >	GetNextChild (NODE &n, uint8_t &byte)

Static Public Attributes
static constexpr NType	NODE_48 = NType::NODE_48
static constexpr uint8_t	CAPACITY = 48
static constexpr uint8_t	EMPTY_MARKER = 48
static constexpr uint8_t	SHRINK_THRESHOLD = 12

Static Private Member Functions
static void	GrowNode16 (ART &art, Node &node48, Node &node16)
static void	ShrinkNode256 (ART &art, Node &node48, Node &node256)
	We shrink at <= Node256::SHRINK_THRESHOLD.

Private Attributes
uint8_t	count
uint8_t	child_index [Node256::CAPACITY]
Node	children [CAPACITY]

Friends
class	Node16
class	Node256

Detailed Description

Node48 holds up to 48 children. The child_index array is indexed by the key byte. It contains the position of the child node in the children array.

Member Function Documentation

New()

static NodeHandle< Node48 > duckdb::Node48::New ( ART &  art, Node &  node  )

inlinestatic

Get a new Node48 handle and initialize the Node48.

                                                        {
        node = Node::GetAllocator(art, NODE_48).New();
        node.SetMetadata(static_cast<uint8_t>(NODE_48));
 
        NodeHandle<Node48> handle(art, node);
        auto &n = handle.Get();
 
        // Reset the node (count and child_index).
        n.count = 0;
        for (uint16_t i = 0; i < Node256::CAPACITY; i++) {
            n.child_index[i] = EMPTY_MARKER;
        }
        // Zero-initialize the node.
        for (uint8_t i = 0; i < CAPACITY; i++) {
            n.children[i].Clear();
        }
 
        return handle;
    }

Here is the call graph for this function:

ReplaceChild()

void duckdb::Node48::ReplaceChild ( const uint8_t  byte, const Node  child  )

inline

Replace the child at byte.

                                                            {
        D_ASSERT(count >= SHRINK_THRESHOLD);
        auto status = children[child_index[byte]].GetGateStatus();
        children[child_index[byte]] = child;
        if (status == GateStatus::GATE_SET && child.HasMetadata()) {
            children[child_index[byte]].SetGateStatus(status);
        }
    }

Here is the call graph for this function:

Iterator()

template<class F , class NODE >

static void duckdb::Node48::Iterator ( NODE &  n, F &&  lambda  )

inlinestatic

                                              {
        D_ASSERT(n.count);
        for (idx_t i = 0; i < Node256::CAPACITY; i++) {
            if (n.child_index[i] != EMPTY_MARKER) {
                lambda(n.children[n.child_index[i]]);
            }
        }
    }

GetChild()

template<class NODE >

static unsafe_optional_ptr< Node > duckdb::Node48::GetChild ( NODE &  n, const uint8_t  byte, const bool  unsafe = false  )

inlinestatic

                                                                                                      {
        if (n.child_index[byte] != Node48::EMPTY_MARKER) {
            if (!unsafe && !n.children[n.child_index[byte]].HasMetadata()) {
                throw InternalException("empty child for byte %d in Node48::GetChild", byte);
            }
            return &n.children[n.child_index[byte]];
        }
        return nullptr;
    }

GetNextChild()

template<class NODE >

static unsafe_optional_ptr< Node > duckdb::Node48::GetNextChild ( NODE &  n, uint8_t &  byte  )

inlinestatic

                                                                          {
        for (idx_t i = byte; i < Node256::CAPACITY; i++) {
            if (n.child_index[i] != EMPTY_MARKER) {
                byte = UnsafeNumericCast<uint8_t>(i);
                return &n.children[n.child_index[i]];
            }
        }
        return nullptr;
    }

ExtractChildren()

NodeChildren duckdb::Node48::ExtractChildren ( ArenaAllocator &  arena )

inline

Extracts the bytes and their respective children. The return value is valid as long as the arena is valid. The node must be freed after calling into this function.

                                                        {
        auto mem_bytes = arena.AllocateAligned(sizeof(uint8_t) * count);
        array_ptr<uint8_t> bytes(mem_bytes, count);
        auto mem_children = arena.AllocateAligned(sizeof(Node) * count);
        array_ptr<Node> children_ptr(reinterpret_cast<Node *>(mem_children), count);
 
        uint16_t ptr_idx = 0;
        for (idx_t i = 0; i < Node256::CAPACITY; i++) {
            if (child_index[i] != EMPTY_MARKER) {
                bytes[ptr_idx] = UnsafeNumericCast<uint8_t>(i);
                children_ptr[ptr_idx] = children[child_index[i]];
                ptr_idx++;
            }
        }
 
        return NodeChildren(bytes, children_ptr);
    }

---

The documentation for this class was generated from the following file:

• external/duckdb/duckdb.cpp