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 */
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 */
29} RBTNode;
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 */
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 */
46typedef struct RBTreeIterator RBTreeIterator;
47
48struct 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 */
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_leftmost(RBTree *rbt);
71
72extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew);
73extern void rbt_delete(RBTree *rbt, RBTNode *node);
74
75extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl,
76 RBTreeIterator *iter);
77extern RBTNode *rbt_iterate(RBTreeIterator *iter);
78
79#endif /* RBTREE_H */
80