1 /* -*- c -*- */ 2 3 /* 4 * avl.h 5 * 6 * chpp 7 * 8 * Copyright (C) 1994-1998 Mark Probst 9 * 10 * This program is free software; you can redistribute it and/or 11 * modify it under the terms of the GNU General Public License 12 * as published by the Free Software Foundation; either version 2 13 * of the License, or (at your option) any later version. 14 * 15 * This program is distributed in the hope that it will be useful, 16 * but WITHOUT ANY WARRANTY; without even the implied warranty of 17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 18 * GNU General Public License for more details. 19 * 20 * You should have received a copy of the GNU General Public License 21 * along with this program; if not, write to the Free Software 22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 23 */ 24 25 #ifndef __AVL_H__ 26 #define __AVL_H__ 27 28 typedef struct _avlNode 29 { 30 void *key; 31 int balance; 32 unsigned int rank; 33 struct _avlNode *up; 34 struct _avlNode *left; 35 struct _avlNode *right; 36 } avlNode; 37 38 typedef struct 39 { 40 avlNode *head; 41 unsigned int numElements; 42 int isSorted; 43 int (*compare) (void*, void*); 44 } avlTree; 45 46 #define AVL_LINK(a,N) (((a) == -1) ? (N)->left : (N)->right) 47 #define AVL_LINK_SET(s,P,V) \ 48 do { \ 49 typeof (V) foo = (((s) == -1) ? (P)->left : (P)->right); \ 50 foo = (V); \ 51 } while (0) 52 53 int avlCompare (avlTree*, void*, unsigned int, avlNode*); 54 int avlBalance (avlNode*, int, avlNode**); 55 avlTree* avlNew (void); 56 avlTree* avlNewSorted (int (*) (void*, void*)); 57 void avlInsert (avlTree*, void*, unsigned int); 58 void avlPut (avlTree*, void*); 59 avlNode* avlFirst (avlTree*, unsigned int); 60 avlNode* avlSearch (avlTree*, void*); 61 unsigned int avlGetPos (avlTree*, void*); 62 avlNode* avlNext (avlNode*); 63 avlNode* avlPrevious (avlNode*); 64 void avlDeleteNode (avlTree*, avlNode*, int); 65 void* avlDelete (avlTree*, unsigned int); 66 void* avlKey (avlNode*); 67 void* avlGet (avlTree*, unsigned int); 68 unsigned int avlNumElements (avlTree*); 69 int avlIsEmpty (avlTree*); 70 int avlBalanced (avlNode*, unsigned int*, unsigned int*); 71 72 #endif 73