VirtualBox

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

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

More updates for 64 bits guest pointers. Introduced AVLOU32TREE.
  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
File size: 32.6 KB
Line 
1/** @file
2 * IPRT - AVL Trees.
3 */
4
5/*
6 * Copyright (C) 1999-2003 knut st. osmundsen <bird-src-spam@anduin.net>
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} AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
420
421/** A offset base tree with uint32_t keys. */
422typedef AVLOGCPTR AVLOGCPTRTREE;
423/** Pointer to a offset base tree with uint32_t keys. */
424typedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
425
426/** Pointer to an internal tree pointer.
427 * In this case it's a pointer to a relative offset. */
428typedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
429
430/** Callback function for RTAvloGCPtrDoWithAll(). */
431typedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
432/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
433typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
434
435RTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
436RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
437RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
438RTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
439RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
440RTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
441RTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
442
443/** @} */
444
445
446/** AVL tree of RTGCPTR ranges.
447 * @{
448 */
449
450/**
451 * AVL Core node.
452 */
453typedef struct _AVLRGCPtrNodeCore
454{
455 /** First key value in the range (inclusive). */
456 RTGCPTR Key;
457 /** Last key value in the range (inclusive). */
458 RTGCPTR KeyLast;
459 /** Offset to the left leaf node, relative to this field. */
460 struct _AVLRGCPtrNodeCore *pLeft;
461 /** Offset to the right leaf node, relative to this field. */
462 struct _AVLRGCPtrNodeCore *pRight;
463 /** Height of this tree: max(height(left), height(right)) + 1 */
464 unsigned char uchHeight;
465} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
466
467/** A offset base tree with RTGCPTR keys. */
468typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
469/** Pointer to a offset base tree with RTGCPTR keys. */
470typedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
471
472/** Pointer to an internal tree pointer.
473 * In this case it's a pointer to a relative offset. */
474typedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
475
476/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
477typedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
478/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
479typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
480
481RTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
482RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
483RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
484RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
485RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
486RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
487RTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
488RTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
489RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
490RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
491RTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode);
492
493/** @} */
494
495
496/** AVL tree of RTGCPTR ranges - using relative offsets internally.
497 * @{
498 */
499
500/**
501 * AVL 'pointer' type for the relative offset pointer scheme.
502 */
503typedef int32_t AVLROGCPTR;
504
505/**
506 * AVL Core node.
507 */
508typedef struct _AVLROGCPtrNodeCore
509{
510 /** First key value in the range (inclusive). */
511 RTGCPTR Key;
512 /** Last key value in the range (inclusive). */
513 RTGCPTR KeyLast;
514 /** Offset to the left leaf node, relative to this field. */
515 AVLROGCPTR pLeft;
516 /** Offset to the right leaf node, relative to this field. */
517 AVLROGCPTR pRight;
518 /** Height of this tree: max(height(left), height(right)) + 1 */
519 unsigned char uchHeight;
520} AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
521
522/** A offset base tree with uint32_t keys. */
523typedef AVLROGCPTR AVLROGCPTRTREE;
524/** Pointer to a offset base tree with uint32_t keys. */
525typedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
526
527/** Pointer to an internal tree pointer.
528 * In this case it's a pointer to a relative offset. */
529typedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
530
531/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
532typedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
533/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
534typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
535
536RTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
537RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
538RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
539RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
540RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
541RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
542RTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
543RTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
544RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
545RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
546RTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
547
548/** @} */
549
550
551/** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
552 * @{
553 */
554
555/**
556 * AVL 'pointer' type for the relative offset pointer scheme.
557 */
558typedef int32_t AVLROOGCPTR;
559
560/**
561 * AVL Core node.
562 */
563typedef struct _AVLROOGCPtrNodeCore
564{
565 /** First key value in the range (inclusive). */
566 RTGCPTR Key;
567 /** Last key value in the range (inclusive). */
568 RTGCPTR KeyLast;
569 /** Offset to the left leaf node, relative to this field. */
570 AVLROOGCPTR pLeft;
571 /** Offset to the right leaf node, relative to this field. */
572 AVLROOGCPTR pRight;
573 /** Pointer to the list of string with the same key. Don't touch. */
574 AVLROOGCPTR pList;
575 /** Height of this tree: max(height(left), height(right)) + 1 */
576 unsigned char uchHeight;
577} AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
578
579/** A offset base tree with uint32_t keys. */
580typedef AVLROOGCPTR AVLROOGCPTRTREE;
581/** Pointer to a offset base tree with uint32_t keys. */
582typedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
583
584/** Pointer to an internal tree pointer.
585 * In this case it's a pointer to a relative offset. */
586typedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
587
588/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
589typedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
590/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
591typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
592
593RTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
594RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
595RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
596RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
597RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
598RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
599RTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
600RTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
601RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
602RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
603RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
604RTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
605
606/** @} */
607
608
609/** AVL tree of RTHCPHYSes - using relative offsets internally.
610 * @{
611 */
612
613/**
614 * AVL 'pointer' type for the relative offset pointer scheme.
615 */
616typedef int32_t AVLOHCPHYS;
617
618/**
619 * AVL Core node.
620 */
621typedef struct _AVLOHCPhysNodeCore
622{
623 /** Key value. */
624 RTHCPHYS Key;
625 /** Offset to the left leaf node, relative to this field. */
626 AVLOHCPHYS pLeft;
627 /** Offset to the right leaf node, relative to this field. */
628 AVLOHCPHYS pRight;
629 /** Height of this tree: max(height(left), height(right)) + 1 */
630 unsigned char uchHeight;
631#if HC_ARCH_BITS == 64 || GC_ARCH_BITS == 64
632 unsigned char Padding[7]; /**< Alignment padding. */
633#endif
634} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
635
636/** A offset base tree with uint32_t keys. */
637typedef AVLOHCPHYS AVLOHCPHYSTREE;
638/** Pointer to a offset base tree with uint32_t keys. */
639typedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
640
641/** Pointer to an internal tree pointer.
642 * In this case it's a pointer to a relative offset. */
643typedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
644
645/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
646typedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
647/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
648typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
649
650RTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
651RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
652RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
653RTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
654RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
655RTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
656RTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
657
658/** @} */
659
660
661
662/** AVL tree of RTIOPORTs - using relative offsets internally.
663 * @{
664 */
665
666/**
667 * AVL 'pointer' type for the relative offset pointer scheme.
668 */
669typedef int32_t AVLOIOPORTPTR;
670
671/**
672 * AVL Core node.
673 */
674typedef struct _AVLOIOPortNodeCore
675{
676 /** Offset to the left leaf node, relative to this field. */
677 AVLOIOPORTPTR pLeft;
678 /** Offset to the right leaf node, relative to this field. */
679 AVLOIOPORTPTR pRight;
680 /** Key value. */
681 RTIOPORT Key;
682 /** Height of this tree: max(height(left), height(right)) + 1 */
683 unsigned char uchHeight;
684} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
685
686/** A offset base tree with uint32_t keys. */
687typedef AVLOIOPORTPTR AVLOIOPORTTREE;
688/** Pointer to a offset base tree with uint32_t keys. */
689typedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
690
691/** Pointer to an internal tree pointer.
692 * In this case it's a pointer to a relative offset. */
693typedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
694
695/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
696typedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
697/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
698typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
699
700RTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
701RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
702RTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
703RTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
704RTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
705
706/** @} */
707
708
709/** AVL tree of RTIOPORT ranges - using relative offsets internally.
710 * @{
711 */
712
713/**
714 * AVL 'pointer' type for the relative offset pointer scheme.
715 */
716typedef int32_t AVLROIOPORTPTR;
717
718/**
719 * AVL Core node.
720 */
721typedef struct _AVLROIOPortNodeCore
722{
723 /** First key value in the range (inclusive). */
724 RTIOPORT Key;
725 /** Last key value in the range (inclusive). */
726 RTIOPORT KeyLast;
727 /** Offset to the left leaf node, relative to this field. */
728 AVLROIOPORTPTR pLeft;
729 /** Offset to the right leaf node, relative to this field. */
730 AVLROIOPORTPTR pRight;
731 /** Height of this tree: max(height(left), height(right)) + 1 */
732 unsigned char uchHeight;
733} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
734
735/** A offset base tree with uint32_t keys. */
736typedef AVLROIOPORTPTR AVLROIOPORTTREE;
737/** Pointer to a offset base tree with uint32_t keys. */
738typedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
739
740/** Pointer to an internal tree pointer.
741 * In this case it's a pointer to a relative offset. */
742typedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
743
744/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
745typedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
746/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
747typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
748
749RTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
750RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
751RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
752RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
753RTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
754RTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
755RTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
756
757/** @} */
758
759
760/** AVL tree of RTHCPHYSes.
761 * @{
762 */
763
764/**
765 * AVL 'pointer' type for the relative offset pointer scheme.
766 */
767typedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
768
769/**
770 * AVL Core node.
771 */
772typedef struct _AVLHCPhysNodeCore
773{
774 /** Offset to the left leaf node, relative to this field. */
775 AVLHCPHYSPTR pLeft;
776 /** Offset to the right leaf node, relative to this field. */
777 AVLHCPHYSPTR pRight;
778 /** Key value. */
779 RTHCPHYS Key;
780 /** Height of this tree: max(height(left), height(right)) + 1 */
781 unsigned char uchHeight;
782} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
783
784/** A offset base tree with RTHCPHYS keys. */
785typedef AVLHCPHYSPTR AVLHCPHYSTREE;
786/** Pointer to a offset base tree with RTHCPHYS keys. */
787typedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
788
789/** Pointer to an internal tree pointer.
790 * In this case it's a pointer to a relative offset. */
791typedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
792
793/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
794typedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
795/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
796typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
797
798RTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
799RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
800RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
801RTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
802RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
803RTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
804RTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
805
806/** @} */
807
808
809/** @} */
810
811__END_DECLS
812
813#endif
814
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