VirtualBox

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

Last change on this file since 2889 was 692, checked in by vboxsync, 18 years ago

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