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