avl.h revision ca3da10d05961c339b5180fbd40a54587d6bad35
1N/A/** @file
1N/A * IPRT - AVL Trees.
1N/A */
1N/A
1N/A/*
1N/A * Copyright (C) 1999-2003 knut st. osmundsen <bird-src-spam@anduin.net>
1N/A *
1N/A * This file is part of VirtualBox Open Source Edition (OSE), as
1N/A * available from http://www.virtualbox.org. This file is free software;
1N/A * you can redistribute it and/or modify it under the terms of the GNU
1N/A * General Public License (GPL) as published by the Free Software
1N/A * Foundation, in version 2 as it comes in the "COPYING" file of the
1N/A * VirtualBox OSE distribution. VirtualBox OSE is distributed in the
1N/A * hope that it will be useful, but WITHOUT ANY WARRANTY of any kind.
1N/A *
1N/A * The contents of this file may alternatively be used under the terms
1N/A * of the Common Development and Distribution License Version 1.0
1N/A * (CDDL) only, as it comes in the "COPYING.CDDL" file of the
1N/A * VirtualBox OSE distribution, in which case the provisions of the
1N/A * CDDL are applicable instead of those of the GPL.
1N/A *
1N/A * You may elect to license modified versions of this file under the
1N/A * terms and conditions of either the GPL or the CDDL or both.
1N/A *
1N/A * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
1N/A * Clara, CA 95054 USA or visit http://www.sun.com if you need
1N/A * additional information or have any questions.
1N/A */
1N/A
1N/A#ifndef ___iprt_avl_h
1N/A#define ___iprt_avl_h
1N/A
1N/A#include <iprt/cdefs.h>
1N/A#include <iprt/types.h>
1N/A
1N/ART_C_DECLS_BEGIN
1N/A
1N/A/** @defgroup grp_rt_avl RTAvl - AVL Trees
1N/A * @ingroup grp_rt
1N/A * @{
1N/A */
1N/A
1N/A
1N/A/** AVL tree of void pointers.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL key type
1N/A */
1N/Atypedef void * AVLPVKEY;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLPVNodeCore
1N/A{
1N/A AVLPVKEY Key; /** Key value. */
1N/A struct _AVLPVNodeCore *pLeft; /** Pointer to left leaf node. */
1N/A struct _AVLPVNodeCore *pRight; /** Pointer to right leaf node. */
1N/A unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A} AVLPVNODECORE, *PAVLPVNODECORE, **PPAVLPVNODECORE;
1N/A
1N/A/** A tree with void pointer keys. */
1N/Atypedef PAVLPVNODECORE AVLPVTREE;
1N/A/** Pointer to a tree with void pointer keys. */
1N/Atypedef PPAVLPVNODECORE PAVLPVTREE;
1N/A
1N/A/** Callback function for AVLPVDoWithAll(). */
1N/Atypedef DECLCALLBACK(int) AVLPVCALLBACK(PAVLPVNODECORE, void *);
1N/A/** Pointer to callback function for AVLPVDoWithAll(). */
1N/Atypedef AVLPVCALLBACK *PAVLPVCALLBACK;
1N/A
1N/A/*
1N/A * Functions.
1N/A */
1N/ARTDECL(bool) RTAvlPVInsert(PAVLPVTREE ppTree, PAVLPVNODECORE pNode);
1N/ARTDECL(PAVLPVNODECORE) RTAvlPVRemove(PAVLPVTREE ppTree, AVLPVKEY Key);
1N/ARTDECL(PAVLPVNODECORE) RTAvlPVGet(PAVLPVTREE ppTree, AVLPVKEY Key);
1N/ARTDECL(PAVLPVNODECORE) RTAvlPVGetBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
1N/ARTDECL(PAVLPVNODECORE) RTAvlPVRemoveBestFit(PAVLPVTREE ppTree, AVLPVKEY Key, bool fAbove);
1N/ARTDECL(int) RTAvlPVDoWithAll(PAVLPVTREE ppTree, int fFromLeft, PAVLPVCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlPVDestroy(PAVLPVTREE ppTree, PAVLPVCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of unsigned long.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL key type
1N/A */
1N/Atypedef unsigned long AVLULKEY;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLULNodeCore
1N/A{
1N/A AVLULKEY Key; /** Key value. */
1N/A struct _AVLULNodeCore *pLeft; /** Pointer to left leaf node. */
1N/A struct _AVLULNodeCore *pRight; /** Pointer to right leaf node. */
1N/A unsigned char uchHeight; /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A} AVLULNODECORE, *PAVLULNODECORE, **PPAVLULNODECORE;
1N/A
1N/A
1N/A/** Callback function for AVLULDoWithAll(). */
1N/Atypedef DECLCALLBACK(int) AVLULCALLBACK(PAVLULNODECORE, void*);
1N/A/** Pointer to callback function for AVLULDoWithAll(). */
1N/Atypedef AVLULCALLBACK *PAVLULCALLBACK;
1N/A
1N/A
1N/A/*
1N/A * Functions.
1N/A */
1N/ARTDECL(bool) RTAvlULInsert(PPAVLULNODECORE ppTree, PAVLULNODECORE pNode);
1N/ARTDECL(PAVLULNODECORE) RTAvlULRemove(PPAVLULNODECORE ppTree, AVLULKEY Key);
1N/ARTDECL(PAVLULNODECORE) RTAvlULGet(PPAVLULNODECORE ppTree, AVLULKEY Key);
1N/ARTDECL(PAVLULNODECORE) RTAvlULGetBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
1N/ARTDECL(PAVLULNODECORE) RTAvlULRemoveBestFit(PPAVLULNODECORE ppTree, AVLULKEY Key, bool fAbove);
1N/ARTDECL(int) RTAvlULDoWithAll(PPAVLULNODECORE ppTree, int fFromLeft, PAVLULCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlULDestroy(PPAVLULNODECORE pTree, PAVLULCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A
1N/A/** AVL tree of uint32_t
1N/A * @{
1N/A */
1N/A
1N/A/** AVL key type. */
1N/Atypedef uint32_t AVLU32KEY;
1N/A
1N/A/** AVL Core node. */
1N/Atypedef struct _AVLU32NodeCore
1N/A{
1N/A AVLU32KEY Key; /**< Key value. */
1N/A struct _AVLU32NodeCore *pLeft; /**< Pointer to left leaf node. */
1N/A struct _AVLU32NodeCore *pRight; /**< Pointer to right leaf node. */
1N/A unsigned char uchHeight; /**< Height of this tree: max(height(left), height(right)) + 1 */
1N/A} AVLU32NODECORE, *PAVLU32NODECORE, **PPAVLU32NODECORE;
1N/A
1N/A/** A tree with void pointer keys. */
1N/Atypedef PAVLU32NODECORE AVLU32TREE;
1N/A/** Pointer to a tree with void pointer keys. */
1N/Atypedef PPAVLU32NODECORE PAVLU32TREE;
1N/A
1N/A/** Callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
1N/Atypedef DECLCALLBACK(int) AVLU32CALLBACK(PAVLU32NODECORE, void*);
1N/A/** Pointer to callback function for AVLU32DoWithAll() & AVLU32Destroy(). */
1N/Atypedef AVLU32CALLBACK *PAVLU32CALLBACK;
1N/A
1N/A
1N/A/*
1N/A * Functions.
1N/A */
1N/ARTDECL(bool) RTAvlU32Insert(PAVLU32TREE pTree, PAVLU32NODECORE pNode);
1N/ARTDECL(PAVLU32NODECORE) RTAvlU32Remove(PAVLU32TREE pTree, AVLU32KEY Key);
1N/ARTDECL(PAVLU32NODECORE) RTAvlU32Get(PAVLU32TREE pTree, AVLU32KEY Key);
1N/ARTDECL(PAVLU32NODECORE) RTAvlU32GetBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
1N/ARTDECL(PAVLU32NODECORE) RTAvlU32RemoveBestFit(PAVLU32TREE pTree, AVLU32KEY Key, bool fAbove);
1N/ARTDECL(int) RTAvlU32DoWithAll(PAVLU32TREE pTree, int fFromLeft, PAVLU32CALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlU32Destroy(PAVLU32TREE pTree, PAVLU32CALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A/**
1N/A * AVL uint32_t type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLOU32;
1N/A
1N/Atypedef uint32_t AVLOU32KEY;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLOU32NodeCore
1N/A{
1N/A /** Key value. */
1N/A AVLOU32KEY Key;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLOU32 pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLOU32 pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLOU32NODECORE, *PAVLOU32NODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLOU32 AVLOU32TREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLOU32TREE *PAVLOU32TREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLOU32TREE *PPAVLOU32NODECORE;
1N/A
1N/A/** Callback function for RTAvloU32DoWithAll(). */
1N/Atypedef DECLCALLBACK(int) AVLOU32CALLBACK(PAVLOU32NODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvloU32DoWithAll(). */
1N/Atypedef AVLOU32CALLBACK *PAVLOU32CALLBACK;
1N/A
1N/ARTDECL(bool) RTAvloU32Insert(PAVLOU32TREE pTree, PAVLOU32NODECORE pNode);
1N/ARTDECL(PAVLOU32NODECORE) RTAvloU32Remove(PAVLOU32TREE pTree, AVLOU32KEY Key);
1N/ARTDECL(PAVLOU32NODECORE) RTAvloU32Get(PAVLOU32TREE pTree, AVLOU32KEY Key);
1N/ARTDECL(int) RTAvloU32DoWithAll(PAVLOU32TREE pTree, int fFromLeft, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLOU32NODECORE) RTAvloU32GetBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
1N/ARTDECL(PAVLOU32NODECORE) RTAvloU32RemoveBestFit(PAVLOU32TREE ppTree, AVLOU32KEY Key, bool fAbove);
1N/ARTDECL(int) RTAvloU32Destroy(PAVLOU32TREE pTree, PAVLOU32CALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of uint32_t, list duplicates.
1N/A * @{
1N/A */
1N/A
1N/A/** AVL key type. */
1N/Atypedef uint32_t AVLLU32KEY;
1N/A
1N/A/** AVL Core node. */
1N/Atypedef struct _AVLLU32NodeCore
1N/A{
1N/A AVLLU32KEY Key; /**< Key value. */
1N/A unsigned char uchHeight; /**< Height of this tree: max(height(left), height(right)) + 1 */
1N/A struct _AVLLU32NodeCore *pLeft; /**< Pointer to left leaf node. */
1N/A struct _AVLLU32NodeCore *pRight; /**< Pointer to right leaf node. */
1N/A struct _AVLLU32NodeCore *pList; /**< Pointer to next node with the same key. */
1N/A} AVLLU32NODECORE, *PAVLLU32NODECORE, **PPAVLLU32NODECORE;
1N/A
1N/A/** Callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
1N/Atypedef DECLCALLBACK(int) AVLLU32CALLBACK(PAVLLU32NODECORE, void*);
1N/A/** Pointer to callback function for RTAvllU32DoWithAll() & RTAvllU32Destroy(). */
1N/Atypedef AVLLU32CALLBACK *PAVLLU32CALLBACK;
1N/A
1N/A
1N/A/*
1N/A * Functions.
1N/A */
1N/ARTDECL(bool) RTAvllU32Insert(PPAVLLU32NODECORE ppTree, PAVLLU32NODECORE pNode);
1N/ARTDECL(PAVLLU32NODECORE) RTAvllU32Remove(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
1N/ARTDECL(PAVLLU32NODECORE) RTAvllU32Get(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key);
1N/ARTDECL(PAVLLU32NODECORE) RTAvllU32GetBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
1N/ARTDECL(PAVLLU32NODECORE) RTAvllU32RemoveBestFit(PPAVLLU32NODECORE ppTree, AVLLU32KEY Key, bool fAbove);
1N/ARTDECL(int) RTAvllU32DoWithAll(PPAVLLU32NODECORE ppTree, int fFromLeft, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvllU32Destroy(PPAVLLU32NODECORE pTree, PAVLLU32CALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A
1N/A/** AVL tree of RTGCPHYSes - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLOGCPHYS;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLOGCPhysNodeCore
1N/A{
1N/A /** Key value. */
1N/A RTGCPHYS Key;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLOGCPHYS pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLOGCPHYS pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A /** Padding */
1N/A unsigned char Padding[7];
1N/A} AVLOGCPHYSNODECORE, *PAVLOGCPHYSNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLOGCPHYS AVLOGCPHYSTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLOGCPHYSTREE *PAVLOGCPHYSTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLOGCPHYSTREE *PPAVLOGCPHYSNODECORE;
1N/A
1N/A/** Callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLOGCPHYSCALLBACK(PAVLOGCPHYSNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvloGCPhysDoWithAll() and RTAvloGCPhysDestroy(). */
1N/Atypedef AVLOGCPHYSCALLBACK *PAVLOGCPHYSCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvloGCPhysInsert(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSNODECORE pNode);
1N/ARTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemove(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
1N/ARTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGet(PAVLOGCPHYSTREE pTree, RTGCPHYS Key);
1N/ARTDECL(int) RTAvloGCPhysDoWithAll(PAVLOGCPHYSTREE pTree, int fFromLeft, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysGetBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
1N/ARTDECL(PAVLOGCPHYSNODECORE) RTAvloGCPhysRemoveBestFit(PAVLOGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
1N/ARTDECL(int) RTAvloGCPhysDestroy(PAVLOGCPHYSTREE pTree, PAVLOGCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTGCPHYS ranges - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLROGCPHYS;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLROGCPhysNodeCore
1N/A{
1N/A /** First key value in the range (inclusive). */
1N/A RTGCPHYS Key;
1N/A /** Last key value in the range (inclusive). */
1N/A RTGCPHYS KeyLast;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLROGCPHYS pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLROGCPHYS pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A /** Padding */
1N/A unsigned char Padding[7];
1N/A} AVLROGCPHYSNODECORE, *PAVLROGCPHYSNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLROGCPHYS AVLROGCPHYSTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLROGCPHYSTREE *PAVLROGCPHYSTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLROGCPHYSTREE *PPAVLROGCPHYSNODECORE;
1N/A
1N/A/** Callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLROGCPHYSCALLBACK(PAVLROGCPHYSNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlroGCPhysDoWithAll() and RTAvlroGCPhysDestroy(). */
1N/Atypedef AVLROGCPHYSCALLBACK *PAVLROGCPHYSCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlroGCPhysInsert(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSNODECORE pNode);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeGet(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysRangeRemove(PAVLROGCPHYSTREE pTree, RTGCPHYS Key);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetBestFit(PAVLROGCPHYSTREE ppTree, RTGCPHYS Key, bool fAbove);
1N/ARTDECL(int) RTAvlroGCPhysDoWithAll(PAVLROGCPHYSTREE pTree, int fFromLeft, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlroGCPhysDestroy(PAVLROGCPHYSTREE pTree, PAVLROGCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRoot(PAVLROGCPHYSTREE pTree);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetLeft(PAVLROGCPHYSNODECORE pNode);
1N/ARTDECL(PAVLROGCPHYSNODECORE) RTAvlroGCPhysGetRight(PAVLROGCPHYSNODECORE pNode);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTGCPTRs.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLGCPtrNodeCore
1N/A{
1N/A /** Key value. */
1N/A RTGCPTR Key;
1N/A /** Pointer to the left node. */
1N/A struct _AVLGCPtrNodeCore *pLeft;
1N/A /** Pointer to the right node. */
1N/A struct _AVLGCPtrNodeCore *pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLGCPTRNODECORE, *PAVLGCPTRNODECORE, **PPAVLGCPTRNODECORE;
1N/A
1N/A/** A tree of RTGCPTR keys. */
1N/Atypedef PAVLGCPTRNODECORE AVLGCPTRTREE;
1N/A/** Pointer to a tree of RTGCPTR keys. */
1N/Atypedef PPAVLGCPTRNODECORE PAVLGCPTRTREE;
1N/A
1N/A/** Callback function for RTAvlGCPtrDoWithAll(). */
1N/Atypedef DECLCALLBACK(int) AVLGCPTRCALLBACK(PAVLGCPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlGCPtrDoWithAll(). */
1N/Atypedef AVLGCPTRCALLBACK *PAVLGCPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlGCPtrInsert(PAVLGCPTRTREE pTree, PAVLGCPTRNODECORE pNode);
1N/ARTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemove(PAVLGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGet(PAVLGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(int) RTAvlGCPtrDoWithAll(PAVLGCPTRTREE pTree, int fFromLeft, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrGetBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(PAVLGCPTRNODECORE) RTAvlGCPtrRemoveBestFit(PAVLGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(int) RTAvlGCPtrDestroy(PAVLGCPTRTREE pTree, PAVLGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTGCPTRs - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLOGCPTR;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLOGCPtrNodeCore
1N/A{
1N/A /** Key value. */
1N/A RTGCPTR Key;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLOGCPTR pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLOGCPTR pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 3];
1N/A} AVLOGCPTRNODECORE, *PAVLOGCPTRNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLOGCPTR AVLOGCPTRTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLOGCPTRTREE *PAVLOGCPTRTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLOGCPTRTREE *PPAVLOGCPTRNODECORE;
1N/A
1N/A/** Callback function for RTAvloGCPtrDoWithAll(). */
1N/Atypedef DECLCALLBACK(int) AVLOGCPTRCALLBACK(PAVLOGCPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvloGCPtrDoWithAll(). */
1N/Atypedef AVLOGCPTRCALLBACK *PAVLOGCPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvloGCPtrInsert(PAVLOGCPTRTREE pTree, PAVLOGCPTRNODECORE pNode);
1N/ARTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemove(PAVLOGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGet(PAVLOGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(int) RTAvloGCPtrDoWithAll(PAVLOGCPTRTREE pTree, int fFromLeft, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrGetBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(PAVLOGCPTRNODECORE) RTAvloGCPtrRemoveBestFit(PAVLOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(int) RTAvloGCPtrDestroy(PAVLOGCPTRTREE pTree, PAVLOGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTGCPTR ranges.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLRGCPtrNodeCore
1N/A{
1N/A /** First key value in the range (inclusive). */
1N/A RTGCPTR Key;
1N/A /** Last key value in the range (inclusive). */
1N/A RTGCPTR KeyLast;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A struct _AVLRGCPtrNodeCore *pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A struct _AVLRGCPtrNodeCore *pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLRGCPTRNODECORE, *PAVLRGCPTRNODECORE;
1N/A
1N/A/** A offset base tree with RTGCPTR keys. */
1N/Atypedef PAVLRGCPTRNODECORE AVLRGCPTRTREE;
1N/A/** Pointer to a offset base tree with RTGCPTR keys. */
1N/Atypedef AVLRGCPTRTREE *PAVLRGCPTRTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLRGCPTRTREE *PPAVLRGCPTRNODECORE;
1N/A
1N/A/** Callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLRGCPTRCALLBACK(PAVLRGCPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlrGCPtrDoWithAll() and RTAvlrGCPtrDestroy(). */
1N/Atypedef AVLRGCPTRCALLBACK *PAVLRGCPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlrGCPtrInsert( PAVLRGCPTRTREE pTree, PAVLRGCPTRNODECORE pNode);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetBestFit( PAVLRGCPTRTREE pTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeGet( PAVLRGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrRangeRemove( PAVLRGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(int) RTAvlrGCPtrDoWithAll( PAVLRGCPTRTREE pTree, int fFromLeft, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlrGCPtrDestroy( PAVLRGCPTRTREE pTree, PAVLRGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRoot( PAVLRGCPTRTREE pTree);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetLeft( PAVLRGCPTRNODECORE pNode);
1N/ARTDECL(PAVLRGCPTRNODECORE) RTAvlrGCPtrGetRight( PAVLRGCPTRNODECORE pNode);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTGCPTR ranges - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLROGCPTR;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLROGCPtrNodeCore
1N/A{
1N/A /** First key value in the range (inclusive). */
1N/A RTGCPTR Key;
1N/A /** Last key value in the range (inclusive). */
1N/A RTGCPTR KeyLast;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLROGCPTR pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLROGCPTR pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A unsigned char padding[GC_ARCH_BITS == 64 ? 7 : 7];
1N/A} AVLROGCPTRNODECORE, *PAVLROGCPTRNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLROGCPTR AVLROGCPTRTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLROGCPTRTREE *PAVLROGCPTRTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLROGCPTRTREE *PPAVLROGCPTRNODECORE;
1N/A
1N/A/** Callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLROGCPTRCALLBACK(PAVLROGCPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlroGCPtrDoWithAll() and RTAvlroGCPtrDestroy(). */
1N/Atypedef AVLROGCPTRCALLBACK *PAVLROGCPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlroGCPtrInsert(PAVLROGCPTRTREE pTree, PAVLROGCPTRNODECORE pNode);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetBestFit(PAVLROGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeGet(PAVLROGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrRangeRemove(PAVLROGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(int) RTAvlroGCPtrDoWithAll(PAVLROGCPTRTREE pTree, int fFromLeft, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlroGCPtrDestroy(PAVLROGCPTRTREE pTree, PAVLROGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRoot(PAVLROGCPTRTREE pTree);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetLeft(PAVLROGCPTRNODECORE pNode);
1N/ARTDECL(PAVLROGCPTRNODECORE) RTAvlroGCPtrGetRight(PAVLROGCPTRNODECORE pNode);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTGCPTR ranges (overlapping supported) - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLROOGCPTR;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLROOGCPtrNodeCore
1N/A{
1N/A /** First key value in the range (inclusive). */
1N/A RTGCPTR Key;
1N/A /** Last key value in the range (inclusive). */
1N/A RTGCPTR KeyLast;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLROOGCPTR pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLROOGCPTR pRight;
1N/A /** Pointer to the list of string with the same key. Don't touch. */
1N/A AVLROOGCPTR pList;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLROOGCPTRNODECORE, *PAVLROOGCPTRNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLROOGCPTR AVLROOGCPTRTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLROOGCPTRTREE *PAVLROOGCPTRTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLROOGCPTRTREE *PPAVLROOGCPTRNODECORE;
1N/A
1N/A/** Callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLROOGCPTRCALLBACK(PAVLROOGCPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlrooGCPtrDoWithAll() and RTAvlrooGCPtrDestroy(). */
1N/Atypedef AVLROOGCPTRCALLBACK *PAVLROOGCPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlrooGCPtrInsert(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRNODECORE pNode);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetBestFit(PAVLROOGCPTRTREE ppTree, RTGCPTR Key, bool fAbove);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeGet(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrRangeRemove(PAVLROOGCPTRTREE pTree, RTGCPTR Key);
1N/ARTDECL(int) RTAvlrooGCPtrDoWithAll(PAVLROOGCPTRTREE pTree, int fFromLeft, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlrooGCPtrDestroy(PAVLROOGCPTRTREE pTree, PAVLROOGCPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRoot(PAVLROOGCPTRTREE pTree);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetLeft(PAVLROOGCPTRNODECORE pNode);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetRight(PAVLROOGCPTRNODECORE pNode);
1N/ARTDECL(PAVLROOGCPTRNODECORE) RTAvlrooGCPtrGetNextEqual(PAVLROOGCPTRNODECORE pNode);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTUINTPTR.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL RTUINTPTR node core.
1N/A */
1N/Atypedef struct _AVLUIntPtrNodeCore
1N/A{
1N/A /** Key value. */
1N/A RTUINTPTR Key;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A struct _AVLUIntPtrNodeCore *pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A struct _AVLUIntPtrNodeCore *pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLUINTPTRNODECORE;
1N/A/** Pointer to a RTUINTPTR AVL node core.*/
1N/Atypedef AVLUINTPTRNODECORE *PAVLUINTPTRNODECORE;
1N/A
1N/A/** A pointer based tree with RTUINTPTR keys. */
1N/Atypedef PAVLUINTPTRNODECORE AVLUINTPTRTREE;
1N/A/** Pointer to a offset base tree with RTUINTPTR keys. */
1N/Atypedef AVLUINTPTRTREE *PAVLUINTPTRTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a pointer. */
1N/Atypedef AVLUINTPTRTREE *PPAVLUINTPTRNODECORE;
1N/A
1N/A/** Callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLUINTPTRCALLBACK(PAVLUINTPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlUIntPtrDoWithAll() and RTAvlUIntPtrDestroy(). */
1N/Atypedef AVLUINTPTRCALLBACK *PAVLUINTPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlUIntPtrInsert( PAVLUINTPTRTREE pTree, PAVLUINTPTRNODECORE pNode);
1N/ARTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrRemove( PAVLUINTPTRTREE pTree, RTUINTPTR Key);
1N/ARTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGet( PAVLUINTPTRTREE pTree, RTUINTPTR Key);
1N/ARTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetBestFit(PAVLUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
1N/ARTDECL(int) RTAvlUIntPtrDoWithAll( PAVLUINTPTRTREE pTree, int fFromLeft, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlUIntPtrDestroy( PAVLUINTPTRTREE pTree, PAVLUINTPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetRoot( PAVLUINTPTRTREE pTree);
1N/ARTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetLeft( PAVLUINTPTRNODECORE pNode);
1N/ARTDECL(PAVLUINTPTRNODECORE) RTAvlUIntPtrGetRight( PAVLUINTPTRNODECORE pNode);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTUINTPTR ranges.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL RTUINTPTR range node core.
1N/A */
1N/Atypedef struct _AVLRUIntPtrNodeCore
1N/A{
1N/A /** First key value in the range (inclusive). */
1N/A RTUINTPTR Key;
1N/A /** Last key value in the range (inclusive). */
1N/A RTUINTPTR KeyLast;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A struct _AVLRUIntPtrNodeCore *pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A struct _AVLRUIntPtrNodeCore *pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLRUINTPTRNODECORE;
1N/A/** Pointer to an AVL RTUINTPTR range node code. */
1N/Atypedef AVLRUINTPTRNODECORE *PAVLRUINTPTRNODECORE;
1N/A
1N/A/** A pointer based tree with RTUINTPTR ranges. */
1N/Atypedef PAVLRUINTPTRNODECORE AVLRUINTPTRTREE;
1N/A/** Pointer to a pointer based tree with RTUINTPTR ranges. */
1N/Atypedef AVLRUINTPTRTREE *PAVLRUINTPTRTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a pointer. */
1N/Atypedef AVLRUINTPTRTREE *PPAVLRUINTPTRNODECORE;
1N/A
1N/A/** Callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLRUINTPTRCALLBACK(PAVLRUINTPTRNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlrUIntPtrDoWithAll() and RTAvlrUIntPtrDestroy(). */
1N/Atypedef AVLRUINTPTRCALLBACK *PAVLRUINTPTRCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlrUIntPtrInsert( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRNODECORE pNode);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRemove( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetBestFit( PAVLRUINTPTRTREE pTree, RTUINTPTR Key, bool fAbove);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeGet( PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrRangeRemove(PAVLRUINTPTRTREE pTree, RTUINTPTR Key);
1N/ARTDECL(int) RTAvlrUIntPtrDoWithAll( PAVLRUINTPTRTREE pTree, int fFromLeft, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlrUIntPtrDestroy( PAVLRUINTPTRTREE pTree, PAVLRUINTPTRCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRoot( PAVLRUINTPTRTREE pTree);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetLeft( PAVLRUINTPTRNODECORE pNode);
1N/ARTDECL(PAVLRUINTPTRNODECORE) RTAvlrUIntPtrGetRight( PAVLRUINTPTRNODECORE pNode);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTHCPHYSes - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLOHCPHYS;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLOHCPhysNodeCore
1N/A{
1N/A /** Key value. */
1N/A RTHCPHYS Key;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLOHCPHYS pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLOHCPHYS pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A#if HC_ARCH_BITS == 64 || GC_ARCH_BITS == 64
1N/A unsigned char Padding[7]; /**< Alignment padding. */
1N/A#endif
1N/A} AVLOHCPHYSNODECORE, *PAVLOHCPHYSNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLOHCPHYS AVLOHCPHYSTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLOHCPHYSTREE *PAVLOHCPHYSTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLOHCPHYSTREE *PPAVLOHCPHYSNODECORE;
1N/A
1N/A/** Callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLOHCPHYSCALLBACK(PAVLOHCPHYSNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvloHCPhysDoWithAll() and RTAvloHCPhysDestroy(). */
1N/Atypedef AVLOHCPHYSCALLBACK *PAVLOHCPHYSCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvloHCPhysInsert(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSNODECORE pNode);
1N/ARTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemove(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
1N/ARTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGet(PAVLOHCPHYSTREE pTree, RTHCPHYS Key);
1N/ARTDECL(int) RTAvloHCPhysDoWithAll(PAVLOHCPHYSTREE pTree, int fFromLeft, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysGetBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
1N/ARTDECL(PAVLOHCPHYSNODECORE) RTAvloHCPhysRemoveBestFit(PAVLOHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
1N/ARTDECL(int) RTAvloHCPhysDestroy(PAVLOHCPHYSTREE pTree, PAVLOHCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A
1N/A/** AVL tree of RTIOPORTs - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLOIOPORTPTR;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLOIOPortNodeCore
1N/A{
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLOIOPORTPTR pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLOIOPORTPTR pRight;
1N/A /** Key value. */
1N/A RTIOPORT Key;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLOIOPORTNODECORE, *PAVLOIOPORTNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLOIOPORTPTR AVLOIOPORTTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLOIOPORTTREE *PAVLOIOPORTTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLOIOPORTTREE *PPAVLOIOPORTNODECORE;
1N/A
1N/A/** Callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLOIOPORTCALLBACK(PAVLOIOPORTNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvloIOPortDoWithAll() and RTAvloIOPortDestroy(). */
1N/Atypedef AVLOIOPORTCALLBACK *PAVLOIOPORTCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvloIOPortInsert(PAVLOIOPORTTREE pTree, PAVLOIOPORTNODECORE pNode);
1N/ARTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemove(PAVLOIOPORTTREE pTree, RTIOPORT Key);
1N/ARTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGet(PAVLOIOPORTTREE pTree, RTIOPORT Key);
1N/ARTDECL(int) RTAvloIOPortDoWithAll(PAVLOIOPORTTREE pTree, int fFromLeft, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortGetBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
1N/ARTDECL(PAVLOIOPORTNODECORE) RTAvloIOPortRemoveBestFit(PAVLOIOPORTTREE ppTree, RTIOPORT Key, bool fAbove);
1N/ARTDECL(int) RTAvloIOPortDestroy(PAVLOIOPORTTREE pTree, PAVLOIOPORTCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTIOPORT ranges - using relative offsets internally.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef int32_t AVLROIOPORTPTR;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLROIOPortNodeCore
1N/A{
1N/A /** First key value in the range (inclusive). */
1N/A RTIOPORT Key;
1N/A /** Last key value in the range (inclusive). */
1N/A RTIOPORT KeyLast;
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLROIOPORTPTR pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLROIOPORTPTR pRight;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLROIOPORTNODECORE, *PAVLROIOPORTNODECORE;
1N/A
1N/A/** A offset base tree with uint32_t keys. */
1N/Atypedef AVLROIOPORTPTR AVLROIOPORTTREE;
1N/A/** Pointer to a offset base tree with uint32_t keys. */
1N/Atypedef AVLROIOPORTTREE *PAVLROIOPORTTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLROIOPORTTREE *PPAVLROIOPORTNODECORE;
1N/A
1N/A/** Callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLROIOPORTCALLBACK(PAVLROIOPORTNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlroIOPortDoWithAll() and RTAvlroIOPortDestroy(). */
1N/Atypedef AVLROIOPORTCALLBACK *PAVLROIOPORTCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlroIOPortInsert(PAVLROIOPORTTREE pTree, PAVLROIOPORTNODECORE pNode);
1N/ARTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
1N/ARTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
1N/ARTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeGet(PAVLROIOPORTTREE pTree, RTIOPORT Key);
1N/ARTDECL(PAVLROIOPORTNODECORE) RTAvlroIOPortRangeRemove(PAVLROIOPORTTREE pTree, RTIOPORT Key);
1N/ARTDECL(int) RTAvlroIOPortDoWithAll(PAVLROIOPORTTREE pTree, int fFromLeft, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(int) RTAvlroIOPortDestroy(PAVLROIOPORTTREE pTree, PAVLROIOPORTCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** AVL tree of RTHCPHYSes.
1N/A * @{
1N/A */
1N/A
1N/A/**
1N/A * AVL 'pointer' type for the relative offset pointer scheme.
1N/A */
1N/Atypedef struct _AVLHCPhysNodeCore *AVLHCPHYSPTR;
1N/A
1N/A/**
1N/A * AVL Core node.
1N/A */
1N/Atypedef struct _AVLHCPhysNodeCore
1N/A{
1N/A /** Offset to the left leaf node, relative to this field. */
1N/A AVLHCPHYSPTR pLeft;
1N/A /** Offset to the right leaf node, relative to this field. */
1N/A AVLHCPHYSPTR pRight;
1N/A /** Key value. */
1N/A RTHCPHYS Key;
1N/A /** Height of this tree: max(height(left), height(right)) + 1 */
1N/A unsigned char uchHeight;
1N/A} AVLHCPHYSNODECORE, *PAVLHCPHYSNODECORE;
1N/A
1N/A/** A offset base tree with RTHCPHYS keys. */
1N/Atypedef AVLHCPHYSPTR AVLHCPHYSTREE;
1N/A/** Pointer to a offset base tree with RTHCPHYS keys. */
1N/Atypedef AVLHCPHYSTREE *PAVLHCPHYSTREE;
1N/A
1N/A/** Pointer to an internal tree pointer.
1N/A * In this case it's a pointer to a relative offset. */
1N/Atypedef AVLHCPHYSTREE *PPAVLHCPHYSNODECORE;
1N/A
1N/A/** Callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
1N/Atypedef DECLCALLBACK(int) AVLHCPHYSCALLBACK(PAVLHCPHYSNODECORE pNode, void *pvUser);
1N/A/** Pointer to callback function for RTAvlHCPhysDoWithAll() and RTAvlHCPhysDestroy(). */
1N/Atypedef AVLHCPHYSCALLBACK *PAVLHCPHYSCALLBACK;
1N/A
1N/ARTDECL(bool) RTAvlHCPhysInsert(PAVLHCPHYSTREE pTree, PAVLHCPHYSNODECORE pNode);
1N/ARTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemove(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
1N/ARTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGet(PAVLHCPHYSTREE pTree, RTHCPHYS Key);
1N/ARTDECL(int) RTAvlHCPhysDoWithAll(PAVLHCPHYSTREE pTree, int fFromLeft, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/ARTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysGetBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
1N/ARTDECL(PAVLHCPHYSNODECORE) RTAvlHCPhysRemoveBestFit(PAVLHCPHYSTREE ppTree, RTHCPHYS Key, bool fAbove);
1N/ARTDECL(int) RTAvlHCPhysDestroy(PAVLHCPHYSTREE pTree, PAVLHCPHYSCALLBACK pfnCallBack, void *pvParam);
1N/A
1N/A/** @} */
1N/A
1N/A
1N/A/** @} */
1N/A
1N/ART_C_DECLS_END
1N/A
1N/A#endif
1N/A
1N/A