1 /* $Id: avl.h 2243 2009-01-10 02:24:02Z bird $ 2 * 3 * AVL-Tree (lookalike) declaration. 4 * 5 * This AVL implementation is configurable from this headerfile. By 6 * for example alterning the AVLKEY typedefinition an the AVL_<L|G|E|N>[E] 7 * macros you are able to create different trees. Currently you may only have 8 * one type of trees within one program (module). 9 * 10 * TREETYPE: Case Sensitive Strings (Key is pointer). 11 * 12 * 13 * Copyright (c) 1999-2009 knut st. osmundsen 14 * 15 * GPL 16 * 17 */ 18 #ifndef _AVL_H_ 19 #define _AVL_H_ 20 21 #ifdef __cplusplus 22 extern "C" { 23 #endif 24 25 /* 26 * AVL configuration. PRIVATE! 27 */ 28 #define AVL_MAX_HEIGHT 19 /* Up to 2^16 nodes. */ 29 #define AVL_MAY_TRY_INSERT_EQUAL 1 /* Ignore attempts to insert existing nodes. */ 30 31 /* 32 * AVL Compare macros 33 */ 34 #define AVL_L(key1, key2) (strcmp(key1, key2) < 0) 35 #define AVL_LE(key1, key2) (strcmp(key1, key2) <= 0) 36 #define AVL_G(key1, key2) (strcmp(key1, key2) > 0) 37 #define AVL_GE(key1, key2) (strcmp(key1, key2) >= 0) 38 #define AVL_E(key1, key2) (strcmp(key1, key2) == 0) 39 #define AVL_NE(key1, key2) (strcmp(key1, key2) != 0) 40 #define AVL_CMP(key1, key2) strcmp(key1, key2) 41 42 /** 43 * AVL key type 44 */ 45 typedef const char *AVLKEY; 46 47 48 /** 49 * AVL Core node. 50 */ 51 typedef struct _AVLNodeCore 52 { 53 AVLKEY Key; /* Key value. */ 54 struct _AVLNodeCore * pLeft; /* Pointer to left leaf node. */ 55 struct _AVLNodeCore * pRight; /* Pointer to right leaf node. */ 56 unsigned char uchHeight; /* Height of this tree: max(heigth(left), heigth(right)) + 1 */ 57 } AVLNODECORE, *PAVLNODECORE, **PPAVLNODECORE; 58 59 60 /** 61 * AVL Enum data - All members are PRIVATE! Don't touch! 62 */ 63 typedef struct _AVLEnumData 64 { 65 char fFromLeft; 66 char cEntries; 67 char achFlags[AVL_MAX_HEIGHT]; 68 PAVLNODECORE aEntries[AVL_MAX_HEIGHT]; 69 } AVLENUMDATA, *PAVLENUMDATA; 70 71 72 /* 73 * callback type 74 */ 75 typedef unsigned ( _PAVLCALLBACK)(PAVLNODECORE, void*); 76 typedef _PAVLCALLBACK *PAVLCALLBACK; 77 78 79 BOOL AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode); 80 PAVLNODECORE AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key); 81 PAVLNODECORE AVLGet(PPAVLNODECORE ppTree, AVLKEY Key); 82 PAVLNODECORE AVLGetWithParent(PPAVLNODECORE ppTree, PPAVLNODECORE ppParent, AVLKEY Key); 83 PAVLNODECORE AVLGetWithAdjecentNodes(PPAVLNODECORE ppTree, AVLKEY Key, PPAVLNODECORE ppLeft, PPAVLNODECORE ppRight); 84 unsigned AVLDoWithAll(PPAVLNODECORE ppTree, int fFromLeft, PAVLCALLBACK pfnCallBack, void *pvParam); 85 PAVLNODECORE AVLBeginEnumTree(PPAVLNODECORE ppTree, PAVLENUMDATA pEnumData, int fFromLeft); 86 PAVLNODECORE AVLGetNextNode(PAVLENUMDATA pEnumData); 87 PAVLNODECORE AVLGetBestFit(PPAVLNODECORE ppTree, AVLKEY Key, int fAbove); 88 89 90 91 /* 92 * Just in case NULL is undefined. 93 */ 94 #ifndef NULL 95 #define NULL ((void*)0) 96 #endif 97 98 #ifdef __cplusplus 99 } 100 #endif 101 102 #endif 103