VirtualBox

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

Last change on this file since 19755 was 19567, checked in by vboxsync, 16 years ago

blank line.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 35.4 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/** Callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
147typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
148/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
149typedef AVLU32CALLBACK *PAVLU32CALLBACK;
150
151
152/*
153 * Functions.
154 */
155RTDECL(bool) RTAvlU32Insert(PPAVLU32NODECORE ppTree, PAVLU32NODECORE pNode);
156RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PPAVLU32NODECORE ppTree, AVLU32KEY Key);
157RTDECL(PAVLU32NODECORE) RTAvlU32Get(PPAVLU32NODECORE ppTree, AVLU32KEY Key);
158RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PPAVLU32NODECORE ppTree, AVLU32KEY Key, bool fAbove);
159RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PPAVLU32NODECORE ppTree, AVLU32KEY Key, bool fAbove);
160RTDECL(int) RTAvlU32DoWithAll(PPAVLU32NODECORE ppTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
161RTDECL(int) RTAvlU32Destroy(PPAVLU32NODECORE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
162
163/** @} */
164
165/**
166 * AVL uint32_t type for the relative offset pointer scheme.
167 */
168typedef int32_t AVLOU32;
169
170typedef uint32_t AVLOU32KEY;
171
172/**
173 * AVL Core node.
174 */
175typedef struct _AVLOU32NodeCore
176{
177 /** Key value. */
178 AVLOU32KEY Key;
179 /** Offset to the left leaf node, relative to this field. */
180 AVLOU32 pLeft;
181 /** Offset to the right leaf node, relative to this field. */
182 AVLOU32 pRight;
183 /** Height of this tree: max(height(left), height(right)) + 1 */
184 unsigned char uchHeight;
185} AVLOU32NODECORE, *PAVLOU32NODECORE;
186
187/** A offset base tree with uint32_t keys. */
188typedef AVLOU32 AVLOU32TREE;
189/** Pointer to a offset base tree with uint32_t keys. */
190typedef AVLOU32TREE *PAVLOU32TREE;
191
192/** Pointer to an internal tree pointer.
193 * In this case it's a pointer to a relative offset. */
194typedef AVLOU32TREE *PPAVLOU32NODECORE;
195
196/** Callback function for RTAvloU32DoWithAll(). */
197typedef DECLCALLBACK(int) AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
198/** Pointer to callback function for RTAvloU32DoWithAll(). */
199typedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
200
201RTDECL(bool) RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
202RTDECL(PAVLOU32NODECORE) RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
203RTDECL(PAVLOU32NODECORE) RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
204RTDECL(int) RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
205RTDECL(PAVLOU32NODECORE) RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
206RTDECL(PAVLOU32NODECORE) RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
207RTDECL(int) RTAvloU32Destroy(PAVLOU32TREE pTree, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
208
209/** @} */
210
211
212/** AVL tree of uint32_t, list duplicates.
213 * @{
214 */
215
216/** AVL key type. */
217typedef uint32_t AVLLU32KEY;
218
219/** AVL Core node. */
220typedef struct _AVLLU32NodeCore
221{
222 AVLLU32KEY Key; /**< Key value. */
223 unsigned char uchHeight; /**< Height of this tree: max(height(left), height(right)) + 1 */
224 struct _AVLLU32NodeCore *pLeft; /**< Pointer to left leaf node. */
225 struct _AVLLU32NodeCore *pRight; /**< Pointer to right leaf node. */
226 struct _AVLLU32NodeCore *pList; /**< Pointer to next node with the same key. */
227} AVLLU32NODECORE, *PAVLLU32NODECORE, **PPAVLLU32NODECORE;
228
229/** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
230typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
231/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
232typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
233
234
235/*
236 * Functions.
237 */
238RTDECL(bool) RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
239RTDECL(PAVLLU32NODECORE) RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
240RTDECL(PAVLLU32NODECORE) RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
241RTDECL(PAVLLU32NODECORE) RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
242RTDECL(PAVLLU32NODECORE) RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
243RTDECL(int) RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
244RTDECL(int) RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
245
246/** @} */
247
248
249
250/** AVL tree of RTGCPHYSes - using relative offsets internally.
251 * @{
252 */
253
254/**
255 * AVL 'pointer' type for the relative offset pointer scheme.
256 */
257typedef int32_t AVLOGCPHYS;
258
259/**
260 * AVL Core node.
261 */
262typedef struct _AVLOGCPhysNodeCore
263{
264 /** Key value. */
265 RTGCPHYS Key;
266 /** Offset to the left leaf node, relative to this field. */
267 AVLOGCPHYS pLeft;
268 /** Offset to the right leaf node, relative to this field. */
269 AVLOGCPHYS pRight;
270 /** Height of this tree: max(height(left), height(right)) + 1 */
271 unsigned char uchHeight;
272 /** Padding */
273 unsigned char Padding[7];
274} AVLOGCPHYSNODECORE, *PAVLOGCPHYSNODECORE;
275
276/** A offset base tree with uint32_t keys. */
277typedef AVLOGCPHYS AVLOGCPHYSTREE;
278/** Pointer to a offset base tree with uint32_t keys. */
279typedef AVLOGCPHYSTREE *PAVLOGCPHYSTREE;
280
281/** Pointer to an internal tree pointer.
282 * In this case it's a pointer to a relative offset. */
283typedef AVLOGCPHYSTREE *PPAVLOGCPHYSNODECORE;
284
285/** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
286typedef DECLCALLBACK(int) AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
287/** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
288typedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
289
290RTDECL(bool) RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
291RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
292RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
293RTDECL(int) RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
294RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
295RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
296RTDECL(int) RTAvloGCPhysDestroy(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
297
298/** @} */
299
300
301/** AVL tree of RTGCPHYS ranges - using relative offsets internally.
302 * @{
303 */
304
305/**
306 * AVL 'pointer' type for the relative offset pointer scheme.
307 */
308typedef int32_t AVLROGCPHYS;
309
310/**
311 * AVL Core node.
312 */
313typedef struct _AVLROGCPhysNodeCore
314{
315 /** First key value in the range (inclusive). */
316 RTGCPHYS Key;
317 /** Last key value in the range (inclusive). */
318 RTGCPHYS KeyLast;
319 /** Offset to the left leaf node, relative to this field. */
320 AVLROGCPHYS pLeft;
321 /** Offset to the right leaf node, relative to this field. */
322 AVLROGCPHYS pRight;
323 /** Height of this tree: max(height(left), height(right)) + 1 */
324 unsigned char uchHeight;
325 /** Padding */
326 unsigned char Padding[7];
327} AVLROGCPHYSNODECORE, *PAVLROGCPHYSNODECORE;
328
329/** A offset base tree with uint32_t keys. */
330typedef AVLROGCPHYS AVLROGCPHYSTREE;
331/** Pointer to a offset base tree with uint32_t keys. */
332typedef AVLROGCPHYSTREE *PAVLROGCPHYSTREE;
333
334/** Pointer to an internal tree pointer.
335 * In this case it's a pointer to a relative offset. */
336typedef AVLROGCPHYSTREE *PPAVLROGCPHYSNODECORE;
337
338/** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
339typedef DECLCALLBACK(int) AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
340/** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
341typedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
342
343RTDECL(bool) RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
344RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
345RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
346RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
347RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
348RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
349RTDECL(int) RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
350RTDECL(int) RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
351RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
352RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
353RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
354
355/** @} */
356
357
358/** AVL tree of RTGCPTRs.
359 * @{
360 */
361
362/**
363 * AVL Core node.
364 */
365typedef struct _AVLGCPtrNodeCore
366{
367 /** Key value. */
368 RTGCPTR Key;
369 /** Pointer to the left node. */
370 struct _AVLGCPtrNodeCore *pLeft;
371 /** Pointer to the right node. */
372 struct _AVLGCPtrNodeCore *pRight;
373 /** Height of this tree: max(height(left), height(right)) + 1 */
374 unsigned char uchHeight;
375} AVLGCPTRNODECORE, *PAVLGCPTRNODECORE, **PPAVLGCPTRNODECORE;
376
377/** A tree of RTGCPTR keys. */
378typedef PAVLGCPTRNODECORE AVLGCPTRTREE;
379/** Pointer to a tree of RTGCPTR keys. */
380typedef PPAVLGCPTRNODECORE PAVLGCPTRTREE;
381
382/** Callback function for RTAvlGCPtrDoWithAll(). */
383typedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
384/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
385typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
386
387RTDECL(bool) RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
388RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
389RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
390RTDECL(int) RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
391RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
392RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
393RTDECL(int) RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
394
395/** @} */
396
397
398/** AVL tree of RTGCPTRs - using relative offsets internally.
399 * @{
400 */
401
402/**
403 * AVL 'pointer' type for the relative offset pointer scheme.
404 */
405typedef int32_t AVLOGCPTR;
406
407/**
408 * AVL Core node.
409 */
410typedef struct _AVLOGCPtrNodeCore
411{
412 /** Key value. */
413 RTGCPTR Key;
414 /** Offset to the left leaf node, relative to this field. */
415 AVLOGCPTR pLeft;
416 /** Offset to the right leaf node, relative to this field. */
417 AVLOGCPTR pRight;
418 /** Height of this tree: max(height(left), height(right)) + 1 */
419 unsigned char uchHeight;
420 unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 3];
421} AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
422
423/** A offset base tree with uint32_t keys. */
424typedef AVLOGCPTR AVLOGCPTRTREE;
425/** Pointer to a offset base tree with uint32_t keys. */
426typedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
427
428/** Pointer to an internal tree pointer.
429 * In this case it's a pointer to a relative offset. */
430typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
431
432/** Callback function for RTAvloGCPtrDoWithAll(). */
433typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
434/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
435typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
436
437RTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
438RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
439RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
440RTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
441RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
442RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
443RTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
444
445/** @} */
446
447
448/** AVL tree of RTGCPTR ranges.
449 * @{
450 */
451
452/**
453 * AVL Core node.
454 */
455typedef struct _AVLRGCPtrNodeCore
456{
457 /** First key value in the range (inclusive). */
458 RTGCPTR Key;
459 /** Last key value in the range (inclusive). */
460 RTGCPTR KeyLast;
461 /** Offset to the left leaf node, relative to this field. */
462 struct _AVLRGCPtrNodeCore *pLeft;
463 /** Offset to the right leaf node, relative to this field. */
464 struct _AVLRGCPtrNodeCore *pRight;
465 /** Height of this tree: max(height(left), height(right)) + 1 */
466 unsigned char uchHeight;
467} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
468
469/** A offset base tree with RTGCPTR keys. */
470typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
471/** Pointer to a offset base tree with RTGCPTR keys. */
472typedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
473
474/** Pointer to an internal tree pointer.
475 * In this case it's a pointer to a relative offset. */
476typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
477
478/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
479typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
480/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
481typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
482
483RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
484RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
485RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
486RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
487RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
488RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
489RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
490RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
491RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
492RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
493RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode);
494
495/** @} */
496
497
498/** AVL tree of RTGCPTR ranges - using relative offsets internally.
499 * @{
500 */
501
502/**
503 * AVL 'pointer' type for the relative offset pointer scheme.
504 */
505typedef int32_t AVLROGCPTR;
506
507/**
508 * AVL Core node.
509 */
510typedef struct _AVLROGCPtrNodeCore
511{
512 /** First key value in the range (inclusive). */
513 RTGCPTR Key;
514 /** Last key value in the range (inclusive). */
515 RTGCPTR KeyLast;
516 /** Offset to the left leaf node, relative to this field. */
517 AVLROGCPTR pLeft;
518 /** Offset to the right leaf node, relative to this field. */
519 AVLROGCPTR pRight;
520 /** Height of this tree: max(height(left), height(right)) + 1 */
521 unsigned char uchHeight;
522 unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 7];
523} AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
524
525/** A offset base tree with uint32_t keys. */
526typedef AVLROGCPTR AVLROGCPTRTREE;
527/** Pointer to a offset base tree with uint32_t keys. */
528typedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
529
530/** Pointer to an internal tree pointer.
531 * In this case it's a pointer to a relative offset. */
532typedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
533
534/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
535typedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
536/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
537typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
538
539RTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
540RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
541RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
542RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
543RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
544RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
545RTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
546RTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
547RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
548RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
549RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
550
551/** @} */
552
553
554/** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
555 * @{
556 */
557
558/**
559 * AVL 'pointer' type for the relative offset pointer scheme.
560 */
561typedef int32_t AVLROOGCPTR;
562
563/**
564 * AVL Core node.
565 */
566typedef struct _AVLROOGCPtrNodeCore
567{
568 /** First key value in the range (inclusive). */
569 RTGCPTR Key;
570 /** Last key value in the range (inclusive). */
571 RTGCPTR KeyLast;
572 /** Offset to the left leaf node, relative to this field. */
573 AVLROOGCPTR pLeft;
574 /** Offset to the right leaf node, relative to this field. */
575 AVLROOGCPTR pRight;
576 /** Pointer to the list of string with the same key. Don't touch. */
577 AVLROOGCPTR pList;
578 /** Height of this tree: max(height(left), height(right)) + 1 */
579 unsigned char uchHeight;
580} AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
581
582/** A offset base tree with uint32_t keys. */
583typedef AVLROOGCPTR AVLROOGCPTRTREE;
584/** Pointer to a offset base tree with uint32_t keys. */
585typedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
586
587/** Pointer to an internal tree pointer.
588 * In this case it's a pointer to a relative offset. */
589typedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
590
591/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
592typedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
593/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
594typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
595
596RTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
597RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
598RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
599RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
600RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
601RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
602RTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
603RTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
604RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
605RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
606RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
607RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
608
609/** @} */
610
611
612/** AVL tree of RTUINTPTR ranges.
613 * @{
614 */
615
616/**
617 * AVL Core node.
618 */
619typedef struct _AVLRUIntPtrNodeCore
620{
621 /** First key value in the range (inclusive). */
622 RTUINTPTR Key;
623 /** Last key value in the range (inclusive). */
624 RTUINTPTR KeyLast;
625 /** Offset to the left leaf node, relative to this field. */
626 struct _AVLRUIntPtrNodeCore *pLeft;
627 /** Offset to the right leaf node, relative to this field. */
628 struct _AVLRUIntPtrNodeCore *pRight;
629 /** Height of this tree: max(height(left), height(right)) + 1 */
630 unsigned char uchHeight;
631} AVLRUINTPTRNODECORE, *PAVLRUINTPTRNODECORE;
632
633/** A offset base tree with RTUINTPTR keys. */
634typedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
635/** Pointer to a offset base tree with RTUINTPTR keys. */
636typedef AVLRUINTPTRTREE *PAVLRUINTPTRTREE;
637
638/** Pointer to an internal tree pointer.
639 * In this case it's a pointer to a relative offset. */
640typedef AVLRUINTPTRTREE *PPAVLRUINTPTRNODECORE;
641
642/** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
643typedef DECLCALLBACK(int) AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
644/** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
645typedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
646
647RTDECL(bool) RTAvlrUIntPtrInsert( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
648RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRemove( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
649RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
650RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
651RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
652RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
653RTDECL(int) RTAvlrUIntPtrDoWithAll( PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
654RTDECL(int) RTAvlrUIntPtrDestroy( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
655RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRoot( PAVLRUINTPTRTREE pTree);
656RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetLeft( PAVLRUINTPTRNODECORE pNode);
657RTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRight( PAVLRUINTPTRNODECORE pNode);
658
659/** @} */
660
661
662/** AVL tree of RTHCPHYSes - using relative offsets internally.
663 * @{
664 */
665
666/**
667 * AVL 'pointer' type for the relative offset pointer scheme.
668 */
669typedef int32_t AVLOHCPHYS;
670
671/**
672 * AVL Core node.
673 */
674typedef struct _AVLOHCPhysNodeCore
675{
676 /** Key value. */
677 RTHCPHYS Key;
678 /** Offset to the left leaf node, relative to this field. */
679 AVLOHCPHYS pLeft;
680 /** Offset to the right leaf node, relative to this field. */
681 AVLOHCPHYS pRight;
682 /** Height of this tree: max(height(left), height(right)) + 1 */
683 unsigned char uchHeight;
684#if HC_ARCH_BITS == 64 || GC_ARCH_BITS == 64
685 unsigned char Padding[7]; /**< Alignment padding. */
686#endif
687} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
688
689/** A offset base tree with uint32_t keys. */
690typedef AVLOHCPHYS AVLOHCPHYSTREE;
691/** Pointer to a offset base tree with uint32_t keys. */
692typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
693
694/** Pointer to an internal tree pointer.
695 * In this case it's a pointer to a relative offset. */
696typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
697
698/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
699typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
700/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
701typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
702
703RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
704RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
705RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
706RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
707RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
708RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
709RTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
710
711/** @} */
712
713
714
715/** AVL tree of RTIOPORTs - using relative offsets internally.
716 * @{
717 */
718
719/**
720 * AVL 'pointer' type for the relative offset pointer scheme.
721 */
722typedef int32_t AVLOIOPORTPTR;
723
724/**
725 * AVL Core node.
726 */
727typedef struct _AVLOIOPortNodeCore
728{
729 /** Offset to the left leaf node, relative to this field. */
730 AVLOIOPORTPTR pLeft;
731 /** Offset to the right leaf node, relative to this field. */
732 AVLOIOPORTPTR pRight;
733 /** Key value. */
734 RTIOPORT Key;
735 /** Height of this tree: max(height(left), height(right)) + 1 */
736 unsigned char uchHeight;
737} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
738
739/** A offset base tree with uint32_t keys. */
740typedef AVLOIOPORTPTR AVLOIOPORTTREE;
741/** Pointer to a offset base tree with uint32_t keys. */
742typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
743
744/** Pointer to an internal tree pointer.
745 * In this case it's a pointer to a relative offset. */
746typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
747
748/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
749typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
750/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
751typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
752
753RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
754RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
755RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
756RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
757RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
758RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
759RTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
760
761/** @} */
762
763
764/** AVL tree of RTIOPORT ranges - using relative offsets internally.
765 * @{
766 */
767
768/**
769 * AVL 'pointer' type for the relative offset pointer scheme.
770 */
771typedef int32_t AVLROIOPORTPTR;
772
773/**
774 * AVL Core node.
775 */
776typedef struct _AVLROIOPortNodeCore
777{
778 /** First key value in the range (inclusive). */
779 RTIOPORT Key;
780 /** Last key value in the range (inclusive). */
781 RTIOPORT KeyLast;
782 /** Offset to the left leaf node, relative to this field. */
783 AVLROIOPORTPTR pLeft;
784 /** Offset to the right leaf node, relative to this field. */
785 AVLROIOPORTPTR pRight;
786 /** Height of this tree: max(height(left), height(right)) + 1 */
787 unsigned char uchHeight;
788} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
789
790/** A offset base tree with uint32_t keys. */
791typedef AVLROIOPORTPTR AVLROIOPORTTREE;
792/** Pointer to a offset base tree with uint32_t keys. */
793typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
794
795/** Pointer to an internal tree pointer.
796 * In this case it's a pointer to a relative offset. */
797typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
798
799/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
800typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
801/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
802typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
803
804RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
805RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
806RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
807RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
808RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
809RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
810RTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
811
812/** @} */
813
814
815/** AVL tree of RTHCPHYSes.
816 * @{
817 */
818
819/**
820 * AVL 'pointer' type for the relative offset pointer scheme.
821 */
822typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
823
824/**
825 * AVL Core node.
826 */
827typedef struct _AVLHCPhysNodeCore
828{
829 /** Offset to the left leaf node, relative to this field. */
830 AVLHCPHYSPTR pLeft;
831 /** Offset to the right leaf node, relative to this field. */
832 AVLHCPHYSPTR pRight;
833 /** Key value. */
834 RTHCPHYS Key;
835 /** Height of this tree: max(height(left), height(right)) + 1 */
836 unsigned char uchHeight;
837} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
838
839/** A offset base tree with RTHCPHYS keys. */
840typedef AVLHCPHYSPTR AVLHCPHYSTREE;
841/** Pointer to a offset base tree with RTHCPHYS keys. */
842typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
843
844/** Pointer to an internal tree pointer.
845 * In this case it's a pointer to a relative offset. */
846typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
847
848/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
849typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
850/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
851typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
852
853RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
854RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
855RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
856RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
857RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
858RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
859RTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
860
861/** @} */
862
863
864/** @} */
865
866__END_DECLS
867
868#endif
869
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