ubuntu/vbox/include/iprt/avl.h

   1 /** @file
   2  * IPRT - AVL Trees.
   3  */
   4
   5 /*
   6  * Copyright (C) 2006-2017 Oracle Corporation
   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
  26 #ifndef ___iprt_avl_h
  27 #define ___iprt_avl_h
  28
  29 #include <iprt/cdefs.h>
  30 #include <iprt/types.h>
  31
  32 RT_C_DECLS_BEGIN
  33
  34 /** @defgroup grp_rt_avl    RTAvl - AVL Trees
  35  * @ingroup grp_rt
  36  * @{
  37  */
  38
  39
  40 /** AVL tree of void pointers.
  41  * @{
  42  */
  43
  44 /**
  45  * AVL key type
  46  */
  47 typedef void *  AVLPVKEY;
  48
  49 /**
  50  * AVL Core node.
  51  */
  52 typedef struct _AVLPVNodeCore
  53 {
  54     AVLPVKEY                Key;        /** Key value. */
  55     struct _AVLPVNodeCore  *pLeft;      /** Pointer to left leaf node. */
  56     struct _AVLPVNodeCore  *pRight;     /** Pointer to right leaf node. */
  57     unsigned char           uchHeight;  /** Height of this tree: max(height(left), height(right)) + 1 */
  58 } AVLPVNODECORE, *PAVLPVNODECORE, **PPAVLPVNODECORE;
  59
  60 /** A tree with void pointer keys. */
  61 typedef PAVLPVNODECORE     AVLPVTREE;
  62 /** Pointer to a tree with void pointer keys. */
  63 typedef PPAVLPVNODECORE    PAVLPVTREE;
  64
  65 /** Callback function for AVLPVDoWithAll().
  66  *  @returns IPRT status codes. */
  67 typedef DECLCALLBACK(int) AVLPVCALLBACK(PAVLPVNODECORE, void *);
  68 /** Pointer to callback function for AVLPVDoWithAll(). */
  69 typedef AVLPVCALLBACK *PAVLPVCALLBACK;
  70
  71 /*
  72  * Functions.
  73  */
  74 RTDECL(bool)            RTAvlPVInsert(PAVLPVTREE ppTree, PAVLPVNODECORE pNode);
  75 RTDECL(PAVLPVNODECORE)  RTAvlPVRemove(PAVLPVTREE ppTree, AVLPVKEY Key);
  76 RTDECL(PAVLPVNODECORE)  RTAvlPVGet(PAVLPVTREE ppTree, AVLPVKEY Key);
  77 RTDECL(PAVLPVNODECORE)  RTAvlPVGetBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
  78 RTDECL(PAVLPVNODECORE)  RTAvlPVRemoveBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
  79 RTDECL(int)             RTAvlPVDoWithAll(PAVLPVTREE ppTree, int fFromLeft, PAVLPVCALLBACK pfnCallBack, void *pvParam);
  80 RTDECL(int)             RTAvlPVDestroy(PAVLPVTREE ppTree, PAVLPVCALLBACK pfnCallBack, void *pvParam);
  81
  82 /** @} */
  83
  84
  85 /** AVL tree of unsigned long.
  86  * @{
  87  */
  88
  89 /**
  90  * AVL key type
  91  */
  92 typedef unsigned long   AVLULKEY;
  93
  94 /**
  95  * AVL Core node.
  96  */
  97 typedef struct _AVLULNodeCore
  98 {
  99     AVLULKEY                Key;        /** Key value. */
 100     struct _AVLULNodeCore  *pLeft;      /** Pointer to left leaf node. */
 101     struct _AVLULNodeCore  *pRight;     /** Pointer to right leaf node. */
 102     unsigned char           uchHeight;  /** Height of this tree: max(height(left), height(right)) + 1 */
 103 } AVLULNODECORE, *PAVLULNODECORE, **PPAVLULNODECORE;
 104
 105
 106 /** Callback function for AVLULDoWithAll().
 107  *  @returns IPRT status codes. */
 108 typedef DECLCALLBACK(int) AVLULCALLBACK(PAVLULNODECORE, void*);
 109 /** Pointer to callback function for AVLULDoWithAll(). */
 110 typedef AVLULCALLBACK *PAVLULCALLBACK;
 111
 112
 113 /*
 114  * Functions.
 115  */
 116 RTDECL(bool)            RTAvlULInsert(PPAVLULNODECORE ppTree, PAVLULNODECORE pNode);
 117 RTDECL(PAVLULNODECORE)  RTAvlULRemove(PPAVLULNODECORE ppTree, AVLULKEY Key);
 118 RTDECL(PAVLULNODECORE)  RTAvlULGet(PPAVLULNODECORE ppTree, AVLULKEY Key);
 119 RTDECL(PAVLULNODECORE)  RTAvlULGetBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
 120 RTDECL(PAVLULNODECORE)  RTAvlULRemoveBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
 121 RTDECL(int)             RTAvlULDoWithAll(PPAVLULNODECORE ppTree, int fFromLeft, PAVLULCALLBACK pfnCallBack, void *pvParam);
 122 RTDECL(int)             RTAvlULDestroy(PPAVLULNODECORE pTree, PAVLULCALLBACK pfnCallBack, void *pvParam);
 123
 124 /** @} */
 125
 126
 127
 128 /** AVL tree of void pointer ranges.
 129  * @{
 130  */
 131
 132 /**
 133  * AVL key type
 134  */
 135 typedef void *AVLRPVKEY;
 136
 137 /**
 138  * AVL Core node.
 139  */
 140 typedef struct AVLRPVNodeCore
 141 {
 142     AVLRPVKEY               Key;        /**< First key value in the range (inclusive). */
 143     AVLRPVKEY               KeyLast;    /**< Last key value in the range (inclusive). */
 144     struct AVLRPVNodeCore  *pLeft;      /**< Pointer to left leaf node. */
 145     struct AVLRPVNodeCore  *pRight;     /**< Pointer to right leaf node. */
 146     unsigned char           uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
 147 } AVLRPVNODECORE, *PAVLRPVNODECORE, **PPAVLRPVNODECORE;
 148
 149 /** A tree with void pointer keys. */
 150 typedef PAVLRPVNODECORE    AVLRPVTREE;
 151 /** Pointer to a tree with void pointer keys. */
 152 typedef PPAVLRPVNODECORE   PAVLRPVTREE;
 153
 154 /** Callback function for AVLPVDoWithAll().
 155  *  @returns IPRT status codes. */
 156 typedef DECLCALLBACK(int) AVLRPVCALLBACK(PAVLRPVNODECORE, void *);
 157 /** Pointer to callback function for AVLPVDoWithAll(). */
 158 typedef AVLRPVCALLBACK *PAVLRPVCALLBACK;
 159
 160 /*
 161  * Functions.
 162  */
 163 RTDECL(bool)            RTAvlrPVInsert(PAVLRPVTREE ppTree, PAVLRPVNODECORE pNode);
 164 RTDECL(PAVLRPVNODECORE) RTAvlrPVRemove(PAVLRPVTREE ppTree, AVLRPVKEY Key);
 165 RTDECL(PAVLRPVNODECORE) RTAvlrPVGet(PAVLRPVTREE ppTree, AVLRPVKEY Key);
 166 RTDECL(PAVLRPVNODECORE) RTAvlrPVRangeGet(PAVLRPVTREE ppTree, AVLRPVKEY Key);
 167 RTDECL(PAVLRPVNODECORE) RTAvlrPVRangeRemove(PAVLRPVTREE ppTree, AVLRPVKEY Key);
 168 RTDECL(PAVLRPVNODECORE) RTAvlrPVGetBestFit(PAVLRPVTREE ppTree, AVLRPVKEY Key, bool fAbove);
 169 RTDECL(PAVLRPVNODECORE) RTAvlrPVRemoveBestFit(PAVLRPVTREE ppTree, AVLRPVKEY Key, bool fAbove);
 170 RTDECL(int)             RTAvlrPVDoWithAll(PAVLRPVTREE ppTree, int fFromLeft, PAVLRPVCALLBACK pfnCallBack, void *pvParam);
 171 RTDECL(int)             RTAvlrPVDestroy(PAVLRPVTREE ppTree, PAVLRPVCALLBACK pfnCallBack, void *pvParam);
 172
 173 /** @} */
 174
 175
 176
 177 /** AVL tree of uint32_t
 178  * @{
 179  */
 180
 181 /** AVL key type. */
 182 typedef uint32_t    AVLU32KEY;
 183
 184 /** AVL Core node. */
 185 typedef struct _AVLU32NodeCore
 186 {
 187     AVLU32KEY               Key;        /**< Key value. */
 188     struct _AVLU32NodeCore *pLeft;      /**< Pointer to left leaf node. */
 189     struct _AVLU32NodeCore *pRight;     /**< Pointer to right leaf node. */
 190     unsigned char           uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
 191 } AVLU32NODECORE, *PAVLU32NODECORE, **PPAVLU32NODECORE;
 192
 193 /** A tree with void pointer keys. */
 194 typedef PAVLU32NODECORE     AVLU32TREE;
 195 /** Pointer to a tree with void pointer keys. */
 196 typedef PPAVLU32NODECORE    PAVLU32TREE;
 197
 198 /** Callback function for AVLU32DoWithAll() & AVLU32Destroy().
 199  *  @returns IPRT status codes. */
 200 typedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
 201 /** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
 202 typedef AVLU32CALLBACK *PAVLU32CALLBACK;
 203
 204
 205 /*
 206  * Functions.
 207  */
 208 RTDECL(bool)            RTAvlU32Insert(PAVLU32TREE pTree, PAVLU32NODECORE pNode);
 209 RTDECL(PAVLU32NODECORE) RTAvlU32Remove(PAVLU32TREE pTree, AVLU32KEY Key);
 210 RTDECL(PAVLU32NODECORE) RTAvlU32Get(PAVLU32TREE pTree, AVLU32KEY Key);
 211 RTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
 212 RTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
 213 RTDECL(int)             RTAvlU32DoWithAll(PAVLU32TREE pTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
 214 RTDECL(int)             RTAvlU32Destroy(PAVLU32TREE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
 215
 216 /** @} */
 217
 218 /**
 219  * AVL uint32_t type for the relative offset pointer scheme.
 220  */
 221 typedef int32_t     AVLOU32;
 222
 223 typedef uint32_t     AVLOU32KEY;
 224
 225 /**
 226  * AVL Core node.
 227  */
 228 typedef struct _AVLOU32NodeCore
 229 {
 230     /** Key value. */
 231     AVLOU32KEY          Key;
 232     /** Offset to the left leaf node, relative to this field. */
 233     AVLOU32             pLeft;
 234     /** Offset to the right leaf node, relative to this field. */
 235     AVLOU32             pRight;
 236     /** Height of this tree: max(height(left), height(right)) + 1 */
 237     unsigned char       uchHeight;
 238 } AVLOU32NODECORE, *PAVLOU32NODECORE;
 239
 240 /** A offset base tree with uint32_t keys. */
 241 typedef AVLOU32         AVLOU32TREE;
 242 /** Pointer to an offset base tree with uint32_t keys. */
 243 typedef AVLOU32TREE    *PAVLOU32TREE;
 244
 245 /** Pointer to an internal tree pointer.
 246  * In this case it's a pointer to a relative offset. */
 247 typedef AVLOU32TREE    *PPAVLOU32NODECORE;
 248
 249 /** Callback function for RTAvloU32DoWithAll().
 250  *  @returns IPRT status codes. */
 251 typedef DECLCALLBACK(int)   AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
 252 /** Pointer to callback function for RTAvloU32DoWithAll(). */
 253 typedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
 254
 255 RTDECL(bool)                  RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
 256 RTDECL(PAVLOU32NODECORE)      RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
 257 RTDECL(PAVLOU32NODECORE)      RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
 258 RTDECL(int)                   RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
 259 RTDECL(PAVLOU32NODECORE)      RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
 260 RTDECL(PAVLOU32NODECORE)      RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
 261 RTDECL(int)                   RTAvloU32Destroy(PAVLOU32TREE pTree, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
 262
 263 /** @} */
 264
 265
 266 /** AVL tree of uint32_t, list duplicates.
 267  * @{
 268  */
 269
 270 /** AVL key type. */
 271 typedef uint32_t    AVLLU32KEY;
 272
 273 /** AVL Core node. */
 274 typedef struct _AVLLU32NodeCore
 275 {
 276     AVLLU32KEY                  Key;        /**< Key value. */
 277     unsigned char               uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
 278     struct _AVLLU32NodeCore    *pLeft;      /**< Pointer to left leaf node. */
 279     struct _AVLLU32NodeCore    *pRight;     /**< Pointer to right leaf node. */
 280     struct _AVLLU32NodeCore    *pList;      /**< Pointer to next node with the same key. */
 281 } AVLLU32NODECORE, *PAVLLU32NODECORE, **PPAVLLU32NODECORE;
 282
 283 /** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy().
 284  *  @returns IPRT status codes. */
 285 typedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
 286 /** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
 287 typedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
 288
 289
 290 /*
 291  * Functions.
 292  */
 293 RTDECL(bool)                RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
 294 RTDECL(PAVLLU32NODECORE)    RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
 295 RTDECL(PAVLLU32NODECORE)    RTAvllU32RemoveNode(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
 296 RTDECL(PAVLLU32NODECORE)    RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
 297 RTDECL(PAVLLU32NODECORE)    RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
 298 RTDECL(PAVLLU32NODECORE)    RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
 299 RTDECL(int)                 RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
 300 RTDECL(int)                 RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
 301
 302 /** @} */
 303
 304
 305
 306 /** AVL tree of uint64_t ranges.
 307  * @{
 308  */
 309
 310 /**
 311  * AVL key type
 312  */
 313 typedef uint64_t AVLRU64KEY;
 314
 315 /**
 316  * AVL Core node.
 317  */
 318 typedef struct AVLRU64NodeCore
 319 {
 320     AVLRU64KEY               Key;        /**< First key value in the range (inclusive). */
 321     AVLRU64KEY               KeyLast;    /**< Last key value in the range (inclusive). */
 322     struct AVLRU64NodeCore  *pLeft;      /**< Pointer to left leaf node. */
 323     struct AVLRU64NodeCore  *pRight;     /**< Pointer to right leaf node. */
 324     unsigned char            uchHeight;  /**< Height of this tree: max(height(left), height(right)) + 1 */
 325 } AVLRU64NODECORE, *PAVLRU64NODECORE, **PPAVLRU64NODECORE;
 326
 327 /** A tree with void pointer keys. */
 328 typedef PAVLRU64NODECORE    AVLRU64TREE;
 329 /** Pointer to a tree with void pointer keys. */
 330 typedef PPAVLRU64NODECORE   PAVLRU64TREE;
 331
 332 /** Callback function for AVLRU64DoWithAll().
 333  *  @returns IPRT status codes. */
 334 typedef DECLCALLBACK(int) AVLRU64CALLBACK(PAVLRU64NODECORE, void *);
 335 /** Pointer to callback function for AVLU64DoWithAll(). */
 336 typedef AVLRU64CALLBACK *PAVLRU64CALLBACK;
 337
 338 /*
 339  * Functions.
 340  */
 341 RTDECL(bool)             RTAvlrU64Insert(PAVLRU64TREE ppTree, PAVLRU64NODECORE pNode);
 342 RTDECL(PAVLRU64NODECORE) RTAvlrU64Remove(PAVLRU64TREE ppTree, AVLRU64KEY Key);
 343 RTDECL(PAVLRU64NODECORE) RTAvlrU64Get(PAVLRU64TREE ppTree, AVLRU64KEY Key);
 344 RTDECL(PAVLRU64NODECORE) RTAvlrU64RangeGet(PAVLRU64TREE ppTree, AVLRU64KEY Key);
 345 RTDECL(PAVLRU64NODECORE) RTAvlrU64RangeRemove(PAVLRU64TREE ppTree, AVLRU64KEY Key);
 346 RTDECL(PAVLRU64NODECORE) RTAvlrU64GetBestFit(PAVLRU64TREE ppTree, AVLRU64KEY Key, bool fAbove);
 347 RTDECL(PAVLRU64NODECORE) RTAvlrU64RemoveBestFit(PAVLRU64TREE ppTree, AVLRU64KEY Key, bool fAbove);
 348 RTDECL(int)              RTAvlrU64DoWithAll(PAVLRU64TREE ppTree, int fFromLeft, PAVLRU64CALLBACK pfnCallBack, void *pvParam);
 349 RTDECL(int)              RTAvlrU64Destroy(PAVLRU64TREE ppTree, PAVLRU64CALLBACK pfnCallBack, void *pvParam);
 350
 351 /** @} */
 352
 353
 354
 355 /** AVL tree of RTGCPHYSes - using relative offsets internally.
 356  * @{
 357  */
 358
 359 /**
 360  * AVL 'pointer' type for the relative offset pointer scheme.
 361  */
 362 typedef int32_t     AVLOGCPHYS;
 363
 364 /**
 365  * AVL Core node.
 366  */
 367 typedef struct _AVLOGCPhysNodeCore
 368 {
 369     /** Key value. */
 370     RTGCPHYS            Key;
 371     /** Offset to the left leaf node, relative to this field. */
 372     AVLOGCPHYS          pLeft;
 373     /** Offset to the right leaf node, relative to this field. */
 374     AVLOGCPHYS          pRight;
 375     /** Height of this tree: max(height(left), height(right)) + 1 */
 376     unsigned char       uchHeight;
 377     /** Padding */
 378     unsigned char       Padding[7];
 379 } AVLOGCPHYSNODECORE, *PAVLOGCPHYSNODECORE;
 380
 381 /** A offset base tree with uint32_t keys. */
 382 typedef AVLOGCPHYS         AVLOGCPHYSTREE;
 383 /** Pointer to an offset base tree with uint32_t keys. */
 384 typedef AVLOGCPHYSTREE    *PAVLOGCPHYSTREE;
 385
 386 /** Pointer to an internal tree pointer.
 387  * In this case it's a pointer to a relative offset. */
 388 typedef AVLOGCPHYSTREE    *PPAVLOGCPHYSNODECORE;
 389
 390 /** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy().
 391  *  @returns IPRT status codes. */
 392 typedef DECLCALLBACK(int)   AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
 393 /** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
 394 typedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
 395
 396 RTDECL(bool)                    RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
 397 RTDECL(PAVLOGCPHYSNODECORE)     RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
 398 RTDECL(PAVLOGCPHYSNODECORE)     RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
 399 RTDECL(int)                     RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
 400 RTDECL(PAVLOGCPHYSNODECORE)     RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
 401 RTDECL(PAVLOGCPHYSNODECORE)     RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
 402 RTDECL(int)                     RTAvloGCPhysDestroy(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
 403
 404 /** @} */
 405
 406
 407 /** AVL tree of RTGCPHYS ranges - using relative offsets internally.
 408  * @{
 409  */
 410
 411 /**
 412  * AVL 'pointer' type for the relative offset pointer scheme.
 413  */
 414 typedef int32_t     AVLROGCPHYS;
 415
 416 /**
 417  * AVL Core node.
 418  */
 419 typedef struct _AVLROGCPhysNodeCore
 420 {
 421     /** First key value in the range (inclusive). */
 422     RTGCPHYS            Key;
 423     /** Last key value in the range (inclusive). */
 424     RTGCPHYS            KeyLast;
 425     /** Offset to the left leaf node, relative to this field. */
 426     AVLROGCPHYS         pLeft;
 427     /** Offset to the right leaf node, relative to this field. */
 428     AVLROGCPHYS         pRight;
 429     /** Height of this tree: max(height(left), height(right)) + 1 */
 430     unsigned char       uchHeight;
 431     /** Padding */
 432     unsigned char       Padding[7];
 433 } AVLROGCPHYSNODECORE, *PAVLROGCPHYSNODECORE;
 434
 435 /** A offset base tree with uint32_t keys. */
 436 typedef AVLROGCPHYS         AVLROGCPHYSTREE;
 437 /** Pointer to an offset base tree with uint32_t keys. */
 438 typedef AVLROGCPHYSTREE    *PAVLROGCPHYSTREE;
 439
 440 /** Pointer to an internal tree pointer.
 441  * In this case it's a pointer to a relative offset. */
 442 typedef AVLROGCPHYSTREE    *PPAVLROGCPHYSNODECORE;
 443
 444 /** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy().
 445  *  @returns IPRT status codes. */
 446 typedef DECLCALLBACK(int)   AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
 447 /** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
 448 typedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
 449
 450 RTDECL(bool)                    RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
 451 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
 452 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
 453 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
 454 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
 455 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
 456 RTDECL(int)                     RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
 457 RTDECL(int)                     RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
 458 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
 459 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
 460 RTDECL(PAVLROGCPHYSNODECORE)    RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
 461
 462 /** @} */
 463
 464
 465 /** AVL tree of RTGCPTRs.
 466  * @{
 467  */
 468
 469 /**
 470  * AVL Core node.
 471  */
 472 typedef struct _AVLGCPtrNodeCore
 473 {
 474     /** Key value. */
 475     RTGCPTR             Key;
 476     /** Pointer to the left node. */
 477     struct _AVLGCPtrNodeCore *pLeft;
 478     /** Pointer to the right node. */
 479     struct _AVLGCPtrNodeCore *pRight;
 480     /** Height of this tree: max(height(left), height(right)) + 1 */
 481     unsigned char       uchHeight;
 482 } AVLGCPTRNODECORE, *PAVLGCPTRNODECORE, **PPAVLGCPTRNODECORE;
 483
 484 /** A tree of RTGCPTR keys. */
 485 typedef PAVLGCPTRNODECORE     AVLGCPTRTREE;
 486 /** Pointer to a tree of RTGCPTR keys. */
 487 typedef PPAVLGCPTRNODECORE    PAVLGCPTRTREE;
 488
 489 /** Callback function for RTAvlGCPtrDoWithAll().
 490  *  @returns IPRT status codes. */
 491 typedef DECLCALLBACK(int)   AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
 492 /** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
 493 typedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
 494
 495 RTDECL(bool)                    RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
 496 RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
 497 RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
 498 RTDECL(int)                     RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
 499 RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
 500 RTDECL(PAVLGCPTRNODECORE)       RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
 501 RTDECL(int)                     RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
 502
 503 /** @} */
 504
 505
 506 /** AVL tree of RTGCPTRs - using relative offsets internally.
 507  * @{
 508  */
 509
 510 /**
 511  * AVL 'pointer' type for the relative offset pointer scheme.
 512  */
 513 typedef int32_t     AVLOGCPTR;
 514
 515 /**
 516  * AVL Core node.
 517  */
 518 typedef struct _AVLOGCPtrNodeCore
 519 {
 520     /** Key value. */
 521     RTGCPTR             Key;
 522     /** Offset to the left leaf node, relative to this field. */
 523     AVLOGCPTR           pLeft;
 524     /** Offset to the right leaf node, relative to this field. */
 525     AVLOGCPTR           pRight;
 526     /** Height of this tree: max(height(left), height(right)) + 1 */
 527     unsigned char       uchHeight;
 528     unsigned char       padding[GC_ARCH_BITS == 64 ? 7 : 3];
 529 } AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
 530
 531 /** A offset base tree with uint32_t keys. */
 532 typedef AVLOGCPTR         AVLOGCPTRTREE;
 533 /** Pointer to an offset base tree with uint32_t keys. */
 534 typedef AVLOGCPTRTREE    *PAVLOGCPTRTREE;
 535
 536 /** Pointer to an internal tree pointer.
 537  * In this case it's a pointer to a relative offset. */
 538 typedef AVLOGCPTRTREE    *PPAVLOGCPTRNODECORE;
 539
 540 /** Callback function for RTAvloGCPtrDoWithAll().
 541  *  @returns IPRT status codes. */
 542 typedef DECLCALLBACK(int)   AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
 543 /** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
 544 typedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
 545
 546 RTDECL(bool)                    RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
 547 RTDECL(PAVLOGCPTRNODECORE)      RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
 548 RTDECL(PAVLOGCPTRNODECORE)      RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
 549 RTDECL(int)                     RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
 550 RTDECL(PAVLOGCPTRNODECORE)      RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
 551 RTDECL(PAVLOGCPTRNODECORE)      RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
 552 RTDECL(int)                     RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
 553
 554 /** @} */
 555
 556
 557 /** AVL tree of RTGCPTR ranges.
 558  * @{
 559  */
 560
 561 /**
 562  * AVL Core node.
 563  */
 564 typedef struct _AVLRGCPtrNodeCore
 565 {
 566     /** First key value in the range (inclusive). */
 567     RTGCPTR             Key;
 568     /** Last key value in the range (inclusive). */
 569     RTGCPTR             KeyLast;
 570     /** Offset to the left leaf node, relative to this field. */
 571     struct _AVLRGCPtrNodeCore  *pLeft;
 572     /** Offset to the right leaf node, relative to this field. */
 573     struct _AVLRGCPtrNodeCore  *pRight;
 574     /** Height of this tree: max(height(left), height(right)) + 1 */
 575     unsigned char       uchHeight;
 576 } AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
 577
 578 /** A offset base tree with RTGCPTR keys. */
 579 typedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
 580 /** Pointer to an offset base tree with RTGCPTR keys. */
 581 typedef AVLRGCPTRTREE    *PAVLRGCPTRTREE;
 582
 583 /** Pointer to an internal tree pointer.
 584  * In this case it's a pointer to a relative offset. */
 585 typedef AVLRGCPTRTREE    *PPAVLRGCPTRNODECORE;
 586
 587 /** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy().
 588  *  @returns IPRT status codes. */
 589 typedef DECLCALLBACK(int)   AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
 590 /** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
 591 typedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
 592
 593 RTDECL(bool)                   RTAvlrGCPtrInsert(       PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
 594 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrRemove(       PAVLRGCPTRTREE pTree, RTGCPTR Key);
 595 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrGet(          PAVLRGCPTRTREE pTree, RTGCPTR Key);
 596 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrGetBestFit(   PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
 597 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrRangeGet(     PAVLRGCPTRTREE pTree, RTGCPTR Key);
 598 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrRangeRemove(  PAVLRGCPTRTREE pTree, RTGCPTR Key);
 599 RTDECL(int)                    RTAvlrGCPtrDoWithAll(    PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
 600 RTDECL(int)                    RTAvlrGCPtrDestroy(      PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
 601 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrGetRoot(      PAVLRGCPTRTREE pTree);
 602 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrGetLeft(      PAVLRGCPTRNODECORE pNode);
 603 RTDECL(PAVLRGCPTRNODECORE)     RTAvlrGCPtrGetRight(     PAVLRGCPTRNODECORE pNode);
 604
 605 /** @} */
 606
 607
 608 /** AVL tree of RTGCPTR ranges - using relative offsets internally.
 609  * @{
 610  */
 611
 612 /**
 613  * AVL 'pointer' type for the relative offset pointer scheme.
 614  */
 615 typedef int32_t     AVLROGCPTR;
 616
 617 /**
 618  * AVL Core node.
 619  */
 620 typedef struct _AVLROGCPtrNodeCore
 621 {
 622     /** First key value in the range (inclusive). */
 623     RTGCPTR             Key;
 624     /** Last key value in the range (inclusive). */
 625     RTGCPTR             KeyLast;
 626     /** Offset to the left leaf node, relative to this field. */
 627     AVLROGCPTR          pLeft;
 628     /** Offset to the right leaf node, relative to this field. */
 629     AVLROGCPTR          pRight;
 630     /** Height of this tree: max(height(left), height(right)) + 1 */
 631     unsigned char       uchHeight;
 632     unsigned char       padding[GC_ARCH_BITS == 64 ? 7 : 7];
 633 } AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
 634
 635 /** A offset base tree with uint32_t keys. */
 636 typedef AVLROGCPTR         AVLROGCPTRTREE;
 637 /** Pointer to an offset base tree with uint32_t keys. */
 638 typedef AVLROGCPTRTREE    *PAVLROGCPTRTREE;
 639
 640 /** Pointer to an internal tree pointer.
 641  * In this case it's a pointer to a relative offset. */
 642 typedef AVLROGCPTRTREE    *PPAVLROGCPTRNODECORE;
 643
 644 /** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy().
 645  *  @returns IPRT status codes. */
 646 typedef DECLCALLBACK(int)   AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
 647 /** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
 648 typedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
 649
 650 RTDECL(bool)                    RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
 651 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
 652 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
 653 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
 654 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
 655 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
 656 RTDECL(int)                     RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
 657 RTDECL(int)                     RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
 658 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
 659 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
 660 RTDECL(PAVLROGCPTRNODECORE)     RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
 661
 662 /** @} */
 663
 664
 665 /** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
 666  * @{
 667  */
 668
 669 /**
 670  * AVL 'pointer' type for the relative offset pointer scheme.
 671  */
 672 typedef int32_t     AVLROOGCPTR;
 673
 674 /**
 675  * AVL Core node.
 676  */
 677 typedef struct _AVLROOGCPtrNodeCore
 678 {
 679     /** First key value in the range (inclusive). */
 680     RTGCPTR             Key;
 681     /** Last key value in the range (inclusive). */
 682     RTGCPTR             KeyLast;
 683     /** Offset to the left leaf node, relative to this field. */
 684     AVLROOGCPTR         pLeft;
 685     /** Offset to the right leaf node, relative to this field. */
 686     AVLROOGCPTR         pRight;
 687     /** Pointer to the list of string with the same key. Don't touch. */
 688     AVLROOGCPTR         pList;
 689     /** Height of this tree: max(height(left), height(right)) + 1 */
 690     unsigned char       uchHeight;
 691 } AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
 692
 693 /** A offset base tree with uint32_t keys. */
 694 typedef AVLROOGCPTR         AVLROOGCPTRTREE;
 695 /** Pointer to an offset base tree with uint32_t keys. */
 696 typedef AVLROOGCPTRTREE    *PAVLROOGCPTRTREE;
 697
 698 /** Pointer to an internal tree pointer.
 699  * In this case it's a pointer to a relative offset. */
 700 typedef AVLROOGCPTRTREE    *PPAVLROOGCPTRNODECORE;
 701
 702 /** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy().
 703  *  @returns IPRT status codes. */
 704 typedef DECLCALLBACK(int)   AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
 705 /** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
 706 typedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
 707
 708 RTDECL(bool)                    RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
 709 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
 710 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
 711 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
 712 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
 713 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
 714 RTDECL(int)                     RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
 715 RTDECL(int)                     RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
 716 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
 717 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
 718 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
 719 RTDECL(PAVLROOGCPTRNODECORE)    RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
 720
 721 /** @} */
 722
 723
 724 /** AVL tree of RTUINTPTR.
 725  * @{
 726  */
 727
 728 /**
 729  * AVL RTUINTPTR node core.
 730  */
 731 typedef struct _AVLUIntPtrNodeCore
 732 {
 733     /** Key value. */
 734     RTUINTPTR                   Key;
 735     /** Offset to the left leaf node, relative to this field. */
 736     struct _AVLUIntPtrNodeCore *pLeft;
 737     /** Offset to the right leaf node, relative to this field. */
 738     struct _AVLUIntPtrNodeCore *pRight;
 739     /** Height of this tree: max(height(left), height(right)) + 1 */
 740     unsigned char               uchHeight;
 741 } AVLUINTPTRNODECORE;
 742 /** Pointer to a RTUINTPTR AVL node core.*/
 743 typedef AVLUINTPTRNODECORE *PAVLUINTPTRNODECORE;
 744
 745 /** A pointer based tree with RTUINTPTR keys. */
 746 typedef PAVLUINTPTRNODECORE AVLUINTPTRTREE;
 747 /** Pointer to an offset base tree with RTUINTPTR keys. */
 748 typedef AVLUINTPTRTREE     *PAVLUINTPTRTREE;
 749
 750 /** Pointer to an internal tree pointer.
 751  * In this case it's a pointer to a pointer. */
 752 typedef AVLUINTPTRTREE     *PPAVLUINTPTRNODECORE;
 753
 754 /** Callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy().
 755  *  @returns IPRT status codes. */
 756 typedef DECLCALLBACK(int)    AVLUINTPTRCALLBACK(PAVLUINTPTRNODECORE pNode, void *pvUser);
 757 /** Pointer to callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
 758 typedef AVLUINTPTRCALLBACK *PAVLUINTPTRCALLBACK;
 759
 760 RTDECL(bool)                    RTAvlUIntPtrInsert(    PAVLUINTPTRTREE pTree, PAVLUINTPTRNODECORE pNode);
 761 RTDECL(PAVLUINTPTRNODECORE)     RTAvlUIntPtrRemove(    PAVLUINTPTRTREE pTree, RTUINTPTR Key);
 762 RTDECL(PAVLUINTPTRNODECORE)     RTAvlUIntPtrGet(       PAVLUINTPTRTREE pTree, RTUINTPTR Key);
 763 RTDECL(PAVLUINTPTRNODECORE)     RTAvlUIntPtrGetBestFit(PAVLUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
 764 RTDECL(int)                     RTAvlUIntPtrDoWithAll( PAVLUINTPTRTREE pTree, int fFromLeft, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
 765 RTDECL(int)                     RTAvlUIntPtrDestroy(   PAVLUINTPTRTREE pTree, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
 766 RTDECL(PAVLUINTPTRNODECORE)     RTAvlUIntPtrGetRoot(   PAVLUINTPTRTREE pTree);
 767 RTDECL(PAVLUINTPTRNODECORE)     RTAvlUIntPtrGetLeft(   PAVLUINTPTRNODECORE pNode);
 768 RTDECL(PAVLUINTPTRNODECORE)     RTAvlUIntPtrGetRight(  PAVLUINTPTRNODECORE pNode);
 769
 770 /** @} */
 771
 772
 773 /** AVL tree of RTUINTPTR ranges.
 774  * @{
 775  */
 776
 777 /**
 778  * AVL RTUINTPTR range node core.
 779  */
 780 typedef struct _AVLRUIntPtrNodeCore
 781 {
 782     /** First key value in the range (inclusive). */
 783     RTUINTPTR                       Key;
 784     /** Last key value in the range (inclusive). */
 785     RTUINTPTR                       KeyLast;
 786     /** Offset to the left leaf node, relative to this field. */
 787     struct _AVLRUIntPtrNodeCore    *pLeft;
 788     /** Offset to the right leaf node, relative to this field. */
 789     struct _AVLRUIntPtrNodeCore    *pRight;
 790     /** Height of this tree: max(height(left), height(right)) + 1 */
 791     unsigned char                   uchHeight;
 792 } AVLRUINTPTRNODECORE;
 793 /** Pointer to an AVL RTUINTPTR range node code. */
 794 typedef AVLRUINTPTRNODECORE *PAVLRUINTPTRNODECORE;
 795
 796 /** A pointer based tree with RTUINTPTR ranges. */
 797 typedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
 798 /** Pointer to a pointer based tree with RTUINTPTR ranges. */
 799 typedef AVLRUINTPTRTREE     *PAVLRUINTPTRTREE;
 800
 801 /** Pointer to an internal tree pointer.
 802  * In this case it's a pointer to a pointer. */
 803 typedef AVLRUINTPTRTREE     *PPAVLRUINTPTRNODECORE;
 804
 805 /** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy().
 806  *  @returns IPRT status codes. */
 807 typedef DECLCALLBACK(int)    AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
 808 /** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
 809 typedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
 810
 811 RTDECL(bool)                   RTAvlrUIntPtrInsert(     PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
 812 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrRemove(     PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
 813 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrGet(        PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
 814 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
 815 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrRangeGet(   PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
 816 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
 817 RTDECL(int)                    RTAvlrUIntPtrDoWithAll(  PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
 818 RTDECL(int)                    RTAvlrUIntPtrDestroy(    PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
 819 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrGetRoot(    PAVLRUINTPTRTREE pTree);
 820 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrGetLeft(    PAVLRUINTPTRNODECORE pNode);
 821 RTDECL(PAVLRUINTPTRNODECORE)   RTAvlrUIntPtrGetRight(   PAVLRUINTPTRNODECORE pNode);
 822
 823 /** @} */
 824
 825
 826 /** AVL tree of RTHCPHYSes - using relative offsets internally.
 827  * @{
 828  */
 829
 830 /**
 831  * AVL 'pointer' type for the relative offset pointer scheme.
 832  */
 833 typedef int32_t     AVLOHCPHYS;
 834
 835 /**
 836  * AVL Core node.
 837  */
 838 typedef struct _AVLOHCPhysNodeCore
 839 {
 840     /** Key value. */
 841     RTHCPHYS            Key;
 842     /** Offset to the left leaf node, relative to this field. */
 843     AVLOHCPHYS          pLeft;
 844     /** Offset to the right leaf node, relative to this field. */
 845     AVLOHCPHYS          pRight;
 846     /** Height of this tree: max(height(left), height(right)) + 1 */
 847     unsigned char       uchHeight;
 848 #if HC_ARCH_BITS == 64 || GC_ARCH_BITS == 64
 849     unsigned char       Padding[7]; /**< Alignment padding. */
 850 #endif
 851 } AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
 852
 853 /** A offset base tree with uint32_t keys. */
 854 typedef AVLOHCPHYS         AVLOHCPHYSTREE;
 855 /** Pointer to an offset base tree with uint32_t keys. */
 856 typedef AVLOHCPHYSTREE    *PAVLOHCPHYSTREE;
 857
 858 /** Pointer to an internal tree pointer.
 859  * In this case it's a pointer to a relative offset. */
 860 typedef AVLOHCPHYSTREE    *PPAVLOHCPHYSNODECORE;
 861
 862 /** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy().
 863  *  @returns IPRT status codes. */
 864 typedef DECLCALLBACK(int)   AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
 865 /** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
 866 typedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
 867
 868 RTDECL(bool)                    RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
 869 RTDECL(PAVLOHCPHYSNODECORE)     RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
 870 RTDECL(PAVLOHCPHYSNODECORE)     RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
 871 RTDECL(int)                     RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
 872 RTDECL(PAVLOHCPHYSNODECORE)     RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
 873 RTDECL(PAVLOHCPHYSNODECORE)     RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
 874 RTDECL(int)                     RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
 875
 876 /** @} */
 877
 878
 879
 880 /** AVL tree of RTIOPORTs - using relative offsets internally.
 881  * @{
 882  */
 883
 884 /**
 885  * AVL 'pointer' type for the relative offset pointer scheme.
 886  */
 887 typedef int32_t     AVLOIOPORTPTR;
 888
 889 /**
 890  * AVL Core node.
 891  */
 892 typedef struct _AVLOIOPortNodeCore
 893 {
 894     /** Offset to the left leaf node, relative to this field. */
 895     AVLOIOPORTPTR       pLeft;
 896     /** Offset to the right leaf node, relative to this field. */
 897     AVLOIOPORTPTR       pRight;
 898     /** Key value. */
 899     RTIOPORT            Key;
 900     /** Height of this tree: max(height(left), height(right)) + 1 */
 901     unsigned char       uchHeight;
 902 } AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
 903
 904 /** A offset base tree with uint32_t keys. */
 905 typedef AVLOIOPORTPTR      AVLOIOPORTTREE;
 906 /** Pointer to an offset base tree with uint32_t keys. */
 907 typedef AVLOIOPORTTREE    *PAVLOIOPORTTREE;
 908
 909 /** Pointer to an internal tree pointer.
 910  * In this case it's a pointer to a relative offset. */
 911 typedef AVLOIOPORTTREE    *PPAVLOIOPORTNODECORE;
 912
 913 /** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy().
 914  *  @returns IPRT status codes. */
 915 typedef DECLCALLBACK(int)   AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
 916 /** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
 917 typedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
 918
 919 RTDECL(bool)                    RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
 920 RTDECL(PAVLOIOPORTNODECORE)     RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
 921 RTDECL(PAVLOIOPORTNODECORE)     RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
 922 RTDECL(int)                     RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
 923 RTDECL(PAVLOIOPORTNODECORE)     RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
 924 RTDECL(PAVLOIOPORTNODECORE)     RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
 925 RTDECL(int)                     RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
 926
 927 /** @} */
 928
 929
 930 /** AVL tree of RTIOPORT ranges - using relative offsets internally.
 931  * @{
 932  */
 933
 934 /**
 935  * AVL 'pointer' type for the relative offset pointer scheme.
 936  */
 937 typedef int32_t     AVLROIOPORTPTR;
 938
 939 /**
 940  * AVL Core node.
 941  */
 942 typedef struct _AVLROIOPortNodeCore
 943 {
 944     /** First key value in the range (inclusive). */
 945     RTIOPORT            Key;
 946     /** Last key value in the range (inclusive). */
 947     RTIOPORT            KeyLast;
 948     /** Offset to the left leaf node, relative to this field. */
 949     AVLROIOPORTPTR      pLeft;
 950     /** Offset to the right leaf node, relative to this field. */
 951     AVLROIOPORTPTR      pRight;
 952     /** Height of this tree: max(height(left), height(right)) + 1 */
 953     unsigned char       uchHeight;
 954 } AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
 955
 956 /** A offset base tree with uint32_t keys. */
 957 typedef AVLROIOPORTPTR      AVLROIOPORTTREE;
 958 /** Pointer to an offset base tree with uint32_t keys. */
 959 typedef AVLROIOPORTTREE    *PAVLROIOPORTTREE;
 960
 961 /** Pointer to an internal tree pointer.
 962  * In this case it's a pointer to a relative offset. */
 963 typedef AVLROIOPORTTREE    *PPAVLROIOPORTNODECORE;
 964
 965 /** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy().
 966  *  @returns IPRT status codes. */
 967 typedef DECLCALLBACK(int)   AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
 968 /** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
 969 typedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
 970
 971 RTDECL(bool)                    RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
 972 RTDECL(PAVLROIOPORTNODECORE)    RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
 973 RTDECL(PAVLROIOPORTNODECORE)    RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
 974 RTDECL(PAVLROIOPORTNODECORE)    RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
 975 RTDECL(PAVLROIOPORTNODECORE)    RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
 976 RTDECL(int)                     RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
 977 RTDECL(int)                     RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
 978
 979 /** @} */
 980
 981
 982 /** AVL tree of RTHCPHYSes.
 983  * @{
 984  */
 985
 986 /**
 987  * AVL 'pointer' type for the relative offset pointer scheme.
 988  */
 989 typedef struct _AVLHCPhysNodeCore  *AVLHCPHYSPTR;
 990
 991 /**
 992  * AVL Core node.
 993  */
 994 typedef struct _AVLHCPhysNodeCore
 995 {
 996     /** Offset to the left leaf node, relative to this field. */
 997     AVLHCPHYSPTR        pLeft;
 998     /** Offset to the right leaf node, relative to this field. */
 999     AVLHCPHYSPTR        pRight;
1000     /** Key value. */
1001     RTHCPHYS            Key;
1002     /** Height of this tree: max(height(left), height(right)) + 1 */
1003     unsigned char       uchHeight;
1004 } AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
1005
1006 /** A offset base tree with RTHCPHYS keys. */
1007 typedef AVLHCPHYSPTR      AVLHCPHYSTREE;
1008 /** Pointer to an offset base tree with RTHCPHYS keys. */
1009 typedef AVLHCPHYSTREE    *PAVLHCPHYSTREE;
1010
1011 /** Pointer to an internal tree pointer.
1012  * In this case it's a pointer to a relative offset. */
1013 typedef AVLHCPHYSTREE    *PPAVLHCPHYSNODECORE;
1014
1015 /** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy().
1016  *  @returns IPRT status codes. */
1017 typedef DECLCALLBACK(int)   AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
1018 /** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
1019 typedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
1020
1021 RTDECL(bool)                    RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
1022 RTDECL(PAVLHCPHYSNODECORE)      RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
1023 RTDECL(PAVLHCPHYSNODECORE)      RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
1024 RTDECL(int)                     RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
1025 RTDECL(PAVLHCPHYSNODECORE)      RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
1026 RTDECL(PAVLHCPHYSNODECORE)      RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
1027 RTDECL(int)                     RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
1028
1029 /** @} */
1030
1031 /** AVL tree of RTGCPHYSes.
1032  * @{
1033  */
1034
1035 /**
1036  * AVL 'pointer' type for the relative offset pointer scheme.
1037  */
1038 typedef struct _AVLGCPhysNodeCore  *AVLGCPHYSPTR;
1039
1040 /**
1041  * AVL Core node.
1042  */
1043 typedef struct _AVLGCPhysNodeCore
1044 {
1045     /** Offset to the left leaf node, relative to this field. */
1046     AVLGCPHYSPTR        pLeft;
1047     /** Offset to the right leaf node, relative to this field. */
1048     AVLGCPHYSPTR        pRight;
1049     /** Key value. */
1050     RTGCPHYS            Key;
1051     /** Height of this tree: max(height(left), height(right)) + 1 */
1052     unsigned char       uchHeight;
1053 } AVLGCPHYSNODECORE, *PAVLGCPHYSNODECORE;
1054
1055 /** A offset base tree with RTGCPHYS keys. */
1056 typedef AVLGCPHYSPTR      AVLGCPHYSTREE;
1057 /** Pointer to an offset base tree with RTGCPHYS keys. */
1058 typedef AVLGCPHYSTREE    *PAVLGCPHYSTREE;
1059
1060 /** Pointer to an internal tree pointer.
1061  * In this case it's a pointer to a relative offset. */
1062 typedef AVLGCPHYSTREE    *PPAVLGCPHYSNODECORE;
1063
1064 /** Callback function for RTAvlGCPhysDoWithAll() and RTAvlGCPhysDestroy().
1065  *  @returns IPRT status codes. */
1066 typedef DECLCALLBACK(int)   AVLGCPHYSCALLBACK(PAVLGCPHYSNODECORE pNode, void *pvUser);
1067 /** Pointer to callback function for RTAvlGCPhysDoWithAll() and RTAvlGCPhysDestroy(). */
1068 typedef AVLGCPHYSCALLBACK *PAVLGCPHYSCALLBACK;
1069
1070 RTDECL(bool)                    RTAvlGCPhysInsert(PAVLGCPHYSTREE pTree, PAVLGCPHYSNODECORE pNode);
1071 RTDECL(PAVLGCPHYSNODECORE)      RTAvlGCPhysRemove(PAVLGCPHYSTREE pTree, RTGCPHYS Key);
1072 RTDECL(PAVLGCPHYSNODECORE)      RTAvlGCPhysGet(PAVLGCPHYSTREE pTree, RTGCPHYS Key);
1073 RTDECL(int)                     RTAvlGCPhysDoWithAll(PAVLGCPHYSTREE pTree, int fFromLeft, PAVLGCPHYSCALLBACK pfnCallBack, void *pvParam);
1074 RTDECL(PAVLGCPHYSNODECORE)      RTAvlGCPhysGetBestFit(PAVLGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
1075 RTDECL(PAVLGCPHYSNODECORE)      RTAvlGCPhysRemoveBestFit(PAVLGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
1076 RTDECL(int)                     RTAvlGCPhysDestroy(PAVLGCPHYSTREE pTree, PAVLGCPHYSCALLBACK pfnCallBack, void *pvParam);
1077
1078 /** @} */
1079
1080
1081 /** AVL tree of RTFOFF ranges.
1082  * @{
1083  */
1084
1085 /**
1086  * AVL Core node.
1087  */
1088 typedef struct _AVLRFOFFNodeCore
1089 {
1090     /** First key value in the range (inclusive). */
1091     RTFOFF             Key;
1092     /** Last key value in the range (inclusive). */
1093     RTFOFF             KeyLast;
1094     /** Offset to the left leaf node, relative to this field. */
1095     struct _AVLRFOFFNodeCore  *pLeft;
1096     /** Offset to the right leaf node, relative to this field. */
1097     struct _AVLRFOFFNodeCore  *pRight;
1098     /** Height of this tree: max(height(left), height(right)) + 1 */
1099     unsigned char       uchHeight;
1100 } AVLRFOFFNODECORE, *PAVLRFOFFNODECORE;
1101
1102 /** A pointer based tree with RTFOFF ranges. */
1103 typedef PAVLRFOFFNODECORE AVLRFOFFTREE;
1104 /** Pointer to a pointer based tree with RTFOFF ranges. */
1105 typedef AVLRFOFFTREE    *PAVLRFOFFTREE;
1106
1107 /** Pointer to an internal tree pointer.
1108  * In this case it's a pointer to a relative offset. */
1109 typedef AVLRFOFFTREE    *PPAVLRFOFFNODECORE;
1110
1111 /** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy().
1112  *  @returns IPRT status codes. */
1113 typedef DECLCALLBACK(int)   AVLRFOFFCALLBACK(PAVLRFOFFNODECORE pNode, void *pvUser);
1114 /** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
1115 typedef AVLRFOFFCALLBACK *PAVLRFOFFCALLBACK;
1116
1117 RTDECL(bool)                  RTAvlrFileOffsetInsert(       PAVLRFOFFTREE pTree, PAVLRFOFFNODECORE pNode);
1118 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetRemove(       PAVLRFOFFTREE pTree, RTFOFF Key);
1119 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetGet(          PAVLRFOFFTREE pTree, RTFOFF Key);
1120 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetGetBestFit(   PAVLRFOFFTREE pTree, RTFOFF Key, bool fAbove);
1121 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetRangeGet(     PAVLRFOFFTREE pTree, RTFOFF Key);
1122 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetRangeRemove(  PAVLRFOFFTREE pTree, RTFOFF Key);
1123 RTDECL(int)                   RTAvlrFileOffsetDoWithAll(    PAVLRFOFFTREE pTree, int fFromLeft, PAVLRFOFFCALLBACK pfnCallBack, void *pvParam);
1124 RTDECL(int)                   RTAvlrFileOffsetDestroy(      PAVLRFOFFTREE pTree, PAVLRFOFFCALLBACK pfnCallBack, void *pvParam);
1125 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetGetRoot(      PAVLRFOFFTREE pTree);
1126 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetGetLeft(      PAVLRFOFFNODECORE pNode);
1127 RTDECL(PAVLRFOFFNODECORE)     RTAvlrFileOffsetGetRight(     PAVLRFOFFNODECORE pNode);
1128
1129 /** @} */
1130
1131 /** @} */
1132
1133 RT_C_DECLS_END
1134
1135 #endif
1136