Ignore:
Timestamp:
Aug 26, 2007, 12:43:27 PM (18 years ago)
Author:
bird
Message:

Merging in kAvl enhancements, doing some config simplications and made them inlineable.

File:
1 edited

Legend:

Unmodified
Added
Removed

  • trunk/kStuff/include/k/kAVLTmpl/kAVLBase.h

    r3553 r3555  
    11/* $Id$ */
    22/** @file
    3  *
    4  * kAVLBase - basic routines for all AVL trees.
    5  *
    6  * Copyright (c) 2001-2002 knut st. osmundsen (bird@anduin.net)
    7  *
    8  * GPL
    9  */
    10 
    11 #ifndef _kAVLBase_h_
    12 #define _kAVLBase_h_
    13 
    14 
    15 /** @design kAVL Template configuration.
    16  *  This is a template made to implemented multiple AVL trees. The difference
    17  *  between the implementations are related to the key used.
    18  *
    19  *  #define KAVL_FN
    20  *  Use this to altern the names of the AVL functions.
    21  *  Must be defined.
    22  *
    23  *  #define KAVL_EQUAL_ALLOWED
     3 * kAVLTmpl - Templated AVL Trees, The Mandatory Base Code.
     4 */
     5
     6/*
     7 * Copyright (c) 2001-2007 knut st. osmundsen <bird-src-spam@anduin.net>
     8 *
     9 * This file is part of kStuff.
     10 *
     11 * kStuff is free software; you can redistribute it and/or
     12 * modify it under the terms of the GNU Lesser General Public
     13 * License as published by the Free Software Foundation; either
     14 * version 2.1 of the License, or (at your option) any later version.
     15 *
     16 * kStuff is distributed in the hope that it will be useful,
     17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
     18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     19 * Lesser General Public License for more details.
     20 *
     21 * You should have received a copy of the GNU Lesser General Public
     22 * License along with kStuff; if not, write to the Free Software
     23 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
     24 *
     25 */
     26
     27
     28/** @page pg_kAVLTmpl   Template Configuration.
     29 *
     30 *  This is a templated implementation of AVL trees in C. The template
     31 *  parameters relates to the kind of key used and how duplicates are
     32 *  treated.
     33 *
     34 *  \#define KAVL_EQUAL_ALLOWED
    2435 *  Define this to tell us that equal keys are allowed.
    25  *  Then Equal keys will be put a list pointed to by pList in the KAVLNODECORE.
     36 *  Then Equal keys will be put in a list pointed to by KAVLNODECORE::pList.
    2637 *  This is by default not defined.
    2738 *
    28  *  #define KAVL_CHECK_FOR_EQUAL_INSERT
     39 *  \#define KAVL_CHECK_FOR_EQUAL_INSERT
    2940 *  Define this to enable insert check for equal nodes.
    3041 *  This is by default not defined.
    3142 *
    32  *  #define KAVL_MAX_STACK
    33  *  Use this to specify the number of stack entries the stack we uses when inserting
    34  *  and removing nodes from the tree will need. I think the size should be about
     43 *  \#define KAVL_MAX_STACK
     44 *  Use this to specify the max number of stack entries the stack will use when inserting
     45 *  and removing nodes from the tree. The size should be something like
    3546 *      log2(<max nodes>) + 3
    3647 *  Must be defined.
    3748 *
    38  */
     49 *  \#define KAVL_RANGE
     50 *  Define this to enable key ranges.
     51 *
     52 *  \#define KAVL_OFFSET
     53 *  Define this to link the tree together using self relative offset
     54 *  instead of memory pointers, thus making the entire tree relocatable
     55 *  provided all the nodes - including the root node variable - are moved
     56 *  the exact same distance.
     57 *
     58 *  \#define KAVLKEY
     59 *  Define this to the name of the AVL key type.
     60 *
     61 *  \#define KAVL_STD_KEY_COMP
     62 *  Define this to use the standard key compare macros. If not set all the
     63 *  compare operations for KAVLKEY have to be defined: KAVL_G, KAVL_E, KAVL_NE,
     64 *  KAVL_R_IS_IDENTICAL, KAVL_R_IS_INTERSECTING and KAVL_R_IS_IN_RANGE. The latter
     65 *  three are only required when KAVL_RANGE is defined.
     66 *
     67 *  \#define KAVLNODECORE
     68 *  Define this to the name (typedef) of the AVL core node structure. This
     69 *  structure must have a pLeft, pRight, Key and uchHeight member.
     70 *  If KAVL_RANGE is defined a  KeyLast is also required.
     71 *  If KAVL_EQUAL_ALLOWED is defined a pList member is required.
     72 *
     73 *  \#define KAVLTREEPTR
     74 *  Define this to the name (typedef) of the tree pointer type. This is
     75 *  required when KAVL_OFFSET is defined. When not defined it defaults
     76 *  to KAVLNODECORE *.
     77 *
     78 *  \#define KAVL_FN
     79 *  Use this to alter the names of the AVL functions.
     80 *  Must be defined.
     81 *
     82 *  \#define KAVL_TYPE(prefix, name)
     83 *  Use this to make external type names and unique. The prefix may be empty.
     84 *  Must be defined.
     85 *
     86 *  \#define KAVL_INT(name)
     87 *  Use this to make internal type names and unique. The prefix may be empty.
     88 *  Must be defined.
     89 *
     90 *  \#define KAVL_DECL(rettype)
     91 *  Function declaration macro that should be set according to the scope
     92 *  the instantiated template should have. For instance an inlined scope
     93 *  (private or public) should K_DECL_INLINE(rettype) here.
     94 *
     95 *  typedef KAVL_TYPE(PFN,CALLBACK)
     96 *  kAVLDoWithAll requires KAVL_TYPE(PFN,CALLBACK) to be a function pointer
     97 *  to a callback suitable for the DoWithAll method.
     98 *
     99 *
     100 *  This version of the kAVL tree offers the option of inlining the entire
     101 *  implementation. This depends on the compiler doing a decent job in both
     102 *  making use of the inlined code and to eliminate const variables.
     103 */
     104
     105
     106/*******************************************************************************
     107*   Internal Functions                                                         *
     108*******************************************************************************/
     109#include <k/kDefs.h>
     110#include <k/kTypes.h>
     111#include <k/kHlpAssert.h>
     112
    39113
    40114/*******************************************************************************
    41115*   Defined Constants And Macros                                               *
    42116*******************************************************************************/
    43 #define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
     117#define KAVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? (pNode)->uchHeight : 0))
     118
     119/** @def KAVL_GET_POINTER
     120 * Reads a 'pointer' value.
     121 *
     122 * @returns The native pointer.
     123 * @param   pp      Pointer to the pointer to read.
     124 * @internal
     125 */
     126
     127/** @def KAVL_GET_POINTER_NULL
     128 * Reads a 'pointer' value which can be KAVL_NULL.
     129 *
     130 * @returns The native pointer.
     131 * @returns NULL pointer if KAVL_NULL.
     132 * @param   pp      Pointer to the pointer to read.
     133 * @internal
     134 */
     135
     136/** @def KAVL_SET_POINTER
     137 * Writes a 'pointer' value.
     138 * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
     139 *
     140 * @returns stored pointer.
     141 * @param   pp      Pointer to where to store the pointer.
     142 * @param   p       Native pointer to assign to *pp.
     143 * @internal
     144 */
     145
     146/** @def KAVL_SET_POINTER_NULL
     147 * Writes a 'pointer' value which can be KAVL_NULL.
     148 *
     149 * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
     150 * if p is not KAVL_NULL of course.
     151 *
     152 * @returns stored pointer.
     153 * @param   pp      Pointer to where to store the pointer.
     154 * @param   pp2     Pointer to where to pointer to assign to pp. This can be KAVL_NULL
     155 * @internal
     156 */
     157
     158#ifndef KAVLTREEPTR
     159# define KAVLTREEPTR                        KAVLNODECORE *
     160#endif
     161
     162#ifdef KAVL_OFFSET
     163# define KAVL_GET_POINTER(pp)               ( (KAVLNODECORE *)((KIPTR)(pp) + *(pp)) )
     164# define KAVL_GET_POINTER_NULL(pp)          ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
     165# define KAVL_SET_POINTER(pp, p)            ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
     166# define KAVL_SET_POINTER_NULL(pp, pp2)     ( (*(pp)) = *(pp2) != KAVL_NULL ? (KIPTR)KAVL_GET_POINTER(pp2) - (KIPTR)(pp) : KAVL_NULL )
     167#else
     168# define KAVL_GET_POINTER(pp)               ( *(pp) )
     169# define KAVL_GET_POINTER_NULL(pp)          ( *(pp) )
     170# define KAVL_SET_POINTER(pp, p)            ( (*(pp)) = (p) )
     171# define KAVL_SET_POINTER_NULL(pp, pp2)     ( (*(pp)) = *(pp2) )
     172#endif
     173
     174
     175/** @def KAVL_NULL
     176 * The NULL 'pointer' equivalent.
     177 */
     178#ifdef KAVL_OFFSET
     179# define KAVL_NULL     0
     180#else
     181# define KAVL_NULL     NULL
     182#endif
     183
     184#ifdef KAVL_STD_KEY_COMP
     185# define KAVL_G(key1, key2)                 ( (key1) >  (key2) )
     186# define KAVL_E(key1, key2)                 ( (key1) == (key2) )
     187# define KAVL_NE(key1, key2)                ( (key1) != (key2) )
     188# ifdef KAVL_RANGE
     189#  define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)       ( (key1B) == (key2B) && (key1E) == (key2E) )
     190#  define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)    ( (key1B) <= (key2E) && (key1E) >= (key2B) )
     191#  define KAVL_R_IS_IN_RANGE(key1B, key1E, key2)                KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
     192# endif
     193#endif
     194
     195#ifndef KAVL_RANGE
     196# define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)     KAVL_E(key1B, key2B)
     197# define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)        KAVL_E(key1B, key2B)
     198#endif
     199
    44200
    45201
    … …  
    48204*******************************************************************************/
    49205/*
    50  * A stack used to avoid recursive calls...
    51  */
    52 typedef struct _kAvlStack
     206 * Two stacks that's used to avoid recursive calls.
     207 */
     208typedef struct
    53209{
    54210    unsigned        cEntries;
    55     PPKAVLNODECORE  aEntries[KAVL_MAX_STACK];
    56 } KAVLSTACK, *PKAVLSTACK;
    57 
    58 typedef struct _kAvlStack2
     211    KAVLTREEPTR    *aEntries[KAVL_MAX_STACK];
     212} KAVL_INT(STACK);
     213
     214typedef struct
    59215{
    60216    unsigned        cEntries;
    61     PKAVLNODECORE   aEntries[KAVL_MAX_STACK];
     217    KAVLNODECORE   *aEntries[KAVL_MAX_STACK];
    62218    char            achFlags[KAVL_MAX_STACK];
    63 } KAVLSTACK2, *PLAVLSTACK2;
    64 
    65 
    66 /*******************************************************************************
    67 *   Internal Functions                                                         *
    68 *******************************************************************************/
    69 KINLINE void KAVL_FN(Rebalance)(PKAVLSTACK pStack);
    70 
    71 
     219} KAVL_INT(STACK2);
     220
     221
     222/**
     223 * Rewinds a stack of node pointer pointers, rebalancing the tree.
     224 *
     225 * @param     pStack  Pointer to stack to rewind.
     226 * @sketch    LOOP thru all stack entries
     227 *            BEGIN
     228 *                Get pointer to pointer to node (and pointer to node) from the stack.
     229 *                IF 2 higher left subtree than in right subtree THEN
     230 *                BEGIN
     231 *                    IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
     232 *                                *                       n+2|n+3
     233 *                              /   \                     /     \
     234 *                            n+2    n       ==>         n+1   n+1|n+2
     235 *                           /   \                             /     \
     236 *                         n+1 n|n+1                          n|n+1  n
     237 *
     238 *                         Or with keys:
     239 *
     240 *                               4                           2
     241 *                             /   \                       /   \
     242 *                            2     5        ==>          1     4
     243 *                           / \                               / \
     244 *                          1   3                             3   5
     245 *
     246 *                    ELSE
     247 *                                *                         n+2
     248 *                              /   \                      /   \
     249 *                            n+2    n                   n+1   n+1
     250 *                           /   \           ==>        /  \   /  \
     251 *                          n    n+1                    n  L   R   n
     252 *                               / \
     253 *                              L   R
     254 *
     255 *                         Or with keys:
     256 *                               6                           4
     257 *                             /   \                       /   \
     258 *                            2     7        ==>          2     6
     259 *                          /   \                       /  \  /  \
     260 *                          1    4                      1  3  5  7
     261 *                              / \
     262 *                             3   5
     263 *                END
     264 *                ELSE IF 2 higher in right subtree than in left subtree THEN
     265 *                BEGIN
     266 *                    Same as above but left <==> right. (invert the picture)
     267 *                ELSE
     268 *                    IF correct height THEN break
     269 *                    ELSE correct height.
     270 *            END
     271 */
     272K_DECL_INLINE(void) KAVL_FN(Rebalance)(KAVL_INT(STACK) *pStack)
     273{
     274    while (pStack->cEntries > 0)
     275    {
     276        KAVLTREEPTR     *ppNode = pStack->aEntries[--pStack->cEntries];
     277        KAVLNODECORE    *pNode = KAVL_GET_POINTER(ppNode);
     278        KAVLNODECORE    *pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
     279        unsigned char    uchLeftHeight = KAVL_HEIGHTOF(pLeftNode);
     280        KAVLNODECORE    *pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
     281        unsigned char    uchRightHeight = KAVL_HEIGHTOF(pRightNode);
     282
     283        if (uchRightHeight + 1 < uchLeftHeight)
     284        {
     285            KAVLNODECORE    *pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
     286            KAVLNODECORE    *pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
     287            unsigned char    uchLeftRightHeight = KAVL_HEIGHTOF(pLeftRightNode);
     288
     289            if (KAVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
     290            {
     291                KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
     292                KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
     293                pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
     294                KAVL_SET_POINTER(ppNode, pLeftNode);
     295            }
     296            else
     297            {
     298                KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
     299                KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
     300                KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
     301                KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
     302                pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
     303                pLeftRightNode->uchHeight = uchLeftHeight;
     304                KAVL_SET_POINTER(ppNode, pLeftRightNode);
     305            }
     306        }
     307        else if (uchLeftHeight + 1 < uchRightHeight)
     308        {
     309            KAVLNODECORE    *pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
     310            unsigned char    uchRightLeftHeight = KAVL_HEIGHTOF(pRightLeftNode);
     311            KAVLNODECORE    *pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
     312
     313            if (KAVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
     314            {
     315                KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
     316                KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
     317                pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
     318                KAVL_SET_POINTER(ppNode, pRightNode);
     319            }
     320            else
     321            {
     322                KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
     323                KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
     324                KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
     325                KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
     326                pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
     327                pRightLeftNode->uchHeight = uchRightHeight;
     328                KAVL_SET_POINTER(ppNode, pRightLeftNode);
     329            }
     330        }
     331        else
     332        {
     333            register unsigned char uchHeight = (unsigned char)(K_MAX(uchLeftHeight, uchRightHeight) + 1);
     334            if (uchHeight == pNode->uchHeight)
     335                break;
     336            pNode->uchHeight = uchHeight;
     337        }
     338    }
     339
     340}
    72341
    73342
    … …  
    78347 * @param     ppTree  Pointer to the AVL-tree root node pointer.
    79348 * @param     pNode   Pointer to the node which is to be added.
    80  * @sketch    Find the location of the node (using binary three algorithm.):
     349 * @sketch    Find the location of the node (using binary tree algorithm.):
    81350 *            LOOP until NULL leaf pointer
    82351 *            BEGIN
    … …  
    89358 *            Fill in leaf node and insert it.
    90359 *            Rebalance the tree.
    91  * @status    completely implemented.
    92  * @author    knut st. osmundsen
    93  */
    94 KBOOL KLIBCALL KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
     360 */
     361KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
    95362{
    96     KLOGENTRY2("KBOOL","PPKAVLNODECORE ppTree, PKAVLNODECORE pNode", ppTree, pNode);
    97     KAVLSTACK               AVLStack;
    98     PPKAVLNODECORE          ppCurNode = ppTree;
     363    KAVL_INT(STACK)        AVLStack;
     364    KAVLTREEPTR            *ppCurNode = ppTree;
    99365    register KAVLKEY        Key = pNode->Key;
    100     register PKAVLNODECORE  pCurNode;
     366#ifdef KAVL_RANGE
     367    register KAVLKEY        KeyLast = pNode->KeyLast;
     368#endif
     369    register KAVLNODECORE  *pCurNode;
    101370
    102371    AVLStack.cEntries = 0;
    103372
    104     while ((pCurNode = *ppCurNode) != NULL)
     373#ifdef KAVL_RANGE
     374    if (Key > KeyLast)
     375        return false;
     376#else
     377    K_NOREF(Key);
     378#endif
     379
     380    while (*ppCurNode != KAVL_NULL)
    105381    {
    106         kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
     382        pCurNode = KAVL_GET_POINTER(ppCurNode);
     383
     384        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
    107385        AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
    108         #ifndef KAVL_EQUAL_ALLOWED
    109         if (AVL_G(pCurNode->Key, Key))
    110             ppCurNode = &pCurNode->pLeft;
    111         else
    112             ppCurNode = &pCurNode->pRight;
    113         #else
    114         if (AVL_G(pCurNode->Key, Key))
    115             ppCurNode = &pCurNode->pLeft;
    116         else if (AVL_L(pCurNode->Key, Key))
    117             ppCurNode = &pCurNode->pRight;
    118         else
     386#ifdef KAVL_EQUAL_ALLOWED
     387        if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
    119388        {
    120389            /*
    121390             * If equal then we'll use a list of equal nodes.
    122391             */
    123             pNode->pLeft = pNode->pRight = NULL;
     392            pNode->pLeft = pNode->pRight = KAVL_NULL;
    124393            pNode->uchHeight = 0;
    125             pNode->pList = pCurNode->pList;
    126             pCurNode->pList = pNode;
    127             KLOGEXIT(FALSE);
    128             return TRUE;
     394            KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
     395            KAVL_SET_POINTER(&pCurNode->pList, pNode);
     396            return K_TRUE;
    129397        }
    130         #endif
     398#endif
     399#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
     400        if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
     401            return K_FALSE;
     402#endif
     403        if (KAVL_G(pCurNode->Key, Key))
     404            ppCurNode = &pCurNode->pLeft;
     405        else
     406            ppCurNode = &pCurNode->pRight;
    131407    }
    132408
    133 #ifdef KAVL_CHECK_FOR_EQUAL_INSERT
    134     /*
    135      * Fail if equal insert was attempted.
    136      */
    137     if (AVLStack.cEntries > 0 && AVL_E((*AVLStack.aEntries[AVLStack.cEntries-1])->Key, pNode->Key))
    138     {
    139         KLOGEXIT(FALSE);
    140         return FALSE;
    141     }
    142 #endif
    143 
    144     #ifndef KAVL_EQUAL_ALLOWED
    145     pNode->pLeft = pNode->pRight = NULL;
    146     #else
    147     pNode->pList = pNode->pLeft = pNode->pRight = NULL;
    148     #endif
     409    pNode->pLeft = pNode->pRight = KAVL_NULL;
     410#ifdef KAVL_EQUAL_ALLOWED
     411    pNode->pList = KAVL_NULL;
     412#endif
    149413    pNode->uchHeight = 1;
    150     *ppCurNode = pNode;
    151 
    152     KAVL_FN(Rebalance)(SSToDS(&AVLStack));
    153     KLOGEXIT(TRUE);
    154     return TRUE;
     414    KAVL_SET_POINTER(ppCurNode, pNode);
     415
     416    KAVL_FN(Rebalance)(&AVLStack);
     417    return K_TRUE;
    155418}
    156419
    … …  
    194457 *            END
    195458 *            return pointer to the removed node (if found).
    196  * @status    completely implemented.
    197  * @author    knut st. osmundsen
    198  */
    199 PKAVLNODECORE KLIBCALL KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
     459 */
     460KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
    200461{
    201     KLOGENTRY2("PKAVLNODECORE","PPKAVLNODECORE ppTree, KAVLKEY Key", ppTree, Key);
    202     KAVLSTACK                AVLStack;
    203     PPKAVLNODECORE           ppDeleteNode = ppTree;
    204     register PKAVLNODECORE   pDeleteNode;
     462    KAVL_INT(STACK)         AVLStack;
     463    KAVLTREEPTR             *ppDeleteNode = ppTree;
     464    register KAVLNODECORE   *pDeleteNode;
    205465
    206466    AVLStack.cEntries = 0;
    207467
    208     while ((pDeleteNode = *ppDeleteNode) != NULL)
     468    for (;;)
    209469    {
    210         kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
     470        if (*ppDeleteNode == KAVL_NULL)
     471            return NULL;
     472        pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
     473
     474        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
    211475        AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
    212         #ifndef AVL_CMP
    213         if (AVL_E(pDeleteNode->Key, Key))
     476        if (KAVL_E(pDeleteNode->Key, Key))
    214477            break;
    215478
    216         if (AVL_G(pDeleteNode->Key, Key))
     479        if (KAVL_G(pDeleteNode->Key, Key))
    217480            ppDeleteNode = &pDeleteNode->pLeft;
    218481        else
    219482            ppDeleteNode = &pDeleteNode->pRight;
    220         #else
     483    }
     484
     485    if (pDeleteNode->pLeft != KAVL_NULL)
     486    {
     487        /* find the rightmost node in the left tree. */
     488        const unsigned          iStackEntry = AVLStack.cEntries;
     489        KAVLTREEPTR            *ppLeftLeast = &pDeleteNode->pLeft;
     490        register KAVLNODECORE  *pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
     491
     492        while (pLeftLeast->pRight != KAVL_NULL)
    221493        {
    222         int register iDiff;
    223         if ((iDiff = AVL_CMP(pDeleteNode->Key, Key)) == 0)
    224             break;
    225 
    226         if (iDiff > 0)
    227             ppDeleteNode = &pDeleteNode->pLeft;
    228         else
    229             ppDeleteNode = &pDeleteNode->pRight;
     494            kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
     495            AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
     496            ppLeftLeast = &pLeftLeast->pRight;
     497            pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
    230498        }
    231         #endif
     499
     500        /* link out pLeftLeast */
     501        KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
     502
     503        /* link it in place of the delete node. */
     504        KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
     505        KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
     506        pLeftLeast->uchHeight = pDeleteNode->uchHeight;
     507        KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
     508        AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
    232509    }
    233 
    234     if (pDeleteNode != NULL)
     510    else
    235511    {
    236         if (pDeleteNode->pLeft != NULL)
    237         {
    238             unsigned                iStackEntry = AVLStack.cEntries;
    239             PPKAVLNODECORE           ppLeftLeast = &pDeleteNode->pLeft;
    240             register PKAVLNODECORE   pLeftLeast;
    241 
    242             while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
    243             {
    244                 kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
    245                 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
    246                 ppLeftLeast = &pLeftLeast->pRight;
    247                 pLeftLeast  = pLeftLeast->pRight;
    248             }
    249 
    250             /* link out pLeftLeast */
    251             *ppLeftLeast = pLeftLeast->pLeft;
    252 
    253             /* link in place of the delete node. */
    254             pLeftLeast->pLeft = pDeleteNode->pLeft;
    255             pLeftLeast->pRight = pDeleteNode->pRight;
    256             pLeftLeast->uchHeight = pDeleteNode->uchHeight;
    257             *ppDeleteNode = pLeftLeast;
    258             AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
    259         }
    260         else
    261         {
    262             *ppDeleteNode = pDeleteNode->pRight;
    263             AVLStack.cEntries--;
    264         }
    265 
    266         KAVL_FN(Rebalance)(SSToDS(&AVLStack));
     512        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
     513        AVLStack.cEntries--;
    267514    }
    268515
    269     KLOGEXIT(pDeleteNode);
     516    KAVL_FN(Rebalance)(&AVLStack);
    270517    return pDeleteNode;
    271518}
    272519
    273 
    274 /**
    275  * Rewindes a stack of pointer to pointers to nodes, rebalancing the tree.
    276  * @param     pStack  Pointer to stack to rewind.
    277  * @sketch    LOOP thru all stack entries
    278  *            BEGIN
    279  *                Get pointer to pointer to node (and pointer to node) from stack.
    280  *                IF 2 higher left subtree than in right subtree THEN
    281  *                BEGIN
    282  *                    IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
    283  *                                *                       n+2|n+3
    284  *                              /   \                     /     \
    285  *                            n+2    n       ==>         n+1   n+1|n+2
    286  *                           /   \                             /     \
    287  *                         n+1 n|n+1                          n|n+1  n
    288  *
    289  *                         Or with keys:
    290  *
    291  *                               4                           2
    292  *                             /   \                       /   \
    293  *                            2     5        ==>          1     4
    294  *                           / \                               / \
    295  *                          1   3                             3   5
    296  *
    297  *                    ELSE
    298  *                                *                         n+2
    299  *                              /   \                      /   \
    300  *                            n+2    n                   n+1   n+1
    301  *                           /   \           ==>        /  \   /  \
    302  *                          n    n+1                    n  L   R   n
    303  *                               / \
    304  *                              L   R
    305  *
    306  *                         Or with keys:
    307  *                               6                           4
    308  *                             /   \                       /   \
    309  *                            2     7        ==>          2     6
    310  *                          /   \                       /  \  /  \
    311  *                          1    4                      1  3  5  7
    312  *                              / \
    313  *                             3   5
    314  *                END
    315  *                ELSE IF 2 higher in right subtree than in left subtree THEN
    316  *                BEGIN
    317  *                    Same as above but left <==> right. (invert the picture)
    318  *                ELSE
    319  *                    IF correct height THEN break
    320  *                    ELSE correct height.
    321  *            END
    322  * @status
    323  * @author    knut st. osmundsen
    324  * @remark
    325  */
    326 KINLINE void KAVL_FN(Rebalance)(PKAVLSTACK pStack)
    327 {
    328     KLOGENTRY1("void","PKAVLSTACK pStack", pStack);
    329     while (pStack->cEntries > 0)
    330     {
    331         PPKAVLNODECORE   ppNode = pStack->aEntries[--pStack->cEntries];
    332         PKAVLNODECORE    pNode = *ppNode;
    333         PKAVLNODECORE    pLeftNode = pNode->pLeft;
    334         unsigned char   uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
    335         PKAVLNODECORE    pRightNode = pNode->pRight;
    336         unsigned char   uchRightHeight = AVL_HEIGHTOF(pRightNode);
    337 
    338         if (uchRightHeight + 1 < uchLeftHeight)
    339         {
    340             PKAVLNODECORE    pLeftLeftNode = pLeftNode->pLeft;
    341             PKAVLNODECORE    pLeftRightNode = pLeftNode->pRight;
    342             unsigned char   uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
    343 
    344             if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
    345             {
    346                 pNode->pLeft = pLeftRightNode;
    347                 pLeftNode->pRight = pNode;
    348                 pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
    349                 *ppNode = pLeftNode;
    350             }
    351             else
    352             {
    353                 pLeftNode->pRight = pLeftRightNode->pLeft;
    354                 pNode->pLeft = pLeftRightNode->pRight;
    355                 pLeftRightNode->pLeft = pLeftNode;
    356                 pLeftRightNode->pRight = pNode;
    357                 pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
    358                 pLeftRightNode->uchHeight = uchLeftHeight;
    359                 *ppNode = pLeftRightNode;
    360             }
    361         }
    362         else if (uchLeftHeight + 1 < uchRightHeight)
    363         {
    364             PKAVLNODECORE    pRightLeftNode = pRightNode->pLeft;
    365             unsigned char   uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
    366             PKAVLNODECORE    pRightRightNode = pRightNode->pRight;
    367 
    368             if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
    369             {
    370                 pNode->pRight = pRightLeftNode;
    371                 pRightNode->pLeft = pNode;
    372                 pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
    373                 *ppNode = pRightNode;
    374             }
    375             else
    376             {
    377                 pRightNode->pLeft = pRightLeftNode->pRight;
    378                 pNode->pRight = pRightLeftNode->pLeft;
    379                 pRightLeftNode->pRight = pRightNode;
    380                 pRightLeftNode->pLeft = pNode;
    381                 pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
    382                 pRightLeftNode->uchHeight = uchRightHeight;
    383                 *ppNode = pRightLeftNode;
    384             }
    385         }
    386         else
    387         {
    388             register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
    389             if (uchHeight == pNode->uchHeight)
    390                 break;
    391             pNode->uchHeight = uchHeight;
    392         }
    393     }
    394 
    395     KLOGEXITVOID();
    396 }
    397 
    398 
    399 
    400 #endif
Note: See TracChangeset for help on using the changeset viewer.