1 /* 2 * 3 * Portions Copyright 1998 Sun Microsystems, Inc. All rights reserved. 4 * Use is subject to license terms. 5 * 6 */ 7 8 #pragma ident "%Z%%M% %I% %E% SMI" 9 10 /* avl.h - avl tree definitions */ 11 /* 12 * Copyright (c) 1993 Regents of the University of Michigan. 13 * All rights reserved. 14 * 15 * Redistribution and use in source and binary forms are permitted 16 * provided that this notice is preserved and that due credit is given 17 * to the University of Michigan at Ann Arbor. The name of the University 18 * may not be used to endorse or promote products derived from this 19 * software without specific prior written permission. This software 20 * is provided ``as is'' without express or implied warranty. 21 */ 22 23 24 #ifndef _AVL 25 #define _AVL 26 27 /* 28 * this structure represents a generic avl tree node. 29 */ 30 31 typedef struct avlnode { 32 caddr_t avl_data; 33 char avl_bf; 34 struct avlnode *avl_left; 35 struct avlnode *avl_right; 36 } Avlnode; 37 38 #define NULLAVL ((Avlnode *) NULL) 39 40 /* balance factor values */ 41 #define LH -1 42 #define EH 0 43 #define RH 1 44 45 /* avl routines */ 46 #define avl_getone(x) (x == 0 ? 0 : (x)->avl_data) 47 #define avl_onenode(x) (x == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0)) 48 extern int avl_insert(); 49 extern caddr_t avl_delete(); 50 extern caddr_t avl_find(); 51 extern caddr_t avl_getfirst(); 52 extern caddr_t avl_getnext(); 53 extern int avl_dup_error(); 54 extern int avl_apply(); 55 56 /* apply traversal types */ 57 #define AVL_PREORDER 1 58 #define AVL_INORDER 2 59 #define AVL_POSTORDER 3 60 /* what apply returns if it ran out of nodes */ 61 #define AVL_NOMORE -6 62 63 typedef int (*IFP)(); 64 65 #endif /* _AVL */ 66