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