Ignore:
Timestamp:
Aug 27, 2007, 12:31:38 AM (18 years ago)
Author:
bird
Message:

Made is possible to redefine the AVLNODE members, thus allowing a structure to be used by more than one kAvl instance (i.e. be in more than one tree). Define the callback and enumdata our selves.

File:
1 edited

Legend:

Unmodified
Added
Removed

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

    r3560 r3562  
    3434 *  \#define KAVL_EQUAL_ALLOWED
    3535 *  Define this to tell us that equal keys are allowed.
    36  *  Then Equal keys will be put in a list pointed to by KAVLNODECORE::pList.
     36 *  Then Equal keys will be put in a list pointed to by KAVLNODE::pList.
    3737 *  This is by default not defined.
    3838 *
    … …  
    6565 *  three are only required when KAVL_RANGE is defined.
    6666 *
    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.
     67 *  \#define KAVLNODE
     68 *  Define this to the name (typedef) of the AVL node structure. This
     69 *  structure must have a mpLeft, mpRight, mKey and mHeight member.
     70 *  If KAVL_RANGE is defined a mKeyLast is also required.
     71 *  If KAVL_EQUAL_ALLOWED is defined a mpList member is required.
     72 *  It's possible to use other member names by redefining the names.
    7273 *
    7374 *  \#define KAVLTREEPTR
    7475 *  Define this to the name (typedef) of the tree pointer type. This is
    7576 *  required when KAVL_OFFSET is defined. When not defined it defaults
    76  *  to KAVLNODECORE *.
     77 *  to KAVLNODE *.
    7778 *
    7879 *  \#define KAVL_FN
    … …  
    9293 *  the instantiated template should have. For instance an inlined scope
    9394 *  (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  *
    9995 *
    10096 *  This version of the kAVL tree offers the option of inlining the entire
    … …  
    115111*   Defined Constants And Macros                                               *
    116112*******************************************************************************/
    117 #define KAVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? (pNode)->uchHeight : 0))
     113#define KAVL_HEIGHTOF(pNode) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
    118114
    119115/** @def KAVL_GET_POINTER
    … …  
    157153
    158154#ifndef KAVLTREEPTR
    159 # define KAVLTREEPTR                        KAVLNODECORE *
     155# define KAVLTREEPTR                        KAVLNODE *
    160156#endif
    161157
    162158#ifdef KAVL_OFFSET
    163 # define KAVL_GET_POINTER(pp)               ( (KAVLNODECORE *)((KIPTR)(pp) + *(pp)) )
     159# define KAVL_GET_POINTER(pp)               ( (KAVLNODE *)((KIPTR)(pp) + *(pp)) )
    164160# define KAVL_GET_POINTER_NULL(pp)          ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
    165161# define KAVL_SET_POINTER(pp, p)            ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
    … …  
    203199*   Structures and Typedefs                                                    *
    204200*******************************************************************************/
    205 /*
    206  * Two stacks that's used to avoid recursive calls.
     201/**
     202 * Stack used to avoid recursive calls during insert and removal.
    207203 */
    208204typedef struct
    … …  
    211207    KAVLTREEPTR    *aEntries[KAVL_MAX_STACK];
    212208} KAVL_INT(STACK);
    213 
    214 typedef struct
    215 {
    216     unsigned        cEntries;
    217     KAVLNODECORE   *aEntries[KAVL_MAX_STACK];
    218     char            achFlags[KAVL_MAX_STACK];
    219 } KAVL_INT(STACK2);
    220209
    221210
    … …  
    275264    {
    276265        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)
     266        KAVLNODE        *pNode = KAVL_GET_POINTER(ppNode);
     267        KAVLNODE        *pLeftNode = KAVL_GET_POINTER_NULL(&pNode->mpLeft);
     268        KU8              uLeftHeight = KAVL_HEIGHTOF(pLeftNode);
     269        KAVLNODE        *pRightNode = KAVL_GET_POINTER_NULL(&pNode->mpRight);
     270        KU8              uRightHeight = KAVL_HEIGHTOF(pRightNode);
     271
     272        if (uRightHeight + 1 < uLeftHeight)
    284273        {
    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)
     274            KAVLNODE    *pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpLeft);
     275            KAVLNODE    *pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpRight);
     276            KU8          uLeftRightHeight = KAVL_HEIGHTOF(pLeftRightNode);
     277
     278            if (KAVL_HEIGHTOF(pLeftLeftNode) >= uLeftRightHeight)
    290279            {
    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)));
     280                KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftNode->mpRight);
     281                KAVL_SET_POINTER(&pLeftNode->mpRight, pNode);
     282                pLeftNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uLeftRightHeight)));
    294283                KAVL_SET_POINTER(ppNode, pLeftNode);
    295284            }
    296285            else
    297286            {
    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;
     287                KAVL_SET_POINTER_NULL(&pLeftNode->mpRight, &pLeftRightNode->mpLeft);
     288                KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftRightNode->mpRight);
     289                KAVL_SET_POINTER(&pLeftRightNode->mpLeft, pLeftNode);
     290                KAVL_SET_POINTER(&pLeftRightNode->mpRight, pNode);
     291                pLeftNode->mHeight = pNode->mHeight = uLeftRightHeight;
     292                pLeftRightNode->mHeight = uLeftHeight;
    304293                KAVL_SET_POINTER(ppNode, pLeftRightNode);
    305294            }
    306295        }
    307         else if (uchLeftHeight + 1 < uchRightHeight)
     296        else if (uLeftHeight + 1 < uRightHeight)
    308297        {
    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)
     298            KAVLNODE    *pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->mpLeft);
     299            KU8          uRightLeftHeight = KAVL_HEIGHTOF(pRightLeftNode);
     300            KAVLNODE    *pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->mpRight);
     301
     302            if (KAVL_HEIGHTOF(pRightRightNode) >= uRightLeftHeight)
    314303            {
    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)));
     304                KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightNode->mpLeft);
     305                KAVL_SET_POINTER(&pRightNode->mpLeft, pNode);
     306                pRightNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uRightLeftHeight)));
    318307                KAVL_SET_POINTER(ppNode, pRightNode);
    319308            }
    320309            else
    321310            {
    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;
     311                KAVL_SET_POINTER_NULL(&pRightNode->mpLeft, &pRightLeftNode->mpRight);
     312                KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightLeftNode->mpLeft);
     313                KAVL_SET_POINTER(&pRightLeftNode->mpRight, pRightNode);
     314                KAVL_SET_POINTER(&pRightLeftNode->mpLeft, pNode);
     315                pRightNode->mHeight = pNode->mHeight = uRightLeftHeight;
     316                pRightLeftNode->mHeight = uRightHeight;
    328317                KAVL_SET_POINTER(ppNode, pRightLeftNode);
    329318            }
    … …  
    331320        else
    332321        {
    333             register unsigned char uchHeight = (unsigned char)(K_MAX(uchLeftHeight, uchRightHeight) + 1);
    334             if (uchHeight == pNode->uchHeight)
     322            KU8 uHeight = (KU8)(K_MAX(uLeftHeight, uRightHeight) + 1);
     323            if (uHeight == pNode->mHeight)
    335324                break;
    336             pNode->uchHeight = uchHeight;
     325            pNode->mHeight = uHeight;
    337326        }
    338327    }
    … …  
    359348 *            Rebalance the tree.
    360349 */
    361 KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
     350KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODE *pNode)
    362351{
    363     KAVL_INT(STACK)        AVLStack;
    364     KAVLTREEPTR            *ppCurNode = ppTree;
    365     register KAVLKEY        Key = pNode->Key;
     352    KAVL_INT(STACK)     AVLStack;
     353    KAVLTREEPTR        *ppCurNode = ppTree;
     354    register KAVLKEY    Key = pNode->mKey;
    366355#ifdef KAVL_RANGE
    367     register KAVLKEY        KeyLast = pNode->KeyLast;
    368 #endif
    369     register KAVLNODECORE  *pCurNode;
    370 
    371     AVLStack.cEntries = 0;
     356    register KAVLKEY    KeyLast = pNode->mKeyLast;
     357#endif
    372358
    373359#ifdef KAVL_RANGE
    374360    if (Key > KeyLast)
    375361        return false;
    376 #else
    377     K_NOREF(Key);
    378 #endif
    379 
     362#endif
     363
     364    AVLStack.cEntries = 0;
    380365    while (*ppCurNode != KAVL_NULL)
    381366    {
    382         pCurNode = KAVL_GET_POINTER(ppCurNode);
     367        register KAVLNODE *pCurNode = KAVL_GET_POINTER(ppCurNode);
    383368
    384369        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
    385370        AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
    386371#ifdef KAVL_EQUAL_ALLOWED
    387         if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
     372        if (KAVL_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
    388373        {
    389374            /*
    390375             * If equal then we'll use a list of equal nodes.
    391376             */
    392             pNode->pLeft = pNode->pRight = KAVL_NULL;
    393             pNode->uchHeight = 0;
    394             KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
    395             KAVL_SET_POINTER(&pCurNode->pList, pNode);
     377            pNode->mpLeft = pNode->mpRight = KAVL_NULL;
     378            pNode->mHeight = 0;
     379            KAVL_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
     380            KAVL_SET_POINTER(&pCurNode->mpList, pNode);
    396381            return K_TRUE;
    397382        }
    398383#endif
    399384#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
    400         if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
     385        if (KAVL_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
    401386            return K_FALSE;
    402387#endif
    403         if (KAVL_G(pCurNode->Key, Key))
    404             ppCurNode = &pCurNode->pLeft;
     388        if (KAVL_G(pCurNode->mKey, Key))
     389            ppCurNode = &pCurNode->mpLeft;
    405390        else
    406             ppCurNode = &pCurNode->pRight;
     391            ppCurNode = &pCurNode->mpRight;
    407392    }
    408393
    409     pNode->pLeft = pNode->pRight = KAVL_NULL;
     394    pNode->mpLeft = pNode->mpRight = KAVL_NULL;
    410395#ifdef KAVL_EQUAL_ALLOWED
    411     pNode->pList = KAVL_NULL;
    412 #endif
    413     pNode->uchHeight = 1;
     396    pNode->mpList = KAVL_NULL;
     397#endif
     398    pNode->mHeight = 1;
    414399    KAVL_SET_POINTER(ppCurNode, pNode);
    415400
    … …  
    458443 *            return pointer to the removed node (if found).
    459444 */
    460 KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
     445KAVL_DECL(KAVLNODE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
    461446{
    462     KAVL_INT(STACK)         AVLStack;
    463     KAVLTREEPTR             *ppDeleteNode = ppTree;
    464     register KAVLNODECORE   *pDeleteNode;
     447    KAVL_INT(STACK)     AVLStack;
     448    KAVLTREEPTR        *ppDeleteNode = ppTree;
     449    register KAVLNODE  *pDeleteNode;
    465450
    466451    AVLStack.cEntries = 0;
    467 
    468452    for (;;)
    469453    {
    … …  
    474458        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
    475459        AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
    476         if (KAVL_E(pDeleteNode->Key, Key))
     460        if (KAVL_E(pDeleteNode->mKey, Key))
    477461            break;
    478462
    479         if (KAVL_G(pDeleteNode->Key, Key))
    480             ppDeleteNode = &pDeleteNode->pLeft;
     463        if (KAVL_G(pDeleteNode->mKey, Key))
     464            ppDeleteNode = &pDeleteNode->mpLeft;
    481465        else
    482             ppDeleteNode = &pDeleteNode->pRight;
     466            ppDeleteNode = &pDeleteNode->mpRight;
    483467    }
    484468
    485     if (pDeleteNode->pLeft != KAVL_NULL)
     469    if (pDeleteNode->mpLeft != KAVL_NULL)
    486470    {
    487471        /* 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)
     472        const unsigned      iStackEntry = AVLStack.cEntries;
     473        KAVLTREEPTR        *ppLeftLeast = &pDeleteNode->mpLeft;
     474        register KAVLNODE  *pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
     475
     476        while (pLeftLeast->mpRight != KAVL_NULL)
    493477        {
    494478            kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
    495479            AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
    496             ppLeftLeast = &pLeftLeast->pRight;
     480            ppLeftLeast = &pLeftLeast->mpRight;
    497481            pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
    498482        }
    499483
    500484        /* link out pLeftLeast */
    501         KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
     485        KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
    502486
    503487        /* 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;
     488        KAVL_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
     489        KAVL_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
     490        pLeftLeast->mHeight = pDeleteNode->mHeight;
    507491        KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
    508         AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
     492        AVLStack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
    509493    }
    510494    else
    511495    {
    512         KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
     496        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
    513497        AVLStack.cEntries--;
    514498    }
Note: See TracChangeset for help on using the changeset viewer.