PostgreSQL Source Code git master
Data Structures | Macros | Typedefs | Enumerations | Functions | Variables
radixtree.h File Reference
#include "nodes/bitmapset.h"
#include "port/pg_bitutils.h"
#include "port/simd.h"
#include "utils/dsa.h"
#include "utils/memutils.h"
Include dependency graph for radixtree.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Data Structures

struct  RT_NODE
 
union  RT_CHILD_PTR
 
struct  RT_NODE_4
 
struct  RT_NODE_16
 
struct  RT_NODE_48
 
struct  RT_NODE_256
 
struct  RT_SIZE_CLASS_ELEM
 
struct  RT_RADIX_TREE_CONTROL
 
struct  RT_RADIX_TREE
 
struct  RT_NODE_ITER
 
struct  RT_ITER
 

Macros

#define RT_MAKE_PREFIX(a)   CppConcat(a,_)
 
#define RT_MAKE_NAME(name)   RT_MAKE_NAME_(RT_MAKE_PREFIX(RT_PREFIX),name)
 
#define RT_MAKE_NAME_(a, b)   CppConcat(a,b)
 
#define RT_STR(s)   RT_STR_(s)
 
#define RT_STR_(s)   #s
 
#define RT_CREATE   RT_MAKE_NAME(create)
 
#define RT_FREE   RT_MAKE_NAME(free)
 
#define RT_FIND   RT_MAKE_NAME(find)
 
#define RT_SET   RT_MAKE_NAME(set)
 
#define RT_BEGIN_ITERATE   RT_MAKE_NAME(begin_iterate)
 
#define RT_ITERATE_NEXT   RT_MAKE_NAME(iterate_next)
 
#define RT_END_ITERATE   RT_MAKE_NAME(end_iterate)
 
#define RT_MEMORY_USAGE   RT_MAKE_NAME(memory_usage)
 
#define RT_DUMP_NODE   RT_MAKE_NAME(dump_node)
 
#define RT_STATS   RT_MAKE_NAME(stats)
 
#define RT_CHILDPTR_IS_VALUE   RT_MAKE_NAME(childptr_is_value)
 
#define RT_VALUE_IS_EMBEDDABLE   RT_MAKE_NAME(value_is_embeddable)
 
#define RT_GET_SLOT_RECURSIVE   RT_MAKE_NAME(get_slot_recursive)
 
#define RT_DELETE_RECURSIVE   RT_MAKE_NAME(delete_recursive)
 
#define RT_ALLOC_NODE   RT_MAKE_NAME(alloc_node)
 
#define RT_ALLOC_LEAF   RT_MAKE_NAME(alloc_leaf)
 
#define RT_FREE_NODE   RT_MAKE_NAME(free_node)
 
#define RT_FREE_LEAF   RT_MAKE_NAME(free_leaf)
 
#define RT_FREE_RECURSE   RT_MAKE_NAME(free_recurse)
 
#define RT_EXTEND_UP   RT_MAKE_NAME(extend_up)
 
#define RT_EXTEND_DOWN   RT_MAKE_NAME(extend_down)
 
#define RT_COPY_COMMON   RT_MAKE_NAME(copy_common)
 
#define RT_PTR_SET_LOCAL   RT_MAKE_NAME(ptr_set_local)
 
#define RT_NODE_16_SEARCH_EQ   RT_MAKE_NAME(node_16_search_eq)
 
#define RT_NODE_4_GET_INSERTPOS   RT_MAKE_NAME(node_4_get_insertpos)
 
#define RT_NODE_16_GET_INSERTPOS   RT_MAKE_NAME(node_16_get_insertpos)
 
#define RT_SHIFT_ARRAYS_FOR_INSERT   RT_MAKE_NAME(shift_arrays_for_insert)
 
#define RT_SHIFT_ARRAYS_AND_DELETE   RT_MAKE_NAME(shift_arrays_and_delete)
 
#define RT_COPY_ARRAYS_FOR_INSERT   RT_MAKE_NAME(copy_arrays_for_insert)
 
#define RT_COPY_ARRAYS_AND_DELETE   RT_MAKE_NAME(copy_arrays_and_delete)
 
#define RT_NODE_48_IS_CHUNK_USED   RT_MAKE_NAME(node_48_is_chunk_used)
 
#define RT_NODE_48_GET_CHILD   RT_MAKE_NAME(node_48_get_child)
 
#define RT_NODE_256_IS_CHUNK_USED   RT_MAKE_NAME(node_256_is_chunk_used)
 
#define RT_NODE_256_GET_CHILD   RT_MAKE_NAME(node_256_get_child)
 
#define RT_KEY_GET_SHIFT   RT_MAKE_NAME(key_get_shift)
 
#define RT_SHIFT_GET_MAX_VAL   RT_MAKE_NAME(shift_get_max_val)
 
#define RT_NODE_SEARCH   RT_MAKE_NAME(node_search)
 
#define RT_NODE_DELETE   RT_MAKE_NAME(node_delete)
 
#define RT_NODE_INSERT   RT_MAKE_NAME(node_insert)
 
#define RT_ADD_CHILD_4   RT_MAKE_NAME(add_child_4)
 
#define RT_ADD_CHILD_16   RT_MAKE_NAME(add_child_16)
 
#define RT_ADD_CHILD_48   RT_MAKE_NAME(add_child_48)
 
#define RT_ADD_CHILD_256   RT_MAKE_NAME(add_child_256)
 
#define RT_GROW_NODE_4   RT_MAKE_NAME(grow_node_4)
 
#define RT_GROW_NODE_16   RT_MAKE_NAME(grow_node_16)
 
#define RT_GROW_NODE_48   RT_MAKE_NAME(grow_node_48)
 
#define RT_REMOVE_CHILD_4   RT_MAKE_NAME(remove_child_4)
 
#define RT_REMOVE_CHILD_16   RT_MAKE_NAME(remove_child_16)
 
#define RT_REMOVE_CHILD_48   RT_MAKE_NAME(remove_child_48)
 
#define RT_REMOVE_CHILD_256   RT_MAKE_NAME(remove_child_256)
 
#define RT_SHRINK_NODE_16   RT_MAKE_NAME(shrink_child_16)
 
#define RT_SHRINK_NODE_48   RT_MAKE_NAME(shrink_child_48)
 
#define RT_SHRINK_NODE_256   RT_MAKE_NAME(shrink_child_256)
 
#define RT_NODE_ITERATE_NEXT   RT_MAKE_NAME(node_iterate_next)
 
#define RT_VERIFY_NODE   RT_MAKE_NAME(verify_node)
 
#define RT_RADIX_TREE   RT_MAKE_NAME(radix_tree)
 
#define RT_RADIX_TREE_CONTROL   RT_MAKE_NAME(radix_tree_control)
 
#define RT_ITER   RT_MAKE_NAME(iter)
 
#define RT_NODE   RT_MAKE_NAME(node)
 
#define RT_CHILD_PTR   RT_MAKE_NAME(child_ptr)
 
#define RT_NODE_ITER   RT_MAKE_NAME(node_iter)
 
#define RT_NODE_4   RT_MAKE_NAME(node_4)
 
#define RT_NODE_16   RT_MAKE_NAME(node_16)
 
#define RT_NODE_48   RT_MAKE_NAME(node_48)
 
#define RT_NODE_256   RT_MAKE_NAME(node_256)
 
#define RT_SIZE_CLASS   RT_MAKE_NAME(size_class)
 
#define RT_SIZE_CLASS_ELEM   RT_MAKE_NAME(size_class_elem)
 
#define RT_SIZE_CLASS_INFO   RT_MAKE_NAME(size_class_info)
 
#define RT_CLASS_4   RT_MAKE_NAME(class_4)
 
#define RT_CLASS_16_LO   RT_MAKE_NAME(class_32_min)
 
#define RT_CLASS_16_HI   RT_MAKE_NAME(class_32_max)
 
#define RT_CLASS_48   RT_MAKE_NAME(class_48)
 
#define RT_CLASS_256   RT_MAKE_NAME(class_256)
 
#define RT_SPAN   BITS_PER_BYTE
 
#define RT_NODE_MAX_SLOTS   (1 << RT_SPAN)
 
#define RT_CHUNK_MASK   ((1 << RT_SPAN) - 1)
 
#define RT_MAX_SHIFT   RT_KEY_GET_SHIFT(UINT64_MAX)
 
#define RT_MAX_LEVEL   ((sizeof(uint64) * BITS_PER_BYTE) / RT_SPAN)
 
#define RT_GET_KEY_CHUNK(key, shift)   ((uint8) (((key) >> (shift)) & RT_CHUNK_MASK))
 
#define RT_BM_IDX(x)   ((x) / BITS_PER_BITMAPWORD)
 
#define RT_BM_BIT(x)   ((x) % BITS_PER_BITMAPWORD)
 
#define RT_NODE_KIND_4   0x00
 
#define RT_NODE_KIND_16   0x01
 
#define RT_NODE_KIND_48   0x02
 
#define RT_NODE_KIND_256   0x03
 
#define RT_NODE_KIND_COUNT   4
 
#define RT_SLAB_BLOCK_SIZE(size)    Max(SLAB_DEFAULT_BLOCK_SIZE, pg_nextpower2_32(size * 32))
 
#define RT_PTR_ALLOC   RT_NODE *
 
#define RT_INVALID_PTR_ALLOC   NULL
 
#define RT_PTR_ALLOC_IS_VALID(ptr)   PointerIsValid(ptr)
 
#define RT_GET_VALUE_SIZE(v)   RT_VARLEN_VALUE_SIZE(v)
 
#define RT_FANOUT_4_MAX   (8 - sizeof(RT_NODE))
 
#define RT_FANOUT_16_MAX   32
 
#define RT_FANOUT_48_MAX   64
 
#define RT_FANOUT_256   RT_NODE_MAX_SLOTS
 
#define RT_INVALID_SLOT_IDX   0xFF
 
#define RT_FANOUT_16_LO   16
 
#define RT_FANOUT_16_HI   RT_FANOUT_16_MAX
 
#define RT_FANOUT_48   RT_FANOUT_48_MAX
 
#define RT_FANOUT_4   4
 
#define RT_NUM_SIZE_CLASSES   lengthof(RT_SIZE_CLASS_INFO)
 
#define RT_NODE_MUST_GROW(node)    ((node)->count == (node)->fanout)
 

Typedefs

typedef struct RT_RADIX_TREE RT_RADIX_TREE
 
typedef struct RT_ITER RT_ITER
 
typedef struct RT_NODE RT_NODE
 
typedef union RT_CHILD_PTR RT_CHILD_PTR
 
typedef struct RT_NODE_4 RT_NODE_4
 
typedef struct RT_NODE_16 RT_NODE_16
 
typedef struct RT_NODE_48 RT_NODE_48
 
typedef struct RT_NODE_256 RT_NODE_256
 
typedef enum RT_SIZE_CLASS RT_SIZE_CLASS
 
typedef struct RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_ELEM
 
typedef struct RT_RADIX_TREE_CONTROL RT_RADIX_TREE_CONTROL
 
typedef struct RT_NODE_ITER RT_NODE_ITER
 

Enumerations

enum  RT_SIZE_CLASS {
  RT_CLASS_4 = 0 , RT_CLASS_16_LO , RT_CLASS_16_HI , RT_CLASS_48 ,
  RT_CLASS_256
}
 

Functions

RT_SCOPE RT_RADIX_TREE * RT_CREATE (MemoryContext ctx)
 
RT_SCOPE void RT_FREE (RT_RADIX_TREE *tree)
 
RT_SCOPE RT_VALUE_TYPE * RT_FIND (RT_RADIX_TREE *tree, uint64 key)
 
RT_SCOPE bool RT_SET (RT_RADIX_TREE *tree, uint64 key, RT_VALUE_TYPE *value_p)
 
RT_SCOPE RT_ITER * RT_BEGIN_ITERATE (RT_RADIX_TREE *tree)
 
RT_SCOPE RT_VALUE_TYPE * RT_ITERATE_NEXT (RT_ITER *iter, uint64 *key_p)
 
RT_SCOPE void RT_END_ITERATE (RT_ITER *iter)
 
RT_SCOPE uint64 RT_MEMORY_USAGE (RT_RADIX_TREE *tree)
 
static bool RT_VALUE_IS_EMBEDDABLE (RT_VALUE_TYPE *value_p)
 
static bool RT_CHILDPTR_IS_VALUE (RT_PTR_ALLOC child)
 
 StaticAssertDecl (RT_FANOUT_4<=RT_FANOUT_4_MAX, "watch struct padding")
 
 StaticAssertDecl (RT_FANOUT_16_LO< RT_FANOUT_16_HI, "LO subclass bigger than HI")
 
 StaticAssertDecl (RT_FANOUT_48<=RT_FANOUT_48_MAX, "more slots than isset bits")
 
static void RT_VERIFY_NODE (RT_NODE *node)
 
static void RT_PTR_SET_LOCAL (RT_RADIX_TREE *tree, RT_CHILD_PTR *node)
 
static bool RT_NODE_48_IS_CHUNK_USED (RT_NODE_48 *node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_NODE_48_GET_CHILD (RT_NODE_48 *node, uint8 chunk)
 
static bool RT_NODE_256_IS_CHUNK_USED (RT_NODE_256 *node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_NODE_256_GET_CHILD (RT_NODE_256 *node, uint8 chunk)
 
static int RT_KEY_GET_SHIFT (uint64 key)
 
static uint64 RT_SHIFT_GET_MAX_VAL (int shift)
 
static RT_CHILD_PTR RT_ALLOC_NODE (RT_RADIX_TREE *tree, const uint8 kind, const RT_SIZE_CLASS size_class)
 
static RT_CHILD_PTR RT_ALLOC_LEAF (RT_RADIX_TREE *tree, size_t allocsize)
 
static void RT_COPY_COMMON (RT_CHILD_PTR newnode, RT_CHILD_PTR oldnode)
 
static void RT_FREE_NODE (RT_RADIX_TREE *tree, RT_CHILD_PTR node)
 
static void RT_FREE_LEAF (RT_RADIX_TREE *tree, RT_PTR_ALLOC leaf)
 
static RT_PTR_ALLOC * RT_NODE_16_SEARCH_EQ (RT_NODE_16 *node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_NODE_SEARCH (RT_NODE *node, uint8 chunk)
 
static int RT_NODE_4_GET_INSERTPOS (RT_NODE_4 *node, uint8 chunk, int count)
 
static int RT_NODE_16_GET_INSERTPOS (RT_NODE_16 *node, uint8 chunk)
 
static void RT_SHIFT_ARRAYS_FOR_INSERT (uint8 *chunks, RT_PTR_ALLOC *children, int count, int insertpos)
 
static void RT_COPY_ARRAYS_FOR_INSERT (uint8 *dst_chunks, RT_PTR_ALLOC *dst_children, uint8 *src_chunks, RT_PTR_ALLOC *src_children, int count, int insertpos)
 
static RT_PTR_ALLOC * RT_ADD_CHILD_256 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline RT_PTR_ALLOC * RT_GROW_NODE_48 (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_ADD_CHILD_48 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline RT_PTR_ALLOC * RT_GROW_NODE_16 (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_ADD_CHILD_16 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline RT_PTR_ALLOC * RT_GROW_NODE_4 (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_ADD_CHILD_4 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOC * RT_NODE_INSERT (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline void RT_EXTEND_UP (RT_RADIX_TREE *tree, uint64 key)
 
static pg_noinline RT_PTR_ALLOC * RT_EXTEND_DOWN (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, uint64 key, int shift)
 
static RT_PTR_ALLOC * RT_GET_SLOT_RECURSIVE (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, uint64 key, int shift, bool *found)
 
 for (int i=0;i< RT_NUM_SIZE_CLASSES;i++)
 
static RT_PTR_ALLOC * RT_NODE_ITERATE_NEXT (RT_ITER *iter, int level)
 

Variables

static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO []
 
RT_SCOPE RT_RADIX_TREE *RT_CHILD_PTR rootnode
 
 tree = (RT_RADIX_TREE *) palloc0(sizeof(RT_RADIX_TREE))
 
tree ctl = (RT_RADIX_TREE_CONTROL *) palloc0(sizeof(RT_RADIX_TREE_CONTROL))
 
tree leaf_context = ctx
 
tree ctl root = rootnode.alloc
 
tree ctl start_shift = 0
 
tree ctl max_val = RT_SHIFT_GET_MAX_VAL(0)
 

Macro Definition Documentation

◆ RT_ADD_CHILD_16

#define RT_ADD_CHILD_16   RT_MAKE_NAME(add_child_16)

Definition at line 228 of file radixtree.h.

◆ RT_ADD_CHILD_256

#define RT_ADD_CHILD_256   RT_MAKE_NAME(add_child_256)

Definition at line 230 of file radixtree.h.

◆ RT_ADD_CHILD_4

#define RT_ADD_CHILD_4   RT_MAKE_NAME(add_child_4)

Definition at line 227 of file radixtree.h.

◆ RT_ADD_CHILD_48

#define RT_ADD_CHILD_48   RT_MAKE_NAME(add_child_48)

Definition at line 229 of file radixtree.h.

◆ RT_ALLOC_LEAF

#define RT_ALLOC_LEAF   RT_MAKE_NAME(alloc_leaf)

Definition at line 203 of file radixtree.h.

◆ RT_ALLOC_NODE

#define RT_ALLOC_NODE   RT_MAKE_NAME(alloc_node)

Definition at line 202 of file radixtree.h.

◆ RT_BEGIN_ITERATE

#define RT_BEGIN_ITERATE   RT_MAKE_NAME(begin_iterate)

Definition at line 187 of file radixtree.h.

◆ RT_BM_BIT

#define RT_BM_BIT (   x)    ((x) % BITS_PER_BITMAPWORD)

Definition at line 336 of file radixtree.h.

◆ RT_BM_IDX

#define RT_BM_IDX (   x)    ((x) / BITS_PER_BITMAPWORD)

Definition at line 335 of file radixtree.h.

◆ RT_CHILD_PTR

#define RT_CHILD_PTR   RT_MAKE_NAME(child_ptr)

Definition at line 252 of file radixtree.h.

◆ RT_CHILDPTR_IS_VALUE

#define RT_CHILDPTR_IS_VALUE   RT_MAKE_NAME(childptr_is_value)

Definition at line 198 of file radixtree.h.

◆ RT_CHUNK_MASK

#define RT_CHUNK_MASK   ((1 << RT_SPAN) - 1)

Definition at line 323 of file radixtree.h.

◆ RT_CLASS_16_HI

#define RT_CLASS_16_HI   RT_MAKE_NAME(class_32_max)

Definition at line 263 of file radixtree.h.

◆ RT_CLASS_16_LO

#define RT_CLASS_16_LO   RT_MAKE_NAME(class_32_min)

Definition at line 262 of file radixtree.h.

◆ RT_CLASS_256

#define RT_CLASS_256   RT_MAKE_NAME(class_256)

Definition at line 265 of file radixtree.h.

◆ RT_CLASS_4

#define RT_CLASS_4   RT_MAKE_NAME(class_4)

Definition at line 261 of file radixtree.h.

◆ RT_CLASS_48

#define RT_CLASS_48   RT_MAKE_NAME(class_48)

Definition at line 264 of file radixtree.h.

◆ RT_COPY_ARRAYS_AND_DELETE

#define RT_COPY_ARRAYS_AND_DELETE   RT_MAKE_NAME(copy_arrays_and_delete)

Definition at line 217 of file radixtree.h.

◆ RT_COPY_ARRAYS_FOR_INSERT

#define RT_COPY_ARRAYS_FOR_INSERT   RT_MAKE_NAME(copy_arrays_for_insert)

Definition at line 216 of file radixtree.h.

◆ RT_COPY_COMMON

#define RT_COPY_COMMON   RT_MAKE_NAME(copy_common)

Definition at line 209 of file radixtree.h.

◆ RT_CREATE

#define RT_CREATE   RT_MAKE_NAME(create)

Definition at line 175 of file radixtree.h.

◆ RT_DELETE_RECURSIVE

#define RT_DELETE_RECURSIVE   RT_MAKE_NAME(delete_recursive)

Definition at line 201 of file radixtree.h.

◆ RT_DUMP_NODE

#define RT_DUMP_NODE   RT_MAKE_NAME(dump_node)

Definition at line 194 of file radixtree.h.

◆ RT_END_ITERATE

#define RT_END_ITERATE   RT_MAKE_NAME(end_iterate)

Definition at line 189 of file radixtree.h.

◆ RT_EXTEND_DOWN

#define RT_EXTEND_DOWN   RT_MAKE_NAME(extend_down)

Definition at line 208 of file radixtree.h.

◆ RT_EXTEND_UP

#define RT_EXTEND_UP   RT_MAKE_NAME(extend_up)

Definition at line 207 of file radixtree.h.

◆ RT_FANOUT_16_HI

#define RT_FANOUT_16_HI   RT_FANOUT_16_MAX

Definition at line 602 of file radixtree.h.

◆ RT_FANOUT_16_LO

#define RT_FANOUT_16_LO   16

Definition at line 600 of file radixtree.h.

◆ RT_FANOUT_16_MAX

#define RT_FANOUT_16_MAX   32

Definition at line 494 of file radixtree.h.

◆ RT_FANOUT_256

#define RT_FANOUT_256   RT_NODE_MAX_SLOTS

Definition at line 506 of file radixtree.h.

◆ RT_FANOUT_4

#define RT_FANOUT_4   4

Definition at line 613 of file radixtree.h.

◆ RT_FANOUT_48

#define RT_FANOUT_48   RT_FANOUT_48_MAX

Definition at line 603 of file radixtree.h.

◆ RT_FANOUT_48_MAX

#define RT_FANOUT_48_MAX   64

Definition at line 504 of file radixtree.h.

◆ RT_FANOUT_4_MAX

#define RT_FANOUT_4_MAX   (8 - sizeof(RT_NODE))

Definition at line 491 of file radixtree.h.

◆ RT_FIND

#define RT_FIND   RT_MAKE_NAME(find)

Definition at line 177 of file radixtree.h.

◆ RT_FREE

#define RT_FREE   RT_MAKE_NAME(free)

Definition at line 176 of file radixtree.h.

◆ RT_FREE_LEAF

#define RT_FREE_LEAF   RT_MAKE_NAME(free_leaf)

Definition at line 205 of file radixtree.h.

◆ RT_FREE_NODE

#define RT_FREE_NODE   RT_MAKE_NAME(free_node)

Definition at line 204 of file radixtree.h.

◆ RT_FREE_RECURSE

#define RT_FREE_RECURSE   RT_MAKE_NAME(free_recurse)

Definition at line 206 of file radixtree.h.

◆ RT_GET_KEY_CHUNK

#define RT_GET_KEY_CHUNK (   key,
  shift 
)    ((uint8) (((key) >> (shift)) & RT_CHUNK_MASK))

Definition at line 332 of file radixtree.h.

◆ RT_GET_SLOT_RECURSIVE

#define RT_GET_SLOT_RECURSIVE   RT_MAKE_NAME(get_slot_recursive)

Definition at line 200 of file radixtree.h.

◆ RT_GET_VALUE_SIZE

#define RT_GET_VALUE_SIZE (   v)    RT_VARLEN_VALUE_SIZE(v)

Definition at line 433 of file radixtree.h.

◆ RT_GROW_NODE_16

#define RT_GROW_NODE_16   RT_MAKE_NAME(grow_node_16)

Definition at line 232 of file radixtree.h.

◆ RT_GROW_NODE_4

#define RT_GROW_NODE_4   RT_MAKE_NAME(grow_node_4)

Definition at line 231 of file radixtree.h.

◆ RT_GROW_NODE_48

#define RT_GROW_NODE_48   RT_MAKE_NAME(grow_node_48)

Definition at line 233 of file radixtree.h.

◆ RT_INVALID_PTR_ALLOC

#define RT_INVALID_PTR_ALLOC   NULL

Definition at line 405 of file radixtree.h.

◆ RT_INVALID_SLOT_IDX

#define RT_INVALID_SLOT_IDX   0xFF

Definition at line 557 of file radixtree.h.

◆ RT_ITER

#define RT_ITER   RT_MAKE_NAME(iter)

Definition at line 247 of file radixtree.h.

◆ RT_ITERATE_NEXT

#define RT_ITERATE_NEXT   RT_MAKE_NAME(iterate_next)

Definition at line 188 of file radixtree.h.

◆ RT_KEY_GET_SHIFT

#define RT_KEY_GET_SHIFT   RT_MAKE_NAME(key_get_shift)

Definition at line 222 of file radixtree.h.

◆ RT_MAKE_NAME

#define RT_MAKE_NAME (   name)    RT_MAKE_NAME_(RT_MAKE_PREFIX(RT_PREFIX),name)

Definition at line 166 of file radixtree.h.

◆ RT_MAKE_NAME_

#define RT_MAKE_NAME_ (   a,
  b 
)    CppConcat(a,b)

Definition at line 167 of file radixtree.h.

◆ RT_MAKE_PREFIX

#define RT_MAKE_PREFIX (   a)    CppConcat(a,_)

Definition at line 165 of file radixtree.h.

◆ RT_MAX_LEVEL

#define RT_MAX_LEVEL   ((sizeof(uint64) * BITS_PER_BYTE) / RT_SPAN)

Definition at line 329 of file radixtree.h.

◆ RT_MAX_SHIFT

#define RT_MAX_SHIFT   RT_KEY_GET_SHIFT(UINT64_MAX)

Definition at line 326 of file radixtree.h.

◆ RT_MEMORY_USAGE

#define RT_MEMORY_USAGE   RT_MAKE_NAME(memory_usage)

Definition at line 193 of file radixtree.h.

◆ RT_NODE

#define RT_NODE   RT_MAKE_NAME(node)

Definition at line 251 of file radixtree.h.

◆ RT_NODE_16

#define RT_NODE_16   RT_MAKE_NAME(node_16)

Definition at line 255 of file radixtree.h.

◆ RT_NODE_16_GET_INSERTPOS

#define RT_NODE_16_GET_INSERTPOS   RT_MAKE_NAME(node_16_get_insertpos)

Definition at line 213 of file radixtree.h.

◆ RT_NODE_16_SEARCH_EQ

#define RT_NODE_16_SEARCH_EQ   RT_MAKE_NAME(node_16_search_eq)

Definition at line 211 of file radixtree.h.

◆ RT_NODE_256

#define RT_NODE_256   RT_MAKE_NAME(node_256)

Definition at line 257 of file radixtree.h.

◆ RT_NODE_256_GET_CHILD

#define RT_NODE_256_GET_CHILD   RT_MAKE_NAME(node_256_get_child)

Definition at line 221 of file radixtree.h.

◆ RT_NODE_256_IS_CHUNK_USED

#define RT_NODE_256_IS_CHUNK_USED   RT_MAKE_NAME(node_256_is_chunk_used)

Definition at line 220 of file radixtree.h.

◆ RT_NODE_4

#define RT_NODE_4   RT_MAKE_NAME(node_4)

Definition at line 254 of file radixtree.h.

◆ RT_NODE_48

#define RT_NODE_48   RT_MAKE_NAME(node_48)

Definition at line 256 of file radixtree.h.

◆ RT_NODE_48_GET_CHILD

#define RT_NODE_48_GET_CHILD   RT_MAKE_NAME(node_48_get_child)

Definition at line 219 of file radixtree.h.

◆ RT_NODE_48_IS_CHUNK_USED

#define RT_NODE_48_IS_CHUNK_USED   RT_MAKE_NAME(node_48_is_chunk_used)

Definition at line 218 of file radixtree.h.

◆ RT_NODE_4_GET_INSERTPOS

#define RT_NODE_4_GET_INSERTPOS   RT_MAKE_NAME(node_4_get_insertpos)

Definition at line 212 of file radixtree.h.

◆ RT_NODE_DELETE

#define RT_NODE_DELETE   RT_MAKE_NAME(node_delete)

Definition at line 225 of file radixtree.h.

◆ RT_NODE_INSERT

#define RT_NODE_INSERT   RT_MAKE_NAME(node_insert)

Definition at line 226 of file radixtree.h.

◆ RT_NODE_ITER

#define RT_NODE_ITER   RT_MAKE_NAME(node_iter)

Definition at line 253 of file radixtree.h.

◆ RT_NODE_ITERATE_NEXT

#define RT_NODE_ITERATE_NEXT   RT_MAKE_NAME(node_iterate_next)

Definition at line 241 of file radixtree.h.

◆ RT_NODE_KIND_16

#define RT_NODE_KIND_16   0x01

Definition at line 361 of file radixtree.h.

◆ RT_NODE_KIND_256

#define RT_NODE_KIND_256   0x03

Definition at line 363 of file radixtree.h.

◆ RT_NODE_KIND_4

#define RT_NODE_KIND_4   0x00

Definition at line 360 of file radixtree.h.

◆ RT_NODE_KIND_48

#define RT_NODE_KIND_48   0x02

Definition at line 362 of file radixtree.h.

◆ RT_NODE_KIND_COUNT

#define RT_NODE_KIND_COUNT   4

Definition at line 364 of file radixtree.h.

◆ RT_NODE_MAX_SLOTS

#define RT_NODE_MAX_SLOTS   (1 << RT_SPAN)

Definition at line 320 of file radixtree.h.

◆ RT_NODE_MUST_GROW

#define RT_NODE_MUST_GROW (   node)     ((node)->count == (node)->fanout)

Definition at line 1131 of file radixtree.h.

◆ RT_NODE_SEARCH

#define RT_NODE_SEARCH   RT_MAKE_NAME(node_search)

Definition at line 224 of file radixtree.h.

◆ RT_NUM_SIZE_CLASSES

#define RT_NUM_SIZE_CLASSES   lengthof(RT_SIZE_CLASS_INFO)

Definition at line 678 of file radixtree.h.

◆ RT_PTR_ALLOC

#define RT_PTR_ALLOC   RT_NODE *

Definition at line 404 of file radixtree.h.

◆ RT_PTR_ALLOC_IS_VALID

#define RT_PTR_ALLOC_IS_VALID (   ptr)    PointerIsValid(ptr)

Definition at line 406 of file radixtree.h.

◆ RT_PTR_SET_LOCAL

#define RT_PTR_SET_LOCAL   RT_MAKE_NAME(ptr_set_local)

Definition at line 210 of file radixtree.h.

◆ RT_RADIX_TREE

#define RT_RADIX_TREE   RT_MAKE_NAME(radix_tree)

Definition at line 245 of file radixtree.h.

◆ RT_RADIX_TREE_CONTROL

#define RT_RADIX_TREE_CONTROL   RT_MAKE_NAME(radix_tree_control)

Definition at line 246 of file radixtree.h.

◆ RT_REMOVE_CHILD_16

#define RT_REMOVE_CHILD_16   RT_MAKE_NAME(remove_child_16)

Definition at line 235 of file radixtree.h.

◆ RT_REMOVE_CHILD_256

#define RT_REMOVE_CHILD_256   RT_MAKE_NAME(remove_child_256)

Definition at line 237 of file radixtree.h.

◆ RT_REMOVE_CHILD_4

#define RT_REMOVE_CHILD_4   RT_MAKE_NAME(remove_child_4)

Definition at line 234 of file radixtree.h.

◆ RT_REMOVE_CHILD_48

#define RT_REMOVE_CHILD_48   RT_MAKE_NAME(remove_child_48)

Definition at line 236 of file radixtree.h.

◆ RT_SET

#define RT_SET   RT_MAKE_NAME(set)

Definition at line 186 of file radixtree.h.

◆ RT_SHIFT_ARRAYS_AND_DELETE

#define RT_SHIFT_ARRAYS_AND_DELETE   RT_MAKE_NAME(shift_arrays_and_delete)

Definition at line 215 of file radixtree.h.

◆ RT_SHIFT_ARRAYS_FOR_INSERT

#define RT_SHIFT_ARRAYS_FOR_INSERT   RT_MAKE_NAME(shift_arrays_for_insert)

Definition at line 214 of file radixtree.h.

◆ RT_SHIFT_GET_MAX_VAL

#define RT_SHIFT_GET_MAX_VAL   RT_MAKE_NAME(shift_get_max_val)

Definition at line 223 of file radixtree.h.

◆ RT_SHRINK_NODE_16

#define RT_SHRINK_NODE_16   RT_MAKE_NAME(shrink_child_16)

Definition at line 238 of file radixtree.h.

◆ RT_SHRINK_NODE_256

#define RT_SHRINK_NODE_256   RT_MAKE_NAME(shrink_child_256)

Definition at line 240 of file radixtree.h.

◆ RT_SHRINK_NODE_48

#define RT_SHRINK_NODE_48   RT_MAKE_NAME(shrink_child_48)

Definition at line 239 of file radixtree.h.

◆ RT_SIZE_CLASS

#define RT_SIZE_CLASS   RT_MAKE_NAME(size_class)

Definition at line 258 of file radixtree.h.

◆ RT_SIZE_CLASS_ELEM

#define RT_SIZE_CLASS_ELEM   RT_MAKE_NAME(size_class_elem)

Definition at line 259 of file radixtree.h.

◆ RT_SIZE_CLASS_INFO

#define RT_SIZE_CLASS_INFO   RT_MAKE_NAME(size_class_info)

Definition at line 260 of file radixtree.h.

◆ RT_SLAB_BLOCK_SIZE

#define RT_SLAB_BLOCK_SIZE (   size)     Max(SLAB_DEFAULT_BLOCK_SIZE, pg_nextpower2_32(size * 32))

Definition at line 370 of file radixtree.h.

◆ RT_SPAN

#define RT_SPAN   BITS_PER_BYTE

Definition at line 314 of file radixtree.h.

◆ RT_STATS

#define RT_STATS   RT_MAKE_NAME(stats)

Definition at line 195 of file radixtree.h.

◆ RT_STR

#define RT_STR (   s)    RT_STR_(s)

Definition at line 171 of file radixtree.h.

◆ RT_STR_

#define RT_STR_ (   s)    #s

Definition at line 172 of file radixtree.h.

◆ RT_VALUE_IS_EMBEDDABLE

#define RT_VALUE_IS_EMBEDDABLE   RT_MAKE_NAME(value_is_embeddable)

Definition at line 199 of file radixtree.h.

◆ RT_VERIFY_NODE

#define RT_VERIFY_NODE   RT_MAKE_NAME(verify_node)

Definition at line 242 of file radixtree.h.

Typedef Documentation

◆ RT_CHILD_PTR

typedef union RT_CHILD_PTR RT_CHILD_PTR

◆ RT_ITER

typedef struct RT_ITER RT_ITER

Definition at line 271 of file radixtree.h.

◆ RT_NODE

typedef struct RT_NODE RT_NODE

◆ RT_NODE_16

typedef struct RT_NODE_16 RT_NODE_16

◆ RT_NODE_256

typedef struct RT_NODE_256 RT_NODE_256

◆ RT_NODE_4

typedef struct RT_NODE_4 RT_NODE_4

◆ RT_NODE_48

typedef struct RT_NODE_48 RT_NODE_48

◆ RT_NODE_ITER

typedef struct RT_NODE_ITER RT_NODE_ITER

◆ RT_RADIX_TREE

typedef struct RT_RADIX_TREE RT_RADIX_TREE

Definition at line 270 of file radixtree.h.

◆ RT_RADIX_TREE_CONTROL

typedef struct RT_RADIX_TREE_CONTROL RT_RADIX_TREE_CONTROL

◆ RT_SIZE_CLASS

typedef enum RT_SIZE_CLASS RT_SIZE_CLASS

◆ RT_SIZE_CLASS_ELEM

typedef struct RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_ELEM

Enumeration Type Documentation

◆ RT_SIZE_CLASS

enum RT_SIZE_CLASS
Enumerator
RT_CLASS_4 
RT_CLASS_16_LO 
RT_CLASS_16_HI 
RT_CLASS_48 
RT_CLASS_256 

Definition at line 632 of file radixtree.h.

633{
634 RT_CLASS_4 = 0,
635 RT_CLASS_16_LO,
636 RT_CLASS_16_HI,
637 RT_CLASS_48,
638 RT_CLASS_256
639} RT_SIZE_CLASS;
RT_SIZE_CLASS
#define RT_SIZE_CLASS
Definition: radixtree.h:258
RT_CLASS_16_LO
#define RT_CLASS_16_LO
Definition: radixtree.h:262
RT_CLASS_256
#define RT_CLASS_256
Definition: radixtree.h:265
RT_CLASS_16_HI
#define RT_CLASS_16_HI
Definition: radixtree.h:263
RT_CLASS_48
#define RT_CLASS_48
Definition: radixtree.h:264
RT_CLASS_4
#define RT_CLASS_4
Definition: radixtree.h:261

Function Documentation

◆ for()

for ( )

Definition at line 1841 of file radixtree.h.

1842 {
1843 RT_SIZE_CLASS_ELEM size_class = RT_SIZE_CLASS_INFO[i];
1844 size_t inner_blocksize = RT_SLAB_BLOCK_SIZE(size_class.allocsize);
1845
1846 tree->node_slabs[i] = SlabContextCreate(ctx,
1847 size_class.name,
1848 inner_blocksize,
1849 size_class.allocsize);
1850 }
i
int i
Definition: isn.c:74
tree
tree
Definition: radixtree.h:1828
RT_SLAB_BLOCK_SIZE
#define RT_SLAB_BLOCK_SIZE(size)
Definition: radixtree.h:370
RT_SIZE_CLASS_INFO
#define RT_SIZE_CLASS_INFO
Definition: radixtree.h:260
SlabContextCreate
MemoryContext SlabContextCreate(MemoryContext parent, const char *name, Size blockSize, Size chunkSize)
Definition: slab.c:322
RT_SIZE_CLASS_ELEM
Definition: radixtree.h:643
RT_SIZE_CLASS_ELEM::allocsize
size_t allocsize
Definition: radixtree.h:646
RT_SIZE_CLASS_ELEM::name
const char * name
Definition: radixtree.h:644

References RT_SIZE_CLASS_ELEM::allocsize, i, RT_SIZE_CLASS_ELEM::name, RT_SIZE_CLASS_INFO, RT_SLAB_BLOCK_SIZE, SlabContextCreate(), and tree.

Referenced by RT_ADD_CHILD_48().

◆ RT_ADD_CHILD_16()

static RT_PTR_ALLOC * RT_ADD_CHILD_16 ( RT_RADIX_TREE *  tree,
RT_CHILD_PTR  node,
uint8  chunk 
)
inlinestatic

Definition at line 1457 of file radixtree.h.

1458{
1459 RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
1460 int insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
1461
1462 /* shift chunks and children */
1463 RT_SHIFT_ARRAYS_FOR_INSERT(n16->chunks, n16->children,
1464 n16->base.count, insertpos);
1465
1466 /* insert new chunk into place */
1467 n16->chunks[insertpos] = chunk;
1468
1469 n16->base.count++;
1470 RT_VERIFY_NODE((RT_NODE *) n16);
1471
1472 return &n16->children[insertpos];
1473}
RT_NODE_16_GET_INSERTPOS
#define RT_NODE_16_GET_INSERTPOS
Definition: radixtree.h:213
RT_VERIFY_NODE
#define RT_VERIFY_NODE
Definition: radixtree.h:242
RT_SHIFT_ARRAYS_FOR_INSERT
#define RT_SHIFT_ARRAYS_FOR_INSERT
Definition: radixtree.h:214
RT_NODE_16
Definition: radixtree.h:529
RT_NODE_16::base
RT_NODE base
Definition: radixtree.h:530
RT_NODE_16::children
RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER]
Definition: radixtree.h:535
RT_NODE_16::chunks
uint8 chunks[RT_FANOUT_16_MAX]
Definition: radixtree.h:532
RT_NODE
Definition: radixtree.h:375
RT_NODE::count
uint8 count
Definition: radixtree.h:394
RT_CHILD_PTR::local
RT_NODE * local
Definition: radixtree.h:421

References RT_NODE_16::base, RT_NODE_16::children, RT_NODE_16::chunks, RT_NODE::count, RT_CHILD_PTR::local, RT_NODE_16_GET_INSERTPOS, RT_SHIFT_ARRAYS_FOR_INSERT, and RT_VERIFY_NODE.

◆ RT_ADD_CHILD_256()

static RT_PTR_ALLOC * RT_ADD_CHILD_256 ( RT_RADIX_TREE *  tree,
RT_CHILD_PTR  node,
uint8  chunk 
)
inlinestatic

Definition at line 1269 of file radixtree.h.

1270{
1271 RT_NODE_256 *n256 = (RT_NODE_256 *) node.local;
1272 int idx = RT_BM_IDX(chunk);
1273 int bitnum = RT_BM_BIT(chunk);
1274
1275 /* Mark the slot used for "chunk" */
1276 n256->isset[idx] |= ((bitmapword) 1 << bitnum);
1277
1278 n256->base.count++;
1279 RT_VERIFY_NODE((RT_NODE *) n256);
1280
1281 return RT_NODE_256_GET_CHILD(n256, chunk);
1282}
idx
Datum idx(PG_FUNCTION_ARGS)
Definition: _int_op.c:259
bitmapword
uint32 bitmapword
Definition: bitmapset.h:44
RT_BM_BIT
#define RT_BM_BIT(x)
Definition: radixtree.h:336
RT_NODE_256_GET_CHILD
#define RT_NODE_256_GET_CHILD
Definition: radixtree.h:221
RT_BM_IDX
#define RT_BM_IDX(x)
Definition: radixtree.h:335
RT_NODE_256
Definition: radixtree.h:569
RT_NODE_256::base
RT_NODE base
Definition: radixtree.h:570
RT_NODE_256::isset
bitmapword isset[RT_BM_IDX(RT_FANOUT_256)]
Definition: radixtree.h:573

References RT_NODE_256::base, RT_NODE::count, idx(), RT_NODE_256::isset, RT_CHILD_PTR::local, RT_BM_BIT, RT_BM_IDX, RT_NODE_256_GET_CHILD, and RT_VERIFY_NODE.

◆ RT_ADD_CHILD_4()

static RT_PTR_ALLOC * RT_ADD_CHILD_4 ( RT_RADIX_TREE *  tree,
RT_CHILD_PTR  node,
uint8  chunk 
)
inlinestatic

Definition at line 1510 of file radixtree.h.

1511{
1512 RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
1513 int count = n4->base.count;
1514 int insertpos = RT_NODE_4_GET_INSERTPOS(n4, chunk, count);
1515
1516 /* shift chunks and children */
1517 RT_SHIFT_ARRAYS_FOR_INSERT(n4->chunks, n4->children,
1518 count, insertpos);
1519
1520 /* insert new chunk into place */
1521 n4->chunks[insertpos] = chunk;
1522
1523 n4->base.count++;
1524 RT_VERIFY_NODE((RT_NODE *) n4);
1525
1526 return &n4->children[insertpos];
1527}
RT_NODE_4_GET_INSERTPOS
#define RT_NODE_4_GET_INSERTPOS
Definition: radixtree.h:212
RT_NODE_4
Definition: radixtree.h:519
RT_NODE_4::children
RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER]
Definition: radixtree.h:525
RT_NODE_4::base
RT_NODE base
Definition: radixtree.h:520
RT_NODE_4::chunks
uint8 chunks[RT_FANOUT_4_MAX]
Definition: radixtree.h:522

References RT_NODE_4::base, RT_NODE_4::children, RT_NODE_4::chunks, RT_NODE::count, RT_CHILD_PTR::local, RT_NODE_4_GET_INSERTPOS, RT_SHIFT_ARRAYS_FOR_INSERT, and RT_VERIFY_NODE.

◆ RT_ADD_CHILD_48()

static RT_PTR_ALLOC * RT_ADD_CHILD_48 ( RT_RADIX_TREE *  tree,
RT_CHILD_PTR  node,
uint8  chunk 
)
inlinestatic

Definition at line 1332 of file radixtree.h.

1333{
1334 RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
1335 int insertpos;
1336 int idx = 0;
1337 bitmapword w,
1338 inverse;
1339
1340 /* get the first word with at least one bit not set */
1341 for (int i = 0; i < RT_BM_IDX(RT_FANOUT_48_MAX); i++)
1342 {
1343 w = n48->isset[i];
1344 if (w < ~((bitmapword) 0))
1345 {
1346 idx = i;
1347 break;
1348 }
1349 }
1350
1351 /* To get the first unset bit in w, get the first set bit in ~w */
1352 inverse = ~w;
1353 insertpos = idx * BITS_PER_BITMAPWORD;
1354 insertpos += bmw_rightmost_one_pos(inverse);
1355 Assert(insertpos < n48->base.fanout);
1356
1357 /* mark the slot used by setting the rightmost zero bit */
1358 n48->isset[idx] |= w + 1;
1359
1360 /* insert new chunk into place */
1361 n48->slot_idxs[chunk] = insertpos;
1362
1363 n48->base.count++;
1364 RT_VERIFY_NODE((RT_NODE *) n48);
1365
1366 return &n48->children[insertpos];
1367}
bmw_rightmost_one_pos
#define bmw_rightmost_one_pos(w)
Definition: bitmapset.h:79
BITS_PER_BITMAPWORD
#define BITS_PER_BITMAPWORD
Definition: bitmapset.h:43
Assert
Assert(PointerIsAligned(start, uint64))
for
for(int i=0;i< RT_NUM_SIZE_CLASSES;i++)
Definition: radixtree.h:1841
RT_FANOUT_48_MAX
#define RT_FANOUT_48_MAX
Definition: radixtree.h:504
RT_NODE_48
Definition: radixtree.h:543
RT_NODE_48::children
RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER]
Definition: radixtree.h:560
RT_NODE_48::slot_idxs
uint8 slot_idxs[RT_NODE_MAX_SLOTS]
Definition: radixtree.h:554
RT_NODE_48::base
RT_NODE base
Definition: radixtree.h:544
RT_NODE_48::isset
bitmapword isset[RT_BM_IDX(RT_FANOUT_48_MAX)]
Definition: radixtree.h:547

References Assert(), RT_NODE_48::base, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, RT_NODE_48::children, RT_NODE::count, for(), i, idx(), RT_NODE_48::isset, RT_CHILD_PTR::local, RT_BM_IDX, RT_FANOUT_48_MAX, RT_VERIFY_NODE, and RT_NODE_48::slot_idxs.

◆ RT_ALLOC_LEAF()

static RT_CHILD_PTR RT_ALLOC_LEAF ( RT_RADIX_TREE *  tree,
size_t  allocsize 
)
static

Definition at line 894 of file radixtree.h.

895{
896 RT_CHILD_PTR leaf;
897
898#ifdef RT_SHMEM
899 leaf.alloc = dsa_allocate(tree->dsa, allocsize);
900 RT_PTR_SET_LOCAL(tree, &leaf);
901#else
902 leaf.alloc = (RT_PTR_ALLOC) MemoryContextAlloc(tree->leaf_context, allocsize);
903#endif
904
905#ifdef RT_DEBUG
906 tree->ctl->num_leaves++;
907#endif
908
909 return leaf;
910}
dsa_allocate
#define dsa_allocate(area, size)
Definition: dsa.h:109
MemoryContextAlloc
void * MemoryContextAlloc(MemoryContext context, Size size)
Definition: mcxt.c:1181
RT_PTR_SET_LOCAL
#define RT_PTR_SET_LOCAL
Definition: radixtree.h:210
RT_PTR_ALLOC
#define RT_PTR_ALLOC
Definition: radixtree.h:404
RT_CHILD_PTR
Definition: radixtree.h:419
RT_CHILD_PTR::alloc
RT_PTR_ALLOC alloc
Definition: radixtree.h:420

References RT_CHILD_PTR::alloc, dsa_allocate, MemoryContextAlloc(), RT_PTR_ALLOC, RT_PTR_SET_LOCAL, and tree.

◆ RT_ALLOC_NODE()

static RT_CHILD_PTR RT_ALLOC_NODE ( RT_RADIX_TREE *  tree,
const uint8  kind,
const RT_SIZE_CLASS  size_class 
)
inlinestatic

Definition at line 831 of file radixtree.h.

832{
833 RT_CHILD_PTR allocnode;
834 RT_NODE *node;
835 size_t allocsize;
836
837 allocsize = RT_SIZE_CLASS_INFO[size_class].allocsize;
838
839#ifdef RT_SHMEM
840 allocnode.alloc = dsa_allocate(tree->dsa, allocsize);
841#else
842 allocnode.alloc = (RT_PTR_ALLOC) MemoryContextAlloc(tree->node_slabs[size_class],
843 allocsize);
844#endif
845
846 RT_PTR_SET_LOCAL(tree, &allocnode);
847 node = allocnode.local;
848
849 /* initialize contents */
850
851 switch (kind)
852 {
853 case RT_NODE_KIND_4:
854 memset(node, 0, offsetof(RT_NODE_4, children));
855 break;
856 case RT_NODE_KIND_16:
857 memset(node, 0, offsetof(RT_NODE_16, children));
858 break;
859 case RT_NODE_KIND_48:
860 {
861 RT_NODE_48 *n48 = (RT_NODE_48 *) node;
862
863 memset(n48, 0, offsetof(RT_NODE_48, slot_idxs));
864 memset(n48->slot_idxs, RT_INVALID_SLOT_IDX, sizeof(n48->slot_idxs));
865 break;
866 }
867 case RT_NODE_KIND_256:
868 memset(node, 0, offsetof(RT_NODE_256, children));
869 break;
870 default:
871 pg_unreachable();
872 }
873
874 node->kind = kind;
875
876 /*
877 * For node256, this will actually overflow to zero, but that's okay
878 * because that node doesn't need to introspect this value.
879 */
880 node->fanout = RT_SIZE_CLASS_INFO[size_class].fanout;
881
882#ifdef RT_DEBUG
883 /* update the statistics */
884 tree->ctl->num_nodes[size_class]++;
885#endif
886
887 return allocnode;
888}
pg_unreachable
#define pg_unreachable()
Definition: c.h:332
RT_NODE_KIND_16
#define RT_NODE_KIND_16
Definition: radixtree.h:361
RT_INVALID_SLOT_IDX
#define RT_INVALID_SLOT_IDX
Definition: radixtree.h:557
RT_NODE_KIND_48
#define RT_NODE_KIND_48
Definition: radixtree.h:362
RT_NODE_KIND_256
#define RT_NODE_KIND_256
Definition: radixtree.h:363
RT_NODE_KIND_4
#define RT_NODE_KIND_4
Definition: radixtree.h:360
RT_NODE::kind
uint8 kind
Definition: radixtree.h:377
RT_NODE::fanout
uint8 fanout
Definition: radixtree.h:386

References RT_CHILD_PTR::alloc, dsa_allocate, RT_NODE::fanout, RT_NODE::kind, RT_CHILD_PTR::local, MemoryContextAlloc(), pg_unreachable, RT_INVALID_SLOT_IDX, RT_NODE_KIND_16, RT_NODE_KIND_256, RT_NODE_KIND_4, RT_NODE_KIND_48, RT_PTR_ALLOC, RT_PTR_SET_LOCAL, RT_SIZE_CLASS_INFO, RT_NODE_48::slot_idxs, and tree.

◆ RT_BEGIN_ITERATE()

RT_SCOPE RT_ITER * RT_BEGIN_ITERATE ( RT_RADIX_TREE *  tree)

Definition at line 2055 of file radixtree.h.

2056{
2057 RT_ITER *iter;
2058 RT_CHILD_PTR root;
2059
2060 iter = (RT_ITER *) palloc0(sizeof(RT_ITER));
2061 iter->tree = tree;
2062
2063 Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2064 root.alloc = iter->tree->ctl->root;
2065 RT_PTR_SET_LOCAL(tree, &root);
2066
2067 iter->top_level = iter->tree->ctl->start_shift / RT_SPAN;
2068
2069 /* Set the root to start */
2070 iter->cur_level = iter->top_level;
2071 iter->node_iters[iter->cur_level].node = root;
2072 iter->node_iters[iter->cur_level].idx = 0;
2073
2074 return iter;
2075}
palloc0
void * palloc0(Size size)
Definition: mcxt.c:1347
RT_SPAN
#define RT_SPAN
Definition: radixtree.h:314
root
tree ctl root
Definition: radixtree.h:1857
RT_PTR_ALLOC_IS_VALID
#define RT_PTR_ALLOC_IS_VALID(ptr)
Definition: radixtree.h:406
RT_ITER
Definition: radixtree.h:744
RT_ITER::node_iters
RT_NODE_ITER node_iters[RT_MAX_LEVEL]
Definition: radixtree.h:751
RT_ITER::cur_level
int cur_level
Definition: radixtree.h:753
RT_ITER::tree
RT_RADIX_TREE * tree
Definition: radixtree.h:745
RT_ITER::top_level
int top_level
Definition: radixtree.h:752
RT_NODE_ITER::idx
int idx
Definition: radixtree.h:739
RT_NODE_ITER::node
RT_CHILD_PTR node
Definition: radixtree.h:732
RT_RADIX_TREE_CONTROL::root
RT_PTR_ALLOC root
Definition: radixtree.h:694
RT_RADIX_TREE_CONTROL::start_shift
int start_shift
Definition: radixtree.h:697
RT_RADIX_TREE::ctl
RT_RADIX_TREE_CONTROL * ctl
Definition: radixtree.h:710

References Assert(), RT_RADIX_TREE::ctl, RT_ITER::cur_level, RT_NODE_ITER::idx, RT_NODE_ITER::node, RT_ITER::node_iters, palloc0(), RT_RADIX_TREE_CONTROL::root, root, RT_PTR_ALLOC_IS_VALID, RT_PTR_SET_LOCAL, RT_SPAN, RT_RADIX_TREE_CONTROL::start_shift, RT_ITER::top_level, RT_ITER::tree, and tree.

◆ RT_CHILDPTR_IS_VALUE()

static bool RT_CHILDPTR_IS_VALUE ( RT_PTR_ALLOC  child)
inlinestatic

Definition at line 463 of file radixtree.h.

464{
465#ifdef RT_VARLEN_VALUE_SIZE
466
467#ifdef RT_RUNTIME_EMBEDDABLE_VALUE
468 /* check for pointer tag */
469#ifdef RT_SHMEM
470 return child & 1;
471#else
472 return ((uintptr_t) child) & 1;
473#endif
474
475#else
476 return false;
477#endif
478
479#else
480 return sizeof(RT_VALUE_TYPE) <= sizeof(RT_PTR_ALLOC);
481#endif
482}
RT_VALUE_TYPE
#define RT_VALUE_TYPE
Definition: tidstore.c:106

References RT_PTR_ALLOC, and RT_VALUE_TYPE.

◆ RT_COPY_ARRAYS_FOR_INSERT()

static void RT_COPY_ARRAYS_FOR_INSERT ( uint8 *  dst_chunks,
RT_PTR_ALLOC *  dst_children,
uint8 *  src_chunks,
RT_PTR_ALLOC *  src_children,
int  count,
int  insertpos 
)
inlinestatic

Definition at line 1252 of file radixtree.h.

1255{
1256 for (int i = 0; i < count; i++)
1257 {
1258 int sourceidx = i;
1259
1260 /* use a branch-free computation to skip the index of the new element */
1261 int destidx = i + (i >= insertpos);
1262
1263 dst_chunks[destidx] = src_chunks[sourceidx];
1264 dst_children[destidx] = src_children[sourceidx];
1265 }
1266}

References i.

◆ RT_COPY_COMMON()

static void RT_COPY_COMMON ( RT_CHILD_PTR  newnode,
RT_CHILD_PTR  oldnode 
)
inlinestatic

Definition at line 917 of file radixtree.h.

918{
919 (newnode.local)->count = (oldnode.local)->count;
920}

References RT_CHILD_PTR::local.

◆ RT_CREATE()

RT_SCOPE RT_RADIX_TREE * RT_CREATE ( MemoryContext  ctx)

◆ RT_END_ITERATE()

RT_SCOPE void RT_END_ITERATE ( RT_ITER *  iter)

Definition at line 2228 of file radixtree.h.

2229{
2230 pfree(iter);
2231}
pfree
void pfree(void *pointer)
Definition: mcxt.c:1524

References pfree().

◆ RT_EXTEND_DOWN()

static pg_noinline RT_PTR_ALLOC * RT_EXTEND_DOWN ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC *  parent_slot,
uint64  key,
int  shift 
)
static

Definition at line 1613 of file radixtree.h.

1614{
1615 RT_CHILD_PTR node,
1616 child;
1617 RT_NODE_4 *n4;
1618
1619 /*
1620 * The child pointer of the first node in the chain goes in the
1621 * caller-provided slot.
1622 */
1623 child = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1624 *parent_slot = child.alloc;
1625
1626 node = child;
1627 shift -= RT_SPAN;
1628
1629 while (shift > 0)
1630 {
1631 child = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1632
1633 /* We open-code the insertion ourselves, for speed. */
1634 n4 = (RT_NODE_4 *) node.local;
1635 n4->base.count = 1;
1636 n4->chunks[0] = RT_GET_KEY_CHUNK(key, shift);
1637 n4->children[0] = child.alloc;
1638
1639 node = child;
1640 shift -= RT_SPAN;
1641 }
1642 Assert(shift == 0);
1643
1644 /* Reserve slot for the value. */
1645 n4 = (RT_NODE_4 *) node.local;
1646 n4->chunks[0] = RT_GET_KEY_CHUNK(key, 0);
1647 n4->base.count = 1;
1648
1649 return &n4->children[0];
1650}
RT_ALLOC_NODE
#define RT_ALLOC_NODE
Definition: radixtree.h:202
RT_GET_KEY_CHUNK
#define RT_GET_KEY_CHUNK(key, shift)
Definition: radixtree.h:332

References RT_CHILD_PTR::alloc, Assert(), RT_NODE_4::base, RT_NODE_4::children, RT_NODE_4::chunks, RT_NODE::count, sort-test::key, RT_CHILD_PTR::local, RT_ALLOC_NODE, RT_CLASS_4, RT_GET_KEY_CHUNK, RT_NODE_KIND_4, RT_SPAN, and tree.

◆ RT_EXTEND_UP()

static pg_noinline void RT_EXTEND_UP ( RT_RADIX_TREE *  tree,
uint64  key 
)
static

Definition at line 1578 of file radixtree.h.

1579{
1580 int target_shift = RT_KEY_GET_SHIFT(key);
1581 int shift = tree->ctl->start_shift;
1582
1583 Assert(shift < target_shift);
1584
1585 /* Grow tree upwards until start shift can accommodate the key */
1586 while (shift < target_shift)
1587 {
1588 RT_CHILD_PTR node;
1589 RT_NODE_4 *n4;
1590
1591 node = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
1592 n4 = (RT_NODE_4 *) node.local;
1593 n4->base.count = 1;
1594 n4->chunks[0] = 0;
1595 n4->children[0] = tree->ctl->root;
1596
1597 /* Update the root */
1598 tree->ctl->root = node.alloc;
1599
1600 shift += RT_SPAN;
1601 }
1602
1603 tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(target_shift);
1604 tree->ctl->start_shift = target_shift;
1605}
RT_SHIFT_GET_MAX_VAL
#define RT_SHIFT_GET_MAX_VAL
Definition: radixtree.h:223
RT_KEY_GET_SHIFT
#define RT_KEY_GET_SHIFT
Definition: radixtree.h:222

References RT_CHILD_PTR::alloc, Assert(), RT_NODE_4::base, RT_NODE_4::children, RT_NODE_4::chunks, RT_NODE::count, sort-test::key, RT_CHILD_PTR::local, RT_ALLOC_NODE, RT_CLASS_4, RT_KEY_GET_SHIFT, RT_NODE_KIND_4, RT_SHIFT_GET_MAX_VAL, RT_SPAN, and tree.

◆ RT_FIND()

RT_SCOPE RT_VALUE_TYPE * RT_FIND ( RT_RADIX_TREE *  tree,
uint64  key 
)

Definition at line 1091 of file radixtree.h.

1092{
1093 RT_CHILD_PTR node;
1094 RT_PTR_ALLOC *slot = NULL;
1095 int shift;
1096
1097#ifdef RT_SHMEM
1098 Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1099#endif
1100
1101 if (key > tree->ctl->max_val)
1102 return NULL;
1103
1104 Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
1105 node.alloc = tree->ctl->root;
1106 shift = tree->ctl->start_shift;
1107
1108 /* Descend the tree */
1109 while (shift >= 0)
1110 {
1111 RT_PTR_SET_LOCAL(tree, &node);
1112 slot = RT_NODE_SEARCH(node.local, RT_GET_KEY_CHUNK(key, shift));
1113 if (slot == NULL)
1114 return NULL;
1115
1116 node.alloc = *slot;
1117 shift -= RT_SPAN;
1118 }
1119
1120 if (RT_CHILDPTR_IS_VALUE(*slot))
1121 return (RT_VALUE_TYPE *) slot;
1122 else
1123 {
1124 RT_PTR_SET_LOCAL(tree, &node);
1125 return (RT_VALUE_TYPE *) node.local;
1126 }
1127}
RT_NODE_SEARCH
#define RT_NODE_SEARCH
Definition: radixtree.h:224
RT_CHILDPTR_IS_VALUE
#define RT_CHILDPTR_IS_VALUE
Definition: radixtree.h:198

References RT_CHILD_PTR::alloc, Assert(), sort-test::key, RT_CHILD_PTR::local, RT_CHILDPTR_IS_VALUE, RT_GET_KEY_CHUNK, RT_NODE_SEARCH, RT_PTR_ALLOC, RT_PTR_ALLOC_IS_VALID, RT_PTR_SET_LOCAL, RT_SPAN, RT_VALUE_TYPE, and tree.

◆ RT_FREE()

RT_SCOPE void RT_FREE ( RT_RADIX_TREE *  tree)

Definition at line 2018 of file radixtree.h.

2019{
2020#ifdef RT_SHMEM
2021 Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2022
2023 /* Free all memory used for radix tree nodes */
2024 Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2025 RT_FREE_RECURSE(tree, tree->ctl->root, tree->ctl->start_shift);
2026
2027 /*
2028 * Vandalize the control block to help catch programming error where other
2029 * backends access the memory formerly occupied by this radix tree.
2030 */
2031 tree->ctl->magic = 0;
2032 dsa_free(tree->dsa, tree->ctl->handle);
2033#else
2034 /*
2035 * Free all space allocated within the leaf context and delete all child
2036 * contexts such as those used for nodes.
2037 */
2038 MemoryContextReset(tree->leaf_context);
2039
2040 pfree(tree->ctl);
2041#endif
2042 pfree(tree);
2043}
dsa_free
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:826
MemoryContextReset
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:383
RT_FREE_RECURSE
#define RT_FREE_RECURSE
Definition: radixtree.h:206

References Assert(), dsa_free(), MemoryContextReset(), pfree(), RT_FREE_RECURSE, RT_PTR_ALLOC_IS_VALID, and tree.

◆ RT_FREE_LEAF()

static void RT_FREE_LEAF ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC  leaf 
)
inlinestatic

Definition at line 956 of file radixtree.h.

957{
958 Assert(leaf != tree->ctl->root);
959
960#ifdef RT_DEBUG
961 /* update the statistics */
962 tree->ctl->num_leaves--;
963 Assert(tree->ctl->num_leaves >= 0);
964#endif
965
966#ifdef RT_SHMEM
967 dsa_free(tree->dsa, leaf);
968#else
969 pfree(leaf);
970#endif
971}

References Assert(), dsa_free(), pfree(), and tree.

◆ RT_FREE_NODE()

static void RT_FREE_NODE ( RT_RADIX_TREE *  tree,
RT_CHILD_PTR  node 
)
static

Definition at line 924 of file radixtree.h.

925{
926#ifdef RT_DEBUG
927 int i;
928
929 /* update the statistics */
930
931 for (i = 0; i < RT_NUM_SIZE_CLASSES; i++)
932 {
933 if ((node.local)->fanout == RT_SIZE_CLASS_INFO[i].fanout)
934 break;
935 }
936
937 /*
938 * The fanout of node256 will appear to be zero within the node header
939 * because of overflow, so we need an extra check here.
940 */
941 if (i == RT_NUM_SIZE_CLASSES)
942 i = RT_CLASS_256;
943
944 tree->ctl->num_nodes[i]--;
945 Assert(tree->ctl->num_nodes[i] >= 0);
946#endif
947
948#ifdef RT_SHMEM
949 dsa_free(tree->dsa, node.alloc);
950#else
951 pfree(node.alloc);
952#endif
953}
RT_NUM_SIZE_CLASSES
#define RT_NUM_SIZE_CLASSES
Definition: radixtree.h:678

References RT_CHILD_PTR::alloc, Assert(), dsa_free(), i, RT_CHILD_PTR::local, pfree(), RT_CLASS_256, RT_NUM_SIZE_CLASSES, RT_SIZE_CLASS_INFO, and tree.

◆ RT_GET_SLOT_RECURSIVE()

static RT_PTR_ALLOC * RT_GET_SLOT_RECURSIVE ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC *  parent_slot,
uint64  key,
int  shift,
bool *  found 
)
static

Definition at line 1660 of file radixtree.h.

1661{
1662 RT_PTR_ALLOC *slot;
1663 RT_CHILD_PTR node;
1664 uint8 chunk = RT_GET_KEY_CHUNK(key, shift);
1665
1666 node.alloc = *parent_slot;
1667 RT_PTR_SET_LOCAL(tree, &node);
1668 slot = RT_NODE_SEARCH(node.local, chunk);
1669
1670 if (slot == NULL)
1671 {
1672 *found = false;
1673
1674 /* reserve slot for the caller to populate */
1675
1676 slot = RT_NODE_INSERT(tree, parent_slot, node, chunk);
1677
1678 if (shift == 0)
1679 return slot;
1680 else
1681 return RT_EXTEND_DOWN(tree, slot, key, shift);
1682 }
1683 else
1684 {
1685 if (shift == 0)
1686 {
1687 *found = true;
1688 return slot;
1689 }
1690 else
1691 return RT_GET_SLOT_RECURSIVE(tree, slot, key, shift - RT_SPAN, found);
1692 }
1693}
uint8
uint8_t uint8
Definition: c.h:500
RT_GET_SLOT_RECURSIVE
#define RT_GET_SLOT_RECURSIVE
Definition: radixtree.h:200
RT_EXTEND_DOWN
#define RT_EXTEND_DOWN
Definition: radixtree.h:208
RT_NODE_INSERT
#define RT_NODE_INSERT
Definition: radixtree.h:226

References RT_CHILD_PTR::alloc, sort-test::key, RT_CHILD_PTR::local, RT_EXTEND_DOWN, RT_GET_KEY_CHUNK, RT_GET_SLOT_RECURSIVE, RT_NODE_INSERT, RT_NODE_SEARCH, RT_PTR_ALLOC, RT_PTR_SET_LOCAL, RT_SPAN, and tree.

◆ RT_GROW_NODE_16()

static pg_noinline RT_PTR_ALLOC * RT_GROW_NODE_16 ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC *  parent_slot,
RT_CHILD_PTR  node,
uint8  chunk 
)
static

Definition at line 1370 of file radixtree.h.

1372{
1373 RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
1374 int insertpos;
1375
1376 if (n16->base.fanout < RT_FANOUT_16_HI)
1377 {
1378 RT_CHILD_PTR newnode;
1379 RT_NODE_16 *new16;
1380
1381 Assert(n16->base.fanout == RT_FANOUT_16_LO);
1382
1383 /* initialize new node */
1384 newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_HI);
1385 new16 = (RT_NODE_16 *) newnode.local;
1386
1387 /* copy over existing entries */
1388 RT_COPY_COMMON(newnode, node);
1389 Assert(n16->base.count == RT_FANOUT_16_LO);
1390 insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
1391 RT_COPY_ARRAYS_FOR_INSERT(new16->chunks, new16->children,
1392 n16->chunks, n16->children,
1393 RT_FANOUT_16_LO, insertpos);
1394
1395 /* insert new chunk into place */
1396 new16->chunks[insertpos] = chunk;
1397
1398 new16->base.count++;
1399 RT_VERIFY_NODE((RT_NODE *) new16);
1400
1401 /* free old node and update references */
1402 RT_FREE_NODE(tree, node);
1403 *parent_slot = newnode.alloc;
1404
1405 return &new16->children[insertpos];
1406 }
1407 else
1408 {
1409 RT_CHILD_PTR newnode;
1410 RT_NODE_48 *new48;
1411 int idx,
1412 bit;
1413
1414 Assert(n16->base.fanout == RT_FANOUT_16_HI);
1415
1416 /* initialize new node */
1417 newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_48, RT_CLASS_48);
1418 new48 = (RT_NODE_48 *) newnode.local;
1419
1420 /* copy over the entries */
1421 RT_COPY_COMMON(newnode, node);
1422 for (int i = 0; i < RT_FANOUT_16_HI; i++)
1423 new48->slot_idxs[n16->chunks[i]] = i;
1424 memcpy(&new48->children[0], &n16->children[0], RT_FANOUT_16_HI * sizeof(new48->children[0]));
1425
1426 /*
1427 * Since we just copied a dense array, we can fill "isset" using a
1428 * single store, provided the length of that array is at most the
1429 * number of bits in a bitmapword.
1430 */
1431 Assert(RT_FANOUT_16_HI <= BITS_PER_BITMAPWORD);
1432 new48->isset[0] = (bitmapword) (((uint64) 1 << RT_FANOUT_16_HI) - 1);
1433
1434 /* put the new child at the end of the copied entries */
1435 insertpos = RT_FANOUT_16_HI;
1436 idx = RT_BM_IDX(insertpos);
1437 bit = RT_BM_BIT(insertpos);
1438
1439 /* mark the slot used */
1440 new48->isset[idx] |= ((bitmapword) 1 << bit);
1441
1442 /* insert new chunk into place */
1443 new48->slot_idxs[chunk] = insertpos;
1444
1445 new48->base.count++;
1446 RT_VERIFY_NODE((RT_NODE *) new48);
1447
1448 /* free old node and update reference in parent */
1449 *parent_slot = newnode.alloc;
1450 RT_FREE_NODE(tree, node);
1451
1452 return &new48->children[insertpos];
1453 }
1454}
uint64
uint64_t uint64
Definition: c.h:503
if
if(TABLE==NULL||TABLE_index==NULL)
Definition: isn.c:78
RT_COPY_ARRAYS_FOR_INSERT
#define RT_COPY_ARRAYS_FOR_INSERT
Definition: radixtree.h:216
RT_COPY_COMMON
#define RT_COPY_COMMON
Definition: radixtree.h:209
RT_FREE_NODE
#define RT_FREE_NODE
Definition: radixtree.h:204
RT_FANOUT_16_HI
#define RT_FANOUT_16_HI
Definition: radixtree.h:602
RT_FANOUT_16_LO
#define RT_FANOUT_16_LO
Definition: radixtree.h:600
bit
Datum bit(PG_FUNCTION_ARGS)
Definition: varbit.c:391

References RT_CHILD_PTR::alloc, Assert(), RT_NODE_16::base, RT_NODE_48::base, bit(), BITS_PER_BITMAPWORD, RT_NODE_16::children, RT_NODE_48::children, RT_NODE_16::chunks, RT_NODE::count, RT_NODE::fanout, i, idx(), if(), RT_NODE_48::isset, RT_CHILD_PTR::local, RT_ALLOC_NODE, RT_BM_BIT, RT_BM_IDX, RT_CLASS_16_HI, RT_CLASS_48, RT_COPY_ARRAYS_FOR_INSERT, RT_COPY_COMMON, RT_FANOUT_16_HI, RT_FANOUT_16_LO, RT_FREE_NODE, RT_NODE_16_GET_INSERTPOS, RT_NODE_KIND_16, RT_NODE_KIND_48, RT_VERIFY_NODE, RT_NODE_48::slot_idxs, and tree.

◆ RT_GROW_NODE_4()

static pg_noinline RT_PTR_ALLOC * RT_GROW_NODE_4 ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC *  parent_slot,
RT_CHILD_PTR  node,
uint8  chunk 
)
static

Definition at line 1476 of file radixtree.h.

1478{
1479 RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
1480 RT_CHILD_PTR newnode;
1481 RT_NODE_16 *new16;
1482 int insertpos;
1483
1484 /* initialize new node */
1485 newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_LO);
1486 new16 = (RT_NODE_16 *) newnode.local;
1487
1488 /* copy over existing entries */
1489 RT_COPY_COMMON(newnode, node);
1490 Assert(n4->base.count == RT_FANOUT_4);
1491 insertpos = RT_NODE_4_GET_INSERTPOS(n4, chunk, RT_FANOUT_4);
1492 RT_COPY_ARRAYS_FOR_INSERT(new16->chunks, new16->children,
1493 n4->chunks, n4->children,
1494 RT_FANOUT_4, insertpos);
1495
1496 /* insert new chunk into place */
1497 new16->chunks[insertpos] = chunk;
1498
1499 new16->base.count++;
1500 RT_VERIFY_NODE((RT_NODE *) new16);
1501
1502 /* free old node and update reference in parent */
1503 *parent_slot = newnode.alloc;
1504 RT_FREE_NODE(tree, node);
1505
1506 return &new16->children[insertpos];
1507}
RT_FANOUT_4
#define RT_FANOUT_4
Definition: radixtree.h:613

References RT_CHILD_PTR::alloc, Assert(), RT_NODE_4::base, RT_NODE_16::base, RT_NODE_4::children, RT_NODE_16::children, RT_NODE_16::chunks, RT_NODE_4::chunks, RT_NODE::count, RT_CHILD_PTR::local, RT_ALLOC_NODE, RT_CLASS_16_LO, RT_COPY_ARRAYS_FOR_INSERT, RT_COPY_COMMON, RT_FANOUT_4, RT_FREE_NODE, RT_NODE_4_GET_INSERTPOS, RT_NODE_KIND_16, RT_VERIFY_NODE, and tree.

◆ RT_GROW_NODE_48()

static pg_noinline RT_PTR_ALLOC * RT_GROW_NODE_48 ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC *  parent_slot,
RT_CHILD_PTR  node,
uint8  chunk 
)
static

Definition at line 1285 of file radixtree.h.

1287{
1288 RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
1289 RT_CHILD_PTR newnode;
1290 RT_NODE_256 *new256;
1291 int i = 0;
1292
1293 /* initialize new node */
1294 newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_256, RT_CLASS_256);
1295 new256 = (RT_NODE_256 *) newnode.local;
1296
1297 /* copy over the entries */
1298 RT_COPY_COMMON(newnode, node);
1299 for (int word_num = 0; word_num < RT_BM_IDX(RT_NODE_MAX_SLOTS); word_num++)
1300 {
1301 bitmapword bitmap = 0;
1302
1303 /*
1304 * Bit manipulation is a surprisingly large portion of the overhead in
1305 * the naive implementation. Doing stores word-at-a-time removes a lot
1306 * of that overhead.
1307 */
1308 for (int bit = 0; bit < BITS_PER_BITMAPWORD; bit++)
1309 {
1310 uint8 offset = n48->slot_idxs[i];
1311
1312 if (offset != RT_INVALID_SLOT_IDX)
1313 {
1314 bitmap |= ((bitmapword) 1 << bit);
1315 new256->children[i] = n48->children[offset];
1316 }
1317
1318 i++;
1319 }
1320
1321 new256->isset[word_num] = bitmap;
1322 }
1323
1324 /* free old node and update reference in parent */
1325 *parent_slot = newnode.alloc;
1326 RT_FREE_NODE(tree, node);
1327
1328 return RT_ADD_CHILD_256(tree, newnode, chunk);
1329}
RT_NODE_MAX_SLOTS
#define RT_NODE_MAX_SLOTS
Definition: radixtree.h:320
RT_ADD_CHILD_256
#define RT_ADD_CHILD_256
Definition: radixtree.h:230

References bit(), BITS_PER_BITMAPWORD, RT_NODE_48::children, i, RT_CHILD_PTR::local, RT_ADD_CHILD_256, RT_ALLOC_NODE, RT_BM_IDX, RT_CLASS_256, RT_COPY_COMMON, RT_FREE_NODE, RT_INVALID_SLOT_IDX, RT_NODE_KIND_256, RT_NODE_MAX_SLOTS, RT_NODE_48::slot_idxs, and tree.

◆ RT_ITERATE_NEXT()

RT_SCOPE RT_VALUE_TYPE * RT_ITERATE_NEXT ( RT_ITER *  iter,
uint64 *  key_p 
)

Definition at line 2178 of file radixtree.h.

2179{
2180 RT_PTR_ALLOC *slot = NULL;
2181
2182 while (iter->cur_level <= iter->top_level)
2183 {
2184 RT_CHILD_PTR node;
2185
2186 slot = RT_NODE_ITERATE_NEXT(iter, iter->cur_level);
2187
2188 if (iter->cur_level == 0 && slot != NULL)
2189 {
2190 /* Found a value at the leaf node */
2191 *key_p = iter->key;
2192 node.alloc = *slot;
2193
2194 if (RT_CHILDPTR_IS_VALUE(*slot))
2195 return (RT_VALUE_TYPE *) slot;
2196 else
2197 {
2198 RT_PTR_SET_LOCAL(iter->tree, &node);
2199 return (RT_VALUE_TYPE *) node.local;
2200 }
2201 }
2202
2203 if (slot != NULL)
2204 {
2205 /* Found the child slot, move down the tree */
2206 node.alloc = *slot;
2207 RT_PTR_SET_LOCAL(iter->tree, &node);
2208
2209 iter->cur_level--;
2210 iter->node_iters[iter->cur_level].node = node;
2211 iter->node_iters[iter->cur_level].idx = 0;
2212 }
2213 else
2214 {
2215 /* Not found the child slot, move up the tree */
2216 iter->cur_level++;
2217 }
2218 }
2219
2220 /* We've visited all nodes, so the iteration finished */
2221 return NULL;
2222}
RT_NODE_ITERATE_NEXT
#define RT_NODE_ITERATE_NEXT
Definition: radixtree.h:241
RT_ITER::key
uint64 key
Definition: radixtree.h:756

References RT_CHILD_PTR::alloc, RT_ITER::cur_level, RT_NODE_ITER::idx, RT_ITER::key, RT_CHILD_PTR::local, RT_NODE_ITER::node, RT_ITER::node_iters, RT_CHILDPTR_IS_VALUE, RT_NODE_ITERATE_NEXT, RT_PTR_ALLOC, RT_PTR_SET_LOCAL, RT_VALUE_TYPE, RT_ITER::top_level, and RT_ITER::tree.

◆ RT_KEY_GET_SHIFT()

static int RT_KEY_GET_SHIFT ( uint64  key)
inlinestatic

Definition at line 807 of file radixtree.h.

808{
809 if (key == 0)
810 return 0;
811 else
812 return (pg_leftmost_one_pos64(key) / RT_SPAN) * RT_SPAN;
813}
pg_leftmost_one_pos64
static int pg_leftmost_one_pos64(uint64 word)
Definition: pg_bitutils.h:72

References sort-test::key, pg_leftmost_one_pos64(), and RT_SPAN.

◆ RT_MEMORY_USAGE()

RT_SCOPE uint64 RT_MEMORY_USAGE ( RT_RADIX_TREE *  tree)

Definition at line 2648 of file radixtree.h.

2649{
2650 size_t total = 0;
2651
2652#ifdef RT_SHMEM
2653 Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2654 total = dsa_get_total_size(tree->dsa);
2655#else
2656 total = MemoryContextMemAllocated(tree->leaf_context, true);
2657#endif
2658
2659 return total;
2660}
dsa_get_total_size
size_t dsa_get_total_size(dsa_area *area)
Definition: dsa.c:1027
MemoryContextMemAllocated
Size MemoryContextMemAllocated(MemoryContext context, bool recurse)
Definition: mcxt.c:762

References Assert(), dsa_get_total_size(), MemoryContextMemAllocated(), and tree.

◆ RT_NODE_16_GET_INSERTPOS()

static int RT_NODE_16_GET_INSERTPOS ( RT_NODE_16 *  node,
uint8  chunk 
)
inlinestatic

Definition at line 1157 of file radixtree.h.

1158{
1159 int count = node->base.count;
1160#if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
1161 int index;
1162#endif
1163
1164#ifndef USE_NO_SIMD
1165 Vector8 spread_chunk;
1166 Vector8 haystack1;
1167 Vector8 haystack2;
1168 Vector8 cmp1;
1169 Vector8 cmp2;
1170 Vector8 min1;
1171 Vector8 min2;
1172 uint32 bitfield;
1173 int index_simd;
1174#endif
1175
1176 /*
1177 * First compare the last element. There are two reasons to branch here:
1178 *
1179 * 1) A realistic pattern is inserting ordered keys. In that case,
1180 * non-SIMD platforms must do a linear search to the last chunk to find
1181 * the insert position. This will get slower as the node fills up.
1182 *
1183 * 2) On SIMD platforms, we must branch anyway to make sure we don't bit
1184 * scan an empty bitfield. Doing the branch here eliminates some work that
1185 * we might otherwise throw away.
1186 */
1187 Assert(count > 0);
1188 if (node->chunks[count - 1] < chunk)
1189 return count;
1190
1191#if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
1192
1193 for (index = 0; index < count; index++)
1194 {
1195 if (node->chunks[index] > chunk)
1196 break;
1197 }
1198#endif
1199
1200#ifndef USE_NO_SIMD
1201
1202 /*
1203 * This is a bit more complicated than RT_NODE_16_SEARCH_EQ(), because no
1204 * unsigned uint8 comparison instruction exists, at least for SSE2. So we
1205 * need to play some trickery using vector8_min() to effectively get >=.
1206 * There'll never be any equal elements in current uses, but that's what
1207 * we get here...
1208 */
1209 spread_chunk = vector8_broadcast(chunk);
1210 vector8_load(&haystack1, &node->chunks[0]);
1211 vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
1212 min1 = vector8_min(spread_chunk, haystack1);
1213 min2 = vector8_min(spread_chunk, haystack2);
1214 cmp1 = vector8_eq(spread_chunk, min1);
1215 cmp2 = vector8_eq(spread_chunk, min2);
1216 bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));
1217
1218 Assert((bitfield & ((UINT64CONST(1) << count) - 1)) != 0);
1219 index_simd = pg_rightmost_one_pos32(bitfield);
1220
1221 Assert(index_simd == index);
1222 return index_simd;
1223#else
1224 return index;
1225#endif
1226}
uint32
uint32_t uint32
Definition: c.h:502
UINT64CONST
#define UINT64CONST(x)
Definition: c.h:517
pg_rightmost_one_pos32
static int pg_rightmost_one_pos32(uint32 word)
Definition: pg_bitutils.h:111
vector8_broadcast
static Vector8 vector8_broadcast(const uint8 c)
Definition: simd.h:135
vector8_load
static void vector8_load(Vector8 *v, const uint8 *s)
Definition: simd.h:108
Vector8
uint64 Vector8
Definition: simd.h:60
index
Definition: type.h:96

References Assert(), RT_NODE_16::base, RT_NODE_16::chunks, RT_NODE::count, pg_rightmost_one_pos32(), UINT64CONST, vector8_broadcast(), and vector8_load().

◆ RT_NODE_16_SEARCH_EQ()

static RT_PTR_ALLOC * RT_NODE_16_SEARCH_EQ ( RT_NODE_16 *  node,
uint8  chunk 
)
inlinestatic

Definition at line 980 of file radixtree.h.

981{
982 int count = node->base.count;
983#ifndef USE_NO_SIMD
984 Vector8 spread_chunk;
985 Vector8 haystack1;
986 Vector8 haystack2;
987 Vector8 cmp1;
988 Vector8 cmp2;
989 uint32 bitfield;
990 RT_PTR_ALLOC *slot_simd = NULL;
991#endif
992
993#if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
994 RT_PTR_ALLOC *slot = NULL;
995
996 for (int i = 0; i < count; i++)
997 {
998 if (node->chunks[i] == chunk)
999 {
1000 slot = &node->children[i];
1001 break;
1002 }
1003 }
1004#endif
1005
1006#ifndef USE_NO_SIMD
1007 /* replicate the search key */
1008 spread_chunk = vector8_broadcast(chunk);
1009
1010 /* compare to all 32 keys stored in the node */
1011 vector8_load(&haystack1, &node->chunks[0]);
1012 vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
1013 cmp1 = vector8_eq(spread_chunk, haystack1);
1014 cmp2 = vector8_eq(spread_chunk, haystack2);
1015
1016 /* convert comparison to a bitfield */
1017 bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));
1018
1019 /* mask off invalid entries */
1020 bitfield &= ((UINT64CONST(1) << count) - 1);
1021
1022 /* convert bitfield to index by counting trailing zeros */
1023 if (bitfield)
1024 slot_simd = &node->children[pg_rightmost_one_pos32(bitfield)];
1025
1026 Assert(slot_simd == slot);
1027 return slot_simd;
1028#else
1029 return slot;
1030#endif
1031}

References Assert(), RT_NODE_16::base, RT_NODE_16::children, RT_NODE_16::chunks, RT_NODE::count, i, pg_rightmost_one_pos32(), RT_PTR_ALLOC, UINT64CONST, vector8_broadcast(), and vector8_load().

◆ RT_NODE_256_GET_CHILD()

static RT_PTR_ALLOC * RT_NODE_256_GET_CHILD ( RT_NODE_256 *  node,
uint8  chunk 
)
inlinestatic

Definition at line 797 of file radixtree.h.

798{
799 Assert(RT_NODE_256_IS_CHUNK_USED(node, chunk));
800 return &node->children[chunk];
801}
RT_NODE_256_IS_CHUNK_USED
#define RT_NODE_256_IS_CHUNK_USED
Definition: radixtree.h:220
RT_NODE_256::children
RT_PTR_ALLOC children[RT_FANOUT_256]
Definition: radixtree.h:576

References Assert(), RT_NODE_256::children, and RT_NODE_256_IS_CHUNK_USED.

◆ RT_NODE_256_IS_CHUNK_USED()

static bool RT_NODE_256_IS_CHUNK_USED ( RT_NODE_256 *  node,
uint8  chunk 
)
inlinestatic

Definition at line 788 of file radixtree.h.

789{
790 int idx = RT_BM_IDX(chunk);
791 int bitnum = RT_BM_BIT(chunk);
792
793 return (node->isset[idx] & ((bitmapword) 1 << bitnum)) != 0;
794}

References idx(), RT_NODE_256::isset, RT_BM_BIT, and RT_BM_IDX.

◆ RT_NODE_48_GET_CHILD()

static RT_PTR_ALLOC * RT_NODE_48_GET_CHILD ( RT_NODE_48 *  node,
uint8  chunk 
)
inlinestatic

Definition at line 781 of file radixtree.h.

782{
783 return &node->children[node->slot_idxs[chunk]];
784}

References RT_NODE_48::children, and RT_NODE_48::slot_idxs.

◆ RT_NODE_48_IS_CHUNK_USED()

static bool RT_NODE_48_IS_CHUNK_USED ( RT_NODE_48 *  node,
uint8  chunk 
)
inlinestatic

Definition at line 775 of file radixtree.h.

776{
777 return node->slot_idxs[chunk] != RT_INVALID_SLOT_IDX;
778}

References RT_INVALID_SLOT_IDX, and RT_NODE_48::slot_idxs.

◆ RT_NODE_4_GET_INSERTPOS()

static int RT_NODE_4_GET_INSERTPOS ( RT_NODE_4 *  node,
uint8  chunk,
int  count 
)
inlinestatic

Definition at line 1139 of file radixtree.h.

1140{
1141 int idx;
1142
1143 for (idx = 0; idx < count; idx++)
1144 {
1145 if (node->chunks[idx] >= chunk)
1146 break;
1147 }
1148
1149 return idx;
1150}

References RT_NODE_4::chunks, and idx().

◆ RT_NODE_INSERT()

static RT_PTR_ALLOC * RT_NODE_INSERT ( RT_RADIX_TREE *  tree,
RT_PTR_ALLOC *  parent_slot,
RT_CHILD_PTR  node,
uint8  chunk 
)
inlinestatic

Definition at line 1538 of file radixtree.h.

1540{
1541 RT_NODE *n = node.local;
1542
1543 switch (n->kind)
1544 {
1545 case RT_NODE_KIND_4:
1546 {
1547 if (unlikely(RT_NODE_MUST_GROW(n)))
1548 return RT_GROW_NODE_4(tree, parent_slot, node, chunk);
1549
1550 return RT_ADD_CHILD_4(tree, node, chunk);
1551 }
1552 case RT_NODE_KIND_16:
1553 {
1554 if (unlikely(RT_NODE_MUST_GROW(n)))
1555 return RT_GROW_NODE_16(tree, parent_slot, node, chunk);
1556
1557 return RT_ADD_CHILD_16(tree, node, chunk);
1558 }
1559 case RT_NODE_KIND_48:
1560 {
1561 if (unlikely(RT_NODE_MUST_GROW(n)))
1562 return RT_GROW_NODE_48(tree, parent_slot, node, chunk);
1563
1564 return RT_ADD_CHILD_48(tree, node, chunk);
1565 }
1566 case RT_NODE_KIND_256:
1567 return RT_ADD_CHILD_256(tree, node, chunk);
1568 default:
1569 pg_unreachable();
1570 }
1571}
unlikely
#define unlikely(x)
Definition: c.h:347
RT_ADD_CHILD_48
#define RT_ADD_CHILD_48
Definition: radixtree.h:229
RT_GROW_NODE_4
#define RT_GROW_NODE_4
Definition: radixtree.h:231
RT_ADD_CHILD_16
#define RT_ADD_CHILD_16
Definition: radixtree.h:228
RT_NODE_MUST_GROW
#define RT_NODE_MUST_GROW(node)
Definition: radixtree.h:1131
RT_ADD_CHILD_4
#define RT_ADD_CHILD_4
Definition: radixtree.h:227
RT_GROW_NODE_16
#define RT_GROW_NODE_16
Definition: radixtree.h:232
RT_GROW_NODE_48
#define RT_GROW_NODE_48
Definition: radixtree.h:233

References RT_NODE::kind, RT_CHILD_PTR::local, pg_unreachable, RT_ADD_CHILD_16, RT_ADD_CHILD_256, RT_ADD_CHILD_4, RT_ADD_CHILD_48, RT_GROW_NODE_16, RT_GROW_NODE_4, RT_GROW_NODE_48, RT_NODE_KIND_16, RT_NODE_KIND_256, RT_NODE_KIND_4, RT_NODE_KIND_48, RT_NODE_MUST_GROW, tree, and unlikely.

◆ RT_NODE_ITERATE_NEXT()

static RT_PTR_ALLOC * RT_NODE_ITERATE_NEXT ( RT_ITER *  iter,
int  level 
)
inlinestatic

Definition at line 2082 of file radixtree.h.

2083{
2084 uint8 key_chunk = 0;
2085 RT_NODE_ITER *node_iter;
2086 RT_CHILD_PTR node;
2087 RT_PTR_ALLOC *slot = NULL;
2088
2089#ifdef RT_SHMEM
2090 Assert(iter->tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2091#endif
2092
2093 node_iter = &(iter->node_iters[level]);
2094 node = node_iter->node;
2095
2096 Assert(node.local != NULL);
2097
2098 switch ((node.local)->kind)
2099 {
2100 case RT_NODE_KIND_4:
2101 {
2102 RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
2103
2104 if (node_iter->idx >= n4->base.count)
2105 return NULL;
2106
2107 slot = &n4->children[node_iter->idx];
2108 key_chunk = n4->chunks[node_iter->idx];
2109 node_iter->idx++;
2110 break;
2111 }
2112 case RT_NODE_KIND_16:
2113 {
2114 RT_NODE_16 *n16 = (RT_NODE_16 *) (node.local);
2115
2116 if (node_iter->idx >= n16->base.count)
2117 return NULL;
2118
2119 slot = &n16->children[node_iter->idx];
2120 key_chunk = n16->chunks[node_iter->idx];
2121 node_iter->idx++;
2122 break;
2123 }
2124 case RT_NODE_KIND_48:
2125 {
2126 RT_NODE_48 *n48 = (RT_NODE_48 *) (node.local);
2127 int chunk;
2128
2129 for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
2130 {
2131 if (RT_NODE_48_IS_CHUNK_USED(n48, chunk))
2132 break;
2133 }
2134
2135 if (chunk >= RT_NODE_MAX_SLOTS)
2136 return NULL;
2137
2138 slot = RT_NODE_48_GET_CHILD(n48, chunk);
2139
2140 key_chunk = chunk;
2141 node_iter->idx = chunk + 1;
2142 break;
2143 }
2144 case RT_NODE_KIND_256:
2145 {
2146 RT_NODE_256 *n256 = (RT_NODE_256 *) (node.local);
2147 int chunk;
2148
2149 for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
2150 {
2151 if (RT_NODE_256_IS_CHUNK_USED(n256, chunk))
2152 break;
2153 }
2154
2155 if (chunk >= RT_NODE_MAX_SLOTS)
2156 return NULL;
2157
2158 slot = RT_NODE_256_GET_CHILD(n256, chunk);
2159
2160 key_chunk = chunk;
2161 node_iter->idx = chunk + 1;
2162 break;
2163 }
2164 }
2165
2166 /* Update the key */
2167 iter->key &= ~(((uint64) RT_CHUNK_MASK) << (level * RT_SPAN));
2168 iter->key |= (((uint64) key_chunk) << (level * RT_SPAN));
2169
2170 return slot;
2171}
RT_NODE_48_GET_CHILD
#define RT_NODE_48_GET_CHILD
Definition: radixtree.h:219
RT_NODE_48_IS_CHUNK_USED
#define RT_NODE_48_IS_CHUNK_USED
Definition: radixtree.h:218
RT_CHUNK_MASK
#define RT_CHUNK_MASK
Definition: radixtree.h:323
RT_NODE_ITER
Definition: radixtree.h:731

References Assert(), RT_NODE_4::base, RT_NODE_16::base, RT_NODE_4::children, RT_NODE_16::children, RT_NODE_16::chunks, RT_NODE_4::chunks, RT_NODE::count, RT_RADIX_TREE::ctl, RT_NODE_ITER::idx, RT_ITER::key, RT_CHILD_PTR::local, RT_NODE_ITER::node, RT_ITER::node_iters, RT_CHUNK_MASK, RT_NODE_256_GET_CHILD, RT_NODE_256_IS_CHUNK_USED, RT_NODE_48_GET_CHILD, RT_NODE_48_IS_CHUNK_USED, RT_NODE_KIND_16, RT_NODE_KIND_256, RT_NODE_KIND_4, RT_NODE_KIND_48, RT_NODE_MAX_SLOTS, RT_PTR_ALLOC, RT_SPAN, and RT_ITER::tree.

◆ RT_NODE_SEARCH()

static RT_PTR_ALLOC * RT_NODE_SEARCH ( RT_NODE *  node,
uint8  chunk 
)
inlinestatic

Definition at line 1039 of file radixtree.h.

1040{
1041 /* Make sure we already converted to local pointer */
1042 Assert(node != NULL);
1043
1044 switch (node->kind)
1045 {
1046 case RT_NODE_KIND_4:
1047 {
1048 RT_NODE_4 *n4 = (RT_NODE_4 *) node;
1049
1050 for (int i = 0; i < n4->base.count; i++)
1051 {
1052 if (n4->chunks[i] == chunk)
1053 return &n4->children[i];
1054 }
1055 return NULL;
1056 }
1057 case RT_NODE_KIND_16:
1058 return RT_NODE_16_SEARCH_EQ((RT_NODE_16 *) node, chunk);
1059 case RT_NODE_KIND_48:
1060 {
1061 RT_NODE_48 *n48 = (RT_NODE_48 *) node;
1062 int slotpos = n48->slot_idxs[chunk];
1063
1064 if (slotpos == RT_INVALID_SLOT_IDX)
1065 return NULL;
1066
1067 return RT_NODE_48_GET_CHILD(n48, chunk);
1068 }
1069 case RT_NODE_KIND_256:
1070 {
1071 RT_NODE_256 *n256 = (RT_NODE_256 *) node;
1072
1073 if (!RT_NODE_256_IS_CHUNK_USED(n256, chunk))
1074 return NULL;
1075
1076 return RT_NODE_256_GET_CHILD(n256, chunk);
1077 }
1078 default:
1079 pg_unreachable();
1080 }
1081}
RT_NODE_16_SEARCH_EQ
#define RT_NODE_16_SEARCH_EQ
Definition: radixtree.h:211

References Assert(), RT_NODE_4::base, RT_NODE_4::children, RT_NODE_4::chunks, RT_NODE::count, i, RT_NODE::kind, pg_unreachable, RT_INVALID_SLOT_IDX, RT_NODE_16_SEARCH_EQ, RT_NODE_256_GET_CHILD, RT_NODE_256_IS_CHUNK_USED, RT_NODE_48_GET_CHILD, RT_NODE_KIND_16, RT_NODE_KIND_256, RT_NODE_KIND_4, RT_NODE_KIND_48, and RT_NODE_48::slot_idxs.

◆ RT_PTR_SET_LOCAL()

static void RT_PTR_SET_LOCAL ( RT_RADIX_TREE *  tree,
RT_CHILD_PTR *  node 
)
inlinestatic

Definition at line 764 of file radixtree.h.

765{
766#ifdef RT_SHMEM
767 node->local = dsa_get_address(tree->dsa, node->alloc);
768#endif
769}
dsa_get_address
void * dsa_get_address(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:942

References RT_CHILD_PTR::alloc, dsa_get_address(), RT_CHILD_PTR::local, and tree.

◆ RT_SET()

RT_SCOPE bool RT_SET ( RT_RADIX_TREE *  tree,
uint64  key,
RT_VALUE_TYPE *  value_p 
)

Definition at line 1702 of file radixtree.h.

1703{
1704 bool found;
1705 RT_PTR_ALLOC *slot;
1706 size_t value_sz = RT_GET_VALUE_SIZE(value_p);
1707
1708#ifdef RT_SHMEM
1709 Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
1710#endif
1711
1712 Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
1713
1714 /* Extend the tree if necessary */
1715 if (unlikely(key > tree->ctl->max_val))
1716 {
1717 if (tree->ctl->num_keys == 0)
1718 {
1719 RT_CHILD_PTR node;
1720 RT_NODE_4 *n4;
1721 int start_shift = RT_KEY_GET_SHIFT(key);
1722
1723 /*
1724 * With an empty root node, we don't extend the tree upwards,
1725 * since that would result in orphan empty nodes. Instead we open
1726 * code inserting into the root node and extend downward from
1727 * there.
1728 */
1729 node.alloc = tree->ctl->root;
1730 RT_PTR_SET_LOCAL(tree, &node);
1731 n4 = (RT_NODE_4 *) node.local;
1732 n4->base.count = 1;
1733 n4->chunks[0] = RT_GET_KEY_CHUNK(key, start_shift);
1734
1735 slot = RT_EXTEND_DOWN(tree, &n4->children[0], key, start_shift);
1736 found = false;
1737 tree->ctl->start_shift = start_shift;
1738 tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(start_shift);
1739 goto have_slot;
1740 }
1741 else
1742 RT_EXTEND_UP(tree, key);
1743 }
1744
1745 slot = RT_GET_SLOT_RECURSIVE(tree, &tree->ctl->root,
1746 key, tree->ctl->start_shift, &found);
1747
1748have_slot:
1749 Assert(slot != NULL);
1750
1751 if (RT_VALUE_IS_EMBEDDABLE(value_p))
1752 {
1753 /* free the existing leaf */
1754 if (found && !RT_CHILDPTR_IS_VALUE(*slot))
1755 RT_FREE_LEAF(tree, *slot);
1756
1757 /* store value directly in child pointer slot */
1758 memcpy(slot, value_p, value_sz);
1759
1760#ifdef RT_RUNTIME_EMBEDDABLE_VALUE
1761 /* tag child pointer */
1762#ifdef RT_SHMEM
1763 *slot |= 1;
1764#else
1765 *((uintptr_t *) slot) |= 1;
1766#endif
1767#endif
1768 }
1769 else
1770 {
1771 RT_CHILD_PTR leaf;
1772
1773 if (found && !RT_CHILDPTR_IS_VALUE(*slot))
1774 {
1775 Assert(RT_PTR_ALLOC_IS_VALID(*slot));
1776 leaf.alloc = *slot;
1777 RT_PTR_SET_LOCAL(tree, &leaf);
1778
1779 if (RT_GET_VALUE_SIZE((RT_VALUE_TYPE *) leaf.local) != value_sz)
1780 {
1781 /*
1782 * different sizes, so first free the existing leaf before
1783 * allocating a new one
1784 */
1785 RT_FREE_LEAF(tree, *slot);
1786 leaf = RT_ALLOC_LEAF(tree, value_sz);
1787 *slot = leaf.alloc;
1788 }
1789 }
1790 else
1791 {
1792 /* allocate new leaf and store it in the child array */
1793 leaf = RT_ALLOC_LEAF(tree, value_sz);
1794 *slot = leaf.alloc;
1795 }
1796
1797 memcpy(leaf.local, value_p, value_sz);
1798 }
1799
1800 /* Update the statistics */
1801 if (!found)
1802 tree->ctl->num_keys++;
1803
1804 return found;
1805}
RT_ALLOC_LEAF
#define RT_ALLOC_LEAF
Definition: radixtree.h:203
RT_VALUE_IS_EMBEDDABLE
#define RT_VALUE_IS_EMBEDDABLE
Definition: radixtree.h:199
start_shift
tree ctl start_shift
Definition: radixtree.h:1858
RT_GET_VALUE_SIZE
#define RT_GET_VALUE_SIZE(v)
Definition: radixtree.h:433
RT_EXTEND_UP
#define RT_EXTEND_UP
Definition: radixtree.h:207
RT_FREE_LEAF
#define RT_FREE_LEAF
Definition: radixtree.h:205

References RT_CHILD_PTR::alloc, Assert(), RT_NODE_4::base, RT_NODE_4::children, RT_NODE_4::chunks, RT_NODE::count, sort-test::key, RT_CHILD_PTR::local, RT_ALLOC_LEAF, RT_CHILDPTR_IS_VALUE, RT_EXTEND_DOWN, RT_EXTEND_UP, RT_FREE_LEAF, RT_GET_KEY_CHUNK, RT_GET_SLOT_RECURSIVE, RT_GET_VALUE_SIZE, RT_KEY_GET_SHIFT, RT_PTR_ALLOC, RT_PTR_ALLOC_IS_VALID, RT_PTR_SET_LOCAL, RT_SHIFT_GET_MAX_VAL, RT_VALUE_IS_EMBEDDABLE, RT_VALUE_TYPE, start_shift, tree, and unlikely.

◆ RT_SHIFT_ARRAYS_FOR_INSERT()

static void RT_SHIFT_ARRAYS_FOR_INSERT ( uint8 *  chunks,
RT_PTR_ALLOC *  children,
int  count,
int  insertpos 
)
inlinestatic

Definition at line 1230 of file radixtree.h.

1231{
1232 /*
1233 * This is basically a memmove, but written in a simple loop for speed on
1234 * small inputs.
1235 */
1236 for (int i = count - 1; i >= insertpos; i--)
1237 {
1238 /* workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101481 */
1239#ifdef __GNUC__
1240 __asm__("");
1241#endif
1242 chunks[i + 1] = chunks[i];
1243 children[i + 1] = children[i];
1244 }
1245}

References i.

◆ RT_SHIFT_GET_MAX_VAL()

static uint64 RT_SHIFT_GET_MAX_VAL ( int  shift)
static

Definition at line 819 of file radixtree.h.

820{
821 if (shift == RT_MAX_SHIFT)
822 return UINT64_MAX;
823 else
824 return (UINT64CONST(1) << (shift + RT_SPAN)) - 1;
825}
RT_MAX_SHIFT
#define RT_MAX_SHIFT
Definition: radixtree.h:326

References RT_MAX_SHIFT, RT_SPAN, and UINT64CONST.

◆ RT_VALUE_IS_EMBEDDABLE()

static bool RT_VALUE_IS_EMBEDDABLE ( RT_VALUE_TYPE *  value_p)
inlinestatic

Definition at line 443 of file radixtree.h.

444{
445#ifdef RT_VARLEN_VALUE_SIZE
446
447#ifdef RT_RUNTIME_EMBEDDABLE_VALUE
448 return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC);
449#else
450 return false;
451#endif
452
453#else
454 return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC);
455#endif
456}

References RT_GET_VALUE_SIZE, and RT_PTR_ALLOC.

◆ RT_VERIFY_NODE()

static void RT_VERIFY_NODE ( RT_NODE *  node)
static

Definition at line 2666 of file radixtree.h.

2667{
2668#ifdef USE_ASSERT_CHECKING
2669
2670 switch (node->kind)
2671 {
2672 case RT_NODE_KIND_4:
2673 {
2674 RT_NODE_4 *n4 = (RT_NODE_4 *) node;
2675
2676 /* RT_DUMP_NODE(node); */
2677
2678 for (int i = 1; i < n4->base.count; i++)
2679 Assert(n4->chunks[i - 1] < n4->chunks[i]);
2680
2681 break;
2682 }
2683 case RT_NODE_KIND_16:
2684 {
2685 RT_NODE_16 *n16 = (RT_NODE_16 *) node;
2686
2687 /* RT_DUMP_NODE(node); */
2688
2689 for (int i = 1; i < n16->base.count; i++)
2690 Assert(n16->chunks[i - 1] < n16->chunks[i]);
2691
2692 break;
2693 }
2694 case RT_NODE_KIND_48:
2695 {
2696 RT_NODE_48 *n48 = (RT_NODE_48 *) node;
2697 int cnt = 0;
2698
2699 /* RT_DUMP_NODE(node); */
2700
2701 for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
2702 {
2703 uint8 slot = n48->slot_idxs[i];
2704 int idx = RT_BM_IDX(slot);
2705 int bitnum = RT_BM_BIT(slot);
2706
2707 if (!RT_NODE_48_IS_CHUNK_USED(n48, i))
2708 continue;
2709
2710 /* Check if the corresponding slot is used */
2711 Assert(slot < node->fanout);
2712 Assert((n48->isset[idx] & ((bitmapword) 1 << bitnum)) != 0);
2713
2714 cnt++;
2715 }
2716
2717 Assert(n48->base.count == cnt);
2718
2719 break;
2720 }
2721 case RT_NODE_KIND_256:
2722 {
2723 RT_NODE_256 *n256 = (RT_NODE_256 *) node;
2724 int cnt = 0;
2725
2726 /* RT_DUMP_NODE(node); */
2727
2728 for (int i = 0; i < RT_BM_IDX(RT_NODE_MAX_SLOTS); i++)
2729 cnt += bmw_popcount(n256->isset[i]);
2730
2731 /*
2732 * Check if the number of used chunk matches, accounting for
2733 * overflow
2734 */
2735 if (cnt == RT_FANOUT_256)
2736 Assert(n256->base.count == 0);
2737 else
2738 Assert(n256->base.count == cnt);
2739
2740 break;
2741 }
2742 }
2743#endif
2744}
bmw_popcount
#define bmw_popcount(w)
Definition: bitmapset.h:80
RT_FANOUT_256
#define RT_FANOUT_256
Definition: radixtree.h:506

References Assert(), RT_NODE_4::base, RT_NODE_16::base, RT_NODE_48::base, RT_NODE_256::base, bmw_popcount, RT_NODE_16::chunks, RT_NODE_4::chunks, RT_NODE::count, i, idx(), RT_NODE_256::isset, RT_NODE_48::isset, RT_NODE::kind, RT_BM_BIT, RT_BM_IDX, RT_FANOUT_256, RT_NODE_48_IS_CHUNK_USED, RT_NODE_KIND_16, RT_NODE_KIND_256, RT_NODE_KIND_4, RT_NODE_KIND_48, RT_NODE_MAX_SLOTS, and RT_NODE_48::slot_idxs.

◆ StaticAssertDecl() [1/3]

StaticAssertDecl ( )

◆ StaticAssertDecl() [2/3]

StaticAssertDecl ( RT_FANOUT_48<=  RT_FANOUT_48_MAX,
"more slots than isset bits"   
)

◆ StaticAssertDecl() [3/3]

StaticAssertDecl ( RT_FANOUT_4<=  RT_FANOUT_4_MAX,
"watch struct padding"   
)

Variable Documentation

◆ ctl

tree ctl = (RT_RADIX_TREE_CONTROL *) palloc0(sizeof(RT_RADIX_TREE_CONTROL))

Definition at line 1838 of file radixtree.h.

Referenced by AddPendingSync(), assign_record_type_typmod(), BuildEventTriggerCache(), CompactCheckpointerRequestQueue(), create_seq_hashtable(), createConnHash(), CreatePartitionDirectory(), do_autovacuum(), EnablePortalManager(), find_all_inheritors(), find_oper_cache_entry(), find_rendezvous_variable(), get_json_object_as_hash(), GetConnection(), init_rel_sync_cache(), init_ts_config_cache(), InitializeAttoptCache(), InitializeRelfilenumberMap(), InitializeShippableCache(), InitializeTableSpaceCache(), json_unique_check_init(), load_categories_hash(), log_invalid_page(), logicalrep_partmap_init(), logicalrep_relmap_init(), lookup_proof_cache(), lookup_ts_dictionary_cache(), lookup_ts_parser_cache(), lookup_type_cache(), LookupOpclassInfo(), pa_allocate_worker(), pg_get_backend_memory_contexts(), plpgsql_estate_setup(), plpgsql_HashTableInit(), populate_recordset_object_start(), process_syncing_tables_for_apply(), RegisterExtensibleNodeEntry(), RelationCacheInitialize(), ResetUnloggedRelationsInDbspaceDir(), ri_InitHashTables(), SerializePendingSyncs(), SimpleLruDoesPhysicalPageExist(), SimpleLruGetBankLock(), SimpleLruInit(), SimpleLruReadPage(), SimpleLruReadPage_ReadOnly(), SimpleLruTruncate(), SimpleLruWaitIO(), SimpleLruWriteAll(), SimpleLruWritePage(), SimpleLruZeroLSNs(), SimpleLruZeroPage(), SlruCorrectSegmentFilenameLength(), SlruDeleteSegment(), SlruFileName(), SlruInternalDeleteSegment(), SlruInternalWritePage(), SlruMayDeleteSegment(), SlruPhysicalReadPage(), SlruPhysicalWritePage(), SlruReportIOError(), SlruScanDirCbDeleteAll(), SlruScanDirCbDeleteCutoff(), SlruScanDirCbFindEarliest(), SlruScanDirCbReportPresence(), SlruScanDirectory(), SlruSelectLRUPage(), SlruSyncFileTag(), smgropen(), StatsShmemInit(), test_slru_scan_cb(), and XLogPrefetcherAllocate().

◆ leaf_context

tree leaf_context = ctx

Definition at line 1852 of file radixtree.h.

◆ max_val

tree ctl max_val = RT_SHIFT_GET_MAX_VAL(0)

Definition at line 1859 of file radixtree.h.

Referenced by add_int_reloption(), add_local_int_reloption(), add_local_real_reloption(), add_real_reloption(), init_int_reloption(), and init_real_reloption().

◆ root

tree ctl root = rootnode.alloc

Definition at line 1857 of file radixtree.h.

Referenced by _int_matchsel(), add_base_clause_to_rel(), add_base_rels_to_query(), add_child_join_rel_equivalences(), add_child_rel_equivalences(), add_foreign_final_paths(), add_foreign_grouping_paths(), add_foreign_ordered_paths(), add_function_cost(), add_join_clause_to_rels(), add_join_rel(), add_non_redundant_clauses(), add_nullingrels_if_needed(), add_other_rels_to_query(), add_outer_joins_to_relids(), add_paths_to_append_rel(), add_paths_to_grouping_rel(), add_paths_to_joinrel(), add_paths_with_pathkeys_for_rel(), add_placeholders_to_base_rels(), add_placeholders_to_joinrel(), add_row_identity_columns(), add_row_identity_var(), add_rtes_to_flat_rtable(), add_setop_child_rel_equivalences(), add_unique_group_var(), add_vars_to_attr_needed(), add_vars_to_targetlist(), adjust_appendrel_attrs(), adjust_appendrel_attrs_multilevel(), adjust_child_relids_multilevel(), adjust_foreign_grouping_path_cost(), adjust_group_pathkeys_for_groupagg(), adjust_inherited_attnums_multilevel(), adjust_paths_for_srfs(), adjust_rowcount_for_semijoins(), appendLimitClause(), apply_child_basequals(), apply_projection_to_path(), apply_scanjoin_target_to_paths(), approx_tuple_count(), approximate_joinrel_size(), arraycontsel(), assign_param_for_placeholdervar(), assign_param_for_var(), assign_special_exec_param(), bernoulli_samplescangetsamplesize(), bitmap_and_cost_est(), bitmap_scan_cost_est(), blcostestimate(), booltestsel(), boolvarsel(), brincostestimate(), btcostestimate(), build_base_rel_tlists(), build_child_join_rel(), build_child_join_reltarget(), build_child_join_sjinfo(), build_expression_pathkey(), build_implied_join_equality(), build_index_pathkeys(), build_index_paths(), build_join_pathkeys(), build_join_rel(), build_join_rel_hash(), build_joinrel_partition_info(), build_joinrel_restrictlist(), build_joinrel_tlist(), build_minmax_path(), build_partition_pathkeys(), build_path_tlist(), build_paths_for_OR(), build_physical_tlist(), build_setop_child_paths(), build_simple_rel(), build_subplan(), BuildParameterizedTidPaths(), cached_scansel(), calc_joinrel_size_estimate(), can_minmax_aggs(), can_partial_agg(), check_index_predicates(), check_redundant_nullability_qual(), choose_bitmap_and(), classifyConditions(), clause_selectivity(), clause_selectivity_ext(), clauselist_apply_dependencies(), clauselist_selectivity(), clauselist_selectivity_ext(), clauselist_selectivity_or(), clean_NOT(), cleanup_tsquery_stopwords(), compute_bitmap_pages(), compute_partition_bounds(), compute_semi_anti_join_factors(), compute_semijoin_info(), consider_groupingsets_paths(), consider_index_join_clauses(), consider_index_join_outer_rels(), consider_new_or_clause(), consider_parallel_mergejoin(), consider_parallel_nestloop(), contain_placeholder_references_to(), convert_ANY_sublink_to_join(), convert_EXISTS_sublink_to_join(), convert_EXISTS_to_ANY(), convert_subquery_pathkeys(), convert_testexpr(), cost_agg(), cost_bitmap_heap_scan(), cost_ctescan(), cost_functionscan(), cost_group(), cost_incremental_sort(), cost_index(), cost_memoize_rescan(), cost_namedtuplestorescan(), cost_qual_eval(), cost_qual_eval_node(), cost_rescan(), cost_resultscan(), cost_samplescan(), cost_seqscan(), cost_subplan(), cost_subqueryscan(), cost_tablefuncscan(), cost_tidrangescan(), cost_tidscan(), cost_valuesscan(), cost_windowagg(), create_agg_path(), create_agg_plan(), create_append_path(), create_append_plan(), create_bitmap_and_path(), create_bitmap_heap_path(), create_bitmap_or_path(), create_bitmap_scan_plan(), create_bitmap_subplan(), create_ctescan_path(), create_ctescan_plan(), create_customscan_plan(), create_degenerate_grouping_paths(), create_distinct_paths(), create_final_distinct_paths(), create_foreignscan_path(), create_foreignscan_plan(), create_functionscan_path(), create_functionscan_plan(), create_gather_merge_path(), create_gather_merge_plan(), create_gather_path(), create_gather_plan(), create_gating_plan(), create_group_path(), create_group_plan(), create_group_result_path(), create_group_result_plan(), create_grouping_paths(), create_groupingsets_path(), create_groupingsets_plan(), create_hashjoin_path(), create_hashjoin_plan(), create_incremental_sort_path(), create_incrementalsort_plan(), create_index_path(), create_index_paths(), create_indexscan_plan(), create_join_clause(), create_join_plan(), create_lateral_join_info(), create_limit_plan(), create_lockrows_plan(), create_material_plan(), create_memoize_plan(), create_merge_append_path(), create_merge_append_plan(), create_mergejoin_path(), create_mergejoin_plan(), create_minmaxagg_path(), create_minmaxagg_plan(), create_modifytable_plan(), create_namedtuplestorescan_path(), create_namedtuplestorescan_plan(), create_nestloop_path(), create_nestloop_plan(), create_one_window_path(), create_ordered_paths(), create_ordinary_grouping_paths(), create_partial_bitmap_paths(), create_partial_distinct_paths(), create_partial_grouping_paths(), create_partitionwise_grouping_paths(), create_plain_partial_paths(), create_plan(), create_plan_recurse(), create_project_set_plan(), create_projection_path(), create_projection_plan(), create_recursiveunion_plan(), create_resultscan_path(), create_resultscan_plan(), create_samplescan_path(), create_samplescan_plan(), create_scan_plan(), create_seqscan_path(), create_seqscan_plan(), create_set_projection_path(), create_setop_plan(), create_sort_path(), create_sort_plan(), create_subqueryscan_path(), create_subqueryscan_plan(), create_tablefuncscan_path(), create_tablefuncscan_plan(), create_tidrangescan_path(), create_tidrangescan_plan(), create_tidscan_path(), create_tidscan_paths(), create_tidscan_plan(), create_unique_path(), create_unique_plan(), create_upper_unique_plan(), create_valuesscan_path(), create_valuesscan_plan(), create_window_paths(), create_windowagg_path(), create_windowagg_plan(), create_worktablescan_path(), create_worktablescan_plan(), deconstruct_distribute(), deconstruct_distribute_oj_quals(), deconstruct_jointree(), deconstruct_recurse(), deparseDirectDeleteSql(), deparseDirectUpdateSql(), deparseFromExprForRel(), deparseLockingClause(), deparseRangeTblRef(), deparseSelectSql(), deparseSelectStmtForRel(), dependencies_clauselist_selectivity(), desirable_join(), distribute_qual_to_rels(), distribute_quals_to_rels(), distribute_restrictinfo_to_rels(), distribute_row_identity_vars(), dofindsubquery(), edge_failure(), eqjoinsel(), eqsel_internal(), estimate_array_length(), estimate_expression_value(), estimate_hash_bucket_stats(), estimate_hashagg_tablesize(), estimate_multivariate_bucketsize(), estimate_multivariate_ndistinct(), estimate_num_groups(), estimate_path_cost_size(), estimate_size(), eval_const_expressions(), examine_simple_variable(), examine_variable(), expand_appendrel_subquery(), expand_indexqual_rowcompare(), expand_inherited_rtentry(), expand_insert_targetlist(), expand_partitioned_rtentry(), expand_planner_arrays(), expand_single_inheritance_child(), expand_virtual_generated_columns(), expr_is_nonnullable(), expression_planner_with_deps(), expression_returns_set_rows(), exprs_known_equal(), extract_jsp_query(), extract_lateral_references(), extract_lateral_vars_from_PHVs(), extract_query_dependencies(), extract_restriction_or_clauses(), fetch_upper_rel(), fileGetForeignPaths(), fileGetForeignRelSize(), final_cost_hashjoin(), final_cost_mergejoin(), final_cost_nestloop(), finalize_plan(), find_appinfos_by_relids(), find_base_rel(), find_base_rel_ignore_join(), find_base_rel_noerr(), find_childrel_parents(), find_compatible_agg(), find_compatible_trans(), find_computable_ec_member(), find_dependent_phvs(), find_dependent_phvs_in_jointree(), find_em_for_rel(), find_em_for_rel_target(), find_join_domain(), find_join_input_rel(), find_join_rel(), find_lateral_references(), find_mergeclauses_for_outer_pathkeys(), find_minmax_agg_replacement_param(), find_partition_scheme(), find_placeholder_info(), find_placeholders_in_expr(), find_placeholders_in_jointree(), find_placeholders_recurse(), find_simplified_clause(), find_single_rel_for_clauses(), findsubquery(), fix_alternative_subplan(), fix_append_rel_relids(), fix_expr_common(), fix_indexorderby_references(), fix_indexqual_clause(), fix_indexqual_references(), fix_join_expr(), fix_param_node(), fix_placeholder_input_needed_levels(), fix_scan_expr(), fix_upper_expr(), fix_windowagg_condition_expr(), flatten_group_exprs(), flatten_join_alias_vars(), flatten_simple_union_all(), foreign_grouping_ok(), foreign_join_ok(), FreePageBtreeCleanup(), FreePageManagerDump(), FreePageManagerPutInternal(), function_selectivity(), gather_grouping_paths(), generate_base_implied_equalities(), generate_base_implied_equalities_broken(), generate_base_implied_equalities_const(), generate_base_implied_equalities_no_const(), generate_bitmap_or_paths(), generate_gather_paths(), generate_implied_equalities_for_column(), generate_join_implied_equalities(), generate_join_implied_equalities_broken(), generate_join_implied_equalities_for_ecs(), generate_join_implied_equalities_normal(), generate_mergejoin_paths(), generate_new_exec_param(), generate_nonunion_paths(), generate_orderedappend_paths(), generate_partitionwise_join_paths(), generate_recursion_path(), generate_subquery_params(), generate_union_paths(), generate_useful_gather_paths(), generic_restriction_selectivity(), genericcostestimate(), geqo(), geqo_eval(), geqo_rand(), geqo_randint(), geqo_selection(), geqo_set_seed(), get_actual_variable_range(), get_agg_clause_costs(), get_baserel_parampathinfo(), get_cheapest_parameterized_child_path(), get_common_eclass_indexes(), get_dependent_generated_columns(), get_eclass_for_sort_expr(), get_eclass_indexes_for_relids(), get_expr_width(), get_foreign_key_join_selectivity(), get_function_rows(), get_gating_quals(), get_index_clause_from_support(), get_index_paths(), get_join_domain_min_rels(), get_join_index_paths(), get_join_variables(), get_joinrel_parampathinfo(), get_json_table(), get_loop_count(), get_matching_part_pairs(), get_memoize_path(), get_number_of_groups(), get_parameterized_baserel_size(), get_parameterized_joinrel_size(), get_rel_all_updated_cols(), get_relation_constraints(), get_relation_foreign_keys(), get_relation_info(), get_restriction_qual_cost(), get_restriction_variable(), get_result_relid(), get_row_security_policies(), get_translated_update_targetlist(), get_useful_ecs_for_relation(), get_useful_group_keys_orderings(), get_useful_pathkeys_for_distinct(), get_useful_pathkeys_for_relation(), get_variable_range(), get_windowclause_startup_tuples(), gimme_edge_table(), gimme_gene(), gimme_tour(), gimme_tree(), gincost_opexpr(), gincost_scalararrayopexpr(), gincostestimate(), ginDataFillRoot(), ginEntryFillRoot(), ginFindParents(), ginVacuumPostingTree(), gistcostestimate(), group_similar_or_args(), grouping_planner(), has_join_restriction(), has_legal_joinclause(), has_relevant_eclass_joinclause(), has_row_triggers(), has_stored_generated_columns(), has_useful_pathkeys(), hash_inner_and_outer(), hashcostestimate(), have_dangerous_phv(), have_join_order_restriction(), have_partkey_equi_join(), have_relevant_eclass_joinclause(), have_relevant_joinclause(), identify_current_nestloop_params(), index_other_operands_eval_cost(), index_pages_fetched(), indexcol_is_bool_constant_for_query(), ineq_histogram_selectivity(), infer_arbiter_indexes(), init_tour(), initial_cost_mergejoin(), initial_cost_nestloop(), initialize_mergeclause_eclasses(), inline_cte(), inline_set_returning_function(), innerrel_is_unique(), innerrel_is_unique_ext(), is_degenerate_grouping(), is_foreign_expr(), is_foreign_pathkey(), is_innerrel_unique_for(), is_parallel_safe(), is_pseudo_constant_for_index(), is_simple_subquery(), is_simple_values(), IsTidEqualAnyClause(), join_is_legal(), join_is_removable(), join_search_one_level(), join_selectivity(), jointree_contains_lateral_outer_refs(), label_incrementalsort_with_costsize(), label_sort_with_costsize(), linear_rand(), logicalrep_partition_open(), ltreeparentsel(), make_bitmap_paths_for_or_group(), make_canonical_pathkey(), make_group_input_target(), make_grouping_rel(), make_inner_pathkeys_for_merge(), make_join_rel(), make_modifytable(), make_one_rel(), make_ordered_path(), make_outerjoininfo(), make_partial_grouping_target(), make_partition_pruneinfo(), make_partitionedrel_pruneinfo(), make_pathkey_from_sortinfo(), make_pathkey_from_sortop(), make_pathkeys_for_sortclauses(), make_pathkeys_for_sortclauses_extended(), make_pathkeys_for_window(), make_placeholder_expr(), make_plain_restrictinfo(), make_rel_from_joinlist(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo(), make_sort_input_target(), make_sub_restrictinfos(), make_subplan(), make_window_input_target(), mark_nullable_by_grouping(), mark_rels_nulled_by_join(), match_boolean_index_clause(), match_clause_to_index(), match_clause_to_indexcol(), match_clauses_to_index(), match_eclass_clauses_to_index(), match_eclasses_to_foreign_key_col(), match_foreign_keys_to_quals(), match_funcclause_to_indexcol(), match_join_clauses_to_index(), match_opclause_to_indexcol(), match_orclause_to_indexcol(), match_restriction_clauses_to_index(), match_rowcompare_to_indexcol(), match_saopclause_to_indexcol(), match_unsorted_outer(), matchingsel(), mcv_clause_selectivity_or(), mcv_clauselist_selectivity(), mcv_get_match_bitmap(), merge_clump(), mergejoinscansel(), minmax_qp_callback(), multirangesel(), neqjoinsel(), networkjoinsel(), networksel(), nulltestsel(), NumRelids(), optimize_window_clauses(), order_qual_clauses(), pathkeys_useful_for_distinct(), pathkeys_useful_for_grouping(), pathkeys_useful_for_merging(), pathkeys_useful_for_ordering(), pathkeys_useful_for_setop(), patternsel(), patternsel_common(), perform_pullup_replace_vars(), plaintree(), plan_cluster_use_sort(), plan_create_index_workers(), plan_set_operations(), plan_union_children(), populate_joinrel_with_paths(), postgresAddForeignUpdateTargets(), postgresGetForeignJoinPaths(), postgresGetForeignPaths(), postgresGetForeignPlan(), postgresGetForeignRelSize(), postgresGetForeignUpperPaths(), postgresPlanDirectModify(), postgresPlanForeignModify(), postprocess_setop_rel(), prefix_selectivity(), preprocess_aggref(), preprocess_aggrefs(), preprocess_aggrefs_walker(), preprocess_expression(), preprocess_function_rtes(), preprocess_groupclause(), preprocess_grouping_sets(), preprocess_limit(), preprocess_minmax_aggregates(), preprocess_phv_expression(), preprocess_qual_conditions(), preprocess_rowmarks(), preprocess_targetlist(), process_equivalence(), process_implied_equality(), process_security_barrier_quals(), process_subquery_nestloop_params(), pull_up_constant_function(), pull_up_simple_subquery(), pull_up_simple_union_all(), pull_up_simple_values(), pull_up_sublinks(), pull_up_sublinks_jointree_recurse(), pull_up_sublinks_qual_recurse(), pull_up_subqueries(), pull_up_subqueries_recurse(), pull_up_union_leaf_queries(), pull_varnos(), pull_varnos_of_level(), query_planner(), random_init_pool(), rangesel(), rebuild_eclass_attr_needed(), rebuild_joinclause_attr_needed(), rebuild_lateral_attr_needed(), rebuild_placeholder_attr_needed(), reconsider_full_join_clause(), reconsider_outer_join_clause(), reconsider_outer_join_clauses(), record_plan_function_dependency(), record_plan_type_dependency(), recurse_set_operations(), reduce_outer_joins(), reduce_outer_joins_pass2(), reduce_unique_semijoins(), register_partpruneinfo(), rel_is_distinct_for(), rel_supports_distinctness(), relation_can_be_sorted_early(), relation_excluded_by_constraints(), relation_has_unique_index_ext(), relation_has_unique_index_for(), remap_groupColIdx(), remove_join_clause_from_rels(), remove_leftjoinrel_from_query(), remove_rel_from_query(), remove_result_refs(), remove_self_join_rel(), remove_self_joins_one_group(), remove_self_joins_recurse(), remove_useless_groupby_columns(), remove_useless_joins(), remove_useless_result_rtes(), remove_useless_results_recurse(), remove_useless_self_joins(), reparameterize_path(), reparameterize_path_by_child(), reparameterize_pathlist_by_child(), replace_correlation_vars_mutator(), replace_nestloop_param_placeholdervar(), replace_nestloop_param_var(), replace_nestloop_params(), replace_nestloop_params_mutator(), replace_outer_agg(), replace_outer_grouping(), replace_outer_merge_support(), replace_outer_placeholdervar(), replace_outer_returning(), replace_outer_var(), RestrictInfoIsTidQual(), restriction_is_always_false(), restriction_is_always_true(), restriction_selectivity(), right_merge_direction(), rowcomparesel(), RT_BEGIN_ITERATE(), scalararraysel(), scalararraysel_containment(), scalarineqsel(), scalarineqsel_wrapper(), select_active_windows(), select_mergejoin_clauses(), select_outer_pathkeys_for_merge(), set_append_references(), set_append_rel_pathlist(), set_append_rel_size(), set_base_rel_consider_startup(), set_base_rel_pathlists(), set_base_rel_sizes(), set_baserel_size_estimates(), set_cte_pathlist(), set_cte_size_estimates(), set_customscan_references(), set_foreign_pathlist(), set_foreign_size(), set_foreign_size_estimates(), set_foreignscan_references(), set_function_pathlist(), set_function_size_estimates(), set_hash_references(), set_indexonlyscan_references(), set_join_references(), set_joinrel_size_estimates(), set_mergeappend_references(), set_namedtuplestore_pathlist(), set_namedtuplestore_size_estimates(), set_param_references(), set_pathtarget_cost_width(), set_plain_rel_pathlist(), set_plain_rel_size(), set_plan_references(), set_plan_refs(), set_rel_consider_parallel(), set_rel_pathlist(), set_rel_size(), set_rel_width(), set_relation_partition_info(), set_result_pathlist(), set_result_size_estimates(), set_returning_clause_references(), set_subquery_pathlist(), set_subquery_size_estimates(), set_subqueryscan_references(), set_tablefunc_pathlist(), set_tablefunc_size_estimates(), set_tablesample_rel_pathlist(), set_tablesample_rel_size(), set_upper_references(), set_values_pathlist(), set_values_size_estimates(), set_windowagg_runcondition_references(), set_worktable_pathlist(), setup_simple_rel_arrays(), simplify_EXISTS_query(), sort_inner_and_outer(), spgcostestimate(), split_pathtarget_at_srfs(), spread_chromo(), SS_attach_initplans(), SS_charge_for_initplans(), SS_finalize_plan(), SS_identify_outer_params(), SS_make_initplan_from_plan(), SS_make_initplan_output_param(), SS_process_ctes(), SS_process_sublinks(), SS_replace_correlation_vars(), standard_join_search(), standard_planner(), standard_qp_callback(), statext_clauselist_selectivity(), statext_is_compatible_clause(), statext_is_compatible_clause_internal(), statext_mcv_clauselist_selectivity(), subquery_planner(), system_rows_samplescangetsamplesize(), system_samplescangetsamplesize(), system_time_samplescangetsamplesize(), TidQualFromRestrictInfoList(), translate_col_privs_multilevel(), treat_as_join_clause(), truncate_useless_pathkeys(), try_hashjoin_path(), try_mergejoin_path(), try_nestloop_path(), try_partial_hashjoin_path(), try_partial_mergejoin_path(), try_partial_nestloop_path(), try_partitionwise_join(), tsmatchsel(), use_physical_tlist(), and xmltotext_with_options().

◆ rootnode

rootnode
Initial value:
{
RT_RADIX_TREE *tree
RT_RADIX_TREE
Definition: radixtree.h:708

Definition at line 1823 of file radixtree.h.

◆ RT_SIZE_CLASS_INFO

const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[]
static
Initial value:
= {
[RT_CLASS_4] = {
.name = RT_STR(RT_PREFIX) "_radix_tree node4",
.fanout = RT_FANOUT_4,
.allocsize = sizeof(RT_NODE_4) + RT_FANOUT_4 * sizeof(RT_PTR_ALLOC),
},
[RT_CLASS_16_LO] = {
.name = RT_STR(RT_PREFIX) "_radix_tree node16_lo",
.fanout = RT_FANOUT_16_LO,
.allocsize = sizeof(RT_NODE_16) + RT_FANOUT_16_LO * sizeof(RT_PTR_ALLOC),
},
[RT_CLASS_16_HI] = {
.name = RT_STR(RT_PREFIX) "_radix_tree node16_hi",
.fanout = RT_FANOUT_16_HI,
.allocsize = sizeof(RT_NODE_16) + RT_FANOUT_16_HI * sizeof(RT_PTR_ALLOC),
},
[RT_CLASS_48] = {
.name = RT_STR(RT_PREFIX) "_radix_tree node48",
.fanout = RT_FANOUT_48,
.allocsize = sizeof(RT_NODE_48) + RT_FANOUT_48 * sizeof(RT_PTR_ALLOC),
},
[RT_CLASS_256] = {
.name = RT_STR(RT_PREFIX) "_radix_tree node256",
.fanout = RT_FANOUT_256,
.allocsize = sizeof(RT_NODE_256),
},
}
RT_STR
#define RT_STR(s)
Definition: radixtree.h:171
RT_NODE_4
#define RT_NODE_4
Definition: radixtree.h:254
RT_NODE_256
#define RT_NODE_256
Definition: radixtree.h:257
RT_NODE_48
#define RT_NODE_48
Definition: radixtree.h:256
RT_NODE_16
#define RT_NODE_16
Definition: radixtree.h:255
RT_FANOUT_48
#define RT_FANOUT_48
Definition: radixtree.h:603
RT_PREFIX
#define RT_PREFIX
Definition: tidstore.c:101

Definition at line 650 of file radixtree.h.

◆ start_shift

tree ctl start_shift = 0

Definition at line 1858 of file radixtree.h.

Referenced by RT_SET().

◆ tree

return tree = (RT_RADIX_TREE *) palloc0(sizeof(RT_RADIX_TREE))

Definition at line 1828 of file radixtree.h.

Referenced by avlAdjustBalance(), avlCollectFields(), avlFree(), avlInit(), avlInsertNode(), avlMergeValue(), for(), lt_q_regex(), ltq_regex(), rbt_create(), rbt_populate(), RT_ALLOC_LEAF(), RT_ALLOC_NODE(), RT_BEGIN_ITERATE(), RT_EXTEND_DOWN(), RT_EXTEND_UP(), RT_FIND(), RT_FREE(), RT_FREE_LEAF(), RT_FREE_NODE(), RT_GET_SLOT_RECURSIVE(), RT_GROW_NODE_16(), RT_GROW_NODE_4(), RT_GROW_NODE_48(), RT_MEMORY_USAGE(), RT_NODE_INSERT(), rt_num_entries(), RT_PTR_SET_LOCAL(), RT_SET(), testdelete(), testfind(), testfindltgt(), testleftmost(), testleftright(), testrightleft(), tsquery_rewrite(), and tsquery_rewrite_query().