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/kAVLRemove2.h

    r3553 r3555  
    11/* $Id$ */
    22/** @file
    3  *
    4  * kAVLRemove2 - Remove specific node (by pointer) from an AVL tree.
    5  *
    6  * Copyright (c) 2001-2002 knut st. osmundsen (bird@anduin.net)
    7  *
    8  * GPL
     3 * kAVLTmpl - Templated AVL Trees, Remove A Specific Node.
    94 */
    105
    11 #ifndef _kAVLRemove2_h_
    12 #define _kAVLRemove2_h_
     6/*
     7 * Copyright (c) 1999-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 */
    1326
    1427
    1528/**
    16  * Removes a node from the AVL-tree given by it's pointer.
    17  * @returns   Pointer to the node.
    18  * @param     ppTree  Pointer to the AVL-tree root node pointer.
    19  * @param     Key     Key value of the node which is to be removed.
    20  * @sketch    Find the node which is to be removed:
    21  *            LOOP until not found
    22  *            BEGIN
    23  *                Add node pointer pointer to the AVL-stack.
    24  *                IF the keys matches THEN break!
    25  *                IF remove key < node key THEN
    26  *                    left
    27  *                ELSE
    28  *                    right
    29  *            END
    30  *            IF found THEN
    31  *            BEGIN
    32  *                IF duplicate keys allowed AND this isn't pNode Then
    33  *                BEGIN
    34  *                    Search list (pList) for the node.
    35  *                    IF found THEN Link it out and return it.
    36  *                    return NULL (if not found).
    37  *                END
    38  *                IF duplicate keys allowed AND this is pNode AND there is nodes in the list Then
    39  *                    Replace pNode with the first node in the list.
    40  *                END
    41  *                IF left node not empty THEN
    42  *                BEGIN
    43  *                    Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
    44  *                    Start at left node.
    45  *                    LOOP until right node is empty
    46  *                    BEGIN
    47  *                        Add to stack.
    48  *                        go right.
    49  *                    END
    50  *                    Link out the found node.
    51  *                    Replace the node which is to be removed with the found node.
    52  *                    Correct the stack entry for the pointer to the left tree.
    53  *                END
    54  *                ELSE
    55  *                BEGIN
    56  *                    Move up right node.
    57  *                    Remove last stack entry.
    58  *                END
    59  *                Balance tree using stack.
    60  *            END
    61  *            return pointer to the removed node (if found).
    62  * @status    completely implemented.
    63  * @author    knut st. osmundsen
     29 * Removes the specified node from the tree.
     30 *
     31 * @returns Pointer to the removed node (NULL if not in the tree)
     32 * @param   ppTree      Pointer to Pointer to the tree root node.
     33 * @param   Key         The Key of which is to be found a best fitting match for..
     34 *
     35 * @remark  This implementation isn't the most efficient, but this short and
     36 *          easier to manage.
    6437 */
    65 PKAVLNODECORE KLIBCALL KAVL_FN(Remove2)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
     38KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
    6639{
    67     KLOGENTRY2("PKAVLNODECORE","PPKAVLNODECORE ppTree, PKAVLNODECORE pNode", ppTree, pNode);
    68     KAVLKEY                  Key = pNode->Key;
    69     KAVLSTACK                AVLStack;
    70     PPKAVLNODECORE           ppDeleteNode = ppTree;
    71     register PKAVLNODECORE   pDeleteNode;
    72 
    73     AVLStack.cEntries = 0;
    74 
    75     while ((pDeleteNode = *ppDeleteNode) != NULL)
     40#ifdef KAVL_EQUAL_ALLOWED
     41    /*
     42     * Find the right node by key and see if it's what we want.
     43     */
     44    KAVLNODECORE *pParent;
     45    KAVLNODECORE *pCurNode = KAVL_FN(GetWithParent)(ppTree, pNode->Key, &pParent);
     46    if (!pCurNode)
     47        return NULL;
     48    if (pCurNode != pNode)
    7649    {
    77         kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
    78         AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
    79         #ifndef AVL_CMP
    80         if (AVL_E(pDeleteNode->Key, Key))
    81             break;
    82 
    83         if (AVL_G(pDeleteNode->Key, Key))
    84             ppDeleteNode = &pDeleteNode->pLeft;
    85         else
    86             ppDeleteNode = &pDeleteNode->pRight;
    87         #else
     50        /*
     51         * It's not the one we want, but it could be in the duplicate list.
     52         */
     53        while (pCurNode->pList != KAVL_NULL)
    8854        {
    89         int register iDiff;
    90         if ((iDiff = AVL_CMP(pDeleteNode->Key, Key)) == 0)
    91             break;
    92 
    93         if (iDiff > 0)
    94             ppDeleteNode = &pDeleteNode->pLeft;
    95         else
    96             ppDeleteNode = &pDeleteNode->pRight;
     55            KAVLNODECORE *pNext = KAVL_GET_POINTER(&pCurNode->pList);
     56            if (pNext == pNode)
     57            {
     58                KAVL_SET_POINTER_NULL(&pCurNode->pList, KAVL_GET_POINTER_NULL(&pNode->pList));
     59                pNode->pList = KAVL_NULL;
     60                return pNode;
     61            }
     62            pCurNode = pNext;
    9763        }
    98         #endif
     64        return NULL;
    9965    }
    10066
    101     if (pDeleteNode != NULL)
     67    /*
     68     * Ok, it's the one we want alright.
     69     *
     70     * Simply remove it if it's the only one with they Key,
     71     * if there are duplicates we'll have to unlink it and
     72     * insert the first duplicate in our place.
     73     */
     74    if (pNode->pList == KAVL_NODE)
     75        KAVL_FN(Remove)(ppTree, pNode->Key);
     76    else
    10277    {
    103         #ifdef KAVL_EQUAL_ALLOWED
    104         if (pDeleteNode != pNode)
     78        KAVLNODECORE *pNewUs = KAVL_GET_POINTER(&pNode->pList);
     79
     80        pNewUs->uchHeight = pNode->uchHeight;
     81
     82        if (pNode->pLeft != KAVL_NULL)
     83            KAVL_SET_POINTER(&pNewUs->pLeft, KAVL_GET_POINTER(&pNode->pLeft))
     84        else
     85            pNewUs->pLeft = KAVL_NULL;
     86
     87        if (pNode->pRight != KAVL_NULL)
     88            KAVL_SET_POINTER(&pNewUs->pRight, KAVL_GET_POINTER(&pNode->pRight))
     89        else
     90            pNewUs->pRight = KAVL_NULL;
     91
     92        if (pParent)
    10593        {
    106             while (pDeleteNode->pList != NULL)
    107             {
    108                 if (pDeleteNode->pList == pNode)
    109                 {
    110                     pDeleteNode->pList = pNode->pList;
    111                     pNode->pList = NULL;                                        //debug only?
    112                     KLOGEXIT(pNode);
    113                     return pNode;
    114                 }
    115                 pDeleteNode = pDeleteNode->pList;
    116             }
    117             KLOGEXIT(NULL);
    118             return NULL;
    119         }
    120 
    121         if (pDeleteNode->pList != NULL)
    122         {
    123             pDeleteNode = pDeleteNode->pList;
    124             pDeleteNode->pLeft = pNode->pLeft;
    125             pDeleteNode->pRight = pNode->pRight;
    126             pDeleteNode->uchHeight = pNode->uchHeight;
    127             kASSERT(*ppDeleteNode == pNode);
    128             *ppDeleteNode = pDeleteNode;
    129             pNode->pList = pNode->pLeft = pNode->pRight = NULL;                 //debug only?
    130             KLOGEXIT(pNode);
    131             return pNode;
    132         }
    133         #endif
    134 
    135         if (pDeleteNode->pLeft != NULL)
    136         {
    137             unsigned                iStackEntry = AVLStack.cEntries;
    138             PPKAVLNODECORE           ppLeftLeast = &pDeleteNode->pLeft;
    139             register PKAVLNODECORE   pLeftLeast;
    140 
    141             while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
    142             {
    143                 kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
    144                 AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
    145                 ppLeftLeast = &pLeftLeast->pRight;
    146                 pLeftLeast  = pLeftLeast->pRight;
    147             }
    148 
    149             /* link out pLeftLeast */
    150             *ppLeftLeast = pLeftLeast->pLeft;
    151 
    152             /* link in place of the delete node. */
    153             pLeftLeast->pLeft = pDeleteNode->pLeft;
    154             pLeftLeast->pRight = pDeleteNode->pRight;
    155             pLeftLeast->uchHeight = pDeleteNode->uchHeight;
    156             *ppDeleteNode = pLeftLeast;
    157             AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
     94            if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
     95                KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
     96            else
     97                KAVL_SET_POINTER(&pParent->pRight, pNewUs);
    15898        }
    15999        else
    160         {
    161             *ppDeleteNode = pDeleteNode->pRight;
    162             AVLStack.cEntries--;
    163         }
     100            KAVL_SET_POINTER(ppTree, pNewUs);
     101    }
     102    return pNode;
    164103
    165         KAVL_FN(Rebalance)(SSToDS(&AVLStack));
    166     }
     104#else
     105    /*
     106     * Delete it, if we got the wrong one, reinsert it.
     107     *
     108     * This ASSUMS that the caller is NOT going to hand us a lot
     109     * of wrong nodes but just uses this API for his convenience.
     110     */
     111    KAVLNODECORE *pRemovedNode = KAVL_FN(Remove)(ppTree, pNode->Key);
     112    if (pRemovedNode == pNode)
     113        return pRemovedNode;
    167114
    168     #ifndef KAVL_EQUAL_ALLOWED                                  //debug only?
    169     pNode->pLeft = pNode->pRight = NULL;                        //debug only?
    170     #else                                                       //debug only?
    171     pNode->pList = pNode->pLeft = pNode->pRight = NULL;         //debug only?
    172     #endif                                                      //debug only?
    173     KLOGEXIT(pDeleteNode);
    174     return pDeleteNode;
     115    KAVL_FN(Insert)(ppTree, pRemovedNode);
     116    return NULL;
     117#endif
    175118}
    176119
    177 #endif
Note: See TracChangeset for help on using the changeset viewer.