VirtualBox

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

Last change on this file since 11015 was 9387, checked in by vboxsync, 17 years ago

64-bit GC alignment fixes
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 32.7 KB
Line 
1/** @file
2 * IPRT - AVL Trees.
3 */
4
5/*
6 * Copyright (C) 1999-2003 knut st. osmundsen <[email protected]>
7 *
8 * This file is part of VirtualBox Open Source Edition (OSE), as
9 * available from http://www.virtualbox.org. This file is free software;
10 * you can redistribute it and/or modify it under the terms of the GNU
11 * General Public License (GPL) as published by the Free Software
12 * Foundation, in version 2 as it comes in the "COPYING" file of the
13 * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
14 * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
15 *
16 * The contents of this file may alternatively be used under the terms
17 * of the Common Development and Distribution License Version 1.0
18 * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
19 * VirtualBox OSE distribution, in which case the provisions of the
20 * CDDL are applicable instead of those of the GPL.
21 *
22 * You may elect to license modified versions of this file under the
23 * terms and conditions of either the GPL or the CDDL or both.
24 *
25 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
26 * Clara, CA 95054 USA or visit http://www.sun.com if you need
27 * additional information or have any questions.
28 */
29
30#ifndef ___iprt_avl_h
31#define ___iprt_avl_h
32
33#include <iprt/cdefs.h>
34#include <iprt/types.h>
35
36__BEGIN_DECLS
37
38/** @defgroup grp_rt_avl RTAvl - AVL Trees
39 * @ingroup grp_rt
40 * @{
41 */
42
43
44/** AVL tree of void pointers.
45 * @{
46 */
47
48/**
49 * AVL key type
50 */
51typedef void * AVLPVKEY;
52
53/**
54 * AVL Core node.
55 */
56typedef struct _AVLPVNodeCore
57{
58 AVLPVKEY Key; /** Key value. */
59 struct _AVLPVNodeCore *pLeft; /** Pointer to left leaf node. */
60 struct _AVLPVNodeCore *pRight; /** Pointer to right leaf node. */
61 unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
62} AVLPVNODECORE, *PAVLPVNODECORE, **PPAVLPVNODECORE;
63
64/** A tree with void pointer keys. */
65typedef PAVLPVNODECORE AVLPVTREE;
66/** Pointer to a tree with void pointer keys. */
67typedef PPAVLPVNODECORE PAVLPVTREE;
68
69/** Callback function for AVLPVDoWithAll(). */
70typedef DECLCALLBACK(int) AVLPVCALLBACK(PAVLPVNODECORE, void *);
71/** Pointer to callback function for AVLPVDoWithAll(). */
72typedef AVLPVCALLBACK *PAVLPVCALLBACK;
73
74/*
75 * Functions.
76 */
77RTDECL(bool) RTAvlPVInsert(PAVLPVTREE ppTree, PAVLPVNODECORE pNode);
78RTDECL(PAVLPVNODECORE) RTAvlPVRemove(PAVLPVTREE ppTree, AVLPVKEY Key);
79RTDECL(PAVLPVNODECORE) RTAvlPVGet(PAVLPVTREE ppTree, AVLPVKEY Key);
80RTDECL(PAVLPVNODECORE) RTAvlPVGetBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
81RTDECL(PAVLPVNODECORE) RTAvlPVRemoveBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
82RTDECL(int) RTAvlPVDoWithAll(PAVLPVTREE ppTree, int fFromLeft, PAVLPVCALLBACK pfnCallBack, void *pvParam);
83RTDECL(int) RTAvlPVDestroy(PAVLPVTREE ppTree, PAVLPVCALLBACK pfnCallBack, void *pvParam);
84
85/** @} */
86
87
88/** AVL tree of unsigned long.
89 * @{
90 */
91
92/**
93 * AVL key type
94 */
95typedef unsigned long AVLULKEY;
96
97/**
98 * AVL Core node.
99 */
100typedef struct _AVLULNodeCore
101{
102 AVLULKEY Key; /** Key value. */
103 struct _AVLULNodeCore *pLeft; /** Pointer to left leaf node. */
104 struct _AVLULNodeCore *pRight; /** Pointer to right leaf node. */
105 unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
106} AVLULNODECORE, *PAVLULNODECORE, **PPAVLULNODECORE;
107
108
109/** Callback function for AVLULDoWithAll(). */
110typedef DECLCALLBACK(int) AVLULCALLBACK(PAVLULNODECORE, void*);
111/** Pointer to callback function for AVLULDoWithAll(). */
112typedef AVLULCALLBACK *PAVLULCALLBACK;
113
114
115/*
116 * Functions.
117 */
118RTDECL(bool) RTAvlULInsert(PPAVLULNODECORE ppTree, PAVLULNODECORE pNode);
119RTDECL(PAVLULNODECORE) RTAvlULRemove(PPAVLULNODECORE ppTree, AVLULKEY Key);
120RTDECL(PAVLULNODECORE) RTAvlULGet(PPAVLULNODECORE ppTree, AVLULKEY Key);
121RTDECL(PAVLULNODECORE) RTAvlULGetBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
122RTDECL(PAVLULNODECORE) RTAvlULRemoveBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
123RTDECL(int) RTAvlULDoWithAll(PPAVLULNODECORE ppTree, int fFromLeft, PAVLULCALLBACK pfnCallBack, void *pvParam);
124
125/** @} */
126
127
128
129/** AVL tree of uint32_t
130 * @{
131 */
132
133/** AVL key type. */
134typedef uint32_t AVLU32KEY;
135
136/** AVL Core node. */
137typedef struct _AVLU32NodeCore
138{
139 AVLU32KEY Key; /**< Key value. */
140 struct _AVLU32NodeCore *pLeft; /**< Pointer to left leaf node. */
141 struct _AVLU32NodeCore *pRight; /**< Pointer to right leaf node. */
142 unsigned char uchHeight; /**< Height of this tree: max(height(left), height(right)) + 1 */
143} AVLU32NODECORE, *PAVLU32NODECORE, **PPAVLU32NODECORE;
144
145/** Callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
146typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
147/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
148typedef AVLU32CALLBACK *PAVLU32CALLBACK;
149
150
151/*
152 * Functions.
153 */
154RTDECL(bool) RTAvlU32Insert(PPAVLU32NODECORE ppTree, PAVLU32NODECORE pNode);
155RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PPAVLU32NODECORE ppTree, AVLU32KEY Key);
156RTDECL(PAVLU32NODECORE) RTAvlU32Get(PPAVLU32NODECORE ppTree, AVLU32KEY Key);
157RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PPAVLU32NODECORE ppTree, AVLU32KEY Key, bool fAbove);
158RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PPAVLU32NODECORE ppTree, AVLU32KEY Key, bool fAbove);
159RTDECL(int) RTAvlU32DoWithAll(PPAVLU32NODECORE ppTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
160RTDECL(int) RTAvlU32Destroy(PPAVLU32NODECORE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
161
162/** @} */
163
164/**
165 * AVL uint32_t type for the relative offset pointer scheme.
166 */
167typedef int32_t AVLOU32;
168
169typedef uint32_t AVLOU32KEY;
170
171/**
172 * AVL Core node.
173 */
174typedef struct _AVLOU32NodeCore
175{
176 /** Key value. */
177 AVLOU32KEY Key;
178 /** Offset to the left leaf node, relative to this field. */
179 AVLOU32 pLeft;
180 /** Offset to the right leaf node, relative to this field. */
181 AVLOU32 pRight;
182 /** Height of this tree: max(height(left), height(right)) + 1 */
183 unsigned char uchHeight;
184} AVLOU32NODECORE, *PAVLOU32NODECORE;
185
186/** A offset base tree with uint32_t keys. */
187typedef AVLOU32 AVLOU32TREE;
188/** Pointer to a offset base tree with uint32_t keys. */
189typedef AVLOU32TREE *PAVLOU32TREE;
190
191/** Pointer to an internal tree pointer.
192 * In this case it's a pointer to a relative offset. */
193typedef AVLOU32TREE *PPAVLOU32NODECORE;
194
195/** Callback function for RTAvloU32DoWithAll(). */
196typedef DECLCALLBACK(int) AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
197/** Pointer to callback function for RTAvloU32DoWithAll(). */
198typedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
199
200RTDECL(bool) RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
201RTDECL(PAVLOU32NODECORE) RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
202RTDECL(PAVLOU32NODECORE) RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
203RTDECL(int) RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
204RTDECL(PAVLOU32NODECORE) RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
205RTDECL(PAVLOU32NODECORE) RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
206RTDECL(int) RTAvloU32Destroy(PAVLOU32TREE pTree, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
207
208/** @} */
209
210
211/** AVL tree of uint32_t, list duplicates.
212 * @{
213 */
214
215/** AVL key type. */
216typedef uint32_t AVLLU32KEY;
217
218/** AVL Core node. */
219typedef struct _AVLLU32NodeCore
220{
221 AVLLU32KEY Key; /**< Key value. */
222 unsigned char uchHeight; /**< Height of this tree: max(height(left), height(right)) + 1 */
223 struct _AVLLU32NodeCore *pLeft; /**< Pointer to left leaf node. */
224 struct _AVLLU32NodeCore *pRight; /**< Pointer to right leaf node. */
225 struct _AVLLU32NodeCore *pList; /**< Pointer to next node with the same key. */
226} AVLLU32NODECORE, *PAVLLU32NODECORE, **PPAVLLU32NODECORE;
227
228/** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
229typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
230/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
231typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
232
233
234/*
235 * Functions.
236 */
237RTDECL(bool) RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
238RTDECL(PAVLLU32NODECORE) RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
239RTDECL(PAVLLU32NODECORE) RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
240RTDECL(PAVLLU32NODECORE) RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
241RTDECL(PAVLLU32NODECORE) RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
242RTDECL(int) RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
243RTDECL(int) RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
244
245/** @} */
246
247
248
249/** AVL tree of RTGCPHYSes - using relative offsets internally.
250 * @{
251 */
252
253/**
254 * AVL 'pointer' type for the relative offset pointer scheme.
255 */
256typedef int32_t AVLOGCPHYS;
257
258/**
259 * AVL Core node.
260 */
261typedef struct _AVLOGCPhysNodeCore
262{
263 /** Key value. */
264 RTGCPHYS Key;
265 /** Offset to the left leaf node, relative to this field. */
266 AVLOGCPHYS pLeft;
267 /** Offset to the right leaf node, relative to this field. */
268 AVLOGCPHYS pRight;
269 /** Height of this tree: max(height(left), height(right)) + 1 */
270 unsigned char uchHeight;
271 /** Padding */
272 unsigned char Padding[7];
273} AVLOGCPHYSNODECORE, *PAVLOGCPHYSNODECORE;
274
275/** A offset base tree with uint32_t keys. */
276typedef AVLOGCPHYS AVLOGCPHYSTREE;
277/** Pointer to a offset base tree with uint32_t keys. */
278typedef AVLOGCPHYSTREE *PAVLOGCPHYSTREE;
279
280/** Pointer to an internal tree pointer.
281 * In this case it's a pointer to a relative offset. */
282typedef AVLOGCPHYSTREE *PPAVLOGCPHYSNODECORE;
283
284/** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
285typedef DECLCALLBACK(int) AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
286/** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
287typedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
288
289RTDECL(bool) RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
290RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
291RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
292RTDECL(int) RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
293RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
294RTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
295RTDECL(int) RTAvloGCPhysDestroy(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
296
297/** @} */
298
299
300/** AVL tree of RTGCPHYS ranges - using relative offsets internally.
301 * @{
302 */
303
304/**
305 * AVL 'pointer' type for the relative offset pointer scheme.
306 */
307typedef int32_t AVLROGCPHYS;
308
309/**
310 * AVL Core node.
311 */
312typedef struct _AVLROGCPhysNodeCore
313{
314 /** First key value in the range (inclusive). */
315 RTGCPHYS Key;
316 /** Last key value in the range (inclusive). */
317 RTGCPHYS KeyLast;
318 /** Offset to the left leaf node, relative to this field. */
319 AVLROGCPHYS pLeft;
320 /** Offset to the right leaf node, relative to this field. */
321 AVLROGCPHYS pRight;
322 /** Height of this tree: max(height(left), height(right)) + 1 */
323 unsigned char uchHeight;
324 /** Padding */
325 unsigned char Padding[7];
326} AVLROGCPHYSNODECORE, *PAVLROGCPHYSNODECORE;
327
328/** A offset base tree with uint32_t keys. */
329typedef AVLROGCPHYS AVLROGCPHYSTREE;
330/** Pointer to a offset base tree with uint32_t keys. */
331typedef AVLROGCPHYSTREE *PAVLROGCPHYSTREE;
332
333/** Pointer to an internal tree pointer.
334 * In this case it's a pointer to a relative offset. */
335typedef AVLROGCPHYSTREE *PPAVLROGCPHYSNODECORE;
336
337/** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
338typedef DECLCALLBACK(int) AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
339/** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
340typedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
341
342RTDECL(bool) RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
343RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
344RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
345RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
346RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
347RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
348RTDECL(int) RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
349RTDECL(int) RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
350RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
351RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
352RTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
353
354/** @} */
355
356
357/** AVL tree of RTGCPTRs.
358 * @{
359 */
360
361/**
362 * AVL Core node.
363 */
364typedef struct _AVLGCPtrNodeCore
365{
366 /** Key value. */
367 RTGCPTR Key;
368 /** Pointer to the left node. */
369 struct _AVLGCPtrNodeCore *pLeft;
370 /** Pointer to the right node. */
371 struct _AVLGCPtrNodeCore *pRight;
372 /** Height of this tree: max(height(left), height(right)) + 1 */
373 unsigned char uchHeight;
374} AVLGCPTRNODECORE, *PAVLGCPTRNODECORE, **PPAVLGCPTRNODECORE;
375
376/** A tree of RTGCPTR keys. */
377typedef PAVLGCPTRNODECORE AVLGCPTRTREE;
378/** Pointer to a tree of RTGCPTR keys. */
379typedef PPAVLGCPTRNODECORE PAVLGCPTRTREE;
380
381/** Callback function for RTAvlGCPtrDoWithAll(). */
382typedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
383/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
384typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
385
386RTDECL(bool) RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
387RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
388RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
389RTDECL(int) RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
390RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
391RTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
392RTDECL(int) RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
393
394/** @} */
395
396
397/** AVL tree of RTGCPTRs - using relative offsets internally.
398 * @{
399 */
400
401/**
402 * AVL 'pointer' type for the relative offset pointer scheme.
403 */
404typedef int32_t AVLOGCPTR;
405
406/**
407 * AVL Core node.
408 */
409typedef struct _AVLOGCPtrNodeCore
410{
411 /** Key value. */
412 RTGCPTR Key;
413 /** Offset to the left leaf node, relative to this field. */
414 AVLOGCPTR pLeft;
415 /** Offset to the right leaf node, relative to this field. */
416 AVLOGCPTR pRight;
417 /** Height of this tree: max(height(left), height(right)) + 1 */
418 unsigned char uchHeight;
419 unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 3];
420} AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
421
422/** A offset base tree with uint32_t keys. */
423typedef AVLOGCPTR AVLOGCPTRTREE;
424/** Pointer to a offset base tree with uint32_t keys. */
425typedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
426
427/** Pointer to an internal tree pointer.
428 * In this case it's a pointer to a relative offset. */
429typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
430
431/** Callback function for RTAvloGCPtrDoWithAll(). */
432typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
433/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
434typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
435
436RTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
437RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
438RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
439RTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
440RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
441RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
442RTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
443
444/** @} */
445
446
447/** AVL tree of RTGCPTR ranges.
448 * @{
449 */
450
451/**
452 * AVL Core node.
453 */
454typedef struct _AVLRGCPtrNodeCore
455{
456 /** First key value in the range (inclusive). */
457 RTGCPTR Key;
458 /** Last key value in the range (inclusive). */
459 RTGCPTR KeyLast;
460 /** Offset to the left leaf node, relative to this field. */
461 struct _AVLRGCPtrNodeCore *pLeft;
462 /** Offset to the right leaf node, relative to this field. */
463 struct _AVLRGCPtrNodeCore *pRight;
464 /** Height of this tree: max(height(left), height(right)) + 1 */
465 unsigned char uchHeight;
466} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
467
468/** A offset base tree with RTGCPTR keys. */
469typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
470/** Pointer to a offset base tree with RTGCPTR keys. */
471typedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
472
473/** Pointer to an internal tree pointer.
474 * In this case it's a pointer to a relative offset. */
475typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
476
477/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
478typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
479/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
480typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
481
482RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
483RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
484RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
485RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
486RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
487RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
488RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
489RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
490RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
491RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
492RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode);
493
494/** @} */
495
496
497/** AVL tree of RTGCPTR ranges - using relative offsets internally.
498 * @{
499 */
500
501/**
502 * AVL 'pointer' type for the relative offset pointer scheme.
503 */
504typedef int32_t AVLROGCPTR;
505
506/**
507 * AVL Core node.
508 */
509typedef struct _AVLROGCPtrNodeCore
510{
511 /** First key value in the range (inclusive). */
512 RTGCPTR Key;
513 /** Last key value in the range (inclusive). */
514 RTGCPTR KeyLast;
515 /** Offset to the left leaf node, relative to this field. */
516 AVLROGCPTR pLeft;
517 /** Offset to the right leaf node, relative to this field. */
518 AVLROGCPTR pRight;
519 /** Height of this tree: max(height(left), height(right)) + 1 */
520 unsigned char uchHeight;
521 unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 3];
522} AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
523
524/** A offset base tree with uint32_t keys. */
525typedef AVLROGCPTR AVLROGCPTRTREE;
526/** Pointer to a offset base tree with uint32_t keys. */
527typedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
528
529/** Pointer to an internal tree pointer.
530 * In this case it's a pointer to a relative offset. */
531typedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
532
533/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
534typedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
535/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
536typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
537
538RTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
539RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
540RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
541RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
542RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
543RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
544RTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
545RTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
546RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
547RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
548RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
549
550/** @} */
551
552
553/** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
554 * @{
555 */
556
557/**
558 * AVL 'pointer' type for the relative offset pointer scheme.
559 */
560typedef int32_t AVLROOGCPTR;
561
562/**
563 * AVL Core node.
564 */
565typedef struct _AVLROOGCPtrNodeCore
566{
567 /** First key value in the range (inclusive). */
568 RTGCPTR Key;
569 /** Last key value in the range (inclusive). */
570 RTGCPTR KeyLast;
571 /** Offset to the left leaf node, relative to this field. */
572 AVLROOGCPTR pLeft;
573 /** Offset to the right leaf node, relative to this field. */
574 AVLROOGCPTR pRight;
575 /** Pointer to the list of string with the same key. Don't touch. */
576 AVLROOGCPTR pList;
577 /** Height of this tree: max(height(left), height(right)) + 1 */
578 unsigned char uchHeight;
579} AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
580
581/** A offset base tree with uint32_t keys. */
582typedef AVLROOGCPTR AVLROOGCPTRTREE;
583/** Pointer to a offset base tree with uint32_t keys. */
584typedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
585
586/** Pointer to an internal tree pointer.
587 * In this case it's a pointer to a relative offset. */
588typedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
589
590/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
591typedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
592/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
593typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
594
595RTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
596RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
597RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
598RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
599RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
600RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
601RTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
602RTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
603RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
604RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
605RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
606RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
607
608/** @} */
609
610
611/** AVL tree of RTHCPHYSes - using relative offsets internally.
612 * @{
613 */
614
615/**
616 * AVL 'pointer' type for the relative offset pointer scheme.
617 */
618typedef int32_t AVLOHCPHYS;
619
620/**
621 * AVL Core node.
622 */
623typedef struct _AVLOHCPhysNodeCore
624{
625 /** Key value. */
626 RTHCPHYS Key;
627 /** Offset to the left leaf node, relative to this field. */
628 AVLOHCPHYS pLeft;
629 /** Offset to the right leaf node, relative to this field. */
630 AVLOHCPHYS pRight;
631 /** Height of this tree: max(height(left), height(right)) + 1 */
632 unsigned char uchHeight;
633#if HC_ARCH_BITS == 64 || GC_ARCH_BITS == 64
634 unsigned char Padding[7]; /**< Alignment padding. */
635#endif
636} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
637
638/** A offset base tree with uint32_t keys. */
639typedef AVLOHCPHYS AVLOHCPHYSTREE;
640/** Pointer to a offset base tree with uint32_t keys. */
641typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
642
643/** Pointer to an internal tree pointer.
644 * In this case it's a pointer to a relative offset. */
645typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
646
647/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
648typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
649/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
650typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
651
652RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
653RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
654RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
655RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
656RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
657RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
658RTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
659
660/** @} */
661
662
663
664/** AVL tree of RTIOPORTs - using relative offsets internally.
665 * @{
666 */
667
668/**
669 * AVL 'pointer' type for the relative offset pointer scheme.
670 */
671typedef int32_t AVLOIOPORTPTR;
672
673/**
674 * AVL Core node.
675 */
676typedef struct _AVLOIOPortNodeCore
677{
678 /** Offset to the left leaf node, relative to this field. */
679 AVLOIOPORTPTR pLeft;
680 /** Offset to the right leaf node, relative to this field. */
681 AVLOIOPORTPTR pRight;
682 /** Key value. */
683 RTIOPORT Key;
684 /** Height of this tree: max(height(left), height(right)) + 1 */
685 unsigned char uchHeight;
686} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
687
688/** A offset base tree with uint32_t keys. */
689typedef AVLOIOPORTPTR AVLOIOPORTTREE;
690/** Pointer to a offset base tree with uint32_t keys. */
691typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
692
693/** Pointer to an internal tree pointer.
694 * In this case it's a pointer to a relative offset. */
695typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
696
697/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
698typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
699/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
700typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
701
702RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
703RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
704RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
705RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
706RTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
707
708/** @} */
709
710
711/** AVL tree of RTIOPORT ranges - using relative offsets internally.
712 * @{
713 */
714
715/**
716 * AVL 'pointer' type for the relative offset pointer scheme.
717 */
718typedef int32_t AVLROIOPORTPTR;
719
720/**
721 * AVL Core node.
722 */
723typedef struct _AVLROIOPortNodeCore
724{
725 /** First key value in the range (inclusive). */
726 RTIOPORT Key;
727 /** Last key value in the range (inclusive). */
728 RTIOPORT KeyLast;
729 /** Offset to the left leaf node, relative to this field. */
730 AVLROIOPORTPTR pLeft;
731 /** Offset to the right leaf node, relative to this field. */
732 AVLROIOPORTPTR pRight;
733 /** Height of this tree: max(height(left), height(right)) + 1 */
734 unsigned char uchHeight;
735} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
736
737/** A offset base tree with uint32_t keys. */
738typedef AVLROIOPORTPTR AVLROIOPORTTREE;
739/** Pointer to a offset base tree with uint32_t keys. */
740typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
741
742/** Pointer to an internal tree pointer.
743 * In this case it's a pointer to a relative offset. */
744typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
745
746/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
747typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
748/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
749typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
750
751RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
752RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
753RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
754RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
755RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
756RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
757RTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
758
759/** @} */
760
761
762/** AVL tree of RTHCPHYSes.
763 * @{
764 */
765
766/**
767 * AVL 'pointer' type for the relative offset pointer scheme.
768 */
769typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
770
771/**
772 * AVL Core node.
773 */
774typedef struct _AVLHCPhysNodeCore
775{
776 /** Offset to the left leaf node, relative to this field. */
777 AVLHCPHYSPTR pLeft;
778 /** Offset to the right leaf node, relative to this field. */
779 AVLHCPHYSPTR pRight;
780 /** Key value. */
781 RTHCPHYS Key;
782 /** Height of this tree: max(height(left), height(right)) + 1 */
783 unsigned char uchHeight;
784} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
785
786/** A offset base tree with RTHCPHYS keys. */
787typedef AVLHCPHYSPTR AVLHCPHYSTREE;
788/** Pointer to a offset base tree with RTHCPHYS keys. */
789typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
790
791/** Pointer to an internal tree pointer.
792 * In this case it's a pointer to a relative offset. */
793typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
794
795/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
796typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
797/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
798typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
799
800RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
801RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
802RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
803RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
804RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
805RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
806RTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
807
808/** @} */
809
810
811/** @} */
812
813__END_DECLS
814
815#endif
816
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