avl.h@ 26201

Last change on this file since 26201 was 22308, checked in by vboxsync, 15 years ago
Runtime: Add RTFOFF Avl tree variant for the I/O cache
Property svn:eol-style set to `native` Property svn:keywords set to `Author Date Id Revision`
File size: 40.2 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	* 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	RT_C_DECLS_BEGIN
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.
618	* @{
619	*/
620
621	/**
622	* AVL RTUINTPTR node core.
623	*/
624	typedef struct _AVLUIntPtrNodeCore
625	{
626	/** Key value. */
627	RTUINTPTR Key;
628	/** Offset to the left leaf node, relative to this field. */
629	struct _AVLUIntPtrNodeCore *pLeft;
630	/** Offset to the right leaf node, relative to this field. */
631	struct _AVLUIntPtrNodeCore *pRight;
632	/** Height of this tree: max(height(left), height(right)) + 1 */
633	unsigned char uchHeight;
634	} AVLUINTPTRNODECORE;
635	/** Pointer to a RTUINTPTR AVL node core.*/
636	typedef AVLUINTPTRNODECORE *PAVLUINTPTRNODECORE;
637
638	/** A pointer based tree with RTUINTPTR keys. */
639	typedef PAVLUINTPTRNODECORE AVLUINTPTRTREE;
640	/** Pointer to a offset base tree with RTUINTPTR keys. */
641	typedef AVLUINTPTRTREE *PAVLUINTPTRTREE;
642
643	/** Pointer to an internal tree pointer.
644	* In this case it's a pointer to a pointer. */
645	typedef AVLUINTPTRTREE *PPAVLUINTPTRNODECORE;
646
647	/** Callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
648	typedef DECLCALLBACK(int) AVLUINTPTRCALLBACK(PAVLUINTPTRNODECORE pNode, void *pvUser);
649	/** Pointer to callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
650	typedef AVLUINTPTRCALLBACK *PAVLUINTPTRCALLBACK;
651
652	RTDECL(bool) RTAvlUIntPtrInsert( PAVLUINTPTRTREE pTree, PAVLUINTPTRNODECORE pNode);
653	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrRemove( PAVLUINTPTRTREE pTree, RTUINTPTR Key);
654	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGet( PAVLUINTPTRTREE pTree, RTUINTPTR Key);
655	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetBestFit(PAVLUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
656	RTDECL(int) RTAvlUIntPtrDoWithAll( PAVLUINTPTRTREE pTree, int fFromLeft, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
657	RTDECL(int) RTAvlUIntPtrDestroy( PAVLUINTPTRTREE pTree, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
658	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetRoot( PAVLUINTPTRTREE pTree);
659	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetLeft( PAVLUINTPTRNODECORE pNode);
660	RTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetRight( PAVLUINTPTRNODECORE pNode);
661
662	/** @} */
663
664
665	/** AVL tree of RTUINTPTR ranges.
666	* @{
667	*/
668
669	/**
670	* AVL RTUINTPTR range node core.
671	*/
672	typedef struct _AVLRUIntPtrNodeCore
673	{
674	/** First key value in the range (inclusive). */
675	RTUINTPTR Key;
676	/** Last key value in the range (inclusive). */
677	RTUINTPTR KeyLast;
678	/** Offset to the left leaf node, relative to this field. */
679	struct _AVLRUIntPtrNodeCore *pLeft;
680	/** Offset to the right leaf node, relative to this field. */
681	struct _AVLRUIntPtrNodeCore *pRight;
682	/** Height of this tree: max(height(left), height(right)) + 1 */
683	unsigned char uchHeight;
684	} AVLRUINTPTRNODECORE;
685	/** Pointer to an AVL RTUINTPTR range node code. */
686	typedef AVLRUINTPTRNODECORE *PAVLRUINTPTRNODECORE;
687
688	/** A pointer based tree with RTUINTPTR ranges. */
689	typedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
690	/** Pointer to a pointer based tree with RTUINTPTR ranges. */
691	typedef AVLRUINTPTRTREE *PAVLRUINTPTRTREE;
692
693	/** Pointer to an internal tree pointer.
694	* In this case it's a pointer to a pointer. */
695	typedef AVLRUINTPTRTREE *PPAVLRUINTPTRNODECORE;
696
697	/** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
698	typedef DECLCALLBACK(int) AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
699	/** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
700	typedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
701
702	RTDECL(bool) RTAvlrUIntPtrInsert( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
703	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRemove( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
704	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
705	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
706	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
707	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
708	RTDECL(int) RTAvlrUIntPtrDoWithAll( PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
709	RTDECL(int) RTAvlrUIntPtrDestroy( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
710	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRoot( PAVLRUINTPTRTREE pTree);
711	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetLeft( PAVLRUINTPTRNODECORE pNode);
712	RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRight( PAVLRUINTPTRNODECORE pNode);
713
714	/** @} */
715
716
717	/** AVL tree of RTHCPHYSes - using relative offsets internally.
718	* @{
719	*/
720
721	/**
722	* AVL 'pointer' type for the relative offset pointer scheme.
723	*/
724	typedef int32_t AVLOHCPHYS;
725
726	/**
727	* AVL Core node.
728	*/
729	typedef struct _AVLOHCPhysNodeCore
730	{
731	/** Key value. */
732	RTHCPHYS Key;
733	/** Offset to the left leaf node, relative to this field. */
734	AVLOHCPHYS pLeft;
735	/** Offset to the right leaf node, relative to this field. */
736	AVLOHCPHYS pRight;
737	/** Height of this tree: max(height(left), height(right)) + 1 */
738	unsigned char uchHeight;
739	#if HC_ARCH_BITS == 64 \|\| GC_ARCH_BITS == 64
740	unsigned char Padding[7]; /*< Alignment padding. /
741	#endif
742	} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
743
744	/** A offset base tree with uint32_t keys. */
745	typedef AVLOHCPHYS AVLOHCPHYSTREE;
746	/** Pointer to a offset base tree with uint32_t keys. */
747	typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
748
749	/** Pointer to an internal tree pointer.
750	* In this case it's a pointer to a relative offset. */
751	typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
752
753	/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
754	typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
755	/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
756	typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
757
758	RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
759	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
760	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
761	RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
762	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
763	RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
764	RTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
765
766	/** @} */
767
768
769
770	/** AVL tree of RTIOPORTs - using relative offsets internally.
771	* @{
772	*/
773
774	/**
775	* AVL 'pointer' type for the relative offset pointer scheme.
776	*/
777	typedef int32_t AVLOIOPORTPTR;
778
779	/**
780	* AVL Core node.
781	*/
782	typedef struct _AVLOIOPortNodeCore
783	{
784	/** Offset to the left leaf node, relative to this field. */
785	AVLOIOPORTPTR pLeft;
786	/** Offset to the right leaf node, relative to this field. */
787	AVLOIOPORTPTR pRight;
788	/** Key value. */
789	RTIOPORT Key;
790	/** Height of this tree: max(height(left), height(right)) + 1 */
791	unsigned char uchHeight;
792	} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
793
794	/** A offset base tree with uint32_t keys. */
795	typedef AVLOIOPORTPTR AVLOIOPORTTREE;
796	/** Pointer to a offset base tree with uint32_t keys. */
797	typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
798
799	/** Pointer to an internal tree pointer.
800	* In this case it's a pointer to a relative offset. */
801	typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
802
803	/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
804	typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
805	/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
806	typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
807
808	RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
809	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
810	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
811	RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
812	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
813	RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
814	RTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
815
816	/** @} */
817
818
819	/** AVL tree of RTIOPORT ranges - using relative offsets internally.
820	* @{
821	*/
822
823	/**
824	* AVL 'pointer' type for the relative offset pointer scheme.
825	*/
826	typedef int32_t AVLROIOPORTPTR;
827
828	/**
829	* AVL Core node.
830	*/
831	typedef struct _AVLROIOPortNodeCore
832	{
833	/** First key value in the range (inclusive). */
834	RTIOPORT Key;
835	/** Last key value in the range (inclusive). */
836	RTIOPORT KeyLast;
837	/** Offset to the left leaf node, relative to this field. */
838	AVLROIOPORTPTR pLeft;
839	/** Offset to the right leaf node, relative to this field. */
840	AVLROIOPORTPTR pRight;
841	/** Height of this tree: max(height(left), height(right)) + 1 */
842	unsigned char uchHeight;
843	} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
844
845	/** A offset base tree with uint32_t keys. */
846	typedef AVLROIOPORTPTR AVLROIOPORTTREE;
847	/** Pointer to a offset base tree with uint32_t keys. */
848	typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
849
850	/** Pointer to an internal tree pointer.
851	* In this case it's a pointer to a relative offset. */
852	typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
853
854	/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
855	typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
856	/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
857	typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
858
859	RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
860	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
861	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
862	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
863	RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
864	RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
865	RTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
866
867	/** @} */
868
869
870	/** AVL tree of RTHCPHYSes.
871	* @{
872	*/
873
874	/**
875	* AVL 'pointer' type for the relative offset pointer scheme.
876	*/
877	typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
878
879	/**
880	* AVL Core node.
881	*/
882	typedef struct _AVLHCPhysNodeCore
883	{
884	/** Offset to the left leaf node, relative to this field. */
885	AVLHCPHYSPTR pLeft;
886	/** Offset to the right leaf node, relative to this field. */
887	AVLHCPHYSPTR pRight;
888	/** Key value. */
889	RTHCPHYS Key;
890	/** Height of this tree: max(height(left), height(right)) + 1 */
891	unsigned char uchHeight;
892	} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
893
894	/** A offset base tree with RTHCPHYS keys. */
895	typedef AVLHCPHYSPTR AVLHCPHYSTREE;
896	/** Pointer to a offset base tree with RTHCPHYS keys. */
897	typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
898
899	/** Pointer to an internal tree pointer.
900	* In this case it's a pointer to a relative offset. */
901	typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
902
903	/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
904	typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
905	/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
906	typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
907
908	RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
909	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
910	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
911	RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
912	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
913	RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
914	RTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
915
916	/** @} */
917
918
919	/** AVL tree of RTFOFF ranges.
920	* @{
921	*/
922
923	/**
924	* AVL Core node.
925	*/
926	typedef struct _AVLRFOFFNodeCore
927	{
928	/** First key value in the range (inclusive). */
929	RTFOFF Key;
930	/** Last key value in the range (inclusive). */
931	RTFOFF KeyLast;
932	/** Offset to the left leaf node, relative to this field. */
933	struct _AVLRFOFFNodeCore *pLeft;
934	/** Offset to the right leaf node, relative to this field. */
935	struct _AVLRFOFFNodeCore *pRight;
936	/** Height of this tree: max(height(left), height(right)) + 1 */
937	unsigned char uchHeight;
938	} AVLRFOFFNODECORE, *PAVLRFOFFNODECORE;
939
940	/** A pointer based tree with RTFOFF ranges. */
941	typedef PAVLRFOFFNODECORE AVLRFOFFTREE;
942	/** Pointer to a pointer based tree with RTFOFF ranges. */
943	typedef AVLRFOFFTREE *PAVLRFOFFTREE;
944
945	/** Pointer to an internal tree pointer.
946	* In this case it's a pointer to a relative offset. */
947	typedef AVLRFOFFTREE *PPAVLRFOFFNODECORE;
948
949	/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
950	typedef DECLCALLBACK(int) AVLRFOFFCALLBACK(PAVLRFOFFNODECORE pNode, void *pvUser);
951	/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
952	typedef AVLRFOFFCALLBACK *PAVLRFOFFCALLBACK;
953
954	RTDECL(bool) RTAvlrFileOffsetInsert( PAVLRFOFFTREE pTree, PAVLRFOFFNODECORE pNode);
955	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetRemove( PAVLRFOFFTREE pTree, RTFOFF Key);
956	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGet( PAVLRFOFFTREE pTree, RTFOFF Key);
957	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetBestFit( PAVLRFOFFTREE pTree, RTFOFF Key, bool fAbove);
958	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetRangeGet( PAVLRFOFFTREE pTree, RTFOFF Key);
959	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetRangeRemove( PAVLRFOFFTREE pTree, RTFOFF Key);
960	RTDECL(int) RTAvlrFileOffsetDoWithAll( PAVLRFOFFTREE pTree, int fFromLeft, PAVLRFOFFCALLBACK pfnCallBack, void *pvParam);
961	RTDECL(int) RTAvlrFileOffsetDestroy( PAVLRFOFFTREE pTree, PAVLRFOFFCALLBACK pfnCallBack, void *pvParam);
962	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetRoot( PAVLRFOFFTREE pTree);
963	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetLeft( PAVLRFOFFNODECORE pNode);
964	RTDECL(PAVLRFOFFNODECORE) RTAvlrFileOffsetGetRight( PAVLRFOFFNODECORE pNode);
965
966	/** @} */
967
968	/** @} */
969
970	RT_C_DECLS_END
971
972	#endif
973

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

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

Download in other formats: