PostgreSQL Source Code git master
rbtree.h
Go to the documentation of this file.
1/*-------------------------------------------------------------------------
2 *
3 * rbtree.h
4 * interface for PostgreSQL generic Red-Black binary tree package
5 *
6 * Copyright (c) 2009-2025, PostgreSQL Global Development Group
7 *
8 * IDENTIFICATION
9 * src/include/lib/rbtree.h
10 *
11 *-------------------------------------------------------------------------
12 */
13#ifndef RBTREE_H
14#define RBTREE_H
15
16/*
17 * RBTNode is intended to be used as the first field of a larger struct,
18 * whose additional fields carry whatever payload data the caller needs
19 * for a tree entry. (The total size of that larger struct is passed to
20 * rbt_create.) RBTNode is declared here to support this usage, but
21 * callers must treat it as an opaque struct.
22 */
23typedef struct RBTNode
24{
25 char color; /* node's current color, red or black */
26 struct RBTNode *left; /* left child, or RBTNIL if none */
27 struct RBTNode *right; /* right child, or RBTNIL if none */
28 struct RBTNode *parent; /* parent, or NULL (not RBTNIL!) if none */
30
31/* Opaque struct representing a whole tree */
32typedef struct RBTree RBTree;
33
34/* Available tree iteration orderings */
35typedef enum RBTOrderControl
36{
37 LeftRightWalk, /* inorder: left child, node, right child */
38 RightLeftWalk /* reverse inorder: right, node, left */
40
41/*
42 * RBTreeIterator holds state while traversing a tree. This is declared
43 * here so that callers can stack-allocate this, but must otherwise be
44 * treated as an opaque struct.
45 */
47
49{
51 RBTNode *(*iterate) (RBTreeIterator *iter);
53 bool is_over;
54};
55
56/* Support functions to be provided by caller */
57typedef int (*rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg);
58typedef void (*rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg);
59typedef RBTNode *(*rbt_allocfunc) (void *arg);
60typedef void (*rbt_freefunc) (RBTNode *x, void *arg);
61
62extern RBTree *rbt_create(Size node_size,
63 rbt_comparator comparator,
64 rbt_combiner combiner,
65 rbt_allocfunc allocfunc,
66 rbt_freefunc freefunc,
67 void *arg);
68
69extern RBTNode *rbt_find(RBTree *rbt, const RBTNode *data);
70extern RBTNode *rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match);
71extern RBTNode *rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match);
72extern RBTNode *rbt_leftmost(RBTree *rbt);
73
74extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew);
75extern void rbt_delete(RBTree *rbt, RBTNode *node);
76
77extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl,
78 RBTreeIterator *iter);
80
81#endif /* RBTREE_H */
size_t Size
Definition: c.h:576
int b
Definition: isn.c:71
int x
Definition: isn.c:72
int a
Definition: isn.c:70
void * arg
const void * data
RBTNode * rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:172
RBTOrderControl
Definition: rbtree.h:36
@ RightLeftWalk
Definition: rbtree.h:38
@ LeftRightWalk
Definition: rbtree.h:37
RBTNode * rbt_iterate(RBTreeIterator *iter)
Definition: rbtree.c:826
RBTNode * rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
Definition: rbtree.c:453
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:802
void(* rbt_freefunc)(RBTNode *x, void *arg)
Definition: rbtree.h:60
void(* rbt_combiner)(RBTNode *existing, const RBTNode *newdata, void *arg)
Definition: rbtree.h:58
RBTNode * rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:203
RBTree * rbt_create(Size node_size, rbt_comparator comparator, rbt_combiner combiner, rbt_allocfunc allocfunc, rbt_freefunc freefunc, void *arg)
Definition: rbtree.c:102
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
RBTNode *(* rbt_allocfunc)(void *arg)
Definition: rbtree.h:59
int(* rbt_comparator)(const RBTNode *a, const RBTNode *b, void *arg)
Definition: rbtree.h:57
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:235
void rbt_delete(RBTree *rbt, RBTNode *node)
Definition: rbtree.c:695
struct RBTNode RBTNode
Definition: rbtree.h:24
struct RBTNode * parent
Definition: rbtree.h:28
char color
Definition: rbtree.h:25
struct RBTNode * left
Definition: rbtree.h:26
struct RBTNode * right
Definition: rbtree.h:27
bool is_over
Definition: rbtree.h:53
RBTree * rbt
Definition: rbtree.h:50
RBTNode * last_visited
Definition: rbtree.h:52
Definition: rbtree.c:42