#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_TREE *	RT_CREATE (MemoryContext ctx)

RT_SCOPE void	RT_FREE (RT_RADIX_TREE *tree)

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

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

RT_SCOPE RT_ITER *	RT_BEGIN_ITERATE (RT_RADIX_TREE *tree)

RT_SCOPE RT_VALUE_TYPE *	RT_ITERATE_NEXT (RT_ITER iter, uint64 key_p)

RT_SCOPE void	RT_END_ITERATE (RT_ITER *iter)

RT_SCOPE uint64	RT_MEMORY_USAGE (RT_RADIX_TREE *tree)

static bool	RT_VALUE_IS_EMBEDDABLE (RT_VALUE_TYPE *value_p)

static bool	RT_CHILDPTR_IS_VALUE (RT_PTR_ALLOC child)

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

	StaticAssertDecl (RT_FANOUT_16_LO< RT_FANOUT_16_HI, "LO subclass bigger than HI")

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

static void	RT_VERIFY_NODE (RT_NODE *node)

static void	RT_PTR_SET_LOCAL (RT_RADIX_TREE tree, RT_CHILD_PTR node)

static bool	RT_NODE_48_IS_CHUNK_USED (RT_NODE_48 *node, uint8 chunk)

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

static bool	RT_NODE_256_IS_CHUNK_USED (RT_NODE_256 *node, uint8 chunk)

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

static int	RT_KEY_GET_SHIFT (uint64 key)

static uint64	RT_SHIFT_GET_MAX_VAL (int shift)

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

static RT_CHILD_PTR	RT_ALLOC_LEAF (RT_RADIX_TREE *tree, size_t allocsize)

static void	RT_COPY_COMMON (RT_CHILD_PTR newnode, RT_CHILD_PTR oldnode)

static void	RT_FREE_NODE (RT_RADIX_TREE *tree, RT_CHILD_PTR node)

static void	RT_FREE_LEAF (RT_RADIX_TREE *tree, RT_PTR_ALLOC leaf)

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

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

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

static int	RT_NODE_16_GET_INSERTPOS (RT_NODE_16 *node, uint8 chunk)

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

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

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

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

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

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

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

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

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

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

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

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

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

	for (int i=0;i< RT_NUM_SIZE_CLASSES;i++)

	MemoryContextSwitchTo (old_ctx)

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

Variables
static const RT_SIZE_CLASS_ELEM	RT_SIZE_CLASS_INFO []

RT_SCOPE RT_RADIX_TREE *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 600 of file radixtree.h.

◆ RT_FANOUT_16_LO

#define RT_FANOUT_16_LO 16

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

◆ RT_FANOUT_48

#define RT_FANOUT_48 RT_FANOUT_48_MAX

Definition at line 601 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 555 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 1132 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 676 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

typedef struct RT_RADIX_TREE_CONTROL RT_RADIX_TREE_CONTROL

◆ RT_SIZE_CLASS

typedef enum RT_SIZE_CLASS RT_SIZE_CLASS

◆ RT_SIZE_CLASS_ELEM

typedef struct RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_ELEM

Enumeration Type Documentation

◆ RT_SIZE_CLASS

enum RT_SIZE_CLASS

Enumerator
RT_CLASS_4
RT_CLASS_16_LO
RT_CLASS_16_HI
RT_CLASS_48
RT_CLASS_256

Definition at line 630 of file radixtree.h.

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

Function Documentation

◆ for()

for ( )

Definition at line 1856 of file radixtree.h.

     {
         RT_SIZE_CLASS_ELEM size_class = RT_SIZE_CLASS_INFO[i];
         size_t      inner_blocksize = RT_SLAB_BLOCK_SIZE(size_class.allocsize);
  
         tree->node_slabs[i] = SlabContextCreate(ctx,
                                                 size_class.name,
                                                 inner_blocksize,
                                                 size_class.allocsize);
     }

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(), AbortOutOfAnyTransaction(), 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(), 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_puttuple_common(), 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 1458 of file radixtree.h.

 {
     RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
     int         insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
  
     /* shift chunks and children */
     RT_SHIFT_ARRAYS_FOR_INSERT(n16->chunks, n16->children,
                                n16->base.count, insertpos);
  
     /* insert new chunk into place */
     n16->chunks[insertpos] = chunk;
  
     n16->base.count++;
     RT_VERIFY_NODE((RT_NODE *) n16);
  
     return &n16->children[insertpos];
 }

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

 {
     RT_NODE_256 *n256 = (RT_NODE_256 *) node.local;
     int         idx = RT_BM_IDX(chunk);
     int         bitnum = RT_BM_BIT(chunk);
  
     /* Mark the slot used for "chunk" */
     n256->isset[idx] |= ((bitmapword) 1 << bitnum);
  
     n256->base.count++;
     RT_VERIFY_NODE((RT_NODE *) n256);
  
     return RT_NODE_256_GET_CHILD(n256, chunk);
 }

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

 {
     RT_NODE_4  *n4 = (RT_NODE_4 *) (node.local);
     int         count = n4->base.count;
     int         insertpos = RT_NODE_4_GET_INSERTPOS(n4, chunk, count);
  
     /* shift chunks and children */
     RT_SHIFT_ARRAYS_FOR_INSERT(n4->chunks, n4->children,
                                count, insertpos);
  
     /* insert new chunk into place */
     n4->chunks[insertpos] = chunk;
  
     n4->base.count++;
     RT_VERIFY_NODE((RT_NODE *) n4);
  
     return &n4->children[insertpos];
 }

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

 {
     RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
     int         insertpos;
     int         idx = 0;
     bitmapword  w,
                 inverse;
  
     /* get the first word with at least one bit not set */
     for (int i = 0; i < RT_BM_IDX(RT_FANOUT_48_MAX); i++)
     {
         w = n48->isset[i];
         if (w < ~((bitmapword) 0))
         {
             idx = i;
             break;
         }
     }
  
     /* To get the first unset bit in w, get the first set bit in ~w */
     inverse = ~w;
     insertpos = idx * BITS_PER_BITMAPWORD;
     insertpos += bmw_rightmost_one_pos(inverse);
     Assert(insertpos < n48->base.fanout);
  
     /* mark the slot used by setting the rightmost zero bit */
     n48->isset[idx] |= w + 1;
  
     /* insert new chunk into place */
     n48->slot_idxs[chunk] = insertpos;
  
     n48->base.count++;
     RT_VERIFY_NODE((RT_NODE *) n48);
  
     return &n48->children[insertpos];
 }

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

 {
     RT_CHILD_PTR leaf;
  
 #ifdef RT_SHMEM
     leaf.alloc = dsa_allocate(tree->dsa, allocsize);
     RT_PTR_SET_LOCAL(tree, &leaf);
 #else
     leaf.alloc = (RT_PTR_ALLOC) MemoryContextAlloc(tree->leaf_context, allocsize);
 #endif
  
 #ifdef RT_DEBUG
     tree->ctl->num_leaves++;
 #endif
  
     return leaf;
 }

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

 {
     RT_CHILD_PTR allocnode;
     RT_NODE    *node;
     size_t      allocsize;
  
     allocsize = RT_SIZE_CLASS_INFO[size_class].allocsize;
  
 #ifdef RT_SHMEM
     allocnode.alloc = dsa_allocate(tree->dsa, allocsize);
 #else
     allocnode.alloc = (RT_PTR_ALLOC) MemoryContextAlloc(tree->node_slabs[size_class],
                                                         allocsize);
 #endif
  
     RT_PTR_SET_LOCAL(tree, &allocnode);
     node = allocnode.local;
  
     /* initialize contents */
  
     switch (kind)
     {
         case RT_NODE_KIND_4:
             memset(node, 0, offsetof(RT_NODE_4, children));
             break;
         case RT_NODE_KIND_16:
             memset(node, 0, offsetof(RT_NODE_16, children));
             break;
         case RT_NODE_KIND_48:
             {
                 RT_NODE_48 *n48 = (RT_NODE_48 *) node;
  
                 memset(n48, 0, offsetof(RT_NODE_48, slot_idxs));
                 memset(n48->slot_idxs, RT_INVALID_SLOT_IDX, sizeof(n48->slot_idxs));
                 break;
             }
         case RT_NODE_KIND_256:
             memset(node, 0, offsetof(RT_NODE_256, children));
             break;
         default:
             pg_unreachable();
     }
  
     node->kind = kind;
  
     /*
      * For node256, this will actually overflow to zero, but that's okay
      * because that node doesn't need to introspect this value.
      */
     node->fanout = RT_SIZE_CLASS_INFO[size_class].fanout;
  
 #ifdef RT_DEBUG
     /* update the statistics */
     tree->ctl->num_nodes[size_class]++;
 #endif
  
     return allocnode;
 }

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

◆ RT_BEGIN_ITERATE()

RT_SCOPE RT_ITER * RT_BEGIN_ITERATE ( RT_RADIX_TREE * tree )

Definition at line 2082 of file radixtree.h.

 {
     RT_ITER    *iter;
     RT_CHILD_PTR root;
  
     iter = (RT_ITER *) MemoryContextAllocZero(tree->iter_context,
                                               sizeof(RT_ITER));
     iter->tree = tree;
  
     Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
     root.alloc = iter->tree->ctl->root;
     RT_PTR_SET_LOCAL(tree, &root);
  
     iter->top_level = iter->tree->ctl->start_shift / RT_SPAN;
  
     /* Set the root to start */
     iter->cur_level = iter->top_level;
     iter->node_iters[iter->cur_level].node = root;
     iter->node_iters[iter->cur_level].idx = 0;
  
     return iter;
 }

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.

 {
 #ifdef RT_VARLEN_VALUE_SIZE
  
 #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
     /* check for pointer tag */
 #ifdef RT_SHMEM
     return child & 1;
 #else
     return ((uintptr_t) child) & 1;
 #endif
  
 #else
     return false;
 #endif
  
 #else
     return sizeof(RT_VALUE_TYPE) <= sizeof(RT_PTR_ALLOC);
 #endif
 }

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

 {
     for (int i = 0; i < count; i++)
     {
         int         sourceidx = i;
  
         /* use a branch-free computation to skip the index of the new element */
         int         destidx = i + (i >= insertpos);
  
         dst_chunks[destidx] = src_chunks[sourceidx];
         dst_children[destidx] = src_children[sourceidx];
     }
 }

References i.

◆ RT_COPY_COMMON()

static void RT_COPY_COMMON	(	RT_CHILD_PTR	newnode,
		RT_CHILD_PTR	oldnode
	)

inlinestatic

Definition at line 918 of file radixtree.h.

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

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

 {
     pfree(iter);
 }

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

 {
     RT_CHILD_PTR node,
                 child;
     RT_NODE_4  *n4;
  
     /*
      * The child pointer of the first node in the chain goes in the
      * caller-provided slot.
      */
     child = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
     *parent_slot = child.alloc;
  
     node = child;
     shift -= RT_SPAN;
  
     while (shift > 0)
     {
         child = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
  
         /* We open-code the insertion ourselves, for speed. */
         n4 = (RT_NODE_4 *) node.local;
         n4->base.count = 1;
         n4->chunks[0] = RT_GET_KEY_CHUNK(key, shift);
         n4->children[0] = child.alloc;
  
         node = child;
         shift -= RT_SPAN;
     }
     Assert(shift == 0);
  
     /* Reserve slot for the value. */
     n4 = (RT_NODE_4 *) node.local;
     n4->chunks[0] = RT_GET_KEY_CHUNK(key, 0);
     n4->base.count = 1;
  
     return &n4->children[0];
 }

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

 {
     int         target_shift = RT_KEY_GET_SHIFT(key);
     int         shift = tree->ctl->start_shift;
  
     Assert(shift < target_shift);
  
     /* Grow tree upwards until start shift can accommodate the key */
     while (shift < target_shift)
     {
         RT_CHILD_PTR node;
         RT_NODE_4  *n4;
  
         node = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4);
         n4 = (RT_NODE_4 *) node.local;
         n4->base.count = 1;
         n4->chunks[0] = 0;
         n4->children[0] = tree->ctl->root;
  
         /* Update the root */
         tree->ctl->root = node.alloc;
  
         shift += RT_SPAN;
     }
  
     tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(target_shift);
     tree->ctl->start_shift = target_shift;
 }

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

 {
     RT_CHILD_PTR node;
     RT_PTR_ALLOC *slot = NULL;
     int         shift;
  
 #ifdef RT_SHMEM
     Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
 #endif
  
     if (key > tree->ctl->max_val)
         return NULL;
  
     Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
     node.alloc = tree->ctl->root;
     shift = tree->ctl->start_shift;
  
     /* Descend the tree */
     while (shift >= 0)
     {
         RT_PTR_SET_LOCAL(tree, &node);
         slot = RT_NODE_SEARCH(node.local, RT_GET_KEY_CHUNK(key, shift));
         if (slot == NULL)
             return NULL;
  
         node.alloc = *slot;
         shift -= RT_SPAN;
     }
  
     if (RT_CHILDPTR_IS_VALUE(*slot))
         return (RT_VALUE_TYPE *) slot;
     else
     {
         RT_PTR_SET_LOCAL(tree, &node);
         return (RT_VALUE_TYPE *) node.local;
     }
 }

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

 {
 #ifdef RT_SHMEM
     Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
  
     /* Free all memory used for radix tree nodes */
     Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
     RT_FREE_RECURSE(tree, tree->ctl->root, tree->ctl->start_shift);
  
     /*
      * Vandalize the control block to help catch programming error where other
      * backends access the memory formerly occupied by this radix tree.
      */
     tree->ctl->magic = 0;
     dsa_free(tree->dsa, tree->ctl->handle);
 #endif
  
     /*
      * Free all space allocated within the tree's context and delete all child
      * contexts such as those used for nodes.
      */
     MemoryContextReset(tree->context);
 }

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

 {
     Assert(leaf != tree->ctl->root);
  
 #ifdef RT_DEBUG
     /* update the statistics */
     tree->ctl->num_leaves--;
     Assert(tree->ctl->num_leaves >= 0);
 #endif
  
 #ifdef RT_SHMEM
     dsa_free(tree->dsa, leaf);
 #else
     pfree(leaf);
 #endif
 }

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

 {
 #ifdef RT_DEBUG
     int         i;
  
     /* update the statistics */
  
     for (i = 0; i < RT_NUM_SIZE_CLASSES; i++)
     {
         if ((node.local)->fanout == RT_SIZE_CLASS_INFO[i].fanout)
             break;
     }
  
     /*
      * The fanout of node256 will appear to be zero within the node header
      * because of overflow, so we need an extra check here.
      */
     if (i == RT_NUM_SIZE_CLASSES)
         i = RT_CLASS_256;
  
     tree->ctl->num_nodes[i]--;
     Assert(tree->ctl->num_nodes[i] >= 0);
 #endif
  
 #ifdef RT_SHMEM
     dsa_free(tree->dsa, node.alloc);
 #else
     pfree(node.alloc);
 #endif
 }

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

 {
     RT_PTR_ALLOC *slot;
     RT_CHILD_PTR node;
     uint8       chunk = RT_GET_KEY_CHUNK(key, shift);
  
     node.alloc = *parent_slot;
     RT_PTR_SET_LOCAL(tree, &node);
     slot = RT_NODE_SEARCH(node.local, chunk);
  
     if (slot == NULL)
     {
         *found = false;
  
         /* reserve slot for the caller to populate */
  
         slot = RT_NODE_INSERT(tree, parent_slot, node, chunk);
  
         if (shift == 0)
             return slot;
         else
             return RT_EXTEND_DOWN(tree, slot, key, shift);
     }
     else
     {
         if (shift == 0)
         {
             *found = true;
             return slot;
         }
         else
             return RT_GET_SLOT_RECURSIVE(tree, slot, key, shift - RT_SPAN, found);
     }
 }

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

 {
     RT_NODE_16 *n16 = (RT_NODE_16 *) node.local;
     int         insertpos;
  
     if (n16->base.fanout < RT_FANOUT_16_HI)
     {
         RT_CHILD_PTR newnode;
         RT_NODE_16 *new16;
  
         Assert(n16->base.fanout == RT_FANOUT_16_LO);
  
         /* initialize new node */
         newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_HI);
         new16 = (RT_NODE_16 *) newnode.local;
  
         /* copy over existing entries */
         RT_COPY_COMMON(newnode, node);
         Assert(n16->base.count == RT_FANOUT_16_LO);
         insertpos = RT_NODE_16_GET_INSERTPOS(n16, chunk);
         RT_COPY_ARRAYS_FOR_INSERT(new16->chunks, new16->children,
                                   n16->chunks, n16->children,
                                   RT_FANOUT_16_LO, insertpos);
  
         /* insert new chunk into place */
         new16->chunks[insertpos] = chunk;
  
         new16->base.count++;
         RT_VERIFY_NODE((RT_NODE *) new16);
  
         /* free old node and update references */
         RT_FREE_NODE(tree, node);
         *parent_slot = newnode.alloc;
  
         return &new16->children[insertpos];
     }
     else
     {
         RT_CHILD_PTR newnode;
         RT_NODE_48 *new48;
         int         idx,
                     bit;
  
         Assert(n16->base.fanout == RT_FANOUT_16_HI);
  
         /* initialize new node */
         newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_48, RT_CLASS_48);
         new48 = (RT_NODE_48 *) newnode.local;
  
         /* copy over the entries */
         RT_COPY_COMMON(newnode, node);
         for (int i = 0; i < RT_FANOUT_16_HI; i++)
             new48->slot_idxs[n16->chunks[i]] = i;
         memcpy(&new48->children[0], &n16->children[0], RT_FANOUT_16_HI * sizeof(new48->children[0]));
  
         /*
          * Since we just copied a dense array, we can fill "isset" using a
          * single store, provided the length of that array is at most the
          * number of bits in a bitmapword.
          */
         Assert(RT_FANOUT_16_HI <= BITS_PER_BITMAPWORD);
         new48->isset[0] = (bitmapword) (((uint64) 1 << RT_FANOUT_16_HI) - 1);
  
         /* put the new child at the end of the copied entries */
         insertpos = RT_FANOUT_16_HI;
         idx = RT_BM_IDX(insertpos);
         bit = RT_BM_BIT(insertpos);
  
         /* mark the slot used */
         new48->isset[idx] |= ((bitmapword) 1 << bit);
  
         /* insert new chunk into place */
         new48->slot_idxs[chunk] = insertpos;
  
         new48->base.count++;
         RT_VERIFY_NODE((RT_NODE *) new48);
  
         /* free old node and update reference in parent */
         *parent_slot = newnode.alloc;
         RT_FREE_NODE(tree, node);
  
         return &new48->children[insertpos];
     }
 }

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

 {
     RT_NODE_4  *n4 = (RT_NODE_4 *) (node.local);
     RT_CHILD_PTR newnode;
     RT_NODE_16 *new16;
     int         insertpos;
  
     /* initialize new node */
     newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_16, RT_CLASS_16_LO);
     new16 = (RT_NODE_16 *) newnode.local;
  
     /* copy over existing entries */
     RT_COPY_COMMON(newnode, node);
     Assert(n4->base.count == RT_FANOUT_4);
     insertpos = RT_NODE_4_GET_INSERTPOS(n4, chunk, RT_FANOUT_4);
     RT_COPY_ARRAYS_FOR_INSERT(new16->chunks, new16->children,
                               n4->chunks, n4->children,
                               RT_FANOUT_4, insertpos);
  
     /* insert new chunk into place */
     new16->chunks[insertpos] = chunk;
  
     new16->base.count++;
     RT_VERIFY_NODE((RT_NODE *) new16);
  
     /* free old node and update reference in parent */
     *parent_slot = newnode.alloc;
     RT_FREE_NODE(tree, node);
  
     return &new16->children[insertpos];
 }

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

 {
     RT_NODE_48 *n48 = (RT_NODE_48 *) node.local;
     RT_CHILD_PTR newnode;
     RT_NODE_256 *new256;
     int         i = 0;
  
     /* initialize new node */
     newnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_256, RT_CLASS_256);
     new256 = (RT_NODE_256 *) newnode.local;
  
     /* copy over the entries */
     RT_COPY_COMMON(newnode, node);
     for (int word_num = 0; word_num < RT_BM_IDX(RT_NODE_MAX_SLOTS); word_num++)
     {
         bitmapword  bitmap = 0;
  
         /*
          * Bit manipulation is a surprisingly large portion of the overhead in
          * the naive implementation. Doing stores word-at-a-time removes a lot
          * of that overhead.
          */
         for (int bit = 0; bit < BITS_PER_BITMAPWORD; bit++)
         {
             uint8       offset = n48->slot_idxs[i];
  
             if (offset != RT_INVALID_SLOT_IDX)
             {
                 bitmap |= ((bitmapword) 1 << bit);
                 new256->children[i] = n48->children[offset];
             }
  
             i++;
         }
  
         new256->isset[word_num] = bitmap;
     }
  
     /* free old node and update reference in parent */
     *parent_slot = newnode.alloc;
     RT_FREE_NODE(tree, node);
  
     return RT_ADD_CHILD_256(tree, newnode, chunk);
 }

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

 {
     RT_PTR_ALLOC *slot = NULL;
  
     while (iter->cur_level <= iter->top_level)
     {
         RT_CHILD_PTR node;
  
         slot = RT_NODE_ITERATE_NEXT(iter, iter->cur_level);
  
         if (iter->cur_level == 0 && slot != NULL)
         {
             /* Found a value at the leaf node */
             *key_p = iter->key;
             node.alloc = *slot;
  
             if (RT_CHILDPTR_IS_VALUE(*slot))
                 return (RT_VALUE_TYPE *) slot;
             else
             {
                 RT_PTR_SET_LOCAL(iter->tree, &node);
                 return (RT_VALUE_TYPE *) node.local;
             }
         }
  
         if (slot != NULL)
         {
             /* Found the child slot, move down the tree */
             node.alloc = *slot;
             RT_PTR_SET_LOCAL(iter->tree, &node);
  
             iter->cur_level--;
             iter->node_iters[iter->cur_level].node = node;
             iter->node_iters[iter->cur_level].idx = 0;
         }
         else
         {
             /* Not found the child slot, move up the tree */
             iter->cur_level++;
         }
     }
  
     /* We've visited all nodes, so the iteration finished */
     return NULL;
 }

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

 {
     if (key == 0)
         return 0;
     else
         return (pg_leftmost_one_pos64(key) / RT_SPAN) * RT_SPAN;
 }

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

 {
     size_t      total = 0;
  
 #ifdef RT_SHMEM
     Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
     total = dsa_get_total_size(tree->dsa);
 #else
     total = MemoryContextMemAllocated(tree->context, true);
 #endif
  
     return total;
 }

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

 {
     int         count = node->base.count;
 #if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
     int         index;
 #endif
  
 #ifndef USE_NO_SIMD
     Vector8     spread_chunk;
     Vector8     haystack1;
     Vector8     haystack2;
     Vector8     cmp1;
     Vector8     cmp2;
     Vector8     min1;
     Vector8     min2;
     uint32      bitfield;
     int         index_simd;
 #endif
  
     /*
      * First compare the last element. There are two reasons to branch here:
      *
      * 1) A realistic pattern is inserting ordered keys. In that case,
      * non-SIMD platforms must do a linear search to the last chunk to find
      * the insert position. This will get slower as the node fills up.
      *
      * 2) On SIMD platforms, we must branch anyway to make sure we don't bit
      * scan an empty bitfield. Doing the branch here eliminates some work that
      * we might otherwise throw away.
      */
     Assert(count > 0);
     if (node->chunks[count - 1] < chunk)
         return count;
  
 #if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
  
     for (index = 0; index < count; index++)
     {
         if (node->chunks[index] > chunk)
             break;
     }
 #endif
  
 #ifndef USE_NO_SIMD
  
     /*
      * This is a bit more complicated than RT_NODE_16_SEARCH_EQ(), because no
      * unsigned uint8 comparison instruction exists, at least for SSE2. So we
      * need to play some trickery using vector8_min() to effectively get >=.
      * There'll never be any equal elements in current uses, but that's what
      * we get here...
      */
     spread_chunk = vector8_broadcast(chunk);
     vector8_load(&haystack1, &node->chunks[0]);
     vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
     min1 = vector8_min(spread_chunk, haystack1);
     min2 = vector8_min(spread_chunk, haystack2);
     cmp1 = vector8_eq(spread_chunk, min1);
     cmp2 = vector8_eq(spread_chunk, min2);
     bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));
  
     Assert((bitfield & ((UINT64CONST(1) << count) - 1)) != 0);
     index_simd = pg_rightmost_one_pos32(bitfield);
  
     Assert(index_simd == index);
     return index_simd;
 #else
     return index;
 #endif
 }

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

 {
     int         count = node->base.count;
 #ifndef USE_NO_SIMD
     Vector8     spread_chunk;
     Vector8     haystack1;
     Vector8     haystack2;
     Vector8     cmp1;
     Vector8     cmp2;
     uint32      bitfield;
     RT_PTR_ALLOC *slot_simd = NULL;
 #endif
  
 #if defined(USE_NO_SIMD) || defined(USE_ASSERT_CHECKING)
     RT_PTR_ALLOC *slot = NULL;
  
     for (int i = 0; i < count; i++)
     {
         if (node->chunks[i] == chunk)
         {
             slot = &node->children[i];
             break;
         }
     }
 #endif
  
 #ifndef USE_NO_SIMD
     /* replicate the search key */
     spread_chunk = vector8_broadcast(chunk);
  
     /* compare to all 32 keys stored in the node */
     vector8_load(&haystack1, &node->chunks[0]);
     vector8_load(&haystack2, &node->chunks[sizeof(Vector8)]);
     cmp1 = vector8_eq(spread_chunk, haystack1);
     cmp2 = vector8_eq(spread_chunk, haystack2);
  
     /* convert comparison to a bitfield */
     bitfield = vector8_highbit_mask(cmp1) | (vector8_highbit_mask(cmp2) << sizeof(Vector8));
  
     /* mask off invalid entries */
     bitfield &= ((UINT64CONST(1) << count) - 1);
  
     /* convert bitfield to index by counting trailing zeros */
     if (bitfield)
         slot_simd = &node->children[pg_rightmost_one_pos32(bitfield)];
  
     Assert(slot_simd == slot);
     return slot_simd;
 #else
     return slot;
 #endif
 }

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

 {
     Assert(RT_NODE_256_IS_CHUNK_USED(node, chunk));
     return &node->children[chunk];
 }

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

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

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

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

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

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

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

 {
     int         idx;
  
     for (idx = 0; idx < count; idx++)
     {
         if (node->chunks[idx] >= chunk)
             break;
     }
  
     return idx;
 }

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

 {
     RT_NODE    *n = node.local;
  
     switch (n->kind)
     {
         case RT_NODE_KIND_4:
             {
                 if (unlikely(RT_NODE_MUST_GROW(n)))
                     return RT_GROW_NODE_4(tree, parent_slot, node, chunk);
  
                 return RT_ADD_CHILD_4(tree, node, chunk);
             }
         case RT_NODE_KIND_16:
             {
                 if (unlikely(RT_NODE_MUST_GROW(n)))
                     return RT_GROW_NODE_16(tree, parent_slot, node, chunk);
  
                 return RT_ADD_CHILD_16(tree, node, chunk);
             }
         case RT_NODE_KIND_48:
             {
                 if (unlikely(RT_NODE_MUST_GROW(n)))
                     return RT_GROW_NODE_48(tree, parent_slot, node, chunk);
  
                 return RT_ADD_CHILD_48(tree, node, chunk);
             }
         case RT_NODE_KIND_256:
             return RT_ADD_CHILD_256(tree, node, chunk);
         default:
             pg_unreachable();
     }
 }

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

 {
     uint8       key_chunk = 0;
     RT_NODE_ITER *node_iter;
     RT_CHILD_PTR node;
     RT_PTR_ALLOC *slot = NULL;
  
 #ifdef RT_SHMEM
     Assert(iter->tree->ctl->magic == RT_RADIX_TREE_MAGIC);
 #endif
  
     node_iter = &(iter->node_iters[level]);
     node = node_iter->node;
  
     Assert(node.local != NULL);
  
     switch ((node.local)->kind)
     {
         case RT_NODE_KIND_4:
             {
                 RT_NODE_4  *n4 = (RT_NODE_4 *) (node.local);
  
                 if (node_iter->idx >= n4->base.count)
                     return NULL;
  
                 slot = &n4->children[node_iter->idx];
                 key_chunk = n4->chunks[node_iter->idx];
                 node_iter->idx++;
                 break;
             }
         case RT_NODE_KIND_16:
             {
                 RT_NODE_16 *n16 = (RT_NODE_16 *) (node.local);
  
                 if (node_iter->idx >= n16->base.count)
                     return NULL;
  
                 slot = &n16->children[node_iter->idx];
                 key_chunk = n16->chunks[node_iter->idx];
                 node_iter->idx++;
                 break;
             }
         case RT_NODE_KIND_48:
             {
                 RT_NODE_48 *n48 = (RT_NODE_48 *) (node.local);
                 int         chunk;
  
                 for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
                 {
                     if (RT_NODE_48_IS_CHUNK_USED(n48, chunk))
                         break;
                 }
  
                 if (chunk >= RT_NODE_MAX_SLOTS)
                     return NULL;
  
                 slot = RT_NODE_48_GET_CHILD(n48, chunk);
  
                 key_chunk = chunk;
                 node_iter->idx = chunk + 1;
                 break;
             }
         case RT_NODE_KIND_256:
             {
                 RT_NODE_256 *n256 = (RT_NODE_256 *) (node.local);
                 int         chunk;
  
                 for (chunk = node_iter->idx; chunk < RT_NODE_MAX_SLOTS; chunk++)
                 {
                     if (RT_NODE_256_IS_CHUNK_USED(n256, chunk))
                         break;
                 }
  
                 if (chunk >= RT_NODE_MAX_SLOTS)
                     return NULL;
  
                 slot = RT_NODE_256_GET_CHILD(n256, chunk);
  
                 key_chunk = chunk;
                 node_iter->idx = chunk + 1;
                 break;
             }
     }
  
     /* Update the key */
     iter->key &= ~(((uint64) RT_CHUNK_MASK) << (level * RT_SPAN));
     iter->key |= (((uint64) key_chunk) << (level * RT_SPAN));
  
     return slot;
 }

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

 {
     /* Make sure we already converted to local pointer */
     Assert(node != NULL);
  
     switch (node->kind)
     {
         case RT_NODE_KIND_4:
             {
                 RT_NODE_4  *n4 = (RT_NODE_4 *) node;
  
                 for (int i = 0; i < n4->base.count; i++)
                 {
                     if (n4->chunks[i] == chunk)
                         return &n4->children[i];
                 }
                 return NULL;
             }
         case RT_NODE_KIND_16:
             return RT_NODE_16_SEARCH_EQ((RT_NODE_16 *) node, chunk);
         case RT_NODE_KIND_48:
             {
                 RT_NODE_48 *n48 = (RT_NODE_48 *) node;
                 int         slotpos = n48->slot_idxs[chunk];
  
                 if (slotpos == RT_INVALID_SLOT_IDX)
                     return NULL;
  
                 return RT_NODE_48_GET_CHILD(n48, chunk);
             }
         case RT_NODE_KIND_256:
             {
                 RT_NODE_256 *n256 = (RT_NODE_256 *) node;
  
                 if (!RT_NODE_256_IS_CHUNK_USED(n256, chunk))
                     return NULL;
  
                 return RT_NODE_256_GET_CHILD(n256, chunk);
             }
         default:
             pg_unreachable();
     }
 }

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

 {
 #ifdef RT_SHMEM
     node->local = dsa_get_address(tree->dsa, node->alloc);
 #endif
 }

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

 {
     bool        found;
     RT_PTR_ALLOC *slot;
     size_t      value_sz = RT_GET_VALUE_SIZE(value_p);
  
 #ifdef RT_SHMEM
     Assert(tree->ctl->magic == RT_RADIX_TREE_MAGIC);
 #endif
  
     Assert(RT_PTR_ALLOC_IS_VALID(tree->ctl->root));
  
     /* Extend the tree if necessary */
     if (unlikely(key > tree->ctl->max_val))
     {
         if (tree->ctl->num_keys == 0)
         {
             RT_CHILD_PTR node;
             RT_NODE_4  *n4;
             int         start_shift = RT_KEY_GET_SHIFT(key);
  
             /*
              * With an empty root node, we don't extend the tree upwards,
              * since that would result in orphan empty nodes. Instead we open
              * code inserting into the root node and extend downward from
              * there.
              */
             node.alloc = tree->ctl->root;
             RT_PTR_SET_LOCAL(tree, &node);
             n4 = (RT_NODE_4 *) node.local;
             n4->base.count = 1;
             n4->chunks[0] = RT_GET_KEY_CHUNK(key, start_shift);
  
             slot = RT_EXTEND_DOWN(tree, &n4->children[0], key, start_shift);
             found = false;
             tree->ctl->start_shift = start_shift;
             tree->ctl->max_val = RT_SHIFT_GET_MAX_VAL(start_shift);
             goto have_slot;
         }
         else
             RT_EXTEND_UP(tree, key);
     }
  
     slot = RT_GET_SLOT_RECURSIVE(tree, &tree->ctl->root,
                                  key, tree->ctl->start_shift, &found);
  
 have_slot:
     Assert(slot != NULL);
  
     if (RT_VALUE_IS_EMBEDDABLE(value_p))
     {
         /* free the existing leaf */
         if (found && !RT_CHILDPTR_IS_VALUE(*slot))
             RT_FREE_LEAF(tree, *slot);
  
         /* store value directly in child pointer slot */
         memcpy(slot, value_p, value_sz);
  
 #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
         /* tag child pointer */
 #ifdef RT_SHMEM
         *slot |= 1;
 #else
         *((uintptr_t *) slot) |= 1;
 #endif
 #endif
     }
     else
     {
         RT_CHILD_PTR leaf;
  
         if (found && !RT_CHILDPTR_IS_VALUE(*slot))
         {
             Assert(RT_PTR_ALLOC_IS_VALID(*slot));
             leaf.alloc = *slot;
             RT_PTR_SET_LOCAL(tree, &leaf);
  
             if (RT_GET_VALUE_SIZE((RT_VALUE_TYPE *) leaf.local) != value_sz)
             {
                 /*
                  * different sizes, so first free the existing leaf before
                  * allocating a new one
                  */
                 RT_FREE_LEAF(tree, *slot);
                 leaf = RT_ALLOC_LEAF(tree, value_sz);
                 *slot = leaf.alloc;
             }
         }
         else
         {
             /* allocate new leaf and store it in the child array */
             leaf = RT_ALLOC_LEAF(tree, value_sz);
             *slot = leaf.alloc;
         }
  
         memcpy(leaf.local, value_p, value_sz);
     }
  
     /* Update the statistics */
     if (!found)
         tree->ctl->num_keys++;
  
     return found;
 }

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

 {
     /*
      * This is basically a memmove, but written in a simple loop for speed on
      * small inputs.
      */
     for (int i = count - 1; i >= insertpos; i--)
     {
         /* workaround for https://gcc.gnu.org/bugzilla/show_bug.cgi?id=101481 */
 #ifdef __GNUC__
         __asm__("");
 #endif
         chunks[i + 1] = chunks[i];
         children[i + 1] = children[i];
     }
 }

References i.

◆ RT_SHIFT_GET_MAX_VAL()

static uint64 RT_SHIFT_GET_MAX_VAL ( int shift )

static

Definition at line 820 of file radixtree.h.

 {
     if (shift == RT_MAX_SHIFT)
         return UINT64_MAX;
     else
         return (UINT64CONST(1) << (shift + RT_SPAN)) - 1;
 }

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.

 {
 #ifdef RT_VARLEN_VALUE_SIZE
  
 #ifdef RT_RUNTIME_EMBEDDABLE_VALUE
     return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC);
 #else
     return false;
 #endif
  
 #else
     return RT_GET_VALUE_SIZE(value_p) <= sizeof(RT_PTR_ALLOC);
 #endif
 }

References RT_GET_VALUE_SIZE, and RT_PTR_ALLOC.

◆ RT_VERIFY_NODE()

static void RT_VERIFY_NODE ( RT_NODE * node )

static

Definition at line 2694 of file radixtree.h.

 {
 #ifdef USE_ASSERT_CHECKING
  
     switch (node->kind)
     {
         case RT_NODE_KIND_4:
             {
                 RT_NODE_4  *n4 = (RT_NODE_4 *) node;
  
                 /* RT_DUMP_NODE(node); */
  
                 for (int i = 1; i < n4->base.count; i++)
                     Assert(n4->chunks[i - 1] < n4->chunks[i]);
  
                 break;
             }
         case RT_NODE_KIND_16:
             {
                 RT_NODE_16 *n16 = (RT_NODE_16 *) node;
  
                 /* RT_DUMP_NODE(node); */
  
                 for (int i = 1; i < n16->base.count; i++)
                     Assert(n16->chunks[i - 1] < n16->chunks[i]);
  
                 break;
             }
         case RT_NODE_KIND_48:
             {
                 RT_NODE_48 *n48 = (RT_NODE_48 *) node;
                 int         cnt = 0;
  
                 /* RT_DUMP_NODE(node); */
  
                 for (int i = 0; i < RT_NODE_MAX_SLOTS; i++)
                 {
                     uint8       slot = n48->slot_idxs[i];
                     int         idx = RT_BM_IDX(slot);
                     int         bitnum = RT_BM_BIT(slot);
  
                     if (!RT_NODE_48_IS_CHUNK_USED(n48, i))
                         continue;
  
                     /* Check if the corresponding slot is used */
                     Assert(slot < node->fanout);
                     Assert((n48->isset[idx] & ((bitmapword) 1 << bitnum)) != 0);
  
                     cnt++;
                 }
  
                 Assert(n48->base.count == cnt);
  
                 break;
             }
         case RT_NODE_KIND_256:
             {
                 RT_NODE_256 *n256 = (RT_NODE_256 *) node;
                 int         cnt = 0;
  
                 /* RT_DUMP_NODE(node); */
  
                 for (int i = 0; i < RT_BM_IDX(RT_NODE_MAX_SLOTS); i++)
                     cnt += bmw_popcount(n256->isset[i]);
  
                 /*
                  * Check if the number of used chunk matches, accounting for
                  * overflow
                  */
                 if (cnt == RT_FANOUT_256)
                     Assert(n256->base.count == 0);
                 else
                     Assert(n256->base.count == cnt);
  
                 break;
             }
     }
 #endif
 }

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 1835 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_memory_context_name_and_ident(), 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

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

Definition at line 1853 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(), pg_get_backend_memory_contexts(), plpgsql_estate_setup(), plpgsql_HashTableInit(), populate_recordset_object_start(), process_syncing_tables_for_apply(), RegisterExtensibleNodeEntry(), RelationCacheInitialize(), ResetUnloggedRelationsInDbspaceDir(), ri_InitHashTables(), SerializePendingSyncs(), SimpleLruDoesPhysicalPageExist(), SimpleLruGetBankLock(), SimpleLruInit(), SimpleLruReadPage(), SimpleLruReadPage_ReadOnly(), SimpleLruTruncate(), SimpleLruWaitIO(), SimpleLruWriteAll(), SimpleLruWritePage(), SimpleLruZeroLSNs(), SimpleLruZeroPage(), SlruCorrectSegmentFilenameLength(), SlruDeleteSegment(), SlruFileName(), SlruInternalDeleteSegment(), SlruInternalWritePage(), SlruMayDeleteSegment(), SlruPhysicalReadPage(), SlruPhysicalWritePage(), SlruReportIOError(), SlruScanDirCbDeleteAll(), SlruScanDirCbDeleteCutoff(), SlruScanDirCbFindEarliest(), SlruScanDirCbReportPresence(), SlruScanDirectory(), SlruSelectLRUPage(), SlruSyncFileTag(), smgropen(), StatsShmemInit(), and test_slru_scan_cb().

◆ iter_context

tree iter_context

Initial value:

= AllocSetContextCreate(ctx,
                                               RT_STR(RT_PREFIX) "_radix_tree iter context",
                                               ALLOCSET_SMALL_SIZES)

Definition at line 1841 of file radixtree.h.

◆ leaf_context

tree leaf_context = tree->context

Definition at line 1868 of file radixtree.h.

◆ max_val

tree ctl max_val = RT_SHIFT_GET_MAX_VAL(0)

Definition at line 1888 of file radixtree.h.

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

◆ old_ctx

old_ctx

Initial value:

{

RT_RADIX_TREE *tree

RT_RADIX_TREE

Definition: radixtree.h:706

Definition at line 1826 of file radixtree.h.

Referenced by daitch_mokotoff(), SnapBuildSerialize(), spg_box_quad_inner_consistent(), test_create(), and test_pattern().

◆ root

tree ctl root = rootnode.alloc

Definition at line 1886 of file radixtree.h.

◆ rootnode

rootnode = RT_ALLOC_NODE(tree, RT_NODE_KIND_4, RT_CLASS_4)

Definition at line 1827 of file radixtree.h.

◆ RT_SIZE_CLASS_INFO

const RT_SIZE_CLASS_ELEM RT_SIZE_CLASS_INFO[]

static

Initial value:

= {
    [RT_CLASS_4] = {
        .name = RT_STR(RT_PREFIX) "_radix_tree node4",
        .fanout = RT_FANOUT_4,
        .allocsize = sizeof(RT_NODE_4) + RT_FANOUT_4 * sizeof(RT_PTR_ALLOC),
    },
    [RT_CLASS_16_LO] = {
        .name = RT_STR(RT_PREFIX) "_radix_tree node16_lo",
        .fanout = RT_FANOUT_16_LO,
        .allocsize = sizeof(RT_NODE_16) + RT_FANOUT_16_LO * sizeof(RT_PTR_ALLOC),
    },
    [RT_CLASS_16_HI] = {
        .name = RT_STR(RT_PREFIX) "_radix_tree node16_hi",
        .fanout = RT_FANOUT_16_HI,
        .allocsize = sizeof(RT_NODE_16) + RT_FANOUT_16_HI * sizeof(RT_PTR_ALLOC),
    },
    [RT_CLASS_48] = {
        .name = RT_STR(RT_PREFIX) "_radix_tree node48",
        .fanout = RT_FANOUT_48,
        .allocsize = sizeof(RT_NODE_48) + RT_FANOUT_48 * sizeof(RT_PTR_ALLOC),
    },
    [RT_CLASS_256] = {
        .name = RT_STR(RT_PREFIX) "_radix_tree node256",
        .fanout = RT_FANOUT_256,
        .allocsize = sizeof(RT_NODE_256),
    },
}

Definition at line 648 of file radixtree.h.

◆ start_shift

tree ctl start_shift = 0

Definition at line 1887 of file radixtree.h.

Referenced by RT_SET().

◆ tree

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

Data Structures

Macros

Typedefs

Enumerations

Functions

Variables

Macro Definition Documentation

◆ RT_ADD_CHILD_16

◆ RT_ADD_CHILD_256

◆ RT_ADD_CHILD_4

◆ RT_ADD_CHILD_48

◆ RT_ALLOC_LEAF

◆ RT_ALLOC_NODE

◆ RT_BEGIN_ITERATE

◆ RT_BM_BIT

◆ RT_BM_IDX

◆ RT_CHILD_PTR

◆ RT_CHILDPTR_IS_VALUE

◆ RT_CHUNK_MASK

◆ RT_CLASS_16_HI

◆ RT_CLASS_16_LO

◆ RT_CLASS_256

◆ RT_CLASS_4

◆ RT_CLASS_48

◆ RT_COPY_ARRAYS_AND_DELETE

◆ RT_COPY_ARRAYS_FOR_INSERT

◆ RT_COPY_COMMON

◆ RT_CREATE

◆ RT_DELETE_RECURSIVE

◆ RT_DUMP_NODE

◆ RT_END_ITERATE

◆ RT_EXTEND_DOWN

◆ RT_EXTEND_UP

◆ RT_FANOUT_16_HI

◆ RT_FANOUT_16_LO

◆ RT_FANOUT_16_MAX

◆ RT_FANOUT_256

◆ RT_FANOUT_4

◆ RT_FANOUT_48

◆ RT_FANOUT_48_MAX

◆ RT_FANOUT_4_MAX

◆ RT_FIND

◆ RT_FREE

◆ RT_FREE_LEAF

◆ RT_FREE_NODE

◆ RT_FREE_RECURSE

◆ RT_GET_KEY_CHUNK

◆ RT_GET_SLOT_RECURSIVE

◆ RT_GET_VALUE_SIZE

◆ RT_GROW_NODE_16

◆ RT_GROW_NODE_4

◆ RT_GROW_NODE_48

◆ RT_INVALID_PTR_ALLOC

◆ RT_INVALID_SLOT_IDX

◆ RT_ITER

◆ RT_ITERATE_NEXT

◆ RT_KEY_GET_SHIFT

◆ RT_MAKE_NAME

◆ RT_MAKE_NAME_

◆ RT_MAKE_PREFIX

◆ RT_MAX_LEVEL

◆ RT_MAX_SHIFT

◆ RT_MEMORY_USAGE

◆ RT_NODE

◆ RT_NODE_16

◆ RT_NODE_16_GET_INSERTPOS

◆ RT_NODE_16_SEARCH_EQ

◆ RT_NODE_256

◆ RT_NODE_256_GET_CHILD

◆ RT_NODE_256_IS_CHUNK_USED

◆ RT_NODE_4

◆ RT_NODE_48

◆ RT_NODE_48_GET_CHILD

◆ RT_NODE_48_IS_CHUNK_USED

◆ RT_NODE_4_GET_INSERTPOS

◆ RT_NODE_DELETE

◆ RT_NODE_INSERT

◆ RT_NODE_ITER

◆ RT_NODE_ITERATE_NEXT

◆ RT_NODE_KIND_16