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-2019, 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 */
29 } RBTNode;
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  */
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_leftmost(RBTree *rbt);
71 
72 extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew);
73 extern void rbt_delete(RBTree *rbt, RBTNode *node);
74 
75 extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl,
76  RBTreeIterator *iter);
77 extern RBTNode *rbt_iterate(RBTreeIterator *iter);
78 
79 #endif /* RBTREE_H */
int(* rbt_comparator)(const RBTNode *a, const RBTNode *b, void *arg)
Definition: rbtree.h:57
struct RBTNode * left
Definition: rbtree.h:26
RBTNode * last_visited
Definition: rbtree.h:52
RBTNode * rbt_iterate(RBTreeIterator *iter)
Definition: rbtree.c:764
void rbt_delete(RBTree *rbt, RBTNode *node)
Definition: rbtree.c:633
void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl, RBTreeIterator *iter)
Definition: rbtree.c:740
struct RBTNode RBTNode
RBTNode *(* rbt_allocfunc)(void *arg)
Definition: rbtree.h:59
bool is_over
Definition: rbtree.h:53
struct RBTNode * parent
Definition: rbtree.h:28
RBTOrderControl
Definition: rbtree.h:35
struct RBTNode * right
Definition: rbtree.h:27
char color
Definition: rbtree.h:25
RBTNode * rbt_leftmost(RBTree *rbt)
Definition: rbtree.c:173
size_t Size
Definition: c.h:467
RBTNode * rbt_find(RBTree *rbt, const RBTNode *data)
Definition: rbtree.c:145
Definition: rbtree.h:23
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_insert(RBTree *rbt, const RBTNode *data, bool *isNew)
Definition: rbtree.c:391
Definition: rbtree.c:41
void * arg
void(* rbt_freefunc)(RBTNode *x, void *arg)
Definition: rbtree.h:60
RBTree * rbt
Definition: rbtree.h:50
void(* rbt_combiner)(RBTNode *existing, const RBTNode *newdata, void *arg)
Definition: rbtree.h:58