Changeset 3562

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.

Location:

trunk/kStuff/include/k

Files:

• kAvlTmpl/kAvlBase.h (modified) (12 diffs)
• kAvlTmpl/kAvlDoWithAll.h (modified) (6 diffs)
• kAvlTmpl/kAvlEnum.h (modified) (9 diffs)
• kAvlTmpl/kAvlGet.h (modified) (1 diff)
• kAvlTmpl/kAvlGetBestFit.h (modified) (2 diffs)
• kAvlTmpl/kAvlGetWithParent.h (modified) (1 diff)
• kAvlTmpl/kAvlRemove2.h (modified) (5 diffs)
• kAvlTmpl/kAvlRemoveBestFit.h (modified) (2 diffs)
• kAvlTmpl/kAvlUndef.h (modified) (2 diffs)
• kAvlU32.h (modified) (2 diffs)
• kAvloU32.h (modified) (2 diffs)
• kAvlrU32.h (modified) (2 diffs)

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

@@ -34 +34 @@
  *  \#define KAVL_EQUAL_ALLOWED
  *  Define this to tell us that equal keys are allowed.
- *  Then Equal keys will be put in a list pointed to by KAVLNODECORE::pList.
+ *  Then Equal keys will be put in a list pointed to by KAVLNODE::pList.
  *  This is by default not defined.
  *
@@ -65 +65 @@
  *  three are only required when KAVL_RANGE is defined.
  *
- *  \#define KAVLNODECORE
- *  Define this to the name (typedef) of the AVL core node structure. This
- *  structure must have a pLeft, pRight, Key and uchHeight member.
- *  If KAVL_RANGE is defined a  KeyLast is also required.
- *  If KAVL_EQUAL_ALLOWED is defined a pList member is required.
+ *  \#define KAVLNODE
+ *  Define this to the name (typedef) of the AVL node structure. This
+ *  structure must have a mpLeft, mpRight, mKey and mHeight member.
+ *  If KAVL_RANGE is defined a mKeyLast is also required.
+ *  If KAVL_EQUAL_ALLOWED is defined a mpList member is required.
+ *  It's possible to use other member names by redefining the names.
  *
  *  \#define KAVLTREEPTR
  *  Define this to the name (typedef) of the tree pointer type. This is
  *  required when KAVL_OFFSET is defined. When not defined it defaults
- *  to KAVLNODECORE *.
+ *  to KAVLNODE *.
  *
  *  \#define KAVL_FN
@@ -92 +93 @@
  *  the instantiated template should have. For instance an inlined scope
  *  (private or public) should K_DECL_INLINE(rettype) here.
- *
- *  typedef KAVL_TYPE(PFN,CALLBACK)
- *  kAVLDoWithAll requires KAVL_TYPE(PFN,CALLBACK) to be a function pointer
- *  to a callback suitable for the DoWithAll method.
- *
  *
  *  This version of the kAVL tree offers the option of inlining the entire
@@ -115 +111 @@
 *   Defined Constants And Macros                                               *
 *******************************************************************************/
-#define KAVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? (pNode)->uchHeight : 0))
+#define KAVL_HEIGHTOF(pNode) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
 
 /** @def KAVL_GET_POINTER
@@ -157 +153 @@
 
 #ifndef KAVLTREEPTR
-# define KAVLTREEPTR                        KAVLNODECORE *
+# define KAVLTREEPTR                        KAVLNODE *
 #endif
 
 #ifdef KAVL_OFFSET
-# define KAVL_GET_POINTER(pp)               ( (KAVLNODECORE *)((KIPTR)(pp) + *(pp)) )
+# define KAVL_GET_POINTER(pp)               ( (KAVLNODE *)((KIPTR)(pp) + *(pp)) )
 # define KAVL_GET_POINTER_NULL(pp)          ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
 # define KAVL_SET_POINTER(pp, p)            ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
@@ -203 +199 @@
 *   Structures and Typedefs                                                    *
 *******************************************************************************/
-/*
- * Two stacks that's used to avoid recursive calls.
+/**
+ * Stack used to avoid recursive calls during insert and removal.
  */
 typedef struct
@@ -211 +207 @@
     KAVLTREEPTR    *aEntries[KAVL_MAX_STACK];
 } KAVL_INT(STACK);
-
-typedef struct
-{
-    unsigned        cEntries;
-    KAVLNODECORE   *aEntries[KAVL_MAX_STACK];
-    char            achFlags[KAVL_MAX_STACK];
-} KAVL_INT(STACK2);
 
 
@@ -275 +264 @@
     {
         KAVLTREEPTR     *ppNode = pStack->aEntries[--pStack->cEntries];
-        KAVLNODECORE    *pNode = KAVL_GET_POINTER(ppNode);
-        KAVLNODECORE    *pLeftNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
-        unsigned char    uchLeftHeight = KAVL_HEIGHTOF(pLeftNode);
-        KAVLNODECORE    *pRightNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
-        unsigned char    uchRightHeight = KAVL_HEIGHTOF(pRightNode);
-
-        if (uchRightHeight + 1 < uchLeftHeight)
+        KAVLNODE        *pNode = KAVL_GET_POINTER(ppNode);
+        KAVLNODE        *pLeftNode = KAVL_GET_POINTER_NULL(&pNode->mpLeft);
+        KU8              uLeftHeight = KAVL_HEIGHTOF(pLeftNode);
+        KAVLNODE        *pRightNode = KAVL_GET_POINTER_NULL(&pNode->mpRight);
+        KU8              uRightHeight = KAVL_HEIGHTOF(pRightNode);
+
+        if (uRightHeight + 1 < uLeftHeight)
         {
-            KAVLNODECORE    *pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->pLeft);
-            KAVLNODECORE    *pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->pRight);
-            unsigned char    uchLeftRightHeight = KAVL_HEIGHTOF(pLeftRightNode);
-
-            if (KAVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
+            KAVLNODE    *pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpLeft);
+            KAVLNODE    *pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpRight);
+            KU8          uLeftRightHeight = KAVL_HEIGHTOF(pLeftRightNode);
+
+            if (KAVL_HEIGHTOF(pLeftLeftNode) >= uLeftRightHeight)
             {
-                KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftNode->pRight);
-                KAVL_SET_POINTER(&pLeftNode->pRight, pNode);
-                pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
+                KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftNode->mpRight);
+                KAVL_SET_POINTER(&pLeftNode->mpRight, pNode);
+                pLeftNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uLeftRightHeight)));
                 KAVL_SET_POINTER(ppNode, pLeftNode);
             }
             else
             {
-                KAVL_SET_POINTER_NULL(&pLeftNode->pRight, &pLeftRightNode->pLeft);
-                KAVL_SET_POINTER_NULL(&pNode->pLeft, &pLeftRightNode->pRight);
-                KAVL_SET_POINTER(&pLeftRightNode->pLeft, pLeftNode);
-                KAVL_SET_POINTER(&pLeftRightNode->pRight, pNode);
-                pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
-                pLeftRightNode->uchHeight = uchLeftHeight;
+                KAVL_SET_POINTER_NULL(&pLeftNode->mpRight, &pLeftRightNode->mpLeft);
+                KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftRightNode->mpRight);
+                KAVL_SET_POINTER(&pLeftRightNode->mpLeft, pLeftNode);
+                KAVL_SET_POINTER(&pLeftRightNode->mpRight, pNode);
+                pLeftNode->mHeight = pNode->mHeight = uLeftRightHeight;
+                pLeftRightNode->mHeight = uLeftHeight;
                 KAVL_SET_POINTER(ppNode, pLeftRightNode);
             }
         }
-        else if (uchLeftHeight + 1 < uchRightHeight)
+        else if (uLeftHeight + 1 < uRightHeight)
         {
-            KAVLNODECORE    *pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->pLeft);
-            unsigned char    uchRightLeftHeight = KAVL_HEIGHTOF(pRightLeftNode);
-            KAVLNODECORE    *pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->pRight);
-
-            if (KAVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
+            KAVLNODE    *pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->mpLeft);
+            KU8          uRightLeftHeight = KAVL_HEIGHTOF(pRightLeftNode);
+            KAVLNODE    *pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->mpRight);
+
+            if (KAVL_HEIGHTOF(pRightRightNode) >= uRightLeftHeight)
             {
-                KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightNode->pLeft);
-                KAVL_SET_POINTER(&pRightNode->pLeft, pNode);
-                pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
+                KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightNode->mpLeft);
+                KAVL_SET_POINTER(&pRightNode->mpLeft, pNode);
+                pRightNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uRightLeftHeight)));
                 KAVL_SET_POINTER(ppNode, pRightNode);
             }
             else
             {
-                KAVL_SET_POINTER_NULL(&pRightNode->pLeft, &pRightLeftNode->pRight);
-                KAVL_SET_POINTER_NULL(&pNode->pRight, &pRightLeftNode->pLeft);
-                KAVL_SET_POINTER(&pRightLeftNode->pRight, pRightNode);
-                KAVL_SET_POINTER(&pRightLeftNode->pLeft, pNode);
-                pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
-                pRightLeftNode->uchHeight = uchRightHeight;
+                KAVL_SET_POINTER_NULL(&pRightNode->mpLeft, &pRightLeftNode->mpRight);
+                KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightLeftNode->mpLeft);
+                KAVL_SET_POINTER(&pRightLeftNode->mpRight, pRightNode);
+                KAVL_SET_POINTER(&pRightLeftNode->mpLeft, pNode);
+                pRightNode->mHeight = pNode->mHeight = uRightLeftHeight;
+                pRightLeftNode->mHeight = uRightHeight;
                 KAVL_SET_POINTER(ppNode, pRightLeftNode);
             }
@@ -331 +320 @@
         else
         {
-            register unsigned char uchHeight = (unsigned char)(K_MAX(uchLeftHeight, uchRightHeight) + 1);
-            if (uchHeight == pNode->uchHeight)
+            KU8 uHeight = (KU8)(K_MAX(uLeftHeight, uRightHeight) + 1);
+            if (uHeight == pNode->mHeight)
                 break;
-            pNode->uchHeight = uchHeight;
+            pNode->mHeight = uHeight;
         }
     }
@@ -359 +348 @@
  *            Rebalance the tree.
  */
-KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
+KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODE *pNode)
 {
-    KAVL_INT(STACK)        AVLStack;
-    KAVLTREEPTR            *ppCurNode = ppTree;
-    register KAVLKEY        Key = pNode->Key;
+    KAVL_INT(STACK)     AVLStack;
+    KAVLTREEPTR        *ppCurNode = ppTree;
+    register KAVLKEY    Key = pNode->mKey;
 #ifdef KAVL_RANGE
-    register KAVLKEY        KeyLast = pNode->KeyLast;
-#endif
-    register KAVLNODECORE  *pCurNode;
-
-    AVLStack.cEntries = 0;
+    register KAVLKEY    KeyLast = pNode->mKeyLast;
+#endif
 
 #ifdef KAVL_RANGE
     if (Key > KeyLast)
         return false;
-#else
-    K_NOREF(Key);
-#endif
-
+#endif
+
+    AVLStack.cEntries = 0;
     while (*ppCurNode != KAVL_NULL)
     {
-        pCurNode = KAVL_GET_POINTER(ppCurNode);
+        register KAVLNODE *pCurNode = KAVL_GET_POINTER(ppCurNode);
 
         kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
         AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
 #ifdef KAVL_EQUAL_ALLOWED
-        if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
+        if (KAVL_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
         {
             /*
              * If equal then we'll use a list of equal nodes.
              */
-            pNode->pLeft = pNode->pRight = KAVL_NULL;
-            pNode->uchHeight = 0;
-            KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
-            KAVL_SET_POINTER(&pCurNode->pList, pNode);
+            pNode->mpLeft = pNode->mpRight = KAVL_NULL;
+            pNode->mHeight = 0;
+            KAVL_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
+            KAVL_SET_POINTER(&pCurNode->mpList, pNode);
             return K_TRUE;
         }
 #endif
 #ifdef KAVL_CHECK_FOR_EQUAL_INSERT
-        if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
+        if (KAVL_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
             return K_FALSE;
 #endif
-        if (KAVL_G(pCurNode->Key, Key))
-            ppCurNode = &pCurNode->pLeft;
+        if (KAVL_G(pCurNode->mKey, Key))
+            ppCurNode = &pCurNode->mpLeft;
         else
-            ppCurNode = &pCurNode->pRight;
+            ppCurNode = &pCurNode->mpRight;
     }
 
-    pNode->pLeft = pNode->pRight = KAVL_NULL;
+    pNode->mpLeft = pNode->mpRight = KAVL_NULL;
 #ifdef KAVL_EQUAL_ALLOWED
-    pNode->pList = KAVL_NULL;
-#endif
-    pNode->uchHeight = 1;
+    pNode->mpList = KAVL_NULL;
+#endif
+    pNode->mHeight = 1;
     KAVL_SET_POINTER(ppCurNode, pNode);
 
@@ -458 +443 @@
  *            return pointer to the removed node (if found).
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
+KAVL_DECL(KAVLNODE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
 {
-    KAVL_INT(STACK)         AVLStack;
-    KAVLTREEPTR             *ppDeleteNode = ppTree;
-    register KAVLNODECORE   *pDeleteNode;
+    KAVL_INT(STACK)     AVLStack;
+    KAVLTREEPTR        *ppDeleteNode = ppTree;
+    register KAVLNODE  *pDeleteNode;
 
     AVLStack.cEntries = 0;
-
     for (;;)
     {
@@ -474 +458 @@
         kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
         AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
-        if (KAVL_E(pDeleteNode->Key, Key))
+        if (KAVL_E(pDeleteNode->mKey, Key))
             break;
 
-        if (KAVL_G(pDeleteNode->Key, Key))
-            ppDeleteNode = &pDeleteNode->pLeft;
+        if (KAVL_G(pDeleteNode->mKey, Key))
+            ppDeleteNode = &pDeleteNode->mpLeft;
         else
-            ppDeleteNode = &pDeleteNode->pRight;
+            ppDeleteNode = &pDeleteNode->mpRight;
     }
 
-    if (pDeleteNode->pLeft != KAVL_NULL)
+    if (pDeleteNode->mpLeft != KAVL_NULL)
     {
         /* find the rightmost node in the left tree. */
-        const unsigned          iStackEntry = AVLStack.cEntries;
-        KAVLTREEPTR            *ppLeftLeast = &pDeleteNode->pLeft;
-        register KAVLNODECORE  *pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
-
-        while (pLeftLeast->pRight != KAVL_NULL)
+        const unsigned      iStackEntry = AVLStack.cEntries;
+        KAVLTREEPTR        *ppLeftLeast = &pDeleteNode->mpLeft;
+        register KAVLNODE  *pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
+
+        while (pLeftLeast->mpRight != KAVL_NULL)
         {
             kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
             AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
-            ppLeftLeast = &pLeftLeast->pRight;
+            ppLeftLeast = &pLeftLeast->mpRight;
             pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
         }
 
         /* link out pLeftLeast */
-        KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
+        KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
 
         /* link it in place of the delete node. */
-        KAVL_SET_POINTER_NULL(&pLeftLeast->pLeft, &pDeleteNode->pLeft);
-        KAVL_SET_POINTER_NULL(&pLeftLeast->pRight, &pDeleteNode->pRight);
-        pLeftLeast->uchHeight = pDeleteNode->uchHeight;
+        KAVL_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
+        KAVL_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
+        pLeftLeast->mHeight = pDeleteNode->mHeight;
         KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
-        AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
+        AVLStack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
     }
     else
     {
-        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
+        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
         AVLStack.cEntries--;
     }

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

@@ -25 +25 @@
  */
 
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/** The callback typedef. */
+typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);
+
+/**
+ * Stack used by DoWithAll to avoid recusive function calls.
+ */
+typedef struct
+{
+    unsigned        cEntries;
+    KAVLNODE       *aEntries[KAVL_MAX_STACK];
+    char            achFlags[KAVL_MAX_STACK];
+} KAVL_INT(STACK2);
+
 
 /**
@@ -38 +54 @@
 KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLTREEPTR *ppTree, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
 {
-    KAVL_INT(STACK2)   AVLStack;
-    KAVLNODECORE       *pNode;
-    unsigned            rc;
+    KAVL_INT(STACK2)    AVLStack;
+    KAVLNODE           *pNode;
+    int                 rc;
 
     if (*ppTree == KAVL_NULL)
@@ -58 +74 @@
             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
             {
-                if (pNode->pLeft != KAVL_NULL)
+                if (pNode->mpLeft != KAVL_NULL)
                 {
                     AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
                     continue;
                 }
@@ -73 +89 @@
             /* right */
             AVLStack.cEntries--;
-            if (pNode->pRight != KAVL_NULL)
+            if (pNode->mpRight != KAVL_NULL)
             {
                 AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
             }
         } /* while */
@@ -86 +102 @@
             pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
 
-
             /* right */
             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
             {
-                if (pNode->pRight != KAVL_NULL)
+                if (pNode->mpRight != KAVL_NULL)
                 {
                     AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
                     continue;
                 }
@@ -105 +120 @@
             /* left */
             AVLStack.cEntries--;
-            if (pNode->pLeft != KAVL_NULL)
+            if (pNode->mpLeft != KAVL_NULL)
             {
                 AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
             }
         } /* while */

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

@@ -25 +25 @@
  */
 
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/**
+ * Enumeration control data.
+ *
+ * This is initialized by BeginEnum and used by GetNext to figure out what
+ * to do next.
+ */
+typedef struct KAVL_TYPE(,ENUMDATA)
+{
+    KBOOL               fFromLeft;
+    KI8                 cEntries;
+    KU8                 achFlags[KAVL_MAX_STACK];
+    KAVLNODE *          aEntries[KAVL_MAX_STACK];
+} KAVL_TYPE(,ENUMDATA), *KAVL_TYPE(P,ENUMDATA);
+
+
 /**
  * Get the next node in the tree enumeration.
- * @returns   Pointer to the first node in the tree.
- * @param     pEnumData  Pointer to enumeration control data.
- * @status    completely implemented.
- * @author    knut st. osmundsen
+ *
+ * @returns Pointer to the first node in the tree.
+ * @param   pEnumData   Pointer to enumeration control data.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetNextNode)(KAVL_TYPE(,ENUMDATA) *pEnumData)
+KAVL_DECL(KAVLNODE *) KAVL_FN(GetNext)(KAVL_TYPE(,ENUMDATA) *pEnumData)
 {
     if (pEnumData->fFromLeft)
@@ -38 +55 @@
         while (pEnumData->cEntries > 0)
         {
-            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+            KAVLNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
 
             /* left */
@@ -44 +61 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->pLeft != KAVL_NULL)
+                if (pNode->mpLeft != KAVL_NULL)
                 {
                     pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
-                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
                     continue;
                 }
@@ -61 +78 @@
             /* right */
             pEnumData->cEntries--;
-            if (pNode->pRight != KAVL_NULL)
+            if (pNode->mpRight != KAVL_NULL)
             {
                 pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
             }
         } /* while */
@@ -72 +89 @@
         while (pEnumData->cEntries > 0)
         {
-            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+            KAVLNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
 
             /* right */
@@ -78 +95 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->pRight != KAVL_NULL)
+                if (pNode->mpRight != KAVL_NULL)
                 {
                     pEnumData->achFlags[pEnumData->cEntries] = 0;  /* 0 right, 1 center, 2 left */
-                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
                     continue;
                 }
@@ -95 +112 @@
             /* left */
             pEnumData->cEntries--;
-            if (pNode->pLeft != KAVL_NULL)
+            if (pNode->mpLeft != KAVL_NULL)
             {
                 pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
             }
         } /* while */
@@ -116 +133 @@
  *                      K_FALSE: Right to left.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(BeginEnumTree)(KAVLTREEPTR *ppTree, KAVL_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft)
+KAVL_DECL(KAVLNODE *) KAVL_FN(BeginEnum)(KAVLTREEPTR *ppTree, KAVL_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft)
 {
     if (*ppTree != KAVL_NULL)
@@ -128 +145 @@
         pEnumData->cEntries = 0;
 
-    return KAVL_FN(GetNextNode)(pEnumData);
+    return KAVL_FN(GetNext)(pEnumData);
 }
 

trunk/kStuff/include/k/kAvlTmpl/kAvlGet.h

@@ -33 +33 @@
  * @param     Key     Key value of the node which is to be found.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(Get)(KAVLTREEPTR *ppTree, KAVLKEY Key)
+KAVL_DECL(KAVLNODE *) KAVL_FN(Get)(KAVLTREEPTR *ppTree, KAVLKEY Key)
 {
-    KAVLNODECORE *pNode;
+    KAVLNODE *pNode;
     if (*ppTree == KAVL_NULL)
         return NULL;
 
     pNode = KAVL_GET_POINTER(ppTree);
-    while (KAVL_NE(pNode->Key, Key))
+    while (KAVL_NE(pNode->mKey, Key))
     {
-        if (KAVL_G(pNode->Key, Key))
+        if (KAVL_G(pNode->mKey, Key))
         {
-            if (pNode->pLeft == KAVL_NULL)
+            if (pNode->mpLeft == KAVL_NULL)
                 return NULL;
-            pNode = KAVL_GET_POINTER(&pNode->pLeft);
+            pNode = KAVL_GET_POINTER(&pNode->mpLeft);
         }
         else
         {
-            if (pNode->pRight == KAVL_NULL)
+            if (pNode->mpRight == KAVL_NULL)
                 return NULL;
-            pNode = KAVL_GET_POINTER(&pNode->pRight);
+            pNode = KAVL_GET_POINTER(&pNode->mpRight);
         }
     }

trunk/kStuff/include/k/kAvlTmpl/kAvlGetBestFit.h

@@ -38 +38 @@
  *          <= (below): the node where you last turned right.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
+KAVL_DECL(KAVLNODE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
 {
-    register KAVLNODECORE *pNode;
-    KAVLNODECORE *pNodeLast;
+    register KAVLNODE  *pNode;
+    KAVLNODE           *pNodeLast;
 
     if (*ppTree == KAVL_NULL)
@@ -49 +49 @@
     pNodeLast = NULL;
     if (fAbove)
-    {   /* pNode->Key >= Key */
-        while (KAVL_NE(pNode->Key, Key))
+    {   /* pNode->mKey >= Key */
+        while (KAVL_NE(pNode->mKey, Key))
         {
-            if (KAVL_G(pNode->Key, Key))
+            if (KAVL_G(pNode->mKey, Key))
             {
-                if (pNode->pLeft == KAVL_NULL)
+                if (pNode->mpLeft == KAVL_NULL)
                     return pNode;
                 pNodeLast = pNode;
-                pNode = KAVL_GET_POINTER(&pNode->pLeft);
+                pNode = KAVL_GET_POINTER(&pNode->mpLeft);
             }
             else
             {
-                if (pNode->pRight == KAVL_NULL)
+                if (pNode->mpRight == KAVL_NULL)
                     return pNodeLast;
-                pNode = KAVL_GET_POINTER(&pNode->pRight);
+                pNode = KAVL_GET_POINTER(&pNode->mpRight);
             }
         }
     }
     else
-    {   /* pNode->Key <= Key */
-        while (KAVL_NE(pNode->Key, Key))
+    {   /* pNode->mKey <= Key */
+        while (KAVL_NE(pNode->mKey, Key))
         {
-            if (KAVL_G(pNode->Key, Key))
+            if (KAVL_G(pNode->mKey, Key))
             {
-                if (pNode->pLeft == KAVL_NULL)
+                if (pNode->mpLeft == KAVL_NULL)
                     return pNodeLast;
-                pNode = KAVL_GET_POINTER(&pNode->pLeft);
+                pNode = KAVL_GET_POINTER(&pNode->mpLeft);
             }
             else
             {
-                if (pNode->pRight == KAVL_NULL)
+                if (pNode->mpRight == KAVL_NULL)
                     return pNode;
                 pNodeLast = pNode;
-                pNode = KAVL_GET_POINTER(&pNode->pRight);
+                pNode = KAVL_GET_POINTER(&pNode->mpRight);
             }
         }

trunk/kStuff/include/k/kAvlTmpl/kAvlGetWithParent.h

@@ -36 +36 @@
  * @param     Key       Key value of the node which is to be found.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetWithParent)(KAVLTREEPTR *ppTree, KAVLNODECORE **ppParent, KAVLKEY Key)
+KAVL_DECL(KAVLNODE *) KAVL_FN(GetWithParent)(KAVLTREEPTR *ppTree, KAVLNODE **ppParent, KAVLKEY Key)
 {
-    register KAVLNODECORE *pNode = KAVL_GET_POINTER_NULL(ppTree);
-    register KAVLNODECORE *pParent = NULL;
+    register KAVLNODE *pNode = KAVL_GET_POINTER_NULL(ppTree);
+    register KAVLNODE *pParent = NULL;
 
     while (     pNode != NULL
-           &&   KAVL_NE(pNode->Key, Key))
+           &&   KAVL_NE(pNode->mKey, Key))
     {
         pParent = pNode;
-        if (KAVL_G(pNode->Key, Key))
-            pNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
+        if (KAVL_G(pNode->mKey, Key))
+            pNode = KAVL_GET_POINTER_NULL(&pNode->mpLeft);
         else
-            pNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
+            pNode = KAVL_GET_POINTER_NULL(&pNode->mpRight);
     }
 

trunk/kStuff/include/k/kAvlTmpl/kAvlRemove2.h

@@ -36 +36 @@
  *          easier to manage.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
+KAVL_DECL(KAVLNODE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODE *pNode)
 {
 #ifdef KAVL_EQUAL_ALLOWED
@@ -42 +42 @@
      * Find the right node by key and see if it's what we want.
      */
-    KAVLNODECORE *pParent;
-    KAVLNODECORE *pCurNode = KAVL_FN(GetWithParent)(ppTree, pNode->Key, &pParent);
+    KAVLNODE *pParent;
+    KAVLNODE *pCurNode = KAVL_FN(GetWithParent)(ppTree, pNode->mKey, &pParent);
     if (!pCurNode)
         return NULL;
@@ -51 +51 @@
          * It's not the one we want, but it could be in the duplicate list.
          */
-        while (pCurNode->pList != KAVL_NULL)
+        while (pCurNode->mpList != KAVL_NULL)
         {
-            KAVLNODECORE *pNext = KAVL_GET_POINTER(&pCurNode->pList);
+            KAVLNODE *pNext = KAVL_GET_POINTER(&pCurNode->mpList);
             if (pNext == pNode)
             {
-                KAVL_SET_POINTER_NULL(&pCurNode->pList, KAVL_GET_POINTER_NULL(&pNode->pList));
-                pNode->pList = KAVL_NULL;
+                KAVL_SET_POINTER_NULL(&pCurNode->mpList, KAVL_GET_POINTER_NULL(&pNode->mpList));
+                pNode->mpList = KAVL_NULL;
                 return pNode;
             }
@@ -72 +72 @@
      * insert the first duplicate in our place.
      */
-    if (pNode->pList == KAVL_NODE)
-        KAVL_FN(Remove)(ppTree, pNode->Key);
+    if (pNode->mpList == KAVL_NODE)
+        KAVL_FN(Remove)(ppTree, pNode->mKey);
     else
     {
-        KAVLNODECORE *pNewUs = KAVL_GET_POINTER(&pNode->pList);
+        KAVLNODE *pNewUs = KAVL_GET_POINTER(&pNode->mpList);
 
-        pNewUs->uchHeight = pNode->uchHeight;
+        pNewUs->mHeight = pNode->mHeight;
 
-        if (pNode->pLeft != KAVL_NULL)
-            KAVL_SET_POINTER(&pNewUs->pLeft, KAVL_GET_POINTER(&pNode->pLeft))
+        if (pNode->mpLeft != KAVL_NULL)
+            KAVL_SET_POINTER(&pNewUs->mpLeft, KAVL_GET_POINTER(&pNode->mpLeft))
         else
-            pNewUs->pLeft = KAVL_NULL;
+            pNewUs->mpLeft = KAVL_NULL;
 
-        if (pNode->pRight != KAVL_NULL)
-            KAVL_SET_POINTER(&pNewUs->pRight, KAVL_GET_POINTER(&pNode->pRight))
+        if (pNode->mpRight != KAVL_NULL)
+            KAVL_SET_POINTER(&pNewUs->mpRight, KAVL_GET_POINTER(&pNode->mpRight))
         else
-            pNewUs->pRight = KAVL_NULL;
+            pNewUs->mpRight = KAVL_NULL;
 
         if (pParent)
         {
-            if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
-                KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
+            if (KAVL_GET_POINTER_NULL(&pParent->mpLeft) == pNode)
+                KAVL_SET_POINTER(&pParent->mpLeft, pNewUs);
             else
-                KAVL_SET_POINTER(&pParent->pRight, pNewUs);
+                KAVL_SET_POINTER(&pParent->mpRight, pNewUs);
         }
         else
@@ -109 +109 @@
      * of wrong nodes but just uses this API for his convenience.
      */
-    KAVLNODECORE *pRemovedNode = KAVL_FN(Remove)(ppTree, pNode->Key);
+    KAVLNODE *pRemovedNode = KAVL_FN(Remove)(ppTree, pNode->mKey);
     if (pRemovedNode == pNode)
         return pRemovedNode;

trunk/kStuff/include/k/kAvlTmpl/kAvlRemoveBestFit.h

@@ -39 +39 @@
  *          code size, and the likelyhood for bugs.
  */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(RemoveBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
+KAVL_DECL(KAVLNODE *) KAVL_FN(RemoveBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
 {
     /*
@@ -46 +46 @@
      * removing the in-tree node as this is way cheaper.
      */
-    KAVLNODECORE *pNode = KAVL_FN(GetBestFit)(ppTree, Key, fAbove);
+    KAVLNODE *pNode = KAVL_FN(GetBestFit)(ppTree, Key, fAbove);
     if (pNode != NULL)
     {
 #ifdef KAVL_EQUAL_ALLOWED
-        if (pNode->pList != KAVL_NULL)
+        if (pNode->mpList != KAVL_NULL)
         {
-            KAVLANODECORE *pRet = KAVL_GET_POINTER(&pNode->pList);
-            KAVL_SET_POINTER_NULL(&pNode->pList, &pRet->pList);
+            KAVLNODE *pRet = KAVL_GET_POINTER(&pNode->mpList);
+            KAVL_SET_POINTER_NULL(&pNode->mpList, &pRet->mpList);
             return pRet;
         }
 #endif
-        pNode = KAVL_FN(Remove)(ppTree, pNode->Key);
+        pNode = KAVL_FN(Remove)(ppTree, pNode->mKey);
     }
     return pNode;

trunk/kStuff/include/k/kAvlTmpl/kAvlUndef.h

@@ -35 +35 @@
 #undef KAVL_STD_KEY_COMP
 #undef KAVLKEY
-#undef KAVLNODECORE
+#undef KAVLNODE
 #undef KAVLTREEPTR
 #undef KAVL_FN
@@ -41 +41 @@
 #undef KAVL_INT
 #undef KAVL_DECL
+#undef mKey
+#undef mKeyLast
+#undef mHeight
+#undef mpLeft
+#undef mpRight
+#undef mpList
 
 /*

trunk/kStuff/include/k/kAvlU32.h

@@ -30 +30 @@
 typedef struct KAVLU32
 {
-    KU32                Key;
-    KU8                 uchHeight;
-    struct KAVLU32     *pLeft;
-    struct KAVLU32     *pRight;
+    KU32                mKey;
+    KU8                 mHeight;
+    struct KAVLU32     *mpLeft;
+    struct KAVLU32     *mpRight;
 } KAVLU32, *PKAVLU32, **PPKAVLU32;
-
-typedef struct
-{
-    KBOOL               fFromLeft;
-    KI8                 cEntries;
-    KU8                 achFlags[32];
-    PKAVLU32            aEntries[32];
-} KAVLU32ENUMDATA, *PKAVLU32ENUMDATA;
-
-typedef int (* PFNKAVLU32CALLBACK)(KAVLU32 *, void *);
 
 /*#define KAVL_EQUAL_ALLOWED*/
@@ -53 +43 @@
 #define KAVL_STD_KEY_COMP
 #define KAVLKEY                 KU32
-#define KAVLNODECORE            KAVLU32
+#define KAVLNODE            KAVLU32
 #define KAVL_FN(name)           kAvlU32 ## name
 #define KAVL_TYPE(prefix,name)  prefix ## KAVLU32 ## name

trunk/kStuff/include/k/kAvloU32.h

@@ -28 +28 @@
 #define ___k_kAvloU32_h___
 
-typedef KU32 KAVLOU32PTR;
+typedef KI32 KAVLOU32PTR;
 
 typedef struct KAVLOU32
 {
-    KU32                Key;
-    KU8                 uchHeight;
-    KAVLOU32PTR         pLeft;
-    KAVLOU32PTR         pRight;
+    KU32                u32;
+    KU8                 cFloorsToGo;
+    KAVLOU32PTR         offLeft;
+    KAVLOU32PTR         offRight;
 } KAVLOU32, *PKAVLOU32, **PPKAVLOU32;
 
-typedef struct
-{
-    KBOOL               fFromLeft;
-    KI8                 cEntries;
-    KU8                 achFlags[32];
-    PKAVLOU32           aEntries[32];
-} KAVLOU32ENUMDATA, *PKAVLOU32ENUMDATA;
-
-typedef int (* PFNKAVLOU32CALLBACK)(KAVLOU32 *, void *);
+#define mKey                    u32
+#define mHeight                 cFloorsToGo
+#define mpLeft                  offLeft
+#define mpRight                 offRight
 
 /*#define KAVL_EQUAL_ALLOWED*/
@@ -56 +51 @@
 #define KAVLKEY                 KU32
 #define KAVLTREEPTR             KAVLOU32PTR
-#define KAVLNODECORE            KAVLOU32
+#define KAVLNODE                KAVLOU32
 #define KAVL_FN(name)           kAvloU32 ## name
 #define KAVL_TYPE(prefix,name)  prefix ## KAVLOU32 ## name

trunk/kStuff/include/k/kAvlrU32.h

@@ -30 +30 @@
 typedef struct KAVLRU32
 {
-    KU32                Key;
-    KU32                KeyLast;
-    struct KAVLRU32    *pLeft;
-    struct KAVLRU32    *pRight;
-    KU8                 uchHeight;
+    KU32                u32Start;
+    KU32                u32Last;
+    struct KAVLRU32    *mpLeft;
+    struct KAVLRU32    *mpRight;
+    KU8                 mHeight;
 } KAVLRU32, *PKAVLRU32, **PPKAVLRU32;
 
-typedef struct
-{
-    KBOOL               fFromLeft;
-    KI8                 cEntries;
-    KU8                 achFlags[32];
-    PKAVLRU32           aEntries[32];
-} KAVLRU32ENUMDATA, *PKAVLRU32ENUMDATA;
-
-typedef int (* PFNKAVLRU32CALLBACK)(KAVLRU32 *, void *);
+#define mKey                    u32Start
+#define mKeyLast                u32Last
 
 /*#define KAVL_EQUAL_ALLOWED*/
@@ -54 +47 @@
 #define KAVL_STD_KEY_COMP
 #define KAVLKEY                 KU32
-#define KAVLNODECORE            KAVLRU32
+#define KAVLNODE                KAVLRU32
 #define KAVL_FN(name)           kAvlrU32 ## name
 #define KAVL_TYPE(prefix,name)  prefix ## KAVLRU32 ## name