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-2024, 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  */
23 typedef 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 */
32 typedef struct RBTree RBTree;
33 
34 /* Available tree iteration orderings */
35 typedef 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  */
46 typedef struct RBTreeIterator RBTreeIterator;
47 
49 {
51  RBTNode *(*iterate) (RBTreeIterator *iter);
53  bool is_over;
54 };
55 
56 /* Support functions to be provided by caller */
57 typedef int (*rbt_comparator) (const RBTNode *a, const RBTNode *b, void *arg);
58 typedef void (*rbt_combiner) (RBTNode *existing, const RBTNode *newdata, void *arg);
59 typedef RBTNode *(*rbt_allocfunc) (void *arg);
60 typedef void (*rbt_freefunc) (RBTNode *x, void *arg);
61 
62 extern 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 
69 extern RBTNode *rbt_find(RBTree *rbt, const RBTNode *data);
70 extern RBTNode *rbt_find_great(RBTree *rbt, const RBTNode *data, bool equal_match);
71 extern RBTNode *rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match);
72 extern RBTNode *rbt_leftmost(RBTree *rbt);
73 
74 extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew);
75 extern void rbt_delete(RBTree *rbt, RBTNode *node);
76 
77 extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl,
78  RBTreeIterator *iter);
79 extern RBTNode *rbt_iterate(RBTreeIterator *iter);
80 
81 #endif /* RBTREE_H */
size_t Size
Definition: c.h:608
int b
Definition: isn.c:70
int x
Definition: isn.c:71
int a
Definition: isn.c:69
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_allocfunc)(void *arg)
Definition: rbtree.h:59
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
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_less(RBTree *rbt, const RBTNode *data, bool equal_match)
Definition: rbtree.c:203
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:235
int(* rbt_comparator)(const RBTNode *a, const RBTNode *b, void *arg)
Definition: rbtree.h:57
void rbt_delete(RBTree *rbt, RBTNode *node)
Definition: rbtree.c:695
struct RBTNode RBTNode
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
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