avl.h@ 32284

Last change on this file since 32284 was 32284, checked in by vboxsync, 14 years ago
Pointer based GCPhys AVL tree
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 41.9 KB

Line
1	/** @file
2	* IPRT - AVL Trees.
3	*/
4
5	/*
6	* Copyright (C) 1999-2003 knut st. osmundsen <bird-src-spam@anduin.net>
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
26	#ifndef ___iprt_avl_h
27	#define ___iprt_avl_h
28
29	#include <iprt/cdefs.h>
30	#include <iprt/types.h>
31
32	RT_C_DECLS_BEGIN
33
34	/** @defgroup grp_rt_avl RTAvl - AVL Trees
35	* @ingroup grp_rt
36	* @{
37	*/
38
39
40	/** AVL tree of void pointers.
41	* @{
42	*/
43
44	/**
45	* AVL key type
46	*/
47	typedef void * AVLPVKEY;
48
49	/**
50	* AVL Core node.
51	*/
52	typedef struct _AVLPVNodeCore
53	{
54	AVLPVKEY Key; /** Key value. */
55	struct _AVLPVNodeCore pLeft; /* Pointer to left leaf node. */
56	struct _AVLPVNodeCore pRight; /* Pointer to right leaf node. */
57	unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
58	} AVLPVNODECORE, PAVLPVNODECORE, *PPAVLPVNODECORE;
59
60	/** A tree with void pointer keys. */
61	typedef PAVLPVNODECORE AVLPVTREE;
62	/** Pointer to a tree with void pointer keys. */
63	typedef PPAVLPVNODECORE PAVLPVTREE;
64
65	/** Callback function for AVLPVDoWithAll(). */
66	typedef DECLCALLBACK(int) AVLPVCALLBACK(PAVLPVNODECORE, void *);
67	/** Pointer to callback function for AVLPVDoWithAll(). */
68	typedef AVLPVCALLBACK *PAVLPVCALLBACK;
69
70	/*
71	* Functions.
72	*/
73	RTDECL(bool) RTAvlPVInsert(PAVLPVTREE ppTree, PAVLPVNODECORE pNode);
74	RTDECL(PAVLPVNODECORE) RTAvlPVRemove(PAVLPVTREE ppTree, AVLPVKEY Key);
75	RTDECL(PAVLPVNODECORE) RTAvlPVGet(PAVLPVTREE ppTree, AVLPVKEY Key);
76	RTDECL(PAVLPVNODECORE) RTAvlPVGetBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
77	RTDECL(PAVLPVNODECORE) RTAvlPVRemoveBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
78	RTDECL(int) RTAvlPVDoWithAll(PAVLPVTREE ppTree, int fFromLeft, PAVLPVCALLBACK pfnCallBack, void *pvParam);
79	RTDECL(int) RTAvlPVDestroy(PAVLPVTREE ppTree, PAVLPVCALLBACK pfnCallBack, void *pvParam);
80
81	/** @} */
82
83
84	/** AVL tree of unsigned long.
85	* @{
86	*/
87
88	/**
89	* AVL key type
90	*/
91	typedef unsigned long AVLULKEY;
92
93	/**
94	* AVL Core node.
95	*/
96	typedef struct _AVLULNodeCore
97	{
98	AVLULKEY Key; /** Key value. */
99	struct _AVLULNodeCore pLeft; /* Pointer to left leaf node. */
100	struct _AVLULNodeCore pRight; /* Pointer to right leaf node. */
101	unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
102	} AVLULNODECORE, PAVLULNODECORE, *PPAVLULNODECORE;
103
104
105	/** Callback function for AVLULDoWithAll(). */
106	typedef DECLCALLBACK(int) AVLULCALLBACK(PAVLULNODECORE, void*);
107	/** Pointer to callback function for AVLULDoWithAll(). */
108	typedef AVLULCALLBACK *PAVLULCALLBACK;
109
110
111	/*
112	* Functions.
113	*/
114	RTDECL(bool) RTAvlULInsert(PPAVLULNODECORE ppTree, PAVLULNODECORE pNode);
115	RTDECL(PAVLULNODECORE) RTAvlULRemove(PPAVLULNODECORE ppTree, AVLULKEY Key);
116	RTDECL(PAVLULNODECORE) RTAvlULGet(PPAVLULNODECORE ppTree, AVLULKEY Key);
117	RTDECL(PAVLULNODECORE) RTAvlULGetBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
118	RTDECL(PAVLULNODECORE) RTAvlULRemoveBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
119	RTDECL(int) RTAvlULDoWithAll(PPAVLULNODECORE ppTree, int fFromLeft, PAVLULCALLBACK pfnCallBack, void *pvParam);
120	RTDECL(int) RTAvlULDestroy(PPAVLULNODECORE pTree, PAVLULCALLBACK pfnCallBack, void *pvParam);
121
122	/** @} */
123
124
125
126	/** AVL tree of uint32_t
127	* @{
128	*/
129
130	/** AVL key type. */
131	typedef uint32_t AVLU32KEY;
132
133	/** AVL Core node. */
134	typedef struct _AVLU32NodeCore
135	{
136	AVLU32KEY Key; /*< Key value. /
137	struct _AVLU32NodeCore pLeft; /< Pointer to left leaf node. /
138	struct _AVLU32NodeCore pRight; /< Pointer to right leaf node. /
139	unsigned char uchHeight; /*< Height of this tree: max(height(left), height(right)) + 1 /
140	} AVLU32NODECORE, PAVLU32NODECORE, *PPAVLU32NODECORE;
141
142	/** A tree with void pointer keys. */
143	typedef PAVLU32NODECORE AVLU32TREE;
144	/** Pointer to a tree with void pointer keys. */
145	typedef PPAVLU32NODECORE PAVLU32TREE;
146
147	/** Callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
148	typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
149	/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
150	typedef AVLU32CALLBACK *PAVLU32CALLBACK;
151
152
153	/*
154	* Functions.
155	*/
156	RTDECL(bool) RTAvlU32Insert(PAVLU32TREE pTree, PAVLU32NODECORE pNode);
157	RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PAVLU32TREE pTree, AVLU32KEY Key);
158	RTDECL(PAVLU32NODECORE) RTAvlU32Get(PAVLU32TREE pTree, AVLU32KEY Key);
159	RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
160	RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
161	RTDECL(int) RTAvlU32DoWithAll(PAVLU32TREE pTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
162	RTDECL(int) RTAvlU32Destroy(PAVLU32TREE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
163
164	/** @} */
165
166	/**
167	* AVL uint32_t type for the relative offset pointer scheme.
168	*/
169	typedef int32_t AVLOU32;
170
171	typedef uint32_t AVLOU32KEY;
172
173	/**
174	* AVL Core node.
175	*/
176	typedef struct _AVLOU32NodeCore
177	{
178	/** Key value. */
179	AVLOU32KEY Key;
180	/** Offset to the left leaf node, relative to this field. */
181	AVLOU32 pLeft;
182	/** Offset to the right leaf node, relative to this field. */
183	AVLOU32 pRight;
184	/** Height of this tree: max(height(left), height(right)) + 1 */
185	unsigned char uchHeight;
186	} AVLOU32NODECORE, *PAVLOU32NODECORE;
187
188	/** A offset base tree with uint32_t keys. */
189	typedef AVLOU32 AVLOU32TREE;
190	/** Pointer to a offset base tree with uint32_t keys. */
191	typedef AVLOU32TREE *PAVLOU32TREE;
192
193	/** Pointer to an internal tree pointer.
194	* In this case it's a pointer to a relative offset. */
195	typedef AVLOU32TREE *PPAVLOU32NODECORE;
196
197	/** Callback function for RTAvloU32DoWithAll(). */
198	typedef DECLCALLBACK(int) AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
199	/** Pointer to callback function for RTAvloU32DoWithAll(). */
200	typedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
201
202	RTDECL(bool) RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
203	RTDECL(PAVLOU32NODECORE) RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
204	RTDECL(PAVLOU32NODECORE) RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
205	RTDECL(int) RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
206	RTDECL(PAVLOU32NODECORE) RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
207	RTDECL(PAVLOU32NODECORE) RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
208	RTDECL(int) RTAvloU32Destroy(PAVLOU32TREE pTree, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
209
210	/** @} */
211
212
213	/** AVL tree of uint32_t, list duplicates.
214	* @{
215	*/
216
217	/** AVL key type. */
218	typedef uint32_t AVLLU32KEY;
219
220	/** AVL Core node. */
221	typedef struct _AVLLU32NodeCore
222	{
223	AVLLU32KEY Key; /*< Key value. /
224	unsigned char uchHeight; /*< Height of this tree: max(height(left), height(right)) + 1 /
225	struct _AVLLU32NodeCore pLeft; /< Pointer to left leaf node. /
226	struct _AVLLU32NodeCore pRight; /< Pointer to right leaf node. /
227	struct _AVLLU32NodeCore pList; /< Pointer to next node with the same key. /
228	} AVLLU32NODECORE, PAVLLU32NODECORE, *PPAVLLU32NODECORE;
229
230	/** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
231	typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
232	/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
233	typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
234
235
236	/*
237	* Functions.
238	*/
239	RTDECL(bool) RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
240	RTDECL(PAVLLU32NODECORE) RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
241	RTDECL(PAVLLU32NODECORE) RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
242	RTDECL(PAVLLU32NODECORE) RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
243	RTDECL(PAVLLU32NODECORE) RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
244	RTDECL(int) RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
245	RTDECL(int) RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
246
247	/** @} */
248
249
250
251	/** AVL tree of RTGCPHYSes - using relative offsets internally.
252	* @{
253	*/
254
255	/**
256	* AVL 'pointer' type for the relative offset pointer scheme.
257	*/
258	typedef int32_t AVLOGCPHYS;
259
260	/**
261	* AVL Core node.
262	*/
263	typedef struct _AVLOGCPhysNodeCore
264	{
265	/** Key value. */
266	RTGCPHYS Key;
267	/** Offset to the left leaf node, relative to this field. */
268	AVLOGCPHYS pLeft;
269	/** Offset to the right leaf node, relative to this field. */
270	AVLOGCPHYS pRight;
271	/** Height of this tree: max(height(left), height(right)) + 1 */
272	unsigned char uchHeight;
273	/** Padding */
274	unsigned char Padding[7];
275	} AVLOGCPHYSNODECORE, *PAVLOGCPHYSNODECORE;
276
277	/** A offset base tree with uint32_t keys. */
278	typedef AVLOGCPHYS AVLOGCPHYSTREE;
279	/** Pointer to a offset base tree with uint32_t keys. */
280	typedef AVLOGCPHYSTREE *PAVLOGCPHYSTREE;
281
282	/** Pointer to an internal tree pointer.
283	* In this case it's a pointer to a relative offset. */
284	typedef AVLOGCPHYSTREE *PPAVLOGCPHYSNODECORE;
285
286	/** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
287	typedef DECLCALLBACK(int) AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
288	/** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
289	typedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
290
291	RTDECL(bool) RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
292	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
293	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
294	RTDECL(int) RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
295	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
296	RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
297	RTDECL(int) RTAvloGCPhysDestroy(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
298
299	/** @} */
300
301
302	/** AVL tree of RTGCPHYS ranges - using relative offsets internally.
303	* @{
304	*/
305
306	/**
307	* AVL 'pointer' type for the relative offset pointer scheme.
308	*/
309	typedef int32_t AVLROGCPHYS;
310
311	/**
312	* AVL Core node.
313	*/
314	typedef struct _AVLROGCPhysNodeCore
315	{
316	/** First key value in the range (inclusive). */
317	RTGCPHYS Key;
318	/** Last key value in the range (inclusive). */
319	RTGCPHYS KeyLast;
320	/** Offset to the left leaf node, relative to this field. */
321	AVLROGCPHYS pLeft;
322	/** Offset to the right leaf node, relative to this field. */
323	AVLROGCPHYS pRight;
324	/** Height of this tree: max(height(left), height(right)) + 1 */
325	unsigned char uchHeight;
326	/** Padding */
327	unsigned char Padding[7];
328	} AVLROGCPHYSNODECORE, *PAVLROGCPHYSNODECORE;
329
330	/** A offset base tree with uint32_t keys. */
331	typedef AVLROGCPHYS AVLROGCPHYSTREE;
332	/** Pointer to a offset base tree with uint32_t keys. */
333	typedef AVLROGCPHYSTREE *PAVLROGCPHYSTREE;
334
335	/** Pointer to an internal tree pointer.
336	* In this case it's a pointer to a relative offset. */
337	typedef AVLROGCPHYSTREE *PPAVLROGCPHYSNODECORE;
338
339	/** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
340	typedef DECLCALLBACK(int) AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
341	/** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
342	typedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
343
344	RTDECL(bool) RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
345	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
346	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
347	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
348	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
349	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
350	RTDECL(int) RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
351	RTDECL(int) RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
352	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
353	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
354	RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
355
356	/** @} */
357
358
359	/** AVL tree of RTGCPTRs.
360	* @{
361	*/
362
363	/**
364	* AVL Core node.
365	*/
366	typedef struct _AVLGCPtrNodeCore
367	{
368	/** Key value. */
369	RTGCPTR Key;
370	/** Pointer to the left node. */
371	struct _AVLGCPtrNodeCore *pLeft;
372	/** Pointer to the right node. */
373	struct _AVLGCPtrNodeCore *pRight;
374	/** Height of this tree: max(height(left), height(right)) + 1 */
375	unsigned char uchHeight;
376	} AVLGCPTRNODECORE, PAVLGCPTRNODECORE, *PPAVLGCPTRNODECORE;
377
378	/** A tree of RTGCPTR keys. */
379	typedef PAVLGCPTRNODECORE AVLGCPTRTREE;
380	/** Pointer to a tree of RTGCPTR keys. */
381	typedef PPAVLGCPTRNODECORE PAVLGCPTRTREE;
382
383	/** Callback function for RTAvlGCPtrDoWithAll(). */
384	typedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
385	/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
386	typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
387
388	RTDECL(bool) RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
389	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
390	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
391	RTDECL(int) RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
392	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
393	RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
394	RTDECL(int) RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
395
396	/** @} */
397
398
399	/** AVL tree of RTGCPTRs - using relative offsets internally.
400	* @{
401	*/
402
403	/**
404	* AVL 'pointer' type for the relative offset pointer scheme.
405	*/
406	typedef int32_t AVLOGCPTR;
407
408	/**
409	* AVL Core node.
410	*/
411	typedef struct _AVLOGCPtrNodeCore
412	{
413	/** Key value. */
414	RTGCPTR Key;
415	/** Offset to the left leaf node, relative to this field. */
416	AVLOGCPTR pLeft;
417	/** Offset to the right leaf node, relative to this field. */
418	AVLOGCPTR pRight;
419	/** Height of this tree: max(height(left), height(right)) + 1 */
420	unsigned char uchHeight;
421	unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 3];
422	} AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
423
424	/** A offset base tree with uint32_t keys. */
425	typedef AVLOGCPTR AVLOGCPTRTREE;
426	/** Pointer to a offset base tree with uint32_t keys. */
427	typedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
428
429	/** Pointer to an internal tree pointer.
430	* In this case it's a pointer to a relative offset. */
431	typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
432
433	/** Callback function for RTAvloGCPtrDoWithAll(). */
434	typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
435	/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
436	typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
437
438	RTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
439	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
440	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
441	RTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
442	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
443	RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
444	RTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
445
446	/** @} */
447
448
449	/** AVL tree of RTGCPTR ranges.
450	* @{
451	*/
452
453	/**
454	* AVL Core node.
455	*/
456	typedef struct _AVLRGCPtrNodeCore
457	{
458	/** First key value in the range (inclusive). */
459	RTGCPTR Key;
460	/** Last key value in the range (inclusive). */
461	RTGCPTR KeyLast;
462	/** Offset to the left leaf node, relative to this field. */
463	struct _AVLRGCPtrNodeCore *pLeft;
464	/** Offset to the right leaf node, relative to this field. */
465	struct _AVLRGCPtrNodeCore *pRight;
466	/** Height of this tree: max(height(left), height(right)) + 1 */
467	unsigned char uchHeight;
468	} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
469
470	/** A offset base tree with RTGCPTR keys. */
471	typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
472	/** Pointer to a offset base tree with RTGCPTR keys. */
473	typedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
474
475	/** Pointer to an internal tree pointer.
476	* In this case it's a pointer to a relative offset. */
477	typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
478
479	/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
480	typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
481	/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
482	typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
483
484	RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
485	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
486	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
487	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
488	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
489	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
490	RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
491	RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
492	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
493	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
494	RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode);
495
496	/** @} */
497
498
499	/** AVL tree of RTGCPTR ranges - using relative offsets internally.
500	* @{
501	*/
502
503	/**
504	* AVL 'pointer' type for the relative offset pointer scheme.
505	*/
506	typedef int32_t AVLROGCPTR;
507
508	/**
509	* AVL Core node.
510	*/
511	typedef struct _AVLROGCPtrNodeCore
512	{
513	/** First key value in the range (inclusive). */
514	RTGCPTR Key;
515	/** Last key value in the range (inclusive). */
516	RTGCPTR KeyLast;
517	/** Offset to the left leaf node, relative to this field. */
518	AVLROGCPTR pLeft;
519	/** Offset to the right leaf node, relative to this field. */
520	AVLROGCPTR pRight;
521	/** Height of this tree: max(height(left), height(right)) + 1 */
522	unsigned char uchHeight;
523	unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 7];
524	} AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
525
526	/** A offset base tree with uint32_t keys. */
527	typedef AVLROGCPTR AVLROGCPTRTREE;
528	/** Pointer to a offset base tree with uint32_t keys. */
529	typedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
530
531	/** Pointer to an internal tree pointer.
532	* In this case it's a pointer to a relative offset. */
533	typedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
534
535	/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
536	typedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
537	/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
538	typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
539
540	RTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
541	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
542	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
543	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
544	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
545	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
546	RTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
547	RTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
548	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
549	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
550	RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
551
552	/** @} */
553
554
555	/** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
556	* @{
557	*/
558
559	/**
560	* AVL 'pointer' type for the relative offset pointer scheme.
561	*/
562	typedef int32_t AVLROOGCPTR;
563
564	/**
565	* AVL Core node.
566	*/
567	typedef struct _AVLROOGCPtrNodeCore
568	{
569	/** First key value in the range (inclusive). */
570	RTGCPTR Key;
571	/** Last key value in the range (inclusive). */
572	RTGCPTR KeyLast;
573	/** Offset to the left leaf node, relative to this field. */
574	AVLROOGCPTR pLeft;
575	/** Offset to the right leaf node, relative to this field. */
576	AVLROOGCPTR pRight;
577	/** Pointer to the list of string with the same key. Don't touch. */
578	AVLROOGCPTR pList;
579	/** Height of this tree: max(height(left), height(right)) + 1 */
580	unsigned char uchHeight;
581	} AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
582
583	/** A offset base tree with uint32_t keys. */
584	typedef AVLROOGCPTR AVLROOGCPTRTREE;
585	/** Pointer to a offset base tree with uint32_t keys. */
586	typedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
587
588	/** Pointer to an internal tree pointer.
589	* In this case it's a pointer to a relative offset. */
590	typedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
591
592	/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
593	typedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
594	/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
595	typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
596
597	RTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
598	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
599	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
600	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
601	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
602	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
603	RTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
604	RTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
605	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
606	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
607	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
608	RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
609
610	/** @} */
611
612
613	/** AVL tree of RTUINTPTR.
614	* @{
615	*/
616
617	/**
618	* AVL RTUINTPTR node core.
619	*/
620	typedef struct _AVLUIntPtrNodeCore
621	{
622	/** Key value. */
623	RTUINTPTR Key;
624	/** Offset to the left leaf node, relative to this field. */
625	struct _AVLUIntPtrNodeCore *pLeft;
626	/** Offset to the right leaf node, relative to this field. */
627	struct _AVLUIntPtrNodeCore *pRight;
628	/** Height of this tree: max(height(left), height(right)) + 1 */
629	unsigned char uchHeight;
630	} AVLUINTPTRNODECORE;
631	/** Pointer to a RTUINTPTR AVL node core.*/
632	typedef AVLUINTPTRNODECORE *PAVLUINTPTRNODECORE;
633
634	/** A pointer based tree with RTUINTPTR keys. */
635	typedef PAVLUINTPTRNODECORE AVLUINTPTRTREE;
636	/** Pointer to a offset base tree with RTUINTPTR keys. */
637	typedef AVLUINTPTRTREE *PAVLUINTPTRTREE;
638
639	/** Pointer to an internal tree pointer.
640	* In this case it's a pointer to a pointer. */
641	typedef AVLUINTPTRTREE *PPAVLUINTPTRNODECORE;
642
643	/** Callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
644	typedef DECLCALLBACK(int) AVLUINTPTRCALLBACK(PAVLUINTPTRNODECORE pNode, void *pvUser);
645	/** Pointer to callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
646	typedef AVLUINTPTRCALLBACK *PAVLUINTPTRCALLBACK;
647
648	RTDECL(bool) RTAvlUIntPtrInsert( PAVLUINTPTRTREE pTree, PAVLUINTPTRNODECORE pNode);
649	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrRemove( PAVLUINTPTRTREE pTree, RTUINTPTR Key);
650	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGet( PAVLUINTPTRTREE pTree, RTUINTPTR Key);
651	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetBestFit(PAVLUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
652	RTDECL(int) RTAvlUIntPtrDoWithAll( PAVLUINTPTRTREE pTree, int fFromLeft, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
653	RTDECL(int) RTAvlUIntPtrDestroy( PAVLUINTPTRTREE pTree, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
654	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetRoot( PAVLUINTPTRTREE pTree);
655	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetLeft( PAVLUINTPTRNODECORE pNode);
656	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetRight( PAVLUINTPTRNODECORE pNode);
657
658	/** @} */
659
660
661	/** AVL tree of RTUINTPTR ranges.
662	* @{
663	*/
664
665	/**
666	* AVL RTUINTPTR range node core.
667	*/
668	typedef struct _AVLRUIntPtrNodeCore
669	{
670	/** First key value in the range (inclusive). */
671	RTUINTPTR Key;
672	/** Last key value in the range (inclusive). */
673	RTUINTPTR KeyLast;
674	/** Offset to the left leaf node, relative to this field. */
675	struct _AVLRUIntPtrNodeCore *pLeft;
676	/** Offset to the right leaf node, relative to this field. */
677	struct _AVLRUIntPtrNodeCore *pRight;
678	/** Height of this tree: max(height(left), height(right)) + 1 */
679	unsigned char uchHeight;
680	} AVLRUINTPTRNODECORE;
681	/** Pointer to an AVL RTUINTPTR range node code. */
682	typedef AVLRUINTPTRNODECORE *PAVLRUINTPTRNODECORE;
683
684	/** A pointer based tree with RTUINTPTR ranges. */
685	typedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
686	/** Pointer to a pointer based tree with RTUINTPTR ranges. */
687	typedef AVLRUINTPTRTREE *PAVLRUINTPTRTREE;
688
689	/** Pointer to an internal tree pointer.
690	* In this case it's a pointer to a pointer. */
691	typedef AVLRUINTPTRTREE *PPAVLRUINTPTRNODECORE;
692
693	/** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
694	typedef DECLCALLBACK(int) AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
695	/** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
696	typedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
697
698	RTDECL(bool) RTAvlrUIntPtrInsert( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
699	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRemove( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
700	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
701	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
702	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
703	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
704	RTDECL(int) RTAvlrUIntPtrDoWithAll( PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
705	RTDECL(int) RTAvlrUIntPtrDestroy( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
706	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRoot( PAVLRUINTPTRTREE pTree);
707	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetLeft( PAVLRUINTPTRNODECORE pNode);
708	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRight( PAVLRUINTPTRNODECORE pNode);
709
710	/** @} */
711
712
713	/** AVL tree of RTHCPHYSes - using relative offsets internally.
714	* @{
715	*/
716
717	/**
718	* AVL 'pointer' type for the relative offset pointer scheme.
719	*/
720	typedef int32_t AVLOHCPHYS;
721
722	/**
723	* AVL Core node.
724	*/
725	typedef struct _AVLOHCPhysNodeCore
726	{
727	/** Key value. */
728	RTHCPHYS Key;
729	/** Offset to the left leaf node, relative to this field. */
730	AVLOHCPHYS pLeft;
731	/** Offset to the right leaf node, relative to this field. */
732	AVLOHCPHYS pRight;
733	/** Height of this tree: max(height(left), height(right)) + 1 */
734	unsigned char uchHeight;
735	#if HC_ARCH_BITS == 64 \|\| GC_ARCH_BITS == 64
736	unsigned char Padding[7]; /*< Alignment padding. /
737	#endif
738	} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
739
740	/** A offset base tree with uint32_t keys. */
741	typedef AVLOHCPHYS AVLOHCPHYSTREE;
742	/** Pointer to a offset base tree with uint32_t keys. */
743	typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
744
745	/** Pointer to an internal tree pointer.
746	* In this case it's a pointer to a relative offset. */
747	typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
748
749	/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
750	typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
751	/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
752	typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
753
754	RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
755	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
756	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
757	RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
758	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
759	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
760	RTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
761
762	/** @} */
763
764
765
766	/** AVL tree of RTIOPORTs - using relative offsets internally.
767	* @{
768	*/
769
770	/**
771	* AVL 'pointer' type for the relative offset pointer scheme.
772	*/
773	typedef int32_t AVLOIOPORTPTR;
774
775	/**
776	* AVL Core node.
777	*/
778	typedef struct _AVLOIOPortNodeCore
779	{
780	/** Offset to the left leaf node, relative to this field. */
781	AVLOIOPORTPTR pLeft;
782	/** Offset to the right leaf node, relative to this field. */
783	AVLOIOPORTPTR pRight;
784	/** Key value. */
785	RTIOPORT Key;
786	/** Height of this tree: max(height(left), height(right)) + 1 */
787	unsigned char uchHeight;
788	} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
789
790	/** A offset base tree with uint32_t keys. */
791	typedef AVLOIOPORTPTR AVLOIOPORTTREE;
792	/** Pointer to a offset base tree with uint32_t keys. */
793	typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
794
795	/** Pointer to an internal tree pointer.
796	* In this case it's a pointer to a relative offset. */
797	typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
798
799	/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
800	typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
801	/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
802	typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
803
804	RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
805	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
806	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
807	RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
808	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
809	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
810	RTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
811
812	/** @} */
813
814
815	/** AVL tree of RTIOPORT ranges - using relative offsets internally.
816	* @{
817	*/
818
819	/**
820	* AVL 'pointer' type for the relative offset pointer scheme.
821	*/
822	typedef int32_t AVLROIOPORTPTR;
823
824	/**
825	* AVL Core node.
826	*/
827	typedef struct _AVLROIOPortNodeCore
828	{
829	/** First key value in the range (inclusive). */
830	RTIOPORT Key;
831	/** Last key value in the range (inclusive). */
832	RTIOPORT KeyLast;
833	/** Offset to the left leaf node, relative to this field. */
834	AVLROIOPORTPTR pLeft;
835	/** Offset to the right leaf node, relative to this field. */
836	AVLROIOPORTPTR pRight;
837	/** Height of this tree: max(height(left), height(right)) + 1 */
838	unsigned char uchHeight;
839	} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
840
841	/** A offset base tree with uint32_t keys. */
842	typedef AVLROIOPORTPTR AVLROIOPORTTREE;
843	/** Pointer to a offset base tree with uint32_t keys. */
844	typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
845
846	/** Pointer to an internal tree pointer.
847	* In this case it's a pointer to a relative offset. */
848	typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
849
850	/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
851	typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
852	/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
853	typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
854
855	RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
856	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
857	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
858	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
859	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
860	RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
861	RTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
862
863	/** @} */
864
865
866	/** AVL tree of RTHCPHYSes.
867	* @{
868	*/
869
870	/**
871	* AVL 'pointer' type for the relative offset pointer scheme.
872	*/
873	typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
874
875	/**
876	* AVL Core node.
877	*/
878	typedef struct _AVLHCPhysNodeCore
879	{
880	/** Offset to the left leaf node, relative to this field. */
881	AVLHCPHYSPTR pLeft;
882	/** Offset to the right leaf node, relative to this field. */
883	AVLHCPHYSPTR pRight;
884	/** Key value. */
885	RTHCPHYS Key;
886	/** Height of this tree: max(height(left), height(right)) + 1 */
887	unsigned char uchHeight;
888	} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
889
890	/** A offset base tree with RTHCPHYS keys. */
891	typedef AVLHCPHYSPTR AVLHCPHYSTREE;
892	/** Pointer to a offset base tree with RTHCPHYS keys. */
893	typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
894
895	/** Pointer to an internal tree pointer.
896	* In this case it's a pointer to a relative offset. */
897	typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
898
899	/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
900	typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
901	/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
902	typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
903
904	RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
905	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
906	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
907	RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
908	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
909	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
910	RTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
911
912	/** @} */
913
914	/** AVL tree of RTGCPHYSes.
915	* @{
916	*/
917
918	/**
919	* AVL 'pointer' type for the relative offset pointer scheme.
920	*/
921	typedef struct _AVLGCPhysNodeCore *AVLGCPHYSPTR;
922
923	/**
924	* AVL Core node.
925	*/
926	typedef struct _AVLGCPhysNodeCore
927	{
928	/** Offset to the left leaf node, relative to this field. */
929	AVLGCPHYSPTR pLeft;
930	/** Offset to the right leaf node, relative to this field. */
931	AVLGCPHYSPTR pRight;
932	/** Key value. */
933	RTGCPHYS Key;
934	/** Height of this tree: max(height(left), height(right)) + 1 */
935	unsigned char uchHeight;
936	} AVLGCPHYSNODECORE, *PAVLGCPHYSNODECORE;
937
938	/** A offset base tree with RTGCPHYS keys. */
939	typedef AVLGCPHYSPTR AVLGCPHYSTREE;
940	/** Pointer to a offset base tree with RTGCPHYS keys. */
941	typedef AVLGCPHYSTREE *PAVLGCPHYSTREE;
942
943	/** Pointer to an internal tree pointer.
944	* In this case it's a pointer to a relative offset. */
945	typedef AVLGCPHYSTREE *PPAVLGCPHYSNODECORE;
946
947	/** Callback function for RTAvlGCPhysDoWithAll() and RTAvlGCPhysDestroy(). */
948	typedef DECLCALLBACK(int) AVLGCPHYSCALLBACK(PAVLGCPHYSNODECORE pNode, void *pvUser);
949	/** Pointer to callback function for RTAvlGCPhysDoWithAll() and RTAvlGCPhysDestroy(). */
950	typedef AVLGCPHYSCALLBACK *PAVLGCPHYSCALLBACK;
951
952	RTDECL(bool) RTAvlGCPhysInsert(PAVLGCPHYSTREE pTree, PAVLGCPHYSNODECORE pNode);
953	RTDECL(PAVLGCPHYSNODECORE) RTAvlGCPhysRemove(PAVLGCPHYSTREE pTree, RTGCPHYS Key);
954	RTDECL(PAVLGCPHYSNODECORE) RTAvlGCPhysGet(PAVLGCPHYSTREE pTree, RTGCPHYS Key);
955	RTDECL(int) RTAvlGCPhysDoWithAll(PAVLGCPHYSTREE pTree, int fFromLeft, PAVLGCPHYSCALLBACK pfnCallBack, void *pvParam);
956	RTDECL(PAVLGCPHYSNODECORE) RTAvlGCPhysGetBestFit(PAVLGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
957	RTDECL(PAVLGCPHYSNODECORE) RTAvlGCPhysRemoveBestFit(PAVLGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
958	RTDECL(int) RTAvlGCPhysDestroy(PAVLGCPHYSTREE pTree, PAVLGCPHYSCALLBACK pfnCallBack, void *pvParam);
959
960	/** @} */
961
962
963	/** AVL tree of RTFOFF ranges.
964	* @{
965	*/
966
967	/**
968	* AVL Core node.
969	*/
970	typedef struct _AVLRFOFFNodeCore
971	{
972	/** First key value in the range (inclusive). */
973	RTFOFF Key;
974	/** Last key value in the range (inclusive). */
975	RTFOFF KeyLast;
976	/** Offset to the left leaf node, relative to this field. */
977	struct _AVLRFOFFNodeCore *pLeft;
978	/** Offset to the right leaf node, relative to this field. */
979	struct _AVLRFOFFNodeCore *pRight;
980	/** Height of this tree: max(height(left), height(right)) + 1 */
981	unsigned char uchHeight;
982	} AVLRFOFFNODECORE, *PAVLRFOFFNODECORE;
983
984	/** A pointer based tree with RTFOFF ranges. */
985	typedef PAVLRFOFFNODECORE AVLRFOFFTREE;
986	/** Pointer to a pointer based tree with RTFOFF ranges. */
987	typedef AVLRFOFFTREE *PAVLRFOFFTREE;
988
989	/** Pointer to an internal tree pointer.
990	* In this case it's a pointer to a relative offset. */
991	typedef AVLRFOFFTREE *PPAVLRFOFFNODECORE;
992
993	/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
994	typedef DECLCALLBACK(int) AVLRFOFFCALLBACK(PAVLRFOFFNODECORE pNode, void *pvUser);
995	/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
996	typedef AVLRFOFFCALLBACK *PAVLRFOFFCALLBACK;
997
998	RTDECL(bool) RTAvlrFileOffsetInsert( PAVLRFOFFTREE pTree, PAVLRFOFFNODECORE pNode);
999	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetRemove( PAVLRFOFFTREE pTree, RTFOFF Key);
1000	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGet( PAVLRFOFFTREE pTree, RTFOFF Key);
1001	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetBestFit( PAVLRFOFFTREE pTree, RTFOFF Key, bool fAbove);
1002	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetRangeGet( PAVLRFOFFTREE pTree, RTFOFF Key);
1003	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetRangeRemove( PAVLRFOFFTREE pTree, RTFOFF Key);
1004	RTDECL(int) RTAvlrFileOffsetDoWithAll( PAVLRFOFFTREE pTree, int fFromLeft, PAVLRFOFFCALLBACK pfnCallBack, void *pvParam);
1005	RTDECL(int) RTAvlrFileOffsetDestroy( PAVLRFOFFTREE pTree, PAVLRFOFFCALLBACK pfnCallBack, void *pvParam);
1006	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetRoot( PAVLRFOFFTREE pTree);
1007	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetLeft( PAVLRFOFFNODECORE pNode);
1008	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetRight( PAVLRFOFFNODECORE pNode);
1009
1010	/** @} */
1011
1012	/** @} */
1013
1014	RT_C_DECLS_END
1015
1016	#endif
1017

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

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

Download in other formats: