PostgreSQL Source Code  git master
radixtree.h File Reference
#include "postgres.h"
#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_TREERT_CREATE (MemoryContext ctx)
 
RT_SCOPE void RT_FREE (RT_RADIX_TREE *tree)
 
RT_SCOPE RT_VALUE_TYPERT_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_ITERRT_BEGIN_ITERATE (RT_RADIX_TREE *tree)
 
RT_SCOPE RT_VALUE_TYPERT_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_ALLOCRT_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_ALLOCRT_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_ALLOCRT_NODE_16_SEARCH_EQ (RT_NODE_16 *node, uint8 chunk)
 
static RT_PTR_ALLOCRT_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_ALLOCRT_ADD_CHILD_256 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline RT_PTR_ALLOCRT_GROW_NODE_48 (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOCRT_ADD_CHILD_48 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline RT_PTR_ALLOCRT_GROW_NODE_16 (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOCRT_ADD_CHILD_16 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static pg_noinline RT_PTR_ALLOCRT_GROW_NODE_4 (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOCRT_ADD_CHILD_4 (RT_RADIX_TREE *tree, RT_CHILD_PTR node, uint8 chunk)
 
static RT_PTR_ALLOCRT_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_ALLOCRT_EXTEND_DOWN (RT_RADIX_TREE *tree, RT_PTR_ALLOC *parent_slot, uint64 key, int shift)
 
static RT_PTR_ALLOCRT_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++)
 
 MemoryContextSwitchTo (old_ctx)
 
static RT_PTR_ALLOCRT_NODE_ITERATE_NEXT (RT_ITER *iter, int level)
 

Variables

static const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO []
 
RT_SCOPE RT_RADIX_TREE *MemoryContext old_ctx
 
RT_CHILD_PTR rootnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4)
 
 tree = (RT_RADIX_TREE *) palloc0(sizeof(RT_RADIX_TREE))
 
tree context = ctx
 
tree iter_context
 
tree ctl = (RT_RADIX_TREE_CONTROL *) palloc0(sizeof(RT_RADIX_TREE_CONTROL))
 
tree leaf_context = tree->context
 
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 226 of file radixtree.h.

◆ RT_ADD_CHILD_256

#define RT_ADD_CHILD_256   RT_MAKE_NAME(add_child_256)

Definition at line 228 of file radixtree.h.

◆ RT_ADD_CHILD_4

#define RT_ADD_CHILD_4   RT_MAKE_NAME(add_child_4)

Definition at line 225 of file radixtree.h.

◆ RT_ADD_CHILD_48

#define RT_ADD_CHILD_48   RT_MAKE_NAME(add_child_48)

Definition at line 227 of file radixtree.h.

◆ RT_ALLOC_LEAF

#define RT_ALLOC_LEAF   RT_MAKE_NAME(alloc_leaf)

Definition at line 201 of file radixtree.h.

◆ RT_ALLOC_NODE

#define RT_ALLOC_NODE   RT_MAKE_NAME(alloc_node)

Definition at line 200 of file radixtree.h.

◆ RT_BEGIN_ITERATE

#define RT_BEGIN_ITERATE   RT_MAKE_NAME(begin_iterate)

Definition at line 185 of file radixtree.h.

◆ RT_BM_BIT

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

Definition at line 334 of file radixtree.h.

◆ RT_BM_IDX

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

Definition at line 333 of file radixtree.h.

◆ RT_CHILD_PTR

#define RT_CHILD_PTR   RT_MAKE_NAME(child_ptr)

Definition at line 250 of file radixtree.h.

◆ RT_CHILDPTR_IS_VALUE

#define RT_CHILDPTR_IS_VALUE   RT_MAKE_NAME(childptr_is_value)

Definition at line 196 of file radixtree.h.

◆ RT_CHUNK_MASK

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

Definition at line 321 of file radixtree.h.

◆ RT_CLASS_16_HI

#define RT_CLASS_16_HI   RT_MAKE_NAME(class_32_max)

Definition at line 261 of file radixtree.h.

◆ RT_CLASS_16_LO

#define RT_CLASS_16_LO   RT_MAKE_NAME(class_32_min)

Definition at line 260 of file radixtree.h.

◆ RT_CLASS_256

#define RT_CLASS_256   RT_MAKE_NAME(class_256)

Definition at line 263 of file radixtree.h.

◆ RT_CLASS_4

#define RT_CLASS_4   RT_MAKE_NAME(class_4)

Definition at line 259 of file radixtree.h.

◆ RT_CLASS_48

#define RT_CLASS_48   RT_MAKE_NAME(class_48)

Definition at line 262 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 215 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 214 of file radixtree.h.

◆ RT_COPY_COMMON

#define RT_COPY_COMMON   RT_MAKE_NAME(copy_common)

Definition at line 207 of file radixtree.h.

◆ RT_CREATE

#define RT_CREATE   RT_MAKE_NAME(create)

Definition at line 173 of file radixtree.h.

◆ RT_DELETE_RECURSIVE

#define RT_DELETE_RECURSIVE   RT_MAKE_NAME(delete_recursive)

Definition at line 199 of file radixtree.h.

◆ RT_DUMP_NODE

#define RT_DUMP_NODE   RT_MAKE_NAME(dump_node)

Definition at line 192 of file radixtree.h.

◆ RT_END_ITERATE

#define RT_END_ITERATE   RT_MAKE_NAME(end_iterate)

Definition at line 187 of file radixtree.h.

◆ RT_EXTEND_DOWN

#define RT_EXTEND_DOWN   RT_MAKE_NAME(extend_down)

Definition at line 206 of file radixtree.h.

◆ RT_EXTEND_UP

#define RT_EXTEND_UP   RT_MAKE_NAME(extend_up)

Definition at line 205 of file radixtree.h.

◆ RT_FANOUT_16_HI

#define RT_FANOUT_16_HI   RT_FANOUT_16_MAX

Definition at line 596 of file radixtree.h.

◆ RT_FANOUT_16_LO

#define RT_FANOUT_16_LO   16

Definition at line 594 of file radixtree.h.

◆ RT_FANOUT_16_MAX

#define RT_FANOUT_16_MAX   32

Definition at line 492 of file radixtree.h.

◆ RT_FANOUT_256

#define RT_FANOUT_256   RT_NODE_MAX_SLOTS

Definition at line 504 of file radixtree.h.

◆ RT_FANOUT_4

#define RT_FANOUT_4   4

Definition at line 607 of file radixtree.h.

◆ RT_FANOUT_48

#define RT_FANOUT_48   RT_FANOUT_48_MAX

Definition at line 597 of file radixtree.h.

◆ RT_FANOUT_48_MAX

#define RT_FANOUT_48_MAX   64

Definition at line 502 of file radixtree.h.

◆ RT_FANOUT_4_MAX

#define RT_FANOUT_4_MAX   (8 - sizeof(RT_NODE))

Definition at line 489 of file radixtree.h.

◆ RT_FIND

#define RT_FIND   RT_MAKE_NAME(find)

Definition at line 175 of file radixtree.h.

◆ RT_FREE

#define RT_FREE   RT_MAKE_NAME(free)

Definition at line 174 of file radixtree.h.

◆ RT_FREE_LEAF

#define RT_FREE_LEAF   RT_MAKE_NAME(free_leaf)

Definition at line 203 of file radixtree.h.

◆ RT_FREE_NODE

#define RT_FREE_NODE   RT_MAKE_NAME(free_node)

Definition at line 202 of file radixtree.h.

◆ RT_FREE_RECURSE

#define RT_FREE_RECURSE   RT_MAKE_NAME(free_recurse)

Definition at line 204 of file radixtree.h.

◆ RT_GET_KEY_CHUNK

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

Definition at line 330 of file radixtree.h.

◆ RT_GET_SLOT_RECURSIVE

#define RT_GET_SLOT_RECURSIVE   RT_MAKE_NAME(get_slot_recursive)

Definition at line 198 of file radixtree.h.

◆ RT_GET_VALUE_SIZE

#define RT_GET_VALUE_SIZE (   v)    RT_VARLEN_VALUE_SIZE(v)

Definition at line 431 of file radixtree.h.

◆ RT_GROW_NODE_16

#define RT_GROW_NODE_16   RT_MAKE_NAME(grow_node_16)

Definition at line 230 of file radixtree.h.

◆ RT_GROW_NODE_4

#define RT_GROW_NODE_4   RT_MAKE_NAME(grow_node_4)

Definition at line 229 of file radixtree.h.

◆ RT_GROW_NODE_48

#define RT_GROW_NODE_48   RT_MAKE_NAME(grow_node_48)

Definition at line 231 of file radixtree.h.

◆ RT_INVALID_PTR_ALLOC

#define RT_INVALID_PTR_ALLOC   NULL

Definition at line 403 of file radixtree.h.

◆ RT_INVALID_SLOT_IDX

#define RT_INVALID_SLOT_IDX   0xFF

Definition at line 548 of file radixtree.h.

◆ RT_ITER

#define RT_ITER   RT_MAKE_NAME(iter)

Definition at line 245 of file radixtree.h.

◆ RT_ITERATE_NEXT

#define RT_ITERATE_NEXT   RT_MAKE_NAME(iterate_next)

Definition at line 186 of file radixtree.h.

◆ RT_KEY_GET_SHIFT

#define RT_KEY_GET_SHIFT   RT_MAKE_NAME(key_get_shift)

Definition at line 220 of file radixtree.h.

◆ RT_MAKE_NAME

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

Definition at line 164 of file radixtree.h.

◆ RT_MAKE_NAME_

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

Definition at line 165 of file radixtree.h.

◆ RT_MAKE_PREFIX

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

Definition at line 163 of file radixtree.h.

◆ RT_MAX_LEVEL

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

Definition at line 327 of file radixtree.h.

◆ RT_MAX_SHIFT

#define RT_MAX_SHIFT   RT_KEY_GET_SHIFT(UINT64_MAX)

Definition at line 324 of file radixtree.h.

◆ RT_MEMORY_USAGE

#define RT_MEMORY_USAGE   RT_MAKE_NAME(memory_usage)

Definition at line 191 of file radixtree.h.

◆ RT_NODE

#define RT_NODE   RT_MAKE_NAME(node)

Definition at line 249 of file radixtree.h.

◆ RT_NODE_16

#define RT_NODE_16   RT_MAKE_NAME(node_16)

Definition at line 253 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 211 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 209 of file radixtree.h.

◆ RT_NODE_256

#define RT_NODE_256   RT_MAKE_NAME(node_256)

Definition at line 255 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 219 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 218 of file radixtree.h.

◆ RT_NODE_4

#define RT_NODE_4   RT_MAKE_NAME(node_4)

Definition at line 252 of file radixtree.h.

◆ RT_NODE_48

#define RT_NODE_48   RT_MAKE_NAME(node_48)

Definition at line 254 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 217 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 216 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 210 of file radixtree.h.

◆ RT_NODE_DELETE

#define RT_NODE_DELETE   RT_MAKE_NAME(node_delete)

Definition at line 223 of file radixtree.h.

◆ RT_NODE_INSERT

#define RT_NODE_INSERT   RT_MAKE_NAME(node_insert)

Definition at line 224 of file radixtree.h.

◆ RT_NODE_ITER

#define RT_NODE_ITER   RT_MAKE_NAME(node_iter)

Definition at line 251 of file radixtree.h.

◆ RT_NODE_ITERATE_NEXT

#define RT_NODE_ITERATE_NEXT   RT_MAKE_NAME(node_iterate_next)

Definition at line 239 of file radixtree.h.

◆ RT_NODE_KIND_16

#define RT_NODE_KIND_16   0x01

Definition at line 359 of file radixtree.h.

◆ RT_NODE_KIND_256

#define RT_NODE_KIND_256   0x03

Definition at line 361 of file radixtree.h.

◆ RT_NODE_KIND_4

#define RT_NODE_KIND_4   0x00

Definition at line 358 of file radixtree.h.

◆ RT_NODE_KIND_48

#define RT_NODE_KIND_48   0x02

Definition at line 360 of file radixtree.h.

◆ RT_NODE_KIND_COUNT

#define RT_NODE_KIND_COUNT   4

Definition at line 362 of file radixtree.h.

◆ RT_NODE_MAX_SLOTS

#define RT_NODE_MAX_SLOTS   (1 << RT_SPAN)

Definition at line 318 of file radixtree.h.

◆ RT_NODE_MUST_GROW

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

Definition at line 1130 of file radixtree.h.

◆ RT_NODE_SEARCH

#define RT_NODE_SEARCH   RT_MAKE_NAME(node_search)

Definition at line 222 of file radixtree.h.

◆ RT_NUM_SIZE_CLASSES

#define RT_NUM_SIZE_CLASSES   lengthof(RT_SIZE_CLASS_INFO)

Definition at line 672 of file radixtree.h.

◆ RT_PTR_ALLOC

#define RT_PTR_ALLOC   RT_NODE *

Definition at line 402 of file radixtree.h.

◆ RT_PTR_ALLOC_IS_VALID

#define RT_PTR_ALLOC_IS_VALID (   ptr)    PointerIsValid(ptr)

Definition at line 404 of file radixtree.h.

◆ RT_PTR_SET_LOCAL

#define RT_PTR_SET_LOCAL   RT_MAKE_NAME(ptr_set_local)

Definition at line 208 of file radixtree.h.

◆ RT_RADIX_TREE

#define RT_RADIX_TREE   RT_MAKE_NAME(radix_tree)

Definition at line 243 of file radixtree.h.

◆ RT_RADIX_TREE_CONTROL

#define RT_RADIX_TREE_CONTROL   RT_MAKE_NAME(radix_tree_control)

Definition at line 244 of file radixtree.h.

◆ RT_REMOVE_CHILD_16

#define RT_REMOVE_CHILD_16   RT_MAKE_NAME(remove_child_16)

Definition at line 233 of file radixtree.h.

◆ RT_REMOVE_CHILD_256

#define RT_REMOVE_CHILD_256   RT_MAKE_NAME(remove_child_256)

Definition at line 235 of file radixtree.h.

◆ RT_REMOVE_CHILD_4

#define RT_REMOVE_CHILD_4   RT_MAKE_NAME(remove_child_4)

Definition at line 232 of file radixtree.h.

◆ RT_REMOVE_CHILD_48

#define RT_REMOVE_CHILD_48   RT_MAKE_NAME(remove_child_48)

Definition at line 234 of file radixtree.h.

◆ RT_SET

#define RT_SET   RT_MAKE_NAME(set)

Definition at line 184 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 213 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 212 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 221 of file radixtree.h.

◆ RT_SHRINK_NODE_16

#define RT_SHRINK_NODE_16   RT_MAKE_NAME(shrink_child_16)

Definition at line 236 of file radixtree.h.

◆ RT_SHRINK_NODE_256

#define RT_SHRINK_NODE_256   RT_MAKE_NAME(shrink_child_256)

Definition at line 238 of file radixtree.h.

◆ RT_SHRINK_NODE_48

#define RT_SHRINK_NODE_48   RT_MAKE_NAME(shrink_child_48)

Definition at line 237 of file radixtree.h.

◆ RT_SIZE_CLASS

#define RT_SIZE_CLASS   RT_MAKE_NAME(size_class)

Definition at line 256 of file radixtree.h.

◆ RT_SIZE_CLASS_ELEM

#define RT_SIZE_CLASS_ELEM   RT_MAKE_NAME(size_class_elem)

Definition at line 257 of file radixtree.h.

◆ RT_SIZE_CLASS_INFO

#define RT_SIZE_CLASS_INFO   RT_MAKE_NAME(size_class_info)

Definition at line 258 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 368 of file radixtree.h.

◆ RT_SPAN

#define RT_SPAN   BITS_PER_BYTE

Definition at line 312 of file radixtree.h.

◆ RT_STATS

#define RT_STATS   RT_MAKE_NAME(stats)

Definition at line 193 of file radixtree.h.

◆ RT_STR

#define RT_STR (   s)    RT_STR_(s)

Definition at line 169 of file radixtree.h.

◆ RT_STR_

#define RT_STR_ (   s)    #s

Definition at line 170 of file radixtree.h.

◆ RT_VALUE_IS_EMBEDDABLE

#define RT_VALUE_IS_EMBEDDABLE   RT_MAKE_NAME(value_is_embeddable)

Definition at line 197 of file radixtree.h.

◆ RT_VERIFY_NODE

#define RT_VERIFY_NODE   RT_MAKE_NAME(verify_node)

Definition at line 240 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 1 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 1 of file radixtree.h.

◆ RT_RADIX_TREE_CONTROL

◆ RT_SIZE_CLASS

◆ RT_SIZE_CLASS_ELEM

Enumeration Type Documentation

◆ RT_SIZE_CLASS

Enumerator
RT_CLASS_4 
RT_CLASS_16_LO 
RT_CLASS_16_HI 
RT_CLASS_48 
RT_CLASS_256 

Definition at line 626 of file radixtree.h.

627 {
628  RT_CLASS_4 = 0,
631  RT_CLASS_48,
633 } RT_SIZE_CLASS;
#define RT_SIZE_CLASS
Definition: radixtree.h:256
#define RT_CLASS_16_LO
Definition: radixtree.h:260
#define RT_CLASS_256
Definition: radixtree.h:263
#define RT_CLASS_16_HI
Definition: radixtree.h:261
#define RT_CLASS_48
Definition: radixtree.h:262
#define RT_CLASS_4
Definition: radixtree.h:259

Function Documentation

◆ for()

for ( )

Definition at line 1854 of file radixtree.h.

1855  {
1856  RT_SIZE_CLASS_ELEM size_class = RT_SIZE_CLASS_INFO[i];
1857  size_t inner_blocksize = RT_SLAB_BLOCK_SIZE(size_class.allocsize);
1858 
1859  tree->node_slabs[i] = SlabContextCreate(ctx,
1860  size_class.name,
1861  inner_blocksize,
1862  size_class.allocsize);
1863  }
int i
Definition: isn.c:73
tree
Definition: radixtree.h:1832
#define RT_SLAB_BLOCK_SIZE(size)
Definition: radixtree.h:368
#define RT_SIZE_CLASS_INFO
Definition: radixtree.h:258
MemoryContext SlabContextCreate(MemoryContext parent, const char *name, Size blockSize, Size chunkSize)
Definition: slab.c:322
const char * name
Definition: radixtree.h:638

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().

◆ MemoryContextSwitchTo()

MemoryContextSwitchTo ( old_ctx  )

Referenced by _brin_parallel_merge(), _bt_preprocess_array_keys(), _SPI_commit(), _SPI_execmem(), _SPI_make_plan_non_temp(), _SPI_procmem(), _SPI_rollback(), _SPI_save_plan(), accumArrayResult(), accumArrayResultArr(), aclexplode(), add_child_join_rel_equivalences(), add_reloption(), advance_transition_function(), advance_windowaggregate(), advance_windowaggregate_base(), afterTriggerCopyBitmap(), allocate_reloption(), AllocateRelationDesc(), AllocateSnapshotBuilder(), analyze_row_processor(), AppendIncrementalManifestData(), apply_handle_delete(), apply_handle_insert(), apply_handle_tuple_routing(), apply_handle_update(), apply_handle_update_internal(), apply_spooled_messages(), ApplyLauncherMain(), array_agg_array_combine(), array_agg_combine(), array_set_element_expanded(), array_unnest(), assign_record_type_typmod(), assign_simple_var(), Async_Notify(), AtAbort_Memory(), AtCleanup_Memory(), AtCommit_Memory(), ATRewriteTable(), AtStart_Memory(), AtSubAbort_Memory(), AtSubCleanup_Memory(), AtSubCommit_Memory(), AtSubStart_Memory(), AttachPartitionEnsureIndexes(), AttachSession(), BackendInitialize(), BackendMain(), BackgroundWriterMain(), BaseBackupAddTarget(), begin_heap_rewrite(), begin_replication_step(), BeginCopyFrom(), BeginCopyTo(), blinsert(), BlockRefTableMarkBlockModified(), bloomBuildCallback(), bpchar_sortsupport(), brin_build_desc(), brin_build_empty_tuple(), brin_deform_tuple(), brin_minmax_multi_add_value(), brin_minmax_multi_union(), brin_revmap_data(), bringetbitmap(), brininsert(), brtuple_disk_tupdesc(), bt_check_level_from_leftmost(), bt_multi_page_stats(), bt_page_items_bytea(), bt_page_items_internal(), btbpchar_pattern_sortsupport(), btnamesortsupport(), btree_redo(), bttext_pattern_sortsupport(), bttextsortsupport(), btvacuumpage(), BuildCachedPlan(), BuildEventTriggerCache(), BuildHardcodedDescriptor(), BuildParamLogString(), BuildRelationExtStatistics(), buildSubPlanHash(), BuildTupleHashTableExt(), bytea_sortsupport(), cache_lookup(), cache_store_tuple(), cached_scansel(), cachedNamespacePath(), CatalogCacheCreateEntry(), CatalogCacheInitializeCache(), check_default_partition_contents(), check_domain_for_new_field(), check_domain_for_new_tuple(), CheckpointerMain(), CloneRowTriggersToPartition(), compactify_ranges(), compile_plperl_function(), compile_pltcl_function(), CompleteCachedPlan(), compute_array_stats(), compute_distinct_stats(), compute_expr_stats(), compute_index_stats(), compute_range_stats(), compute_scalar_stats(), compute_tsvector_stats(), ComputeExtStatisticsRows(), connectby(), connectby_text(), connectby_text_serial(), convert_prep_stmt_params(), convert_value_to_string(), CopyCachedPlan(), CopyFrom(), CopyMultiInsertBufferFlush(), CopyOneRowTo(), create_cursor(), create_join_clause(), create_unique_path(), CreateCachedPlan(), CreateDecodingContext(), CreateExecutorState(), CreateExprContextInternal(), CreateIncrementalBackupInfo(), CreateInitDecodingContext(), CreateParallelContext(), CreatePartitionDirectory(), createTrgmNFA(), CreateTriggerFiringOn(), crosstab(), crosstab_hash(), daitch_mokotoff(), dblink_get_pkey(), deconstruct_expanded_array(), DiscreteKnapsack(), do_analyze_rel(), do_autovacuum(), do_cast_value(), do_compile(), do_numeric_accum(), do_numeric_discard(), do_start_worker(), domain_check_input(), DoPortalRewind(), dsnowball_lexize(), each_object_field_end(), each_worker_jsonb(), elements_array_element_end(), elements_worker_jsonb(), EmitErrorReport(), ensure_free_space_in_buffer(), errbacktrace(), errcontext_msg(), errdetail(), errdetail_internal(), errdetail_log(), errdetail_log_plural(), errdetail_plural(), errfinish(), errhint(), errhint_plural(), errmsg(), errmsg_internal(), errmsg_plural(), eval_windowaggregates(), eval_windowfunction(), EvalOrderByExpressions(), EvalPlanQualEnd(), EvalPlanQualNext(), EvalPlanQualSlot(), EvalPlanQualStart(), evaluate_expr(), EventTriggerAlterTableEnd(), EventTriggerAlterTableStart(), EventTriggerCollectAlterDefPrivs(), EventTriggerCollectAlterOpFam(), EventTriggerCollectAlterTableSubcmd(), EventTriggerCollectAlterTSConfig(), EventTriggerCollectCreateOpClass(), EventTriggerCollectGrant(), EventTriggerCollectSimpleCommand(), EventTriggerInvoke(), EventTriggerSQLDropAddObject(), exec_assign_c_string(), exec_bind_message(), exec_describe_portal_message(), exec_describe_statement_message(), exec_eval_datum(), exec_eval_simple_expr(), exec_eval_using_params(), exec_init_tuple_store(), Exec_ListenCommit(), exec_move_row_from_datum(), exec_parse_message(), exec_replication_command(), exec_simple_check_plan(), exec_simple_query(), exec_stmt_block(), exec_stmt_close(), exec_stmt_fetch(), exec_stmt_forc(), exec_stmt_foreach_a(), exec_stmt_getdiag(), exec_stmt_open(), exec_stmt_raise(), exec_stmt_return_next(), exec_stmt_return_query(), ExecAggCopyTransValue(), ExecAggInitGroup(), ExecAggPlainTransByRef(), ExecAggPlainTransByVal(), ExecCallTriggerFunc(), ExecComputeStoredGenerated(), ExecCrossPartitionUpdate(), ExecEvalConvertRowtype(), ExecEvalExprSwitchContext(), ExecEvalHashedScalarArrayOp(), ExecEvalPreOrderedDistinctSingle(), ExecEvalWholeRowVar(), ExecFindMatchingSubPlans(), ExecFindPartition(), ExecForceStoreHeapTuple(), ExecGetAllUpdatedCols(), ExecGetReturningSlot(), ExecGetRootToChildMap(), ExecGetTriggerNewSlot(), ExecGetTriggerOldSlot(), ExecGetTriggerResultRel(), ExecHashGetHashValue(), ExecHashIncreaseNumBatches(), ExecHashJoinSaveTuple(), ExecHashTableCreate(), ExecHashTableReset(), ExecIndexEvalArrayKeys(), ExecIndexEvalRuntimeKeys(), ExecInitPartitionDispatchInfo(), ExecInitPartitionInfo(), ExecInitRoutingInfo(), ExecInitStoredGenerated(), ExecInsert(), ExecInterpExpr(), ExecMakeFunctionResultSet(), ExecMakeTableFunctionResult(), ExecParallelHashEnsureBatchAccessors(), ExecParallelHashJoinSetUpBatches(), ExecParallelRetrieveInstrumentation(), ExecPartitionCheck(), ExecPrepareCheck(), ExecPrepareExpr(), ExecPrepareExprList(), ExecPrepareQual(), ExecPrepareTuplestoreResult(), ExecProjectSRF(), ExecRelCheck(), ExecScanSubPlan(), ExecSetParamPlan(), execTuplesUnequal(), execute_sql_string(), executeDateTimeMethod(), ExecutorRewind(), ExecVacuum(), expand_array(), expand_vacuum_rel(), expanded_record_set_field_internal(), expanded_record_set_fields(), expanded_record_set_tuple(), explain_ExecutorEnd(), explain_ExecutorStart(), ExplainExecuteQuery(), ExportSnapshot(), fetch_array_arg_replace_nulls(), fetch_more_data(), FetchTableStates(), file_acquire_sample_rows(), fileIterateForeignScan(), fill_hba_view(), fill_ident_view(), finalize_aggregate(), finalize_partialaggregate(), finalize_windowaggregate(), FinalizeIncrementalManifest(), find_plan(), FindTupleHashEntry(), fmgr_security_definer(), fmgr_sql(), ForeignNext(), format_elog_string(), format_expr_params(), format_preparedparamsdata(), generate_partition_qual(), generate_series_step_int4(), generate_series_step_int8(), generate_series_step_numeric(), generate_series_timestamp(), generate_series_timestamptz_internal(), generate_subscripts(), geqo_eval(), get_actual_variable_endpoint(), get_actual_variable_range(), get_all_vacuum_rels(), get_cast_hashentry(), get_database_list(), get_eclass_for_sort_expr(), get_qual_for_range(), get_record_type_from_query(), get_rel_sync_entry(), get_subscription_list(), get_tables_to_cluster(), get_tables_to_cluster_partitioned(), GetAfterTriggersStoreSlot(), GetAfterTriggersTableData(), GetCachedExpression(), GetConnection(), GetCurrentFDWTuplestore(), getmissingattr(), GetNamedDSMSegment(), GetSearchPathMatcher(), GetSessionDsmHandle(), GetWALRecordsInfo(), GetXLogSummaryStats(), gin_leafpage_items(), gin_redo(), ginbuild(), ginBuildCallback(), ginHeapTupleBulkInsert(), gininsert(), ginInsertCleanup(), ginPlaceToPage(), ginVacuumPostingTreeLeaves(), gist_indexsortbuild_levelstate_flush(), gist_redo(), gistbeginscan(), gistbuild(), gistBuildCallback(), gistEmptyAllBuffers(), gistFetchTuple(), gistGetNodeBuffer(), gistgettuple(), gistinsert(), gistPushItupToNodeBuffer(), gistrescan(), gistScanPage(), gistSortedBuildCallback(), gistvacuumscan(), HandleParallelApplyMessages(), HandleParallelMessages(), hash_array(), hash_page_items(), heap_page_items(), hypothetical_dense_rank_final(), IdentifySystem(), index_getprocinfo(), index_register(), init_sexpr(), init_sql_fcache(), init_tuple_slot(), InitCatCache(), InitDeadLockChecking(), initGISTstate(), initialize_aggregate(), initialize_brin_insertstate(), initialize_target_list(), initialize_windowaggregate(), InitializeLogRepWorker(), InitializeParallelDSM(), InitializeSearchPath(), InitMaterializedSRF(), initTrie(), injection_points_attach(), injection_points_detach(), inline_function(), inline_set_returning_function(), innerrel_is_unique(), int8_avg_combine(), json_agg_transfn_worker(), json_object_agg_transfn_worker(), json_object_keys(), json_unique_builder_get_throwawaybuf(), jsonb_agg_transfn_worker(), jsonb_object_agg_transfn_worker(), jsonb_object_keys(), jsonb_path_query_internal(), JsonTablePlanScanNextRow(), JsonTableResetRowPattern(), keyGetItem(), LaunchParallelWorkers(), libpqrcv_processTuples(), llvm_compile_module(), llvm_session_initialize(), load_categories_hash(), load_domaintype_info(), load_enum_cache_data(), load_hba(), load_ident(), load_tzoffsets(), LogicalParallelApplyLoop(), logicalrep_launcher_attach_dshmem(), logicalrep_partition_open(), logicalrep_rel_open(), logicalrep_relmap_update(), LogicalRepApplyLoop(), LogicalRepWorkersWakeupAtCommit(), lookup_ts_dictionary_cache(), LookupTupleHashEntry(), LookupTupleHashEntry_internal(), LookupTupleHashEntryHash(), lowerstr_ctx(), macaddr_sortsupport(), make_callstmt_target(), make_canonical_pathkey(), make_datum_param(), make_expanded_record_from_datum(), make_expanded_record_from_exprecord(), make_expanded_record_from_tupdesc(), make_tuple_from_result_row(), make_tuple_indirect(), makeArrayResultArr(), makeIntervalAggState(), makeMdArrayResult(), makeNumericAggState(), makeStringAggState(), MakeTransitionCaptureState(), mark_dummy_rel(), MarkGUCPrefixReserved(), materializeResult(), maybe_reread_subscription(), MemoizeHash_equal(), MemoizeHash_hash(), MJCompare(), MJEvalInnerValues(), MJEvalOuterValues(), moveSplitTableRows(), multirange_unnest(), network_sortsupport(), next_field_expand(), normal_rand(), numeric_avg_combine(), numeric_combine(), numeric_poly_combine(), numeric_sortsupport(), operator_predicate_proof(), ordered_set_startup(), pa_launch_parallel_worker(), pa_start_subtrans(), perform_work_item(), PerformCursorOpen(), PersistHoldablePortal(), pg_backup_start(), pg_buffercache_pages(), pg_check_frozen(), pg_check_visible(), pg_decode_change(), pg_decode_truncate(), pg_get_catalog_foreign_keys(), pg_get_keywords(), pg_get_multixact_members(), pg_get_publication_tables(), pg_get_wal_block_info(), pg_lock_status(), pg_logical_slot_get_changes_guts(), pg_partition_ancestors(), pg_partition_tree(), pg_prepared_xact(), pg_stats_ext_mcvlist_items(), pg_timezone_abbrevs(), pg_visibility_map_rel(), pg_visibility_rel(), pgarch_archiveXlog(), pgoutput_change(), pgoutput_row_filter_init(), pgoutput_truncate(), pgp_armor_headers(), pgss_ExecutorStart(), pgstat_attach_shmem(), plperl_return_next(), plperl_return_next_internal(), plperl_spi_commit(), plperl_spi_exec(), plperl_spi_exec_prepared(), plperl_spi_fetchrow(), plperl_spi_prepare(), plperl_spi_query(), plperl_spi_query_prepared(), plperl_spi_rollback(), plperl_util_elog(), plpgsql_compile_inline(), plpgsql_create_econtext(), plpgsql_exec_function(), plpgsql_fulfill_promise(), plpgsql_parse_cwordrowtype(), plpgsql_parse_cwordtype(), pltcl_commit(), pltcl_elog(), pltcl_func_handler(), pltcl_init_tuple_store(), pltcl_rollback(), pltcl_SPI_prepare(), pltcl_subtrans_abort(), pltcl_subtrans_begin(), pltcl_subtrans_commit(), pltcl_subtransaction(), PLy_abort_open_subtransactions(), PLy_commit(), PLy_input_convert(), PLy_input_from_tuple(), PLy_output(), PLy_procedure_create(), PLy_rollback(), PLy_spi_execute_fetch_result(), PLy_spi_prepare(), PLy_spi_subtransaction_abort(), PLy_spi_subtransaction_begin(), PLy_spi_subtransaction_commit(), PLy_subtransaction_enter(), PLy_subtransaction_exit(), PopTransaction(), populate_recordset_worker(), populate_typ_list(), PortalCreateHoldStore(), PortalDrop(), PortalRun(), PortalRunFetch(), PortalRunUtility(), PortalStart(), PostgresMain(), postmaster_child_launch(), PostmasterMain(), postquel_get_single_result(), prep_domain_constraints(), prepare_probe_slot(), PrepareClientEncoding(), PrepareForIncrementalBackup(), printtup(), process_ordered_aggregate_single(), ProcessStartupPacket(), prs_setup_firstcall(), pub_collist_to_bitmapset(), publicationListToArray(), queue_listen(), RE_compile_and_cache(), rebuild_database_list(), recomputeNamespacePath(), regexp_matches(), regexp_split_to_table(), register_label_provider(), register_on_commit_action(), ReindexMultipleTables(), ReindexPartitions(), ReindexRelationConcurrently(), RelationBuildDesc(), RelationBuildLocalRelation(), RelationBuildPartitionDesc(), RelationBuildPartitionKey(), RelationBuildPublicationDesc(), RelationBuildRowSecurity(), RelationBuildRuleLock(), RelationBuildTriggers(), RelationBuildTupleDesc(), RelationCacheInitializePhase2(), RelationCacheInitializePhase3(), RelationGetExclusionInfo(), RelationGetFKeyList(), RelationGetIdentityKeyBitmap(), RelationGetIndexAttOptions(), RelationGetIndexAttrBitmap(), RelationGetIndexExpressions(), RelationGetIndexList(), RelationGetIndexPredicate(), RelationGetStatExtList(), RelationInitIndexAccessInfo(), ReleaseCurrentSubTransaction(), RememberSyncRequest(), RememberToFreeTupleDescAtEOX(), ReorderBufferAddInvalidations(), ReorderBufferProcessTXN(), ReorderBufferQueueMessage(), ReorderBufferToastReplace(), reorderqueue_push(), reparameterize_path_by_child(), resetSpGistScanOpaque(), ResetUnloggedRelations(), RestoreReindexState(), ReThrowError(), RevalidateCachedQuery(), rewrite_heap_tuple(), roles_is_member_of(), RunFromStore(), scanPendingInsert(), SearchCatCacheList(), send_feedback(), sepgsql_avc_compute(), sepgsql_fmgr_hook(), sepgsql_set_client_label(), serializeAnalyzeReceive(), set_schema_sent_in_streamed_txn(), setup_background_workers(), setup_firstcall(), SharedRecordTypmodRegistryAttach(), SharedRecordTypmodRegistryInit(), shdepReassignOwned(), show_all_settings(), ShutdownExprContext(), SnapBuildSerialize(), spg_box_quad_inner_consistent(), spg_kd_inner_consistent(), spg_quad_inner_consistent(), spg_range_quad_inner_consistent(), spg_redo(), spgInnerTest(), spginsert(), spgistBuildCallback(), spgLeafTest(), SPI_connect_ext(), SPI_copytuple(), SPI_cursor_open_internal(), SPI_datumTransfer(), spi_dest_startup(), SPI_finish(), SPI_modifytuple(), spi_printtup(), SPI_returntuple(), spool_tuples(), ssl_extension_info(), standard_ExecutorEnd(), standard_ExecutorFinish(), standard_ExecutorRun(), standard_ExecutorStart(), standard_ExplainOneQuery(), startScanKey(), StartTransactionCommand(), StartupDecodingContext(), statext_dependencies_build(), store_flush_position(), storeRow(), stream_open_file(), stream_start_internal(), string_agg_combine(), strlist_to_textarray(), sts_parallel_scan_next(), sts_puttuple(), subxact_info_add(), subxact_info_read(), test_create(), test_pattern(), test_regex(), tfuncFetchRows(), tfuncLoadRows(), ThrowErrorData(), tokenize_auth_file(), tokenize_expand_file(), TriggerEnabled(), ts_setup_firstcall(), tsquery_rewrite_query(), tstoreReceiveSlot_detoast(), tsvector_unnest(), tt_setup_firstcall(), tts_buffer_heap_copyslot(), tts_buffer_heap_materialize(), tts_heap_copyslot(), tts_heap_materialize(), tts_minimal_copyslot(), tts_minimal_materialize(), TupleHashTableHash(), tuplesort_begin_batch(), tuplesort_begin_cluster(), tuplesort_begin_common(), tuplesort_begin_datum(), tuplesort_begin_heap(), tuplesort_begin_index_btree(), tuplesort_begin_index_gist(), tuplesort_begin_index_hash(), tuplesort_free(), tuplesort_getbrintuple(), tuplesort_getdatum(), tuplesort_getheaptuple(), tuplesort_getindextuple(), tuplesort_gettupleslot(), tuplesort_markpos(), tuplesort_performsort(), tuplesort_putbrintuple(), tuplesort_putdatum(), tuplesort_putheaptuple(), tuplesort_puttuple_common(), tuplesort_puttupleslot(), tuplesort_rescan(), tuplesort_restorepos(), tuplesort_skiptuples(), tuplestore_puttuple(), tuplestore_puttupleslot(), tuplestore_putvalues(), union_tuples(), update_cached_tupdesc(), update_frameheadpos(), update_frametailpos(), update_grouptailpos(), uuid_sortsupport(), vacuum(), validateForeignKeyConstraint(), ValuesNext(), WalSummarizerMain(), WalWriterMain(), window_gettupleslot(), and XLogInsertRecord().

◆ 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 1456 of file radixtree.h.

1457 {
1458  RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
1459  int insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
1460 
1461  /* shift chunks and children */
1463  n16->base.count, insertpos);
1464 
1465  /* insert new chunk into place */
1466  n16->chunks[insertpos] = chunk;
1467 
1468  n16->base.count++;
1469  RT_VERIFY_NODE((RT_NODE *) n16);
1470 
1471  return &n16->children[insertpos];
1472 }
uint64 chunk
#define RT_NODE_16_GET_INSERTPOS
Definition: radixtree.h:211
#define RT_VERIFY_NODE
Definition: radixtree.h:240
#define RT_SHIFT_ARRAYS_FOR_INSERT
Definition: radixtree.h:212
RT_NODE base
Definition: radixtree.h:528
RT_PTR_ALLOC children[FLEXIBLE_ARRAY_MEMBER]
Definition: radixtree.h:533
uint8 chunks[RT_FANOUT_16_MAX]
Definition: radixtree.h:530
uint8 count
Definition: radixtree.h:392
RT_NODE * local
Definition: radixtree.h:419

References RT_NODE_16::base, RT_NODE_16::children, chunk, 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 1268 of file radixtree.h.

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

References RT_NODE_256::base, chunk, 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 1509 of file radixtree.h.

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

References RT_NODE_4::base, RT_NODE_4::children, chunk, 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 1331 of file radixtree.h.

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

References Assert, RT_NODE_48::base, BITS_PER_BITMAPWORD, bmw_rightmost_one_pos, RT_NODE_48::children, chunk, 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 893 of file radixtree.h.

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

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 828 of file radixtree.h.

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

References RT_CHILD_PTR::alloc, dsa_allocate, RT_NODE::fanout, RT_NODE_256::isset, RT_NODE_48::isset, 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 2080 of file radixtree.h.

2081 {
2082  RT_ITER *iter;
2084 
2085  iter = (RT_ITER *) MemoryContextAllocZero(tree->iter_context,
2086  sizeof(RT_ITER));
2087  iter->tree = tree;
2088 
2089  Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2090  root.alloc = iter->tree->ctl->root;
2092 
2093  iter->top_level = iter->tree->ctl->start_shift / RT_SPAN;
2094 
2095  /* Set the root to start */
2096  iter->cur_level = iter->top_level;
2097  iter->node_iters[iter->cur_level].node = root;
2098  iter->node_iters[iter->cur_level].idx = 0;
2099 
2100  return iter;
2101 }
void * MemoryContextAllocZero(MemoryContext context, Size size)
Definition: mcxt.c:1214
#define RT_SPAN
Definition: radixtree.h:312
tree ctl root
Definition: radixtree.h:1884
#define RT_PTR_ALLOC_IS_VALID(ptr)
Definition: radixtree.h:404
RT_NODE_ITER node_iters[RT_MAX_LEVEL]
Definition: radixtree.h:748
int cur_level
Definition: radixtree.h:750
RT_RADIX_TREE * tree
Definition: radixtree.h:742
int top_level
Definition: radixtree.h:749
RT_CHILD_PTR node
Definition: radixtree.h:729
RT_PTR_ALLOC root
Definition: radixtree.h:688
RT_RADIX_TREE_CONTROL * ctl
Definition: radixtree.h:706

References Assert, RT_RADIX_TREE::ctl, RT_ITER::cur_level, RT_NODE_ITER::idx, MemoryContextAllocZero(), RT_NODE_ITER::node, RT_ITER::node_iters, 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 461 of file radixtree.h.

462 {
463 #ifdef RT_VARLEN_VALUE_SIZE
464 
465 #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
466  /* check for pointer tag */
467 #ifdef RT_SHMEM
468  return child & 1;
469 #else
470  return ((uintptr_t) child) & 1;
471 #endif
472 
473 #else
474  return false;
475 #endif
476 
477 #else
478  return sizeof(RT_VALUE_TYPE) <= sizeof(RT_PTR_ALLOC);
479 #endif
480 }
#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 1251 of file radixtree.h.

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

References i.

◆ RT_COPY_COMMON()

static void RT_COPY_COMMON ( RT_CHILD_PTR  newnode,
RT_CHILD_PTR  oldnode 
)
inlinestatic

Definition at line 916 of file radixtree.h.

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

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 2254 of file radixtree.h.

2255 {
2256  pfree(iter);
2257 }
void pfree(void *pointer)
Definition: mcxt.c:1520

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 1612 of file radixtree.h.

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

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 1577 of file radixtree.h.

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

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 1090 of file radixtree.h.

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

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 2047 of file radixtree.h.

2048 {
2049 #ifdef RT_SHMEM
2050  Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2051 
2052  /* Free all memory used for radix tree nodes */
2053  Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
2054  RT_FREE_RECURSE(tree, tree->ctl->root, tree->ctl->start_shift);
2055 
2056  /*
2057  * Vandalize the control block to help catch programming error where other
2058  * backends access the memory formerly occupied by this radix tree.
2059  */
2060  tree->ctl->magic = 0;
2061  dsa_free(tree->dsa, tree->ctl->handle);
2062 #endif
2063 
2064  /*
2065  * Free all space allocated within the tree's context and delete all child
2066  * contexts such as those used for nodes.
2067  */
2068  MemoryContextReset(tree->context);
2069 }
void dsa_free(dsa_area *area, dsa_pointer dp)
Definition: dsa.c:826
void MemoryContextReset(MemoryContext context)
Definition: mcxt.c:383
#define RT_FREE_RECURSE
Definition: radixtree.h:204

References Assert, dsa_free(), MemoryContextReset(), 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 955 of file radixtree.h.

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

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 923 of file radixtree.h.

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

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 1659 of file radixtree.h.

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

References RT_CHILD_PTR::alloc, chunk, 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 1369 of file radixtree.h.

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

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

References RT_CHILD_PTR::alloc, Assert, RT_NODE_4::base, RT_NODE_16::base, RT_NODE_4::children, RT_NODE_16::children, chunk, 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 1284 of file radixtree.h.

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

References bit(), BITS_PER_BITMAPWORD, RT_NODE_48::children, chunk, 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 2204 of file radixtree.h.

2205 {
2206  RT_PTR_ALLOC *slot = NULL;
2207 
2208  while (iter->cur_level <= iter->top_level)
2209  {
2210  RT_CHILD_PTR node;
2211 
2212  slot = RT_NODE_ITERATE_NEXT(iter, iter->cur_level);
2213 
2214  if (iter->cur_level == 0 && slot != NULL)
2215  {
2216  /* Found a value at the leaf node */
2217  *key_p = iter->key;
2218  node.alloc = *slot;
2219 
2220  if (RT_CHILDPTR_IS_VALUE(*slot))
2221  return (RT_VALUE_TYPE *) slot;
2222  else
2223  {
2224  RT_PTR_SET_LOCAL(iter->tree, &node);
2225  return (RT_VALUE_TYPE *) node.local;
2226  }
2227  }
2228 
2229  if (slot != NULL)
2230  {
2231  /* Found the child slot, move down the tree */
2232  node.alloc = *slot;
2233  RT_PTR_SET_LOCAL(iter->tree, &node);
2234 
2235  iter->cur_level--;
2236  iter->node_iters[iter->cur_level].node = node;
2237  iter->node_iters[iter->cur_level].idx = 0;
2238  }
2239  else
2240  {
2241  /* Not found the child slot, move up the tree */
2242  iter->cur_level++;
2243  }
2244  }
2245 
2246  /* We've visited all nodes, so the iteration finished */
2247  return NULL;
2248 }
#define RT_NODE_ITERATE_NEXT
Definition: radixtree.h:239
uint64 key
Definition: radixtree.h:753

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 804 of file radixtree.h.

805 {
806  if (key == 0)
807  return 0;
808  else
810 }
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 2674 of file radixtree.h.

2675 {
2676  size_t total = 0;
2677 
2678 #ifdef RT_SHMEM
2679  Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2680  total = dsa_get_total_size(tree->dsa);
2681 #else
2682  total = MemoryContextMemAllocated(tree->context, true);
2683 #endif
2684 
2685  return total;
2686 }
size_t dsa_get_total_size(dsa_area *area)
Definition: dsa.c:1027
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 1156 of file radixtree.h.

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

References Assert, RT_NODE_16::base, chunk, RT_NODE_16::chunks, RT_NODE::count, pg_rightmost_one_pos32(), 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 979 of file radixtree.h.

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

References Assert, RT_NODE_16::base, RT_NODE_16::children, chunk, RT_NODE_16::chunks, RT_NODE::count, i, pg_rightmost_one_pos32(), RT_PTR_ALLOC, 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 794 of file radixtree.h.

795 {
797  return &node->children[chunk];
798 }
#define RT_NODE_256_IS_CHUNK_USED
Definition: radixtree.h:218
RT_PTR_ALLOC children[RT_FANOUT_256]
Definition: radixtree.h:570

References Assert, RT_NODE_256::children, chunk, 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 785 of file radixtree.h.

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

References chunk, 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 778 of file radixtree.h.

779 {
780  return &node->children[node->slot_idxs[chunk]];
781 }

References RT_NODE_48::children, chunk, 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 772 of file radixtree.h.

773 {
774  return node->slot_idxs[chunk] != RT_INVALID_SLOT_IDX;
775 }

References chunk, 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 1138 of file radixtree.h.

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

References chunk, 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 1537 of file radixtree.h.

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

References chunk, 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 2108 of file radixtree.h.

2109 {
2110  uint8 key_chunk = 0;
2111  RT_NODE_ITER *node_iter;
2112  RT_CHILD_PTR node;
2113  RT_PTR_ALLOC *slot = NULL;
2114 
2115 #ifdef RT_SHMEM
2116  Assert(iter->tree->ctl->magic == RT_RADIX_TREE_MAGIC);
2117 #endif
2118 
2119  node_iter = &(iter->node_iters[level]);
2120  node = node_iter->node;
2121 
2122  Assert(node.local != NULL);
2123 
2124  switch ((node.local)->kind)
2125  {
2126  case RT_NODE_KIND_4:
2127  {
2128  RT_NODE_4 *n4 = (RT_NODE_4 *) (node.local);
2129 
2130  if (node_iter->idx >= n4->base.count)
2131  return NULL;
2132 
2133  slot = &n4->children[node_iter->idx];
2134  key_chunk = n4->chunks[node_iter->idx];
2135  node_iter->idx++;
2136  break;
2137  }
2138  case RT_NODE_KIND_16:
2139  {
2140  RT_NODE_16 *n16 = (RT_NODE_16 *) (node.local);
2141 
2142  if (node_iter->idx >= n16->base.count)
2143  return NULL;
2144 
2145  slot = &n16->children[node_iter->idx];
2146  key_chunk = n16->chunks[node_iter->idx];
2147  node_iter->idx++;
2148  break;
2149  }
2150  case RT_NODE_KIND_48:
2151  {
2152  RT_NODE_48 *n48 = (RT_NODE_48 *) (node.local);
2153  int chunk;
2154 
2155  for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
2156  {
2157  if (RT_NODE_48_IS_CHUNK_USED(n48, chunk))
2158  break;
2159  }
2160 
2161  if (chunk >= RT_NODE_MAX_SLOTS)
2162  return NULL;
2163 
2164  slot = RT_NODE_48_GET_CHILD(n48, chunk);
2165 
2166  key_chunk = chunk;
2167  node_iter->idx = chunk + 1;
2168  break;
2169  }
2170  case RT_NODE_KIND_256:
2171  {
2172  RT_NODE_256 *n256 = (RT_NODE_256 *) (node.local);
2173  int chunk;
2174 
2175  for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
2176  {
2177  if (RT_NODE_256_IS_CHUNK_USED(n256, chunk))
2178  break;
2179  }
2180 
2181  if (chunk >= RT_NODE_MAX_SLOTS)
2182  return NULL;
2183 
2184  slot = RT_NODE_256_GET_CHILD(n256, chunk);
2185 
2186  key_chunk = chunk;
2187  node_iter->idx = chunk + 1;
2188  break;
2189  }
2190  }
2191 
2192  /* Update the key */
2193  iter->key &= ~(((uint64) RT_CHUNK_MASK) << (level * RT_SPAN));
2194  iter->key |= (((uint64) key_chunk) << (level * RT_SPAN));
2195 
2196  return slot;
2197 }
#define RT_NODE_48_GET_CHILD
Definition: radixtree.h:217
#define RT_NODE_48_IS_CHUNK_USED
Definition: radixtree.h:216
#define RT_CHUNK_MASK
Definition: radixtree.h:321

References Assert, RT_NODE_4::base, RT_NODE_16::base, RT_NODE_4::children, RT_NODE_16::children, chunk, 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 1038 of file radixtree.h.

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

References Assert, RT_NODE_4::base, RT_NODE_4::children, chunk, 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 761 of file radixtree.h.

762 {
763 #ifdef RT_SHMEM
764  node->local = dsa_get_address(tree->dsa, node->alloc);
765 #endif
766 }
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 1701 of file radixtree.h.

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

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 1229 of file radixtree.h.

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

References i.

◆ RT_SHIFT_GET_MAX_VAL()

static uint64 RT_SHIFT_GET_MAX_VAL ( int  shift)
static

Definition at line 816 of file radixtree.h.

817 {
818  if (shift == RT_MAX_SHIFT)
819  return UINT64_MAX;
820  else
821  return (UINT64CONST(1) << (shift + RT_SPAN)) - 1;
822 }
#define RT_MAX_SHIFT
Definition: radixtree.h:324

References RT_MAX_SHIFT, and RT_SPAN.

◆ RT_VALUE_IS_EMBEDDABLE()

static bool RT_VALUE_IS_EMBEDDABLE ( RT_VALUE_TYPE value_p)
inlinestatic

Definition at line 441 of file radixtree.h.

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

References RT_GET_VALUE_SIZE, and RT_PTR_ALLOC.

◆ RT_VERIFY_NODE()

static void RT_VERIFY_NODE ( RT_NODE node)
static

Definition at line 2692 of file radixtree.h.

2693 {
2694 #ifdef USE_ASSERT_CHECKING
2695 
2696  switch (node->kind)
2697  {
2698  case RT_NODE_KIND_4:
2699  {
2700  RT_NODE_4 *n4 = (RT_NODE_4 *) node;
2701 
2702  /* RT_DUMP_NODE(node); */
2703 
2704  for (int i = 1; i < n4->base.count; i++)
2705  Assert(n4->chunks[i - 1] < n4->chunks[i]);
2706 
2707  break;
2708  }
2709  case RT_NODE_KIND_16:
2710  {
2711  RT_NODE_16 *n16 = (RT_NODE_16 *) node;
2712 
2713  /* RT_DUMP_NODE(node); */
2714 
2715  for (int i = 1; i < n16->base.count; i++)
2716  Assert(n16->chunks[i - 1] < n16->chunks[i]);
2717 
2718  break;
2719  }
2720  case RT_NODE_KIND_48:
2721  {
2722  RT_NODE_48 *n48 = (RT_NODE_48 *) node;
2723  int cnt = 0;
2724 
2725  /* RT_DUMP_NODE(node); */
2726 
2727  for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
2728  {
2729  uint8 slot = n48->slot_idxs[i];
2730  int idx = RT_BM_IDX(slot);
2731  int bitnum = RT_BM_BIT(slot);
2732 
2733  if (!RT_NODE_48_IS_CHUNK_USED(n48, i))
2734  continue;
2735 
2736  /* Check if the corresponding slot is used */
2737  Assert(slot < node->fanout);
2738  Assert((n48->isset[idx] & ((bitmapword) 1 << bitnum)) != 0);
2739 
2740  cnt++;
2741  }
2742 
2743  Assert(n48->base.count == cnt);
2744 
2745  break;
2746  }
2747  case RT_NODE_KIND_256:
2748  {
2749  RT_NODE_256 *n256 = (RT_NODE_256 *) node;
2750  int cnt = 0;
2751 
2752  /* RT_DUMP_NODE(node); */
2753 
2754  for (int i = 0; i < RT_BM_IDX(RT_NODE_MAX_SLOTS); i++)
2755  cnt += bmw_popcount(n256->isset[i]);
2756 
2757  /*
2758  * Check if the number of used chunk matches, accounting for
2759  * overflow
2760  */
2761  if (cnt == RT_FANOUT_256)
2762  Assert(n256->base.count == 0);
2763  else
2764  Assert(n256->base.count == cnt);
2765 
2766  break;
2767  }
2768  }
2769 #endif
2770 }
#define bmw_popcount(w)
Definition: bitmapset.h:80
#define RT_FANOUT_256
Definition: radixtree.h:504

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

◆ context

tree context = ctx

Definition at line 1833 of file radixtree.h.

Referenced by _SPI_execute_plan(), acquireLocksOnSubLinks(), AcquireRewriteLocks(), add_nulling_relids(), add_nulling_relids_mutator(), adjust_appendrel_attrs(), adjust_appendrel_attrs_mutator(), adjust_inherited_attnums(), AllocateSnapshotBuilder(), AllocSetAlloc(), AllocSetAllocFromNewBlock(), AllocSetAllocLarge(), AllocSetDelete(), AllocSetIsEmpty(), AllocSetReset(), AllocSetStats(), AlterTable(), appendAggOrderBy(), appendConditions(), appendContextKeyword(), appendFunctionName(), appendGroupByClause(), appendLimitClause(), appendOrderByClause(), appendOrderBySuffix(), appendWhereClause(), assign_collations_walker(), assign_expr_collations(), ATController(), ATExecAddColumn(), ATExecAttachPartition(), ATExecCmd(), ATExecMergePartitions(), ATExecSplitPartition(), ATParseTransformCmd(), ATPrepAddColumn(), ATPrepAlterColumnType(), ATPrepCmd(), ATPrepDropColumn(), ATPrepSetNotNull(), ATRewriteCatalogs(), ATRewriteTables(), ATSimpleRecursion(), ATTypedTableRecursion(), bbstreamer_content(), bbstreamer_extractor_content(), bbstreamer_recovery_injector_content(), bbstreamer_tar_archiver_content(), bbstreamer_tar_parser_content(), bbstreamer_tar_terminator_content(), be_tls_init(), BuildV1Call(), BumpAlloc(), BumpAllocFromNewBlock(), BumpAllocLarge(), BumpBlockInit(), BumpDelete(), BumpIsEmpty(), BumpReset(), BumpStats(), can_minmax_aggs(), ChangeVarNodes(), ChangeVarNodes_walker(), check_agg_arguments(), check_agg_arguments_walker(), check_functions_in_node(), check_nested_generated_walker(), check_ungrouped_columns(), check_ungrouped_columns_walker(), checkExprHasSubLink_walker(), coerce_to_common_type(), combinebackup_per_file_cb(), combinebackup_per_wal_range_cb(), combinebackup_system_identifier_cb(), contain_agg_clause_walker(), contain_aggs_of_level(), contain_aggs_of_level_walker(), contain_dml_walker(), contain_invalid_rfcolumn_walker(), contain_leaked_vars_walker(), contain_mutable_functions_walker(), contain_non_const_walker(), contain_nonstrict_functions_walker(), contain_placeholder_references_to(), contain_placeholder_references_walker(), contain_subplans_walker(), contain_var_clause_walker(), contain_volatile_functions_not_nextval_walker(), contain_volatile_functions_walker(), contain_windowfuncs_walker(), contains_multiexpr_param(), convert_combining_aggrefs(), convert_testexpr(), convert_testexpr_mutator(), CopyAndAddInvertedQual(), cost_qual_eval(), cost_qual_eval_node(), cost_qual_eval_walker(), CreateIncrementalBackupInfo(), createPartitionTable(), dblink_fdw_validator(), default_openssl_tls_init(), DefineCustomBoolVariable(), DefineCustomEnumVariable(), DefineCustomIntVariable(), DefineCustomRealVariable(), DefineCustomStringVariable(), deparse_expression_pretty(), deparseAggref(), deparseArrayExpr(), deparseBoolExpr(), deparseCaseExpr(), deparseConst(), deparseDirectDeleteSql(), deparseDirectUpdateSql(), deparseDistinctExpr(), deparseExplicitTargetList(), deparseExpr(), deparseFromExpr(), deparseFromExprForRel(), deparseFuncExpr(), deparseLockingClause(), deparseNullTest(), deparseOpExpr(), deparseParam(), deparseRelabelType(), deparseScalarArrayOpExpr(), deparseSelectSql(), deparseSelectStmtForRel(), deparseSortGroupClause(), deparseSubqueryTargetList(), deparseSubscriptingRef(), deparseVar(), ece_function_is_safe(), errcontext_msg(), errsave_finish(), errsave_start(), estimate_expression_value(), eval_const_expressions(), eval_const_expressions_mutator(), evaluate_function(), EventTriggerInvoke(), exec_object_restorecon(), ExecCrossPartitionUpdate(), ExecCrossPartitionUpdateForeignKey(), ExecDelete(), ExecDeleteAct(), ExecDeleteEpilogue(), ExecDeletePrologue(), ExecInsert(), ExecMerge(), ExecMergeMatched(), ExecMergeNotMatched(), ExecModifyTable(), ExecOnConflictUpdate(), ExecShutdownNode_walker(), ExecUpdate(), ExecUpdateAct(), ExecUpdateEpilogue(), ExecUpdatePrologue(), expression_returns_set_walker(), expression_tree_mutator_impl(), extract_query_dependencies_walker(), finalize_agg_primnode(), finalize_grouping_exprs(), finalize_grouping_exprs_walker(), finalize_plan(), finalize_primnode(), find_cols(), find_cols_walker(), find_dependent_phvs(), find_dependent_phvs_in_jointree(), find_dependent_phvs_walker(), find_expr_references_walker(), find_param_generator(), find_param_referent(), fireRIRrules(), fix_join_expr(), fix_join_expr_mutator(), fix_opfuncids_walker(), fix_scan_expr(), fix_scan_expr_mutator(), fix_scan_expr_walker(), fix_upper_expr(), fix_upper_expr_mutator(), fix_windowagg_condition_expr(), fix_windowagg_condition_expr_mutator(), flatten_join_alias_vars(), flatten_join_alias_vars_mutator(), fmgr_security_definer(), FreeSnapshotBuilder(), g_box_consider_split(), gen_partprune_steps(), gen_partprune_steps_internal(), gen_prune_step_combine(), gen_prune_step_op(), gen_prune_steps_from_opexps(), GenerationAlloc(), GenerationAllocFromNewBlock(), GenerationAllocLarge(), GenerationBlockInit(), GenerationDelete(), GenerationIsEmpty(), GenerationReset(), GenerationStats(), get_agg_combine_expr(), get_agg_expr(), get_agg_expr_helper(), get_basic_select_query(), get_coercion_expr(), get_column_alias_list(), get_const_collation(), get_const_expr(), get_delete_query_def(), get_from_clause(), get_from_clause_coldeflist(), get_from_clause_item(), get_func_expr(), get_func_sql_syntax(), get_insert_query_def(), get_json_agg_constructor(), get_json_behavior(), get_json_constructor(), get_json_expr_options(), get_json_path_spec(), get_json_table(), get_json_table_columns(), get_json_table_nested_columns(), get_list_partvalue_string(), get_matching_hash_bounds(), get_matching_list_bounds(), get_matching_partitions(), get_matching_range_bounds(), get_merge_query_def(), get_name_for_var_field(), get_oper_expr(), get_parameter(), get_query_def(), get_range_partbound_string(), get_rtable_name(), get_rte_alias(), get_rule_expr(), get_rule_expr_funccall(), get_rule_expr_paren(), get_rule_expr_toplevel(), get_rule_groupingset(), get_rule_list_toplevel(), get_rule_orderby(), get_rule_sortgroupclause(), get_rule_windowclause(), get_rule_windowspec(), get_select_query_def(), get_setop_query(), get_special_variable(), get_steps_using_prefix(), get_steps_using_prefix_recurse(), get_sublink_expr(), get_tablefunc(), get_tablesample_def(), get_target_list(), get_update_query_def(), get_update_query_targetlist_def(), get_utility_query_def(), get_values_def(), get_variable(), get_windowfunc_expr(), get_windowfunc_expr_helper(), get_with_clause(), get_xmltable(), GetSearchPathMatcher(), gist_box_picksplit(), IncrementVarSublevelsUp(), IncrementVarSublevelsUp_rtable(), IncrementVarSublevelsUp_walker(), index_form_tuple_context(), init_custom_variable(), initialize_dh(), initialize_ecdh(), InitPartitionPruneContext(), inline_cte(), inline_cte_walker(), inline_function(), is_conninfo_option(), is_parallel_safe(), is_valid_dblink_option(), is_valid_option(), isPlainForeignVar(), isQueryUsingTempRelation_walker(), jit_release_context(), json_manifest_finalize_file(), json_manifest_finalize_system_identifier(), json_manifest_finalize_version(), json_manifest_finalize_wal_range(), json_manifest_parse_failure(), json_parse_manifest(), json_parse_manifest_incremental_chunk(), json_parse_manifest_incremental_init(), llvm_compile_expr(), llvm_compile_module(), llvm_create_context(), llvm_expand_funcname(), llvm_get_function(), llvm_mutable_module(), llvm_optimize_module(), llvm_release_context(), load_backup_manifest(), locate_agg_of_level(), locate_agg_of_level_walker(), locate_var_of_level(), locate_var_of_level_walker(), locate_windowfunc(), locate_windowfunc_walker(), LockViewRecurse(), LockViewRecurse_walker(), lookupCreateVariable(), main(), make_partitionedrel_pruneinfo(), make_ruledef(), manifest_process_file(), manifest_process_system_identifier(), manifest_process_version(), manifest_process_wal_range(), map_variable_attnos(), map_variable_attnos_mutator(), match_clause_to_partition_key(), max_parallel_hazard(), max_parallel_hazard_checker(), max_parallel_hazard_test(), max_parallel_hazard_walker(), MemoryContextAlloc(), MemoryContextAllocAligned(), MemoryContextAllocationFailure(), MemoryContextAllocExtended(), MemoryContextAllocHuge(), MemoryContextAllocZero(), MemoryContextAllowInCriticalSection(), MemoryContextCallResetCallbacks(), MemoryContextCheckSize(), MemoryContextDelete(), MemoryContextDeleteChildren(), MemoryContextDeleteOnly(), MemoryContextGetParent(), MemoryContextIsEmpty(), MemoryContextMemAllocated(), MemoryContextMemConsumed(), MemoryContextRegisterResetCallback(), MemoryContextReset(), MemoryContextResetChildren(), MemoryContextResetOnly(), MemoryContextSetIdentifier(), MemoryContextSetParent(), MemoryContextStats(), MemoryContextStatsDetail(), MemoryContextStatsInternal(), MemoryContextStatsPrint(), MemoryContextStrdup(), MemoryContextSwitchTo(), merge_collation_state(), OffsetVarNodes(), OffsetVarNodes_walker(), palloc(), palloc0(), palloc_extended(), ParallelSlotSetHandler(), parse_manifest_file(), parse_required_wal(), partkey_datum_from_expr(), perform_pruning_base_step(), perform_pruning_combine_step(), pfree(), pg_checksum_final(), pg_checksum_init(), pg_checksum_update(), pg_get_constraintdef_worker(), pg_get_expr_worker(), pg_get_indexdef_worker(), pg_get_partconstrdef_string(), pg_get_partition_constraintdef(), pg_get_partkeydef_worker(), pg_get_statisticsobj_worker(), pg_get_statisticsobjdef_expressions(), pg_get_triggerdef_worker(), pg_sha224_final(), pg_sha224_init(), pg_sha224_update(), pg_sha256_final(), pg_sha256_init(), pg_sha256_update(), pg_sha384_final(), pg_sha384_init(), pg_sha384_update(), pg_sha512_final(), pg_sha512_init(), pg_sha512_update(), pgss_ProcessUtility(), planstate_tree_walker_impl(), PLy_get_scratch_context(), PLy_pop_execution_context(), PLy_push_execution_context(), pqParseIntParam(), printRemoteParam(), printRemotePlaceholder(), printSubscripts(), process_function_rte_ref(), process_sublinks_mutator(), ProcessConfigFileInternal(), ProcessGUCArray(), processIndirection(), ProcessUtility(), ProcessUtilityForAlterTable(), ProcessUtilitySlow(), prune_append_rel_partitions(), pub_rf_contains_invalid_column(), pull_exec_paramids_walker(), pull_paramids_walker(), pull_var_clause(), pull_var_clause_walker(), pull_varattnos(), pull_varattnos_walker(), pull_varnos(), pull_varnos_of_level(), pull_varnos_walker(), pull_vars_of_level(), pull_vars_walker(), pullup_replace_vars(), pullup_replace_vars_callback(), pullup_replace_vars_subquery(), PutMemoryContextsStatsTupleStore(), putVariable(), putVariableInt(), putVariableValue(), query_contains_extern_params_walker(), query_or_expression_tree_mutator_impl(), query_or_expression_tree_walker_impl(), query_tree_mutator_impl(), query_tree_walker_impl(), range_gist_consider_split(), range_gist_double_sorting_split(), range_table_walker_impl(), rangeTableEntry_used(), rangeTableEntry_used_walker(), rank_up(), recordDependencyOnExpr(), recordDependencyOnSingleRelExpr(), REGRESS_utility_command(), remove_nulling_relids(), remove_nulling_relids_mutator(), ReorderBufferFree(), repalloc(), repalloc_extended(), replace_rte_variables(), replace_rte_variables_mutator(), replace_vars_in_jointree(), ReplaceVarsFromTargetList(), ReplaceVarsFromTargetList_callback(), report_backup_error(), report_extra_backup_files(), resolve_special_varno(), ResOwnerReleaseJitContext(), RestoreUserContext(), rewriteRuleAction(), rewriteTargetView(), select_common_collation(), select_common_type(), sepgsql_utility_command(), set_config_option(), set_config_option_ext(), set_config_with_handle(), set_debug_options(), set_plan_disabling_options(), set_rot13(), SetConfigOption(), setRuleCheckAsUser_walker(), SHA256_Last(), SHA256_Transform(), SHA512_Last(), SHA512_Transform(), should_ignore_relpath(), show_expression(), show_grouping_set_keys(), show_grouping_sets(), show_memoize_info(), show_plan_tlist(), show_sort_group_keys(), show_tablesample(), simplify_and_arguments(), simplify_function(), simplify_or_arguments(), SlabAlloc(), SlabAllocFromNewBlock(), SlabAllocSetupNewChunk(), SlabDelete(), SlabIsEmpty(), SlabReset(), SlabStats(), slot_compile_deform(), split_pathtarget_at_srfs(), split_pathtarget_walker(), SS_process_sublinks(), standard_ProcessUtility(), StartupDecodingContext(), substitute_actual_parameters(), substitute_actual_parameters_mutator(), substitute_actual_srf_parameters(), substitute_actual_srf_parameters_mutator(), substitute_phv_relids(), substitute_phv_relids_walker(), SwitchToUntrustedUser(), transformSetOperationTree(), ValidJsonBehaviorDefaultExpr(), verify_backup_checksums(), verify_backup_directory(), verify_backup_file(), verify_btree_slot_handler(), verify_file_checksum(), verify_heap_slot_handler(), verify_manifest_checksum(), verifybackup_per_file_cb(), verifybackup_per_wal_range_cb(), verifybackup_system_identifier(), verifybackup_version_cb(), WalSummarizerMain(), window_cume_dist(), window_dense_rank(), window_ntile(), window_percent_rank(), window_rank(), and WritebackContextInit().

◆ ctl

Definition at line 1851 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_collation_cache(), lookup_proof_cache(), lookup_ts_dictionary_cache(), lookup_ts_parser_cache(), lookup_type_cache(), LookupOpclassInfo(), pa_allocate_worker(), 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(), and test_slru_scan_cb().

◆ iter_context

tree iter_context
Initial value:
RT_STR(RT_PREFIX) "_radix_tree iter context",
#define AllocSetContextCreate
Definition: memutils.h:129
#define ALLOCSET_SMALL_SIZES
Definition: memutils.h:170
#define RT_STR(s)
Definition: radixtree.h:169
#define RT_PREFIX
Definition: tidstore.c:101

Definition at line 1839 of file radixtree.h.

◆ leaf_context

tree leaf_context = tree->context

Definition at line 1866 of file radixtree.h.

◆ max_val

◆ old_ctx

◆ root

tree ctl root = rootnode.alloc

Definition at line 1884 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_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_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(), choose_hashed_setop(), 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_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_partitioned_rtentry(), expand_planner_arrays(), expand_single_inheritance_child(), expr_is_nonnullable(), expression_planner_with_deps(), expression_returns_set_rows(), exprs_known_equal(), extract_jsp_query(), extract_lateral_references(), 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_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_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(), groupclause_apply_groupingset(), 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(), 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_sort_with_costsize(), linear_rand(), logicalrep_partition_open(), ltreeparentsel(), 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_rel_from_joinlist(), make_rels_by_clause_joins(), make_rels_by_clauseless_joins(), make_restrictinfo(), make_restrictinfo_internal(), make_sort_input_target(), make_sub_restrictinfos(), make_subplan(), make_window_input_target(), 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_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_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_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(), 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(), rel_is_distinct_for(), rel_supports_distinctness(), relation_can_be_sorted_early(), relation_excluded_by_constraints(), remap_groupColIdx(), remove_join_clause_from_rels(), remove_rel_from_query(), remove_result_refs(), remove_useless_groupby_columns(), remove_useless_joins(), remove_useless_result_rtes(), remove_useless_results_recurse(), 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_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

Definition at line 1825 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),
},
.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),
},
.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),
},
.name = RT_STR(RT_PREFIX) "_radix_tree node48",
.fanout = RT_FANOUT_48,
.allocsize = sizeof(RT_NODE_48) + RT_FANOUT_48 * sizeof(RT_PTR_ALLOC),
},
.name = RT_STR(RT_PREFIX) "_radix_tree node256",
.fanout = RT_FANOUT_256,
.allocsize = sizeof(RT_NODE_256),
},
}
#define RT_NODE_4
Definition: radixtree.h:252
#define RT_NODE_256
Definition: radixtree.h:255
#define RT_NODE_48
Definition: radixtree.h:254
#define RT_NODE_16
Definition: radixtree.h:253
#define RT_FANOUT_48
Definition: radixtree.h:597

Definition at line 644 of file radixtree.h.

◆ start_shift

tree ctl start_shift = 0

Definition at line 1885 of file radixtree.h.

Referenced by RT_SET().

◆ tree