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