VirtualBox

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

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

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

© 2023 Oracle
Contact – Privacy policy – Terms of Use