1 /* ---------------------------------------------------------------------- 2 * avl_tree.h 3 * 4 * Declarations for AVL style balanced tree support. 5 * 6 * Copyright (c) 2003-2009, PostgreSQL Global Development Group 7 * Author: Jan Wieck, Afilias USA INC. 8 * 9 * 10 * ---------------------------------------------------------------------- 11 */ 12 13 #ifndef _AVL_TREE_H_INCLUDED_ 14 #define _AVL_TREE_H_INCLUDED_ 15 16 /* ---- 17 * Callback function type declarations 18 * ---- 19 */ 20 typedef int (AVLcompfunc) (void *, void *); 21 typedef void (AVLfreefunc) (void *); 22 23 24 /* ---- 25 * Data structures 26 * ---- 27 */ 28 typedef struct AVLnode_s 29 { 30 struct AVLnode_s *lnode, 31 *rnode; 32 int ldepth, 33 rdepth; 34 void *cdata; 35 int deleted; 36 } AVLnode; 37 38 typedef struct AVLtree_s 39 { 40 AVLnode *root; 41 AVLcompfunc *compfunc; 42 AVLfreefunc *freefunc; 43 } AVLtree; 44 45 /* ---- 46 * Macros 47 * ---- 48 */ 49 #define AVL_DATA(n) (n)->cdata 50 #define AVL_SETDATA(n,p) ((n)->cdata = (p)) 51 #define AVL_MAXDEPTH(n) (((n)->ldepth > (n)->rdepth) ? (n)->ldepth : (n)->rdepth) 52 #define AVL_BALANCE(n) ((n)->rdepth - (n)->ldepth) 53 54 #define AVL_INITIALIZER(cmp,free) {NULL, (cmp), (free)} 55 56 57 /* ---- 58 * Public functions 59 * ---- 60 */ 61 void avl_init(AVLtree * tree, AVLcompfunc * compfunc, 62 AVLfreefunc * freefunc); 63 void avl_reset(AVLtree * tree); 64 AVLnode *avl_insert(AVLtree * tree, void *cdata); 65 AVLnode *avl_lookup(AVLtree * tree, void *cdata); 66 int avl_delete(AVLtree * tree, void *cdata); 67 68 #endif /* _AVL_TREE_H_INCLUDED_ */ 69