10Sstevel@tonic-gate /* 20Sstevel@tonic-gate * 3*3857Sstevel * Portions Copyright 1998 Sun Microsystems, Inc. All rights reserved. 4*3857Sstevel * Use is subject to license terms. 50Sstevel@tonic-gate * 60Sstevel@tonic-gate */ 70Sstevel@tonic-gate 80Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI" 90Sstevel@tonic-gate 100Sstevel@tonic-gate /* avl.h - avl tree definitions */ 110Sstevel@tonic-gate /* 120Sstevel@tonic-gate * Copyright (c) 1993 Regents of the University of Michigan. 130Sstevel@tonic-gate * All rights reserved. 140Sstevel@tonic-gate * 150Sstevel@tonic-gate * Redistribution and use in source and binary forms are permitted 160Sstevel@tonic-gate * provided that this notice is preserved and that due credit is given 170Sstevel@tonic-gate * to the University of Michigan at Ann Arbor. The name of the University 180Sstevel@tonic-gate * may not be used to endorse or promote products derived from this 190Sstevel@tonic-gate * software without specific prior written permission. This software 200Sstevel@tonic-gate * is provided ``as is'' without express or implied warranty. 210Sstevel@tonic-gate */ 220Sstevel@tonic-gate 230Sstevel@tonic-gate 240Sstevel@tonic-gate #ifndef _AVL 250Sstevel@tonic-gate #define _AVL 260Sstevel@tonic-gate 270Sstevel@tonic-gate /* 280Sstevel@tonic-gate * this structure represents a generic avl tree node. 290Sstevel@tonic-gate */ 300Sstevel@tonic-gate 310Sstevel@tonic-gate typedef struct avlnode { 320Sstevel@tonic-gate caddr_t avl_data; 330Sstevel@tonic-gate char avl_bf; 340Sstevel@tonic-gate struct avlnode *avl_left; 350Sstevel@tonic-gate struct avlnode *avl_right; 360Sstevel@tonic-gate } Avlnode; 370Sstevel@tonic-gate 380Sstevel@tonic-gate #define NULLAVL ((Avlnode *) NULL) 390Sstevel@tonic-gate 400Sstevel@tonic-gate /* balance factor values */ 410Sstevel@tonic-gate #define LH -1 420Sstevel@tonic-gate #define EH 0 430Sstevel@tonic-gate #define RH 1 440Sstevel@tonic-gate 450Sstevel@tonic-gate /* avl routines */ 460Sstevel@tonic-gate #define avl_getone(x) (x == 0 ? 0 : (x)->avl_data) 470Sstevel@tonic-gate #define avl_onenode(x) (x == 0 || ((x)->avl_left == 0 && (x)->avl_right == 0)) 480Sstevel@tonic-gate extern int avl_insert(); 490Sstevel@tonic-gate extern caddr_t avl_delete(); 500Sstevel@tonic-gate extern caddr_t avl_find(); 510Sstevel@tonic-gate extern caddr_t avl_getfirst(); 520Sstevel@tonic-gate extern caddr_t avl_getnext(); 530Sstevel@tonic-gate extern int avl_dup_error(); 540Sstevel@tonic-gate extern int avl_apply(); 550Sstevel@tonic-gate 560Sstevel@tonic-gate /* apply traversal types */ 570Sstevel@tonic-gate #define AVL_PREORDER 1 580Sstevel@tonic-gate #define AVL_INORDER 2 590Sstevel@tonic-gate #define AVL_POSTORDER 3 600Sstevel@tonic-gate /* what apply returns if it ran out of nodes */ 610Sstevel@tonic-gate #define AVL_NOMORE -6 620Sstevel@tonic-gate 630Sstevel@tonic-gate typedef int (*IFP)(); 640Sstevel@tonic-gate 650Sstevel@tonic-gate #endif /* _AVL */ 66