VirtualBox

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

Last change on this file since 19944 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 */
51typedef void * AVLPVKEY;
52
53/**
54 * AVL Core node.
55 */
56typedef 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. */
65typedef PAVLPVNODECORE AVLPVTREE;
66/** Pointer to a tree with void pointer keys. */
67typedef PPAVLPVNODECORE PAVLPVTREE;
68
69/** Callback function for AVLPVDoWithAll(). */
70typedef DECLCALLBACK(int) AVLPVCALLBACK(PAVLPVNODECORE, void *);
71/** Pointer to callback function for AVLPVDoWithAll(). */
72typedef AVLPVCALLBACK *PAVLPVCALLBACK;
73
74/*
75 * Functions.
76 */
77RTDECL(bool) RTAvlPVInsert(PAVLPVTREE ppTree, PAVLPVNODECORE pNode);
78RTDECL(PAVLPVNODECORE) RTAvlPVRemove(PAVLPVTREE ppTree, AVLPVKEY Key);
79RTDECL(PAVLPVNODECORE) RTAvlPVGet(PAVLPVTREE ppTree, AVLPVKEY Key);
80RTDECL(PAVLPVNODECORE) RTAvlPVGetBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
81RTDECL(PAVLPVNODECORE) RTAvlPVRemoveBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
82RTDECL(int) RTAvlPVDoWithAll(PAVLPVTREE ppTree, int fFromLeft, PAVLPVCALLBACK pfnCallBack, void *pvParam);
83RTDECL(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 */
95typedef unsigned long AVLULKEY;
96
97/**
98 * AVL Core node.
99 */
100typedef 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(). */
110typedef DECLCALLBACK(int) AVLULCALLBACK(PAVLULNODECORE, void*);
111/** Pointer to callback function for AVLULDoWithAll(). */
112typedef AVLULCALLBACK *PAVLULCALLBACK;
113
114
115/*
116 * Functions.
117 */
118RTDECL(bool) RTAvlULInsert(PPAVLULNODECORE ppTree, PAVLULNODECORE pNode);
119RTDECL(PAVLULNODECORE) RTAvlULRemove(PPAVLULNODECORE ppTree, AVLULKEY Key);
120RTDECL(PAVLULNODECORE) RTAvlULGet(PPAVLULNODECORE ppTree, AVLULKEY Key);
121RTDECL(PAVLULNODECORE) RTAvlULGetBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
122RTDECL(PAVLULNODECORE) RTAvlULRemoveBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
123RTDECL(int) RTAvlULDoWithAll(PPAVLULNODECORE ppTree, int fFromLeft, PAVLULCALLBACK pfnCallBack, void *pvParam);
124RTDECL(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. */
135typedef uint32_t AVLU32KEY;
136
137/** AVL Core node. */
138typedef 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. */
147typedef PAVLU32NODECORE AVLU32TREE;
148/** Pointer to a tree with void pointer keys. */
149typedef PPAVLU32NODECORE PAVLU32TREE;
150
151/** Callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
152typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
153/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
154typedef AVLU32CALLBACK *PAVLU32CALLBACK;
155
156
157/*
158 * Functions.
159 */
160RTDECL(bool) RTAvlU32Insert(PAVLU32TREE pTree, PAVLU32NODECORE pNode);
161RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PAVLU32TREE pTree, AVLU32KEY Key);
162RTDECL(PAVLU32NODECORE) RTAvlU32Get(PAVLU32TREE pTree, AVLU32KEY Key);
163RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
164RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
165RTDECL(int) RTAvlU32DoWithAll(PAVLU32TREE pTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
166RTDECL(int) RTAvlU32Destroy(PAVLU32TREE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
167
168/** @} */
169
170/**
171 * AVL uint32_t type for the relative offset pointer scheme.
172 */
173typedef int32_t AVLOU32;
174
175typedef uint32_t AVLOU32KEY;
176
177/**
178 * AVL Core node.
179 */
180typedef 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. */
193typedef AVLOU32 AVLOU32TREE;
194/** Pointer to a offset base tree with uint32_t keys. */
195typedef AVLOU32TREE *PAVLOU32TREE;
196
197/** Pointer to an internal tree pointer.
198 * In this case it's a pointer to a relative offset. */
199typedef AVLOU32TREE *PPAVLOU32NODECORE;
200
201/** Callback function for RTAvloU32DoWithAll(). */
202typedef DECLCALLBACK(int) AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
203/** Pointer to callback function for RTAvloU32DoWithAll(). */
204typedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
205
206RTDECL(bool) RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
207RTDECL(PAVLOU32NODECORE) RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
208RTDECL(PAVLOU32NODECORE) RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
209RTDECL(int) RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
210RTDECL(PAVLOU32NODECORE) RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
211RTDECL(PAVLOU32NODECORE) RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
212RTDECL(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. */
222typedef uint32_t AVLLU32KEY;
223
224/** AVL Core node. */
225typedef 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(). */
235typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
236/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
237typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
238
239
240/*
241 * Functions.
242 */
243RTDECL(bool) RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
244RTDECL(PAVLLU32NODECORE) RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
245RTDECL(PAVLLU32NODECORE) RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
246RTDECL(PAVLLU32NODECORE) RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
247RTDECL(PAVLLU32NODECORE) RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
248RTDECL(int) RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
249RTDECL(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 */
262typedef int32_t AVLOGCPHYS;
263
264/**
265 * AVL Core node.
266 */
267typedef 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. */
282typedef AVLOGCPHYS AVLOGCPHYSTREE;
283/** Pointer to a offset base tree with uint32_t keys. */
284typedef AVLOGCPHYSTREE *PAVLOGCPHYSTREE;
285
286/** Pointer to an internal tree pointer.
287 * In this case it's a pointer to a relative offset. */
288typedef AVLOGCPHYSTREE *PPAVLOGCPHYSNODECORE;
289
290/** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
291typedef DECLCALLBACK(int) AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
292/** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
293typedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
294
295RTDECL(bool) RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
296RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
297RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
298RTDECL(int) RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
299RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
300RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
301RTDECL(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 */
313typedef int32_t AVLROGCPHYS;
314
315/**
316 * AVL Core node.
317 */
318typedef 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. */
335typedef AVLROGCPHYS AVLROGCPHYSTREE;
336/** Pointer to a offset base tree with uint32_t keys. */
337typedef AVLROGCPHYSTREE *PAVLROGCPHYSTREE;
338
339/** Pointer to an internal tree pointer.
340 * In this case it's a pointer to a relative offset. */
341typedef AVLROGCPHYSTREE *PPAVLROGCPHYSNODECORE;
342
343/** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
344typedef DECLCALLBACK(int) AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
345/** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
346typedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
347
348RTDECL(bool) RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
349RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
350RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
351RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
352RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
353RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
354RTDECL(int) RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
355RTDECL(int) RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
356RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
357RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
358RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
359
360/** @} */
361
362
363/** AVL tree of RTGCPTRs.
364 * @{
365 */
366
367/**
368 * AVL Core node.
369 */
370typedef 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. */
383typedef PAVLGCPTRNODECORE AVLGCPTRTREE;
384/** Pointer to a tree of RTGCPTR keys. */
385typedef PPAVLGCPTRNODECORE PAVLGCPTRTREE;
386
387/** Callback function for RTAvlGCPtrDoWithAll(). */
388typedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
389/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
390typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
391
392RTDECL(bool) RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
393RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
394RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
395RTDECL(int) RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
396RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
397RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
398RTDECL(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 */
410typedef int32_t AVLOGCPTR;
411
412/**
413 * AVL Core node.
414 */
415typedef 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. */
429typedef AVLOGCPTR AVLOGCPTRTREE;
430/** Pointer to a offset base tree with uint32_t keys. */
431typedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
432
433/** Pointer to an internal tree pointer.
434 * In this case it's a pointer to a relative offset. */
435typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
436
437/** Callback function for RTAvloGCPtrDoWithAll(). */
438typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
439/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
440typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
441
442RTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
443RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
444RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
445RTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
446RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
447RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
448RTDECL(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 */
460typedef 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. */
475typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
476/** Pointer to a offset base tree with RTGCPTR keys. */
477typedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
478
479/** Pointer to an internal tree pointer.
480 * In this case it's a pointer to a relative offset. */
481typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
482
483/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
484typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
485/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
486typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
487
488RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
489RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
490RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
491RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
492RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
493RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
494RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
495RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
496RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
497RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
498RTDECL(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 */
510typedef int32_t AVLROGCPTR;
511
512/**
513 * AVL Core node.
514 */
515typedef 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. */
531typedef AVLROGCPTR AVLROGCPTRTREE;
532/** Pointer to a offset base tree with uint32_t keys. */
533typedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
534
535/** Pointer to an internal tree pointer.
536 * In this case it's a pointer to a relative offset. */
537typedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
538
539/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
540typedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
541/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
542typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
543
544RTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
545RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
546RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
547RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
548RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
549RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
550RTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
551RTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
552RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
553RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
554RTDECL(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 */
566typedef int32_t AVLROOGCPTR;
567
568/**
569 * AVL Core node.
570 */
571typedef 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. */
588typedef AVLROOGCPTR AVLROOGCPTRTREE;
589/** Pointer to a offset base tree with uint32_t keys. */
590typedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
591
592/** Pointer to an internal tree pointer.
593 * In this case it's a pointer to a relative offset. */
594typedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
595
596/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
597typedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
598/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
599typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
600
601RTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
602RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
603RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
604RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
605RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
606RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
607RTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
608RTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
609RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
610RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
611RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
612RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
613
614/** @} */
615
616
617/** AVL tree of RTUINTPTR ranges.
618 * @{
619 */
620
621/**
622 * AVL Core node.
623 */
624typedef 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. */
639typedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
640/** Pointer to a offset base tree with RTUINTPTR keys. */
641typedef AVLRUINTPTRTREE *PAVLRUINTPTRTREE;
642
643/** Pointer to an internal tree pointer.
644 * In this case it's a pointer to a relative offset. */
645typedef AVLRUINTPTRTREE *PPAVLRUINTPTRNODECORE;
646
647/** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
648typedef DECLCALLBACK(int) AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
649/** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
650typedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
651
652RTDECL(bool) RTAvlrUIntPtrInsert( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
653RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRemove( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
654RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
655RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
656RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
657RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
658RTDECL(int) RTAvlrUIntPtrDoWithAll( PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
659RTDECL(int) RTAvlrUIntPtrDestroy( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
660RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRoot( PAVLRUINTPTRTREE pTree);
661RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetLeft( PAVLRUINTPTRNODECORE pNode);
662RTDECL(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 */
674typedef int32_t AVLOHCPHYS;
675
676/**
677 * AVL Core node.
678 */
679typedef 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. */
695typedef AVLOHCPHYS AVLOHCPHYSTREE;
696/** Pointer to a offset base tree with uint32_t keys. */
697typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
698
699/** Pointer to an internal tree pointer.
700 * In this case it's a pointer to a relative offset. */
701typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
702
703/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
704typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
705/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
706typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
707
708RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
709RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
710RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
711RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
712RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
713RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
714RTDECL(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 */
727typedef int32_t AVLOIOPORTPTR;
728
729/**
730 * AVL Core node.
731 */
732typedef 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. */
745typedef AVLOIOPORTPTR AVLOIOPORTTREE;
746/** Pointer to a offset base tree with uint32_t keys. */
747typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
748
749/** Pointer to an internal tree pointer.
750 * In this case it's a pointer to a relative offset. */
751typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
752
753/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
754typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
755/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
756typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
757
758RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
759RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
760RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
761RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
762RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
763RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
764RTDECL(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 */
776typedef int32_t AVLROIOPORTPTR;
777
778/**
779 * AVL Core node.
780 */
781typedef 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. */
796typedef AVLROIOPORTPTR AVLROIOPORTTREE;
797/** Pointer to a offset base tree with uint32_t keys. */
798typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
799
800/** Pointer to an internal tree pointer.
801 * In this case it's a pointer to a relative offset. */
802typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
803
804/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
805typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
806/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
807typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
808
809RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
810RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
811RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
812RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
813RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
814RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
815RTDECL(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 */
827typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
828
829/**
830 * AVL Core node.
831 */
832typedef 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. */
845typedef AVLHCPHYSPTR AVLHCPHYSTREE;
846/** Pointer to a offset base tree with RTHCPHYS keys. */
847typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
848
849/** Pointer to an internal tree pointer.
850 * In this case it's a pointer to a relative offset. */
851typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
852
853/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
854typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
855/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
856typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
857
858RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
859RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
860RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
861RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
862RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
863RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
864RTDECL(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.

© 2024 Oracle Support Privacy / Do Not Sell My Info Terms of Use Trademark Policy Automated Access Etiquette