VirtualBox

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

Last change on this file since 103224 was 98103, checked in by vboxsync, 21 months ago

Copyright year updates by scm.

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