src/include/lib/rbtree.h

   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 */