Changeset 3564 for trunk


Ignore:
Timestamp:
Aug 27, 2007, 5:43:09 AM (18 years ago)
Author:
bird
Message:

Implemented a Destroy function. Corrected the DoWithAll function to enumerate the chain of nodes with the same key too.

Location:
trunk/kStuff/include/k/kAvlTmpl
Files:
3 edited
1 copied

Legend:

Unmodified
Added
Removed

  • trunk/kStuff/include/k/kAvlTmpl/kAvlBase.h

    r3563 r3564  
    213213    KAVLTREEPTR    *aEntries[KAVL_MAX_STACK];
    214214} KAVL_INT(STACK);
     215
     216/**
     217 * The callback used by the Destroy and DoWithAll functions.
     218 */
     219typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);
     220
    215221
    216222

  • trunk/kStuff/include/k/kAvlTmpl/kAvlDestroy.h

    r3563 r3564  
    11/* $Id$ */
    22/** @file
    3  * kAvlTmpl - Templated AVL Trees, The Callback Iterator.
     3 * kAvlTmpl - Templated AVL Trees, Destroy the tree.
    44 */
    55
    … …  
    3232 */
    3333
    34 /*******************************************************************************
    35 *   Structures and Typedefs                                                    *
    36 *******************************************************************************/
    37 /** The callback typedef. */
    38 typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);
    3934
    4035/**
    41  * Stack used by DoWithAll to avoid recusive function calls.
     36 * Destroys the specified tree, starting with the root node and working our way down.
     37 *
     38 * @returns 0 on success.
     39 * @returns Return value from callback on failure. On failure, the tree will be in
     40 *          an unbalanced condition and only further calls to the Destroy should be
     41 *          made on it. Note that the node we fail on will be considered dead and
     42 *          no action is taken to link it back into the tree.
     43 * @param   ppTree          Pointer to the AVL-tree root node pointer.
     44 * @param   pfnCallBack     Pointer to callback function.
     45 * @param   pvUser          User parameter passed on to the callback function.
    4246 */
    43 typedef struct
     47KAVL_DECL(int) KAVL_FN(Destroy)(KAVLTREEPTR *ppTree, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
    4448{
    45     unsigned        cEntries;
    46     KAVLNODE       *aEntries[KAVL_MAX_STACK];
    47     char            achFlags[KAVL_MAX_STACK];
    48 } KAVL_INT(STACK2);
    49 
    50 
    51 /**
    52  * Iterates tru all nodes in the given tree.
    53  *
    54  * @returns   0 on success. Return from callback on failure.
    55  * @param     ppTree       Pointer to the AVL-tree root node pointer.
    56  * @param     fFromLeft    K_TRUE:  Left to right.
    57  *                         K_FALSE: Right to left.
    58  * @param     pfnCallBack  Pointer to callback function.
    59  * @param     pvUser       User parameter passed on to the callback function.
    60  */
    61 KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLTREEPTR *ppTree, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
    62 {
    63     KAVL_INT(STACK2)    AVLStack;
    64     KAVLNODE           *pNode;
    65     int                 rc;
     49    unsigned    cEntries;
     50    KAVLNODE   *apEntries[KAVL_MAX_STACK];
     51    int         rc;
    6652
    6753    if (*ppTree == KAVL_NULL)
    6854        return 0;
    6955
    70     AVLStack.cEntries = 1;
    71     AVLStack.achFlags[0] = 0;
    72     AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
     56    cEntries = 1;
     57    apEntries[0] = KAVL_GET_POINTER(ppTree);
     58    while (cEntries > 0)
     59    {
     60        /*
     61         * Process the subtrees first.
     62         */
     63        KAVLNODE *pNode = apEntries[cEntries - 1];
     64        if (pNode->mpLeft != KAVL_NULL)
     65            apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
     66        else if (pNode->mpRight != KAVL_NULL)
     67            apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
     68        else
     69        {
     70#ifdef KAVL_EQUAL_ALLOWED
     71            /*
     72             * Process nodes with the same key.
     73             */
     74            while (pNode->pList != KAVL_NULL)
     75            {
     76                KAVLNODE *pEqual = KAVL_GET_POINTER(&pNode->pList);
     77                KAVL_SET_POINTER(&pNode->pList) = KAVL_GET_POINTER_NULL(&pEqual->pList);
     78                pEqual->pList = KAVL_NULL;
    7379
    74     if (fFromLeft)
    75     {   /* from left */
    76         while (AVLStack.cEntries > 0)
    77         {
    78             pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
     80                rc = pfnCallBack(pEqual, pvUser);
     81                if (rc)
     82                    return rc;
     83            }
     84#endif
    7985
    80             /* left */
    81             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
     86            /*
     87             * Unlink the node.
     88             */
     89            if (--cEntries > 0)
    8290            {
    83                 if (pNode->mpLeft != KAVL_NULL)
    84                 {
    85                     AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
    86                     AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
    87                     continue;
    88                 }
     91                KAVLNODE *pParent = apEntries[cEntries - 1];
     92                if (KAVL_GET_POINTER(&pParent->mpLeft) == pNode)
     93                    pParent->mpLeft = KAVL_NULL;
     94                else
     95                    pParent->mpRight = KAVL_NULL;
    8996            }
     97            else
     98                *ppTree = KAVL_NULL;
    9099
    91             /* center */
     100            kHlpAssert(pNode->mLeft == KAVL_NULL);
     101            kHlpAssert(pNode->mRight == KAVL_NULL);
    92102            rc = pfnCallBack(pNode, pvUser);
    93103            if (rc)
    94104                return rc;
    95 
    96             /* right */
    97             AVLStack.cEntries--;
    98             if (pNode->mpRight != KAVL_NULL)
    99             {
    100                 AVLStack.achFlags[AVLStack.cEntries] = 0;
    101                 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
    102             }
    103         } /* while */
    104     }
    105     else
    106     {   /* from right */
    107         while (AVLStack.cEntries > 0)
    108         {
    109             pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
    110 
    111             /* right */
    112             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
    113             {
    114                 if (pNode->mpRight != KAVL_NULL)
    115                 {
    116                     AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
    117                     AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
    118                     continue;
    119                 }
    120             }
    121 
    122             /* center */
    123             rc = pfnCallBack(pNode, pvUser);
    124             if (rc)
    125                 return rc;
    126 
    127             /* left */
    128             AVLStack.cEntries--;
    129             if (pNode->mpLeft != KAVL_NULL)
    130             {
    131                 AVLStack.achFlags[AVLStack.cEntries] = 0;
    132                 AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
    133             }
    134         } /* while */
    135     }
     105        }
     106    } /* while */
     107    kHlpAssert(*ppTree == KAVL_NULL);
    136108
    137109    return 0;

  • trunk/kStuff/include/k/kAvlTmpl/kAvlDoWithAll.h

    r3563 r3564  
    3535*   Structures and Typedefs                                                    *
    3636*******************************************************************************/
    37 /** The callback typedef. */
    38 typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);
    39 
    4037/**
    4138 * Stack used by DoWithAll to avoid recusive function calls.
    … …  
    5047
    5148/**
    52  * Iterates tru all nodes in the given tree.
     49 * Iterates thru all nodes in the given tree.
    5350 *
    5451 * @returns   0 on success. Return from callback on failure.
    … …  
    6360    KAVL_INT(STACK2)    AVLStack;
    6461    KAVLNODE           *pNode;
     62#ifdef KAVL_EQUAL_ALLOWED
     63    KAVLNODE           *pEqual;
     64#endif
    6565    int                 rc;
    6666
    … …  
    9393            if (rc)
    9494                return rc;
     95#ifdef KAVL_EQUAL_ALLOWED
     96            if (pNode->pList != KAVL_NULL)
     97                for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pNext))
     98                {
     99                    rc = pfnCallBack(pEqual, pvUser);
     100                    if (rc)
     101                        return rc;
     102                }
     103#endif
    95104
    96105            /* right */
    … …  
    124133            if (rc)
    125134                return rc;
     135#ifdef KAVL_EQUAL_ALLOWED
     136            if (pNode->pList != KAVL_NULL)
     137                for (pEqual = KAVL_GET_POINTER(&pNode->pList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pNext))
     138                {
     139                    rc = pfnCallBack(pEqual, pvUser);
     140                    if (rc)
     141                        return rc;
     142                }
     143#endif
    126144
    127145            /* left */

  • trunk/kStuff/include/k/kAvlTmpl/kAvlEnum.h

    r3563 r3564  
    5252/**
    5353 * Get the next node in the tree enumeration.
     54 *
     55 * The current implementation of this function willl not walk the mpList
     56 * chain like the DoWithAll function does. This may be changed later.
    5457 *
    5558 * @returns Pointer to the first node in the tree.
    … …  
    134137 * Starts an enumeration of all nodes in the given AVL tree.
    135138 *
     139 * The current implementation of this function willl not walk the mpList
     140 * chain like the DoWithAll function does. This may be changed later.
     141 *
    136142 * @returns Pointer to the first node in the enumeration.
    137143 * @param   ppTree      Pointer to the AVL-tree root node pointer.
Note: See TracChangeset for help on using the changeset viewer.