codekingpro/portable-devtools

1/*-------------------------------------------------------------------------2 *3 * rbtree.h4 *	  interface for PostgreSQL generic Red-Black binary tree package5 *6 * Copyright (c) 2009-2023, PostgreSQL Global Development Group7 *8 * IDENTIFICATION9 *		src/include/lib/rbtree.h10 *11 *-------------------------------------------------------------------------12 */13#ifndef RBTREE_H14#define RBTREE_H15 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 needs19 * for a tree entry.  (The total size of that larger struct is passed to20 * rbt_create.)	RBTNode is declared here to support this usage, but21 * callers must treat it as an opaque struct.22 */23typedef struct RBTNode24{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 RBTOrderControl36{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 declared43 * here so that callers can stack-allocate this, but must otherwise be44 * treated as an opaque struct.45 */46typedef struct RBTreeIterator RBTreeIterator;47 48struct RBTreeIterator49{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_find_great(RBTree *rbt, const RBTNode *data, bool equal_match);71extern RBTNode *rbt_find_less(RBTree *rbt, const RBTNode *data, bool equal_match);72extern RBTNode *rbt_leftmost(RBTree *rbt);73 74extern RBTNode *rbt_insert(RBTree *rbt, const RBTNode *data, bool *isNew);75extern void rbt_delete(RBTree *rbt, RBTNode *node);76 77extern void rbt_begin_iterate(RBTree *rbt, RBTOrderControl ctrl,78							  RBTreeIterator *iter);79extern RBTNode *rbt_iterate(RBTreeIterator *iter);80 81#endif							/* RBTREE_H */82