VirtualBox

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

Last change on this file since 34575 was 34218, checked in by vboxsync, 14 years ago

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