VirtualBox

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

Last change on this file since 4672 was 4071, checked in by vboxsync, 17 years ago

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