1 /*-------------------------------------------------------------------------
2  *
3  * rbtree.h
4  *	  interface for PostgreSQL generic Red-Black binary tree package
5  *
6  * Copyright (c) 2009-2021, 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 */
39 } RBTOrderControl;
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 
48 struct RBTreeIterator
49 {
50 	RBTree	   *rbt;
51 	RBTNode    *(*iterate) (RBTreeIterator *iter);
52 	RBTNode    *last_visited;
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 */
80