source/include/rbtree.h

0001 /*-------------------------------------------------------------------------
0002  *
0003  * rbtree.h
0004  *      interface for PostgreSQL generic Red-Black binary tree package
0005  *
0006  * Copyright (c) 2009-2023, PostgreSQL Global Development Group
0007  *
0008  * IDENTIFICATION
0009  *        src/include/lib/rbtree.h
0010  *
0011  *-------------------------------------------------------------------------
0012  */
0013 #ifndef RBTREE_H
0014 #define RBTREE_H
0015
0016 #include <ndrstandard.h>
0017
0018 /*
0019  * RBTNode is intended to be used as the first field of a larger struct,
0020  * whose additional fields carry whatever payload data the caller needs
0021  * for a tree entry.  (The total size of that larger struct is passed to
0022  * rbt_create.)    RBTNode is declared here to support this usage, but
0023  * callers must treat it as an opaque struct.
0024  */
0025 typedef struct ndrx_rbt_node
0026 {
0027     char color;                     /* node's current color, red or black */
0028     struct ndrx_rbt_node *left;     /* left child, or RBTNIL if none */
0029     struct ndrx_rbt_node *right;    /* right child, or RBTNIL if none */
0030     struct ndrx_rbt_node *parent;   /* parent, or NULL (not RBTNIL!) if none */
0031 } ndrx_rbt_node_t;
0032
0033 /* Support functions to be provided by caller */
0034 typedef int (*rbt_comparator) (const ndrx_rbt_node_t *a,
0035                                 const ndrx_rbt_node_t *b, void *arg);
0036 typedef void (*rbt_combiner) (ndrx_rbt_node_t *existing,
0037                                 const ndrx_rbt_node_t *newdata, void *arg);
0038 typedef void (*rbt_freefunc) (ndrx_rbt_node_t *x, void *arg);
0039
0040 /*
0041  * RBTree control structure
0042  */
0043 struct ndrx_rbt_tree
0044 {
0045     ndrx_rbt_node_t *root;            /* root node, or RBTNIL if tree is empty */
0046     /* Remaining fields are constant after rbt_create */
0047     /* The caller-supplied manipulation functions */
0048     rbt_comparator  comparator;
0049     rbt_combiner    combiner;
0050     rbt_freefunc    freefunc;
0051     /* Passthrough arg passed to all manipulation functions */
0052     void            *arg;
0053 };
0054
0055 /* struct representing a whole tree */
0056 typedef struct ndrx_rbt_tree ndrx_rbt_tree_t;
0057
0058 /* Available tree iteration orderings */
0059 typedef enum ndrx_rbt_order_control
0060 {
0061     LeftRightWalk,                /* inorder: left child, node, right child */
0062     RightLeftWalk                 /* reverse inorder: right, node, left */
0063 } ndrx_rbt_order_control_t;
0064
0065 /*
0066  * RBTreeIterator holds state while traversing a tree.  This is declared
0067  * here so that callers can stack-allocate this, but must otherwise be
0068  * treated as an opaque struct.
0069  */
0070 typedef struct ndrx_rbt_tree_iterator ndrx_rbt_tree_iterator_t;
0071
0072 struct ndrx_rbt_tree_iterator
0073 {
0074     ndrx_rbt_tree_t     *rbt;
0075     ndrx_rbt_node_t     *(*iterate) (ndrx_rbt_tree_iterator_t *iter);
0076     ndrx_rbt_node_t     *last_visited;
0077     int                 is_over;
0078 };
0079
0080 extern ndrx_rbt_tree_t *ndrx_rbt_create(rbt_comparator comparator,
0081                                             rbt_combiner combiner,
0082                                             rbt_freefunc freefunc,
0083                                             void *arg);
0084
0085 extern ndrx_rbt_tree_t *ndrx_rbt_init(ndrx_rbt_tree_t *tree,
0086                                     rbt_comparator comparator,
0087                                     rbt_combiner combiner,
0088                                     rbt_freefunc freefunc,
0089                                     void *arg);
0090
0091 extern ndrx_rbt_node_t *ndrx_rbt_find(ndrx_rbt_tree_t *rbt,
0092                                         const ndrx_rbt_node_t *data);
0093 extern ndrx_rbt_node_t *ndrx_rbt_find_great(ndrx_rbt_tree_t *rbt,
0094                                             const ndrx_rbt_node_t *data,
0095                                             int equal_match);
0096 extern ndrx_rbt_node_t *ndrx_rbt_find_less(ndrx_rbt_tree_t *rbt,
0097                                             const ndrx_rbt_node_t *data,
0098                                             int equal_match);
0099 extern ndrx_rbt_node_t *ndrx_rbt_leftmost(ndrx_rbt_tree_t *rbt);
0100 extern ndrx_rbt_node_t *ndrx_rbt_rightmost(ndrx_rbt_tree_t *rbt);
0101
0102 extern ndrx_rbt_node_t *ndrx_rbt_insert(ndrx_rbt_tree_t *rbt,
0103                                         ndrx_rbt_node_t *data, int *isNew);
0104 extern void ndrx_rbt_delete(ndrx_rbt_tree_t *rbt, ndrx_rbt_node_t *node);
0105
0106 extern void ndrx_rbt_begin_iterate(ndrx_rbt_tree_t *rbt,
0107                                     ndrx_rbt_order_control_t ctrl,
0108                                     ndrx_rbt_tree_iterator_t *iter);
0109
0110 extern ndrx_rbt_node_t *ndrx_rbt_iterate(ndrx_rbt_tree_iterator_t *iter);
0111
0112 extern int ndrx_rbt_is_empty(ndrx_rbt_tree_t *rbt);
0113
0114 #endif                            /* RBTREE_H */