avl.h@ 20355

Last change on this file since 20355 was 19756, checked in by vboxsync, 16 years ago
iprt/avl.h: added a AVLU32TREE type for the RTAvlU32* API.
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 35.6 KB

Line
1	/** @file
2	* IPRT - AVL Trees.
3	*/
4
5	/*
6	* Copyright (C) 1999-2003 knut st. osmundsen <[email protected]>
7	*
8	* This file is part of VirtualBox Open Source Edition (OSE), as
9	* available from http://www.virtualbox.org. This file is free software;
10	* you can redistribute it and/or modify it under the terms of the GNU
11	* General Public License (GPL) as published by the Free Software
12	* Foundation, in version 2 as it comes in the "COPYING" file of the
13	* VirtualBox OSE distribution. VirtualBox OSE is distributed in the
14	* hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
15	*
16	* The contents of this file may alternatively be used under the terms
17	* of the Common Development and Distribution License Version 1.0
18	* (CDDL) only, as it comes in the "COPYING.CDDL" file of the
19	* VirtualBox OSE distribution, in which case the provisions of the
20	* CDDL are applicable instead of those of the GPL.
21	*
22	* You may elect to license modified versions of this file under the
23	* terms and conditions of either the GPL or the CDDL or both.
24	*
25	* Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
26	* Clara, CA 95054 USA or visit http://www.sun.com if you need
27	* additional information or have any questions.
28	*/
29
30	#ifndef ___iprt_avl_h
31	#define ___iprt_avl_h
32
33	#include <iprt/cdefs.h>
34	#include <iprt/types.h>
35
36	__BEGIN_DECLS
37
38	/** @defgroup grp_rt_avl RTAvl - AVL Trees
39	* @ingroup grp_rt
40	* @{
41	*/
42
43
44	/** AVL tree of void pointers.
45	* @{
46	*/
47
48	/**
49	* AVL key type
50	*/
51	typedef void * AVLPVKEY;
52
53	/**
54	* AVL Core node.
55	*/
56	typedef struct _AVLPVNodeCore
57	{
58	AVLPVKEY Key; /** Key value. */
59	struct _AVLPVNodeCore pLeft; /* Pointer to left leaf node. */
60	struct _AVLPVNodeCore pRight; /* Pointer to right leaf node. */
61	unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
62	} AVLPVNODECORE, PAVLPVNODECORE, *PPAVLPVNODECORE;
63
64	/** A tree with void pointer keys. */
65	typedef PAVLPVNODECORE AVLPVTREE;
66	/** Pointer to a tree with void pointer keys. */
67	typedef PPAVLPVNODECORE PAVLPVTREE;
68
69	/** Callback function for AVLPVDoWithAll(). */
70	typedef DECLCALLBACK(int) AVLPVCALLBACK(PAVLPVNODECORE, void *);
71	/** Pointer to callback function for AVLPVDoWithAll(). */
72	typedef AVLPVCALLBACK *PAVLPVCALLBACK;
73
74	/*
75	* Functions.
76	*/
77	RTDECL(bool) RTAvlPVInsert(PAVLPVTREE ppTree, PAVLPVNODECORE pNode);
78	RTDECL(PAVLPVNODECORE) RTAvlPVRemove(PAVLPVTREE ppTree, AVLPVKEY Key);
79	RTDECL(PAVLPVNODECORE) RTAvlPVGet(PAVLPVTREE ppTree, AVLPVKEY Key);
80	RTDECL(PAVLPVNODECORE) RTAvlPVGetBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
81	RTDECL(PAVLPVNODECORE) RTAvlPVRemoveBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
82	RTDECL(int) RTAvlPVDoWithAll(PAVLPVTREE ppTree, int fFromLeft, PAVLPVCALLBACK pfnCallBack, void *pvParam);
83	RTDECL(int) RTAvlPVDestroy(PAVLPVTREE ppTree, PAVLPVCALLBACK pfnCallBack, void *pvParam);
84
85	/** @} */
86
87
88	/** AVL tree of unsigned long.
89	* @{
90	*/
91
92	/**
93	* AVL key type
94	*/
95	typedef unsigned long AVLULKEY;
96
97	/**
98	* AVL Core node.
99	*/
100	typedef struct _AVLULNodeCore
101	{
102	AVLULKEY Key; /** Key value. */
103	struct _AVLULNodeCore pLeft; /* Pointer to left leaf node. */
104	struct _AVLULNodeCore pRight; /* Pointer to right leaf node. */
105	unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
106	} AVLULNODECORE, PAVLULNODECORE, *PPAVLULNODECORE;
107
108
109	/** Callback function for AVLULDoWithAll(). */
110	typedef DECLCALLBACK(int) AVLULCALLBACK(PAVLULNODECORE, void*);
111	/** Pointer to callback function for AVLULDoWithAll(). */
112	typedef AVLULCALLBACK *PAVLULCALLBACK;
113
114
115	/*
116	* Functions.
117	*/
118	RTDECL(bool) RTAvlULInsert(PPAVLULNODECORE ppTree, PAVLULNODECORE pNode);
119	RTDECL(PAVLULNODECORE) RTAvlULRemove(PPAVLULNODECORE ppTree, AVLULKEY Key);
120	RTDECL(PAVLULNODECORE) RTAvlULGet(PPAVLULNODECORE ppTree, AVLULKEY Key);
121	RTDECL(PAVLULNODECORE) RTAvlULGetBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
122	RTDECL(PAVLULNODECORE) RTAvlULRemoveBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
123	RTDECL(int) RTAvlULDoWithAll(PPAVLULNODECORE ppTree, int fFromLeft, PAVLULCALLBACK pfnCallBack, void *pvParam);
124	RTDECL(int) RTAvlULDestroy(PPAVLULNODECORE pTree, PAVLULCALLBACK pfnCallBack, void *pvParam);
125
126	/** @} */
127
128
129
130	/** AVL tree of uint32_t
131	* @{
132	*/
133
134	/** AVL key type. */
135	typedef uint32_t AVLU32KEY;
136
137	/** AVL Core node. */
138	typedef struct _AVLU32NodeCore
139	{
140	AVLU32KEY Key; /*< Key value. /
141	struct _AVLU32NodeCore pLeft; /< Pointer to left leaf node. /
142	struct _AVLU32NodeCore pRight; /< Pointer to right leaf node. /
143	unsigned char uchHeight; /*< Height of this tree: max(height(left), height(right)) + 1 /
144	} AVLU32NODECORE, PAVLU32NODECORE, *PPAVLU32NODECORE;
145
146	/** A tree with void pointer keys. */
147	typedef PAVLU32NODECORE AVLU32TREE;
148	/** Pointer to a tree with void pointer keys. */
149	typedef PPAVLU32NODECORE PAVLU32TREE;
150
151	/** Callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
152	typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
153	/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
154	typedef AVLU32CALLBACK *PAVLU32CALLBACK;
155
156
157	/*
158	* Functions.
159	*/
160	RTDECL(bool) RTAvlU32Insert(PAVLU32TREE pTree, PAVLU32NODECORE pNode);
161	RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PAVLU32TREE pTree, AVLU32KEY Key);
162	RTDECL(PAVLU32NODECORE) RTAvlU32Get(PAVLU32TREE pTree, AVLU32KEY Key);
163	RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
164	RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
165	RTDECL(int) RTAvlU32DoWithAll(PAVLU32TREE pTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
166	RTDECL(int) RTAvlU32Destroy(PAVLU32TREE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
167
168	/** @} */
169
170	/**
171	* AVL uint32_t type for the relative offset pointer scheme.
172	*/
173	typedef int32_t AVLOU32;
174
175	typedef uint32_t AVLOU32KEY;
176
177	/**
178	* AVL Core node.
179	*/
180	typedef struct _AVLOU32NodeCore
181	{
182	/** Key value. */
183	AVLOU32KEY Key;
184	/** Offset to the left leaf node, relative to this field. */
185	AVLOU32 pLeft;
186	/** Offset to the right leaf node, relative to this field. */
187	AVLOU32 pRight;
188	/** Height of this tree: max(height(left), height(right)) + 1 */
189	unsigned char uchHeight;
190	} AVLOU32NODECORE, *PAVLOU32NODECORE;
191
192	/** A offset base tree with uint32_t keys. */
193	typedef AVLOU32 AVLOU32TREE;
194	/** Pointer to a offset base tree with uint32_t keys. */
195	typedef AVLOU32TREE *PAVLOU32TREE;
196
197	/** Pointer to an internal tree pointer.
198	* In this case it's a pointer to a relative offset. */
199	typedef AVLOU32TREE *PPAVLOU32NODECORE;
200
201	/** Callback function for RTAvloU32DoWithAll(). */
202	typedef DECLCALLBACK(int) AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
203	/** Pointer to callback function for RTAvloU32DoWithAll(). */
204	typedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
205
206	RTDECL(bool) RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
207	RTDECL(PAVLOU32NODECORE) RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
208	RTDECL(PAVLOU32NODECORE) RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
209	RTDECL(int) RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
210	RTDECL(PAVLOU32NODECORE) RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
211	RTDECL(PAVLOU32NODECORE) RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
212	RTDECL(int) RTAvloU32Destroy(PAVLOU32TREE pTree, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
213
214	/** @} */
215
216
217	/** AVL tree of uint32_t, list duplicates.
218	* @{
219	*/
220
221	/** AVL key type. */
222	typedef uint32_t AVLLU32KEY;
223
224	/** AVL Core node. */
225	typedef struct _AVLLU32NodeCore
226	{
227	AVLLU32KEY Key; /*< Key value. /
228	unsigned char uchHeight; /*< Height of this tree: max(height(left), height(right)) + 1 /
229	struct _AVLLU32NodeCore pLeft; /< Pointer to left leaf node. /
230	struct _AVLLU32NodeCore pRight; /< Pointer to right leaf node. /
231	struct _AVLLU32NodeCore pList; /< Pointer to next node with the same key. /
232	} AVLLU32NODECORE, PAVLLU32NODECORE, *PPAVLLU32NODECORE;
233
234	/** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
235	typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
236	/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
237	typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
238
239
240	/*
241	* Functions.
242	*/
243	RTDECL(bool) RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
244	RTDECL(PAVLLU32NODECORE) RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
245	RTDECL(PAVLLU32NODECORE) RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
246	RTDECL(PAVLLU32NODECORE) RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
247	RTDECL(PAVLLU32NODECORE) RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
248	RTDECL(int) RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
249	RTDECL(int) RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
250
251	/** @} */
252
253
254
255	/** AVL tree of RTGCPHYSes - using relative offsets internally.
256	* @{
257	*/
258
259	/**
260	* AVL 'pointer' type for the relative offset pointer scheme.
261	*/
262	typedef int32_t AVLOGCPHYS;
263
264	/**
265	* AVL Core node.
266	*/
267	typedef struct _AVLOGCPhysNodeCore
268	{
269	/** Key value. */
270	RTGCPHYS Key;
271	/** Offset to the left leaf node, relative to this field. */
272	AVLOGCPHYS pLeft;
273	/** Offset to the right leaf node, relative to this field. */
274	AVLOGCPHYS pRight;
275	/** Height of this tree: max(height(left), height(right)) + 1 */
276	unsigned char uchHeight;
277	/** Padding */
278	unsigned char Padding[7];
279	} AVLOGCPHYSNODECORE, *PAVLOGCPHYSNODECORE;
280
281	/** A offset base tree with uint32_t keys. */
282	typedef AVLOGCPHYS AVLOGCPHYSTREE;
283	/** Pointer to a offset base tree with uint32_t keys. */
284	typedef AVLOGCPHYSTREE *PAVLOGCPHYSTREE;
285
286	/** Pointer to an internal tree pointer.
287	* In this case it's a pointer to a relative offset. */
288	typedef AVLOGCPHYSTREE *PPAVLOGCPHYSNODECORE;
289
290	/** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
291	typedef DECLCALLBACK(int) AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
292	/** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
293	typedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
294
295	RTDECL(bool) RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
296	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
297	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
298	RTDECL(int) RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
299	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
300	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
301	RTDECL(int) RTAvloGCPhysDestroy(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
302
303	/** @} */
304
305
306	/** AVL tree of RTGCPHYS ranges - using relative offsets internally.
307	* @{
308	*/
309
310	/**
311	* AVL 'pointer' type for the relative offset pointer scheme.
312	*/
313	typedef int32_t AVLROGCPHYS;
314
315	/**
316	* AVL Core node.
317	*/
318	typedef struct _AVLROGCPhysNodeCore
319	{
320	/** First key value in the range (inclusive). */
321	RTGCPHYS Key;
322	/** Last key value in the range (inclusive). */
323	RTGCPHYS KeyLast;
324	/** Offset to the left leaf node, relative to this field. */
325	AVLROGCPHYS pLeft;
326	/** Offset to the right leaf node, relative to this field. */
327	AVLROGCPHYS pRight;
328	/** Height of this tree: max(height(left), height(right)) + 1 */
329	unsigned char uchHeight;
330	/** Padding */
331	unsigned char Padding[7];
332	} AVLROGCPHYSNODECORE, *PAVLROGCPHYSNODECORE;
333
334	/** A offset base tree with uint32_t keys. */
335	typedef AVLROGCPHYS AVLROGCPHYSTREE;
336	/** Pointer to a offset base tree with uint32_t keys. */
337	typedef AVLROGCPHYSTREE *PAVLROGCPHYSTREE;
338
339	/** Pointer to an internal tree pointer.
340	* In this case it's a pointer to a relative offset. */
341	typedef AVLROGCPHYSTREE *PPAVLROGCPHYSNODECORE;
342
343	/** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
344	typedef DECLCALLBACK(int) AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
345	/** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
346	typedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
347
348	RTDECL(bool) RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
349	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
350	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
351	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
352	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
353	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
354	RTDECL(int) RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
355	RTDECL(int) RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
356	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
357	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
358	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
359
360	/** @} */
361
362
363	/** AVL tree of RTGCPTRs.
364	* @{
365	*/
366
367	/**
368	* AVL Core node.
369	*/
370	typedef struct _AVLGCPtrNodeCore
371	{
372	/** Key value. */
373	RTGCPTR Key;
374	/** Pointer to the left node. */
375	struct _AVLGCPtrNodeCore *pLeft;
376	/** Pointer to the right node. */
377	struct _AVLGCPtrNodeCore *pRight;
378	/** Height of this tree: max(height(left), height(right)) + 1 */
379	unsigned char uchHeight;
380	} AVLGCPTRNODECORE, PAVLGCPTRNODECORE, *PPAVLGCPTRNODECORE;
381
382	/** A tree of RTGCPTR keys. */
383	typedef PAVLGCPTRNODECORE AVLGCPTRTREE;
384	/** Pointer to a tree of RTGCPTR keys. */
385	typedef PPAVLGCPTRNODECORE PAVLGCPTRTREE;
386
387	/** Callback function for RTAvlGCPtrDoWithAll(). */
388	typedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
389	/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
390	typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
391
392	RTDECL(bool) RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
393	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
394	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
395	RTDECL(int) RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
396	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
397	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
398	RTDECL(int) RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
399
400	/** @} */
401
402
403	/** AVL tree of RTGCPTRs - using relative offsets internally.
404	* @{
405	*/
406
407	/**
408	* AVL 'pointer' type for the relative offset pointer scheme.
409	*/
410	typedef int32_t AVLOGCPTR;
411
412	/**
413	* AVL Core node.
414	*/
415	typedef struct _AVLOGCPtrNodeCore
416	{
417	/** Key value. */
418	RTGCPTR Key;
419	/** Offset to the left leaf node, relative to this field. */
420	AVLOGCPTR pLeft;
421	/** Offset to the right leaf node, relative to this field. */
422	AVLOGCPTR pRight;
423	/** Height of this tree: max(height(left), height(right)) + 1 */
424	unsigned char uchHeight;
425	unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 3];
426	} AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
427
428	/** A offset base tree with uint32_t keys. */
429	typedef AVLOGCPTR AVLOGCPTRTREE;
430	/** Pointer to a offset base tree with uint32_t keys. */
431	typedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
432
433	/** Pointer to an internal tree pointer.
434	* In this case it's a pointer to a relative offset. */
435	typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
436
437	/** Callback function for RTAvloGCPtrDoWithAll(). */
438	typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
439	/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
440	typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
441
442	RTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
443	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
444	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
445	RTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
446	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
447	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
448	RTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
449
450	/** @} */
451
452
453	/** AVL tree of RTGCPTR ranges.
454	* @{
455	*/
456
457	/**
458	* AVL Core node.
459	*/
460	typedef struct _AVLRGCPtrNodeCore
461	{
462	/** First key value in the range (inclusive). */
463	RTGCPTR Key;
464	/** Last key value in the range (inclusive). */
465	RTGCPTR KeyLast;
466	/** Offset to the left leaf node, relative to this field. */
467	struct _AVLRGCPtrNodeCore *pLeft;
468	/** Offset to the right leaf node, relative to this field. */
469	struct _AVLRGCPtrNodeCore *pRight;
470	/** Height of this tree: max(height(left), height(right)) + 1 */
471	unsigned char uchHeight;
472	} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
473
474	/** A offset base tree with RTGCPTR keys. */
475	typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
476	/** Pointer to a offset base tree with RTGCPTR keys. */
477	typedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
478
479	/** Pointer to an internal tree pointer.
480	* In this case it's a pointer to a relative offset. */
481	typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
482
483	/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
484	typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
485	/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
486	typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
487
488	RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
489	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
490	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
491	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
492	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
493	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
494	RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
495	RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
496	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
497	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
498	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode);
499
500	/** @} */
501
502
503	/** AVL tree of RTGCPTR ranges - using relative offsets internally.
504	* @{
505	*/
506
507	/**
508	* AVL 'pointer' type for the relative offset pointer scheme.
509	*/
510	typedef int32_t AVLROGCPTR;
511
512	/**
513	* AVL Core node.
514	*/
515	typedef struct _AVLROGCPtrNodeCore
516	{
517	/** First key value in the range (inclusive). */
518	RTGCPTR Key;
519	/** Last key value in the range (inclusive). */
520	RTGCPTR KeyLast;
521	/** Offset to the left leaf node, relative to this field. */
522	AVLROGCPTR pLeft;
523	/** Offset to the right leaf node, relative to this field. */
524	AVLROGCPTR pRight;
525	/** Height of this tree: max(height(left), height(right)) + 1 */
526	unsigned char uchHeight;
527	unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 7];
528	} AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
529
530	/** A offset base tree with uint32_t keys. */
531	typedef AVLROGCPTR AVLROGCPTRTREE;
532	/** Pointer to a offset base tree with uint32_t keys. */
533	typedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
534
535	/** Pointer to an internal tree pointer.
536	* In this case it's a pointer to a relative offset. */
537	typedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
538
539	/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
540	typedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
541	/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
542	typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
543
544	RTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
545	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
546	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
547	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
548	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
549	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
550	RTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
551	RTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
552	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
553	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
554	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
555
556	/** @} */
557
558
559	/** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
560	* @{
561	*/
562
563	/**
564	* AVL 'pointer' type for the relative offset pointer scheme.
565	*/
566	typedef int32_t AVLROOGCPTR;
567
568	/**
569	* AVL Core node.
570	*/
571	typedef struct _AVLROOGCPtrNodeCore
572	{
573	/** First key value in the range (inclusive). */
574	RTGCPTR Key;
575	/** Last key value in the range (inclusive). */
576	RTGCPTR KeyLast;
577	/** Offset to the left leaf node, relative to this field. */
578	AVLROOGCPTR pLeft;
579	/** Offset to the right leaf node, relative to this field. */
580	AVLROOGCPTR pRight;
581	/** Pointer to the list of string with the same key. Don't touch. */
582	AVLROOGCPTR pList;
583	/** Height of this tree: max(height(left), height(right)) + 1 */
584	unsigned char uchHeight;
585	} AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
586
587	/** A offset base tree with uint32_t keys. */
588	typedef AVLROOGCPTR AVLROOGCPTRTREE;
589	/** Pointer to a offset base tree with uint32_t keys. */
590	typedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
591
592	/** Pointer to an internal tree pointer.
593	* In this case it's a pointer to a relative offset. */
594	typedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
595
596	/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
597	typedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
598	/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
599	typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
600
601	RTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
602	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
603	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
604	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
605	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
606	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
607	RTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
608	RTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
609	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
610	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
611	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
612	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
613
614	/** @} */
615
616
617	/** AVL tree of RTUINTPTR ranges.
618	* @{
619	*/
620
621	/**
622	* AVL Core node.
623	*/
624	typedef struct _AVLRUIntPtrNodeCore
625	{
626	/** First key value in the range (inclusive). */
627	RTUINTPTR Key;
628	/** Last key value in the range (inclusive). */
629	RTUINTPTR KeyLast;
630	/** Offset to the left leaf node, relative to this field. */
631	struct _AVLRUIntPtrNodeCore *pLeft;
632	/** Offset to the right leaf node, relative to this field. */
633	struct _AVLRUIntPtrNodeCore *pRight;
634	/** Height of this tree: max(height(left), height(right)) + 1 */
635	unsigned char uchHeight;
636	} AVLRUINTPTRNODECORE, *PAVLRUINTPTRNODECORE;
637
638	/** A offset base tree with RTUINTPTR keys. */
639	typedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
640	/** Pointer to a offset base tree with RTUINTPTR keys. */
641	typedef AVLRUINTPTRTREE *PAVLRUINTPTRTREE;
642
643	/** Pointer to an internal tree pointer.
644	* In this case it's a pointer to a relative offset. */
645	typedef AVLRUINTPTRTREE *PPAVLRUINTPTRNODECORE;
646
647	/** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
648	typedef DECLCALLBACK(int) AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
649	/** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
650	typedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
651
652	RTDECL(bool) RTAvlrUIntPtrInsert( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
653	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRemove( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
654	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
655	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
656	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
657	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
658	RTDECL(int) RTAvlrUIntPtrDoWithAll( PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
659	RTDECL(int) RTAvlrUIntPtrDestroy( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
660	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRoot( PAVLRUINTPTRTREE pTree);
661	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetLeft( PAVLRUINTPTRNODECORE pNode);
662	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRight( PAVLRUINTPTRNODECORE pNode);
663
664	/** @} */
665
666
667	/** AVL tree of RTHCPHYSes - using relative offsets internally.
668	* @{
669	*/
670
671	/**
672	* AVL 'pointer' type for the relative offset pointer scheme.
673	*/
674	typedef int32_t AVLOHCPHYS;
675
676	/**
677	* AVL Core node.
678	*/
679	typedef struct _AVLOHCPhysNodeCore
680	{
681	/** Key value. */
682	RTHCPHYS Key;
683	/** Offset to the left leaf node, relative to this field. */
684	AVLOHCPHYS pLeft;
685	/** Offset to the right leaf node, relative to this field. */
686	AVLOHCPHYS pRight;
687	/** Height of this tree: max(height(left), height(right)) + 1 */
688	unsigned char uchHeight;
689	#if HC_ARCH_BITS == 64 \|\| GC_ARCH_BITS == 64
690	unsigned char Padding[7]; /*< Alignment padding. /
691	#endif
692	} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
693
694	/** A offset base tree with uint32_t keys. */
695	typedef AVLOHCPHYS AVLOHCPHYSTREE;
696	/** Pointer to a offset base tree with uint32_t keys. */
697	typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
698
699	/** Pointer to an internal tree pointer.
700	* In this case it's a pointer to a relative offset. */
701	typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
702
703	/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
704	typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
705	/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
706	typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
707
708	RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
709	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
710	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
711	RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
712	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
713	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
714	RTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
715
716	/** @} */
717
718
719
720	/** AVL tree of RTIOPORTs - using relative offsets internally.
721	* @{
722	*/
723
724	/**
725	* AVL 'pointer' type for the relative offset pointer scheme.
726	*/
727	typedef int32_t AVLOIOPORTPTR;
728
729	/**
730	* AVL Core node.
731	*/
732	typedef struct _AVLOIOPortNodeCore
733	{
734	/** Offset to the left leaf node, relative to this field. */
735	AVLOIOPORTPTR pLeft;
736	/** Offset to the right leaf node, relative to this field. */
737	AVLOIOPORTPTR pRight;
738	/** Key value. */
739	RTIOPORT Key;
740	/** Height of this tree: max(height(left), height(right)) + 1 */
741	unsigned char uchHeight;
742	} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
743
744	/** A offset base tree with uint32_t keys. */
745	typedef AVLOIOPORTPTR AVLOIOPORTTREE;
746	/** Pointer to a offset base tree with uint32_t keys. */
747	typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
748
749	/** Pointer to an internal tree pointer.
750	* In this case it's a pointer to a relative offset. */
751	typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
752
753	/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
754	typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
755	/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
756	typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
757
758	RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
759	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
760	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
761	RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
762	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
763	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
764	RTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
765
766	/** @} */
767
768
769	/** AVL tree of RTIOPORT ranges - using relative offsets internally.
770	* @{
771	*/
772
773	/**
774	* AVL 'pointer' type for the relative offset pointer scheme.
775	*/
776	typedef int32_t AVLROIOPORTPTR;
777
778	/**
779	* AVL Core node.
780	*/
781	typedef struct _AVLROIOPortNodeCore
782	{
783	/** First key value in the range (inclusive). */
784	RTIOPORT Key;
785	/** Last key value in the range (inclusive). */
786	RTIOPORT KeyLast;
787	/** Offset to the left leaf node, relative to this field. */
788	AVLROIOPORTPTR pLeft;
789	/** Offset to the right leaf node, relative to this field. */
790	AVLROIOPORTPTR pRight;
791	/** Height of this tree: max(height(left), height(right)) + 1 */
792	unsigned char uchHeight;
793	} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
794
795	/** A offset base tree with uint32_t keys. */
796	typedef AVLROIOPORTPTR AVLROIOPORTTREE;
797	/** Pointer to a offset base tree with uint32_t keys. */
798	typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
799
800	/** Pointer to an internal tree pointer.
801	* In this case it's a pointer to a relative offset. */
802	typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
803
804	/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
805	typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
806	/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
807	typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
808
809	RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
810	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
811	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
812	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
813	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
814	RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
815	RTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
816
817	/** @} */
818
819
820	/** AVL tree of RTHCPHYSes.
821	* @{
822	*/
823
824	/**
825	* AVL 'pointer' type for the relative offset pointer scheme.
826	*/
827	typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
828
829	/**
830	* AVL Core node.
831	*/
832	typedef struct _AVLHCPhysNodeCore
833	{
834	/** Offset to the left leaf node, relative to this field. */
835	AVLHCPHYSPTR pLeft;
836	/** Offset to the right leaf node, relative to this field. */
837	AVLHCPHYSPTR pRight;
838	/** Key value. */
839	RTHCPHYS Key;
840	/** Height of this tree: max(height(left), height(right)) + 1 */
841	unsigned char uchHeight;
842	} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
843
844	/** A offset base tree with RTHCPHYS keys. */
845	typedef AVLHCPHYSPTR AVLHCPHYSTREE;
846	/** Pointer to a offset base tree with RTHCPHYS keys. */
847	typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
848
849	/** Pointer to an internal tree pointer.
850	* In this case it's a pointer to a relative offset. */
851	typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
852
853	/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
854	typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
855	/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
856	typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
857
858	RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
859	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
860	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
861	RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
862	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
863	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
864	RTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
865
866	/** @} */
867
868
869	/** @} */
870
871	__END_DECLS
872
873	#endif
874

Note: See TracBrowser for help on using the repository browser.

source: vbox/trunk/include/iprt/avl.h@ 20355

Download in other formats: