Changeset 3555

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.

Location:

trunk/kStuff/include/k

Files:

• kAVLTmpl/kAVLBase.h (modified) (5 diffs)
• kAVLTmpl/kAVLDoWithAll.h (modified) (5 diffs)
• kAVLTmpl/kAVLEnum.h (modified) (9 diffs)
• kAVLTmpl/kAVLGet.h (modified) (1 diff)
• kAVLTmpl/kAVLGet2.h (deleted)
• kAVLTmpl/kAVLGetBestFit.h (modified) (1 diff)
• kAVLTmpl/kAVLGetWithParent.h (modified) (2 diffs)
• kAVLTmpl/kAVLRemove2.h (modified) (1 diff)
• kAVLTmpl/kAVLRemoveBestFit.h (modified) (1 diff)
• kAVLTmpl/kAVLUndef.h (added)
• kAvlU32.h (added)
• kAvloU32.h (added)
• kAvlrU32.h (added)

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

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLBase - basic routines for all AVL trees.
- *
- * Copyright (c) 2001-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
- */
-
-#ifndef _kAVLBase_h_
-#define _kAVLBase_h_
-
-
-/** @design kAVL Template configuration.
- *  This is a template made to implemented multiple AVL trees. The difference
- *  between the implementations are related to the key used.
- *
- *  #define KAVL_FN
- *  Use this to altern the names of the AVL functions.
- *  Must be defined.
- *
- *  #define KAVL_EQUAL_ALLOWED
+ * kAVLTmpl - Templated AVL Trees, The Mandatory Base Code.
+ */
+
+/*
+ * Copyright (c) 2001-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
+
+
+/** @page pg_kAVLTmpl   Template Configuration.
+ *
+ *  This is a templated implementation of AVL trees in C. The template
+ *  parameters relates to the kind of key used and how duplicates are
+ *  treated.
+ *
+ *  \#define KAVL_EQUAL_ALLOWED
  *  Define this to tell us that equal keys are allowed.
- *  Then Equal keys will be put a list pointed to by pList in the KAVLNODECORE.
+ *  Then Equal keys will be put in a list pointed to by KAVLNODECORE::pList.
  *  This is by default not defined.
  *
- *  #define KAVL_CHECK_FOR_EQUAL_INSERT
+ *  \#define KAVL_CHECK_FOR_EQUAL_INSERT
  *  Define this to enable insert check for equal nodes.
  *  This is by default not defined.
  *
- *  #define KAVL_MAX_STACK
- *  Use this to specify the number of stack entries the stack we uses when inserting
- *  and removing nodes from the tree will need. I think the size should be about
+ *  \#define KAVL_MAX_STACK
+ *  Use this to specify the max number of stack entries the stack will use when inserting
+ *  and removing nodes from the tree. The size should be something like
  *      log2(<max nodes>) + 3
  *  Must be defined.
  *
- */
+ *  \#define KAVL_RANGE
+ *  Define this to enable key ranges.
+ *
+ *  \#define KAVL_OFFSET
+ *  Define this to link the tree together using self relative offset
+ *  instead of memory pointers, thus making the entire tree relocatable
+ *  provided all the nodes - including the root node variable - are moved
+ *  the exact same distance.
+ *
+ *  \#define KAVLKEY
+ *  Define this to the name of the AVL key type.
+ *
+ *  \#define KAVL_STD_KEY_COMP
+ *  Define this to use the standard key compare macros. If not set all the
+ *  compare operations for KAVLKEY have to be defined: KAVL_G, KAVL_E, KAVL_NE,
+ *  KAVL_R_IS_IDENTICAL, KAVL_R_IS_INTERSECTING and KAVL_R_IS_IN_RANGE. The latter
+ *  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 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 *.
+ *
+ *  \#define KAVL_FN
+ *  Use this to alter the names of the AVL functions.
+ *  Must be defined.
+ *
+ *  \#define KAVL_TYPE(prefix, name)
+ *  Use this to make external type names and unique. The prefix may be empty.
+ *  Must be defined.
+ *
+ *  \#define KAVL_INT(name)
+ *  Use this to make internal type names and unique. The prefix may be empty.
+ *  Must be defined.
+ *
+ *  \#define KAVL_DECL(rettype)
+ *  Function declaration macro that should be set according to the scope
+ *  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
+ *  implementation. This depends on the compiler doing a decent job in both
+ *  making use of the inlined code and to eliminate const variables.
+ */
+
+
+/*******************************************************************************
+*   Internal Functions                                                         *
+*******************************************************************************/
+#include <k/kDefs.h>
+#include <k/kTypes.h>
+#include <k/kHlpAssert.h>
+
 
 /*******************************************************************************
 *   Defined Constants And Macros                                               *
 *******************************************************************************/
-#define AVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? pNode->uchHeight : 0))
+#define KAVL_HEIGHTOF(pNode) ((unsigned char)((pNode) != NULL ? (pNode)->uchHeight : 0))
+
+/** @def KAVL_GET_POINTER
+ * Reads a 'pointer' value.
+ *
+ * @returns The native pointer.
+ * @param   pp      Pointer to the pointer to read.
+ * @internal
+ */
+
+/** @def KAVL_GET_POINTER_NULL
+ * Reads a 'pointer' value which can be KAVL_NULL.
+ *
+ * @returns The native pointer.
+ * @returns NULL pointer if KAVL_NULL.
+ * @param   pp      Pointer to the pointer to read.
+ * @internal
+ */
+
+/** @def KAVL_SET_POINTER
+ * Writes a 'pointer' value.
+ * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
+ *
+ * @returns stored pointer.
+ * @param   pp      Pointer to where to store the pointer.
+ * @param   p       Native pointer to assign to *pp.
+ * @internal
+ */
+
+/** @def KAVL_SET_POINTER_NULL
+ * Writes a 'pointer' value which can be KAVL_NULL.
+ *
+ * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
+ * if p is not KAVL_NULL of course.
+ *
+ * @returns stored pointer.
+ * @param   pp      Pointer to where to store the pointer.
+ * @param   pp2     Pointer to where to pointer to assign to pp. This can be KAVL_NULL
+ * @internal
+ */
+
+#ifndef KAVLTREEPTR
+# define KAVLTREEPTR                        KAVLNODECORE *
+#endif
+
+#ifdef KAVL_OFFSET
+# define KAVL_GET_POINTER(pp)               ( (KAVLNODECORE *)((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)) )
+# define KAVL_SET_POINTER_NULL(pp, pp2)     ( (*(pp)) = *(pp2) != KAVL_NULL ? (KIPTR)KAVL_GET_POINTER(pp2) - (KIPTR)(pp) : KAVL_NULL )
+#else
+# define KAVL_GET_POINTER(pp)               ( *(pp) )
+# define KAVL_GET_POINTER_NULL(pp)          ( *(pp) )
+# define KAVL_SET_POINTER(pp, p)            ( (*(pp)) = (p) )
+# define KAVL_SET_POINTER_NULL(pp, pp2)     ( (*(pp)) = *(pp2) )
+#endif
+
+
+/** @def KAVL_NULL
+ * The NULL 'pointer' equivalent.
+ */
+#ifdef KAVL_OFFSET
+# define KAVL_NULL     0
+#else
+# define KAVL_NULL     NULL
+#endif
+
+#ifdef KAVL_STD_KEY_COMP
+# define KAVL_G(key1, key2)                 ( (key1) >  (key2) )
+# define KAVL_E(key1, key2)                 ( (key1) == (key2) )
+# define KAVL_NE(key1, key2)                ( (key1) != (key2) )
+# ifdef KAVL_RANGE
+#  define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)       ( (key1B) == (key2B) && (key1E) == (key2E) )
+#  define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)    ( (key1B) <= (key2E) && (key1E) >= (key2B) )
+#  define KAVL_R_IS_IN_RANGE(key1B, key1E, key2)                KAVL_R_IS_INTERSECTING(key1B, key2, key1E, key2)
+# endif
+#endif
+
+#ifndef KAVL_RANGE
+# define KAVL_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)     KAVL_E(key1B, key2B)
+# define KAVL_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)        KAVL_E(key1B, key2B)
+#endif
+
 
 
@@ -48 +204 @@
 *******************************************************************************/
 /*
- * A stack used to avoid recursive calls...
- */
-typedef struct _kAvlStack
+ * Two stacks that's used to avoid recursive calls.
+ */
+typedef struct
 {
     unsigned        cEntries;
-    PPKAVLNODECORE  aEntries[KAVL_MAX_STACK];
-} KAVLSTACK, *PKAVLSTACK;
-
-typedef struct _kAvlStack2
+    KAVLTREEPTR    *aEntries[KAVL_MAX_STACK];
+} KAVL_INT(STACK);
+
+typedef struct
 {
     unsigned        cEntries;
-    PKAVLNODECORE   aEntries[KAVL_MAX_STACK];
+    KAVLNODECORE   *aEntries[KAVL_MAX_STACK];
     char            achFlags[KAVL_MAX_STACK];
-} KAVLSTACK2, *PLAVLSTACK2;
-
-
-/*******************************************************************************
-*   Internal Functions                                                         *
-*******************************************************************************/
-KINLINE void KAVL_FN(Rebalance)(PKAVLSTACK pStack);
-
-
+} KAVL_INT(STACK2);
+
+
+/**
+ * Rewinds a stack of node pointer pointers, rebalancing the tree.
+ *
+ * @param     pStack  Pointer to stack to rewind.
+ * @sketch    LOOP thru all stack entries
+ *            BEGIN
+ *                Get pointer to pointer to node (and pointer to node) from the stack.
+ *                IF 2 higher left subtree than in right subtree THEN
+ *                BEGIN
+ *                    IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
+ *                                *                       n+2|n+3
+ *                              /   \                     /     \
+ *                            n+2    n       ==>         n+1   n+1|n+2
+ *                           /   \                             /     \
+ *                         n+1 n|n+1                          n|n+1  n
+ *
+ *                         Or with keys:
+ *
+ *                               4                           2
+ *                             /   \                       /   \
+ *                            2     5        ==>          1     4
+ *                           / \                               / \
+ *                          1   3                             3   5
+ *
+ *                    ELSE
+ *                                *                         n+2
+ *                              /   \                      /   \
+ *                            n+2    n                   n+1   n+1
+ *                           /   \           ==>        /  \   /  \
+ *                          n    n+1                    n  L   R   n
+ *                               / \
+ *                              L   R
+ *
+ *                         Or with keys:
+ *                               6                           4
+ *                             /   \                       /   \
+ *                            2     7        ==>          2     6
+ *                          /   \                       /  \  /  \
+ *                          1    4                      1  3  5  7
+ *                              / \
+ *                             3   5
+ *                END
+ *                ELSE IF 2 higher in right subtree than in left subtree THEN
+ *                BEGIN
+ *                    Same as above but left <==> right. (invert the picture)
+ *                ELSE
+ *                    IF correct height THEN break
+ *                    ELSE correct height.
+ *            END
+ */
+K_DECL_INLINE(void) KAVL_FN(Rebalance)(KAVL_INT(STACK) *pStack)
+{
+    while (pStack->cEntries > 0)
+    {
+        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)
+        {
+            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)
+            {
+                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(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(ppNode, pLeftRightNode);
+            }
+        }
+        else if (uchLeftHeight + 1 < uchRightHeight)
+        {
+            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)
+            {
+                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(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(ppNode, pRightLeftNode);
+            }
+        }
+        else
+        {
+            register unsigned char uchHeight = (unsigned char)(K_MAX(uchLeftHeight, uchRightHeight) + 1);
+            if (uchHeight == pNode->uchHeight)
+                break;
+            pNode->uchHeight = uchHeight;
+        }
+    }
+
+}
 
 
@@ -78 +347 @@
  * @param     ppTree  Pointer to the AVL-tree root node pointer.
  * @param     pNode   Pointer to the node which is to be added.
- * @sketch    Find the location of the node (using binary three algorithm.):
+ * @sketch    Find the location of the node (using binary tree algorithm.):
  *            LOOP until NULL leaf pointer
  *            BEGIN
@@ -89 +358 @@
  *            Fill in leaf node and insert it.
  *            Rebalance the tree.
- * @status    completely implemented.
- * @author    knut st. osmundsen
- */
-KBOOL KLIBCALL KAVL_FN(Insert)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
+ */
+KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
 {
-    KLOGENTRY2("KBOOL","PPKAVLNODECORE ppTree, PKAVLNODECORE pNode", ppTree, pNode);
-    KAVLSTACK               AVLStack;
-    PPKAVLNODECORE          ppCurNode = ppTree;
+    KAVL_INT(STACK)        AVLStack;
+    KAVLTREEPTR            *ppCurNode = ppTree;
     register KAVLKEY        Key = pNode->Key;
-    register PKAVLNODECORE  pCurNode;
+#ifdef KAVL_RANGE
+    register KAVLKEY        KeyLast = pNode->KeyLast;
+#endif
+    register KAVLNODECORE  *pCurNode;
 
     AVLStack.cEntries = 0;
 
-    while ((pCurNode = *ppCurNode) != NULL)
+#ifdef KAVL_RANGE
+    if (Key > KeyLast)
+        return false;
+#else
+    K_NOREF(Key);
+#endif
+
+    while (*ppCurNode != KAVL_NULL)
     {
-        kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
+        pCurNode = KAVL_GET_POINTER(ppCurNode);
+
+        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
         AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
-        #ifndef KAVL_EQUAL_ALLOWED
-        if (AVL_G(pCurNode->Key, Key))
-            ppCurNode = &pCurNode->pLeft;
-        else
-            ppCurNode = &pCurNode->pRight;
-        #else
-        if (AVL_G(pCurNode->Key, Key))
-            ppCurNode = &pCurNode->pLeft;
-        else if (AVL_L(pCurNode->Key, Key))
-            ppCurNode = &pCurNode->pRight;
-        else
+#ifdef KAVL_EQUAL_ALLOWED
+        if (KAVL_R_IS_IDENTICAL(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
         {
             /*
              * If equal then we'll use a list of equal nodes.
              */
-            pNode->pLeft = pNode->pRight = NULL;
+            pNode->pLeft = pNode->pRight = KAVL_NULL;
             pNode->uchHeight = 0;
-            pNode->pList = pCurNode->pList;
-            pCurNode->pList = pNode;
-            KLOGEXIT(FALSE);
-            return TRUE;
+            KAVL_SET_POINTER_NULL(&pNode->pList, &pCurNode->pList);
+            KAVL_SET_POINTER(&pCurNode->pList, pNode);
+            return K_TRUE;
         }
-        #endif
+#endif
+#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
+        if (KAVL_R_IS_INTERSECTING(pCurNode->Key, Key, pCurNode->KeyLast, KeyLast))
+            return K_FALSE;
+#endif
+        if (KAVL_G(pCurNode->Key, Key))
+            ppCurNode = &pCurNode->pLeft;
+        else
+            ppCurNode = &pCurNode->pRight;
     }
 
-#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
-    /*
-     * Fail if equal insert was attempted.
-     */
-    if (AVLStack.cEntries > 0 && AVL_E((*AVLStack.aEntries[AVLStack.cEntries-1])->Key, pNode->Key))
-    {
-        KLOGEXIT(FALSE);
-        return FALSE;
-    }
-#endif
-
-    #ifndef KAVL_EQUAL_ALLOWED
-    pNode->pLeft = pNode->pRight = NULL;
-    #else
-    pNode->pList = pNode->pLeft = pNode->pRight = NULL;
-    #endif
+    pNode->pLeft = pNode->pRight = KAVL_NULL;
+#ifdef KAVL_EQUAL_ALLOWED
+    pNode->pList = KAVL_NULL;
+#endif
     pNode->uchHeight = 1;
-    *ppCurNode = pNode;
-
-    KAVL_FN(Rebalance)(SSToDS(&AVLStack));
-    KLOGEXIT(TRUE);
-    return TRUE;
+    KAVL_SET_POINTER(ppCurNode, pNode);
+
+    KAVL_FN(Rebalance)(&AVLStack);
+    return K_TRUE;
 }
 
@@ -194 +457 @@
  *            END
  *            return pointer to the removed node (if found).
- * @status    completely implemented.
- * @author    knut st. osmundsen
- */
-PKAVLNODECORE KLIBCALL KAVL_FN(Remove)(PPKAVLNODECORE ppTree, KAVLKEY Key)
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
 {
-    KLOGENTRY2("PKAVLNODECORE","PPKAVLNODECORE ppTree, KAVLKEY Key", ppTree, Key);
-    KAVLSTACK                AVLStack;
-    PPKAVLNODECORE           ppDeleteNode = ppTree;
-    register PKAVLNODECORE   pDeleteNode;
+    KAVL_INT(STACK)         AVLStack;
+    KAVLTREEPTR             *ppDeleteNode = ppTree;
+    register KAVLNODECORE   *pDeleteNode;
 
     AVLStack.cEntries = 0;
 
-    while ((pDeleteNode = *ppDeleteNode) != NULL)
+    for (;;)
     {
-        kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
+        if (*ppDeleteNode == KAVL_NULL)
+            return NULL;
+        pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
+
+        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
         AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
-        #ifndef AVL_CMP
-        if (AVL_E(pDeleteNode->Key, Key))
+        if (KAVL_E(pDeleteNode->Key, Key))
             break;
 
-        if (AVL_G(pDeleteNode->Key, Key))
+        if (KAVL_G(pDeleteNode->Key, Key))
             ppDeleteNode = &pDeleteNode->pLeft;
         else
             ppDeleteNode = &pDeleteNode->pRight;
-        #else
+    }
+
+    if (pDeleteNode->pLeft != 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)
         {
-        int register iDiff;
-        if ((iDiff = AVL_CMP(pDeleteNode->Key, Key)) == 0)
-            break;
-
-        if (iDiff > 0)
-            ppDeleteNode = &pDeleteNode->pLeft;
-        else
-            ppDeleteNode = &pDeleteNode->pRight;
+            kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
+            AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
+            ppLeftLeast = &pLeftLeast->pRight;
+            pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
         }
-        #endif
+
+        /* link out pLeftLeast */
+        KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->pLeft);
+
+        /* 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(ppDeleteNode, pLeftLeast);
+        AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
     }
-
-    if (pDeleteNode != NULL)
+    else
     {
-        if (pDeleteNode->pLeft != NULL)
-        {
-            unsigned                iStackEntry = AVLStack.cEntries;
-            PPKAVLNODECORE           ppLeftLeast = &pDeleteNode->pLeft;
-            register PKAVLNODECORE   pLeftLeast;
-
-            while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
-            {
-                kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
-                AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
-                ppLeftLeast = &pLeftLeast->pRight;
-                pLeftLeast  = pLeftLeast->pRight;
-            }
-
-            /* link out pLeftLeast */
-            *ppLeftLeast = pLeftLeast->pLeft;
-
-            /* link in place of the delete node. */
-            pLeftLeast->pLeft = pDeleteNode->pLeft;
-            pLeftLeast->pRight = pDeleteNode->pRight;
-            pLeftLeast->uchHeight = pDeleteNode->uchHeight;
-            *ppDeleteNode = pLeftLeast;
-            AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
-        }
-        else
-        {
-            *ppDeleteNode = pDeleteNode->pRight;
-            AVLStack.cEntries--;
-        }
-
-        KAVL_FN(Rebalance)(SSToDS(&AVLStack));
+        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
+        AVLStack.cEntries--;
     }
 
-    KLOGEXIT(pDeleteNode);
+    KAVL_FN(Rebalance)(&AVLStack);
     return pDeleteNode;
 }
 
-
-/**
- * Rewindes a stack of pointer to pointers to nodes, rebalancing the tree.
- * @param     pStack  Pointer to stack to rewind.
- * @sketch    LOOP thru all stack entries
- *            BEGIN
- *                Get pointer to pointer to node (and pointer to node) from stack.
- *                IF 2 higher left subtree than in right subtree THEN
- *                BEGIN
- *                    IF higher (or equal) left-sub-subtree than right-sub-subtree THEN
- *                                *                       n+2|n+3
- *                              /   \                     /     \
- *                            n+2    n       ==>         n+1   n+1|n+2
- *                           /   \                             /     \
- *                         n+1 n|n+1                          n|n+1  n
- *
- *                         Or with keys:
- *
- *                               4                           2
- *                             /   \                       /   \
- *                            2     5        ==>          1     4
- *                           / \                               / \
- *                          1   3                             3   5
- *
- *                    ELSE
- *                                *                         n+2
- *                              /   \                      /   \
- *                            n+2    n                   n+1   n+1
- *                           /   \           ==>        /  \   /  \
- *                          n    n+1                    n  L   R   n
- *                               / \
- *                              L   R
- *
- *                         Or with keys:
- *                               6                           4
- *                             /   \                       /   \
- *                            2     7        ==>          2     6
- *                          /   \                       /  \  /  \
- *                          1    4                      1  3  5  7
- *                              / \
- *                             3   5
- *                END
- *                ELSE IF 2 higher in right subtree than in left subtree THEN
- *                BEGIN
- *                    Same as above but left <==> right. (invert the picture)
- *                ELSE
- *                    IF correct height THEN break
- *                    ELSE correct height.
- *            END
- * @status
- * @author    knut st. osmundsen
- * @remark
- */
-KINLINE void KAVL_FN(Rebalance)(PKAVLSTACK pStack)
-{
-    KLOGENTRY1("void","PKAVLSTACK pStack", pStack);
-    while (pStack->cEntries > 0)
-    {
-        PPKAVLNODECORE   ppNode = pStack->aEntries[--pStack->cEntries];
-        PKAVLNODECORE    pNode = *ppNode;
-        PKAVLNODECORE    pLeftNode = pNode->pLeft;
-        unsigned char   uchLeftHeight = AVL_HEIGHTOF(pLeftNode);
-        PKAVLNODECORE    pRightNode = pNode->pRight;
-        unsigned char   uchRightHeight = AVL_HEIGHTOF(pRightNode);
-
-        if (uchRightHeight + 1 < uchLeftHeight)
-        {
-            PKAVLNODECORE    pLeftLeftNode = pLeftNode->pLeft;
-            PKAVLNODECORE    pLeftRightNode = pLeftNode->pRight;
-            unsigned char   uchLeftRightHeight = AVL_HEIGHTOF(pLeftRightNode);
-
-            if (AVL_HEIGHTOF(pLeftLeftNode) >= uchLeftRightHeight)
-            {
-                pNode->pLeft = pLeftRightNode;
-                pLeftNode->pRight = pNode;
-                pLeftNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchLeftRightHeight)));
-                *ppNode = pLeftNode;
-            }
-            else
-            {
-                pLeftNode->pRight = pLeftRightNode->pLeft;
-                pNode->pLeft = pLeftRightNode->pRight;
-                pLeftRightNode->pLeft = pLeftNode;
-                pLeftRightNode->pRight = pNode;
-                pLeftNode->uchHeight = pNode->uchHeight = uchLeftRightHeight;
-                pLeftRightNode->uchHeight = uchLeftHeight;
-                *ppNode = pLeftRightNode;
-            }
-        }
-        else if (uchLeftHeight + 1 < uchRightHeight)
-        {
-            PKAVLNODECORE    pRightLeftNode = pRightNode->pLeft;
-            unsigned char   uchRightLeftHeight = AVL_HEIGHTOF(pRightLeftNode);
-            PKAVLNODECORE    pRightRightNode = pRightNode->pRight;
-
-            if (AVL_HEIGHTOF(pRightRightNode) >= uchRightLeftHeight)
-            {
-                pNode->pRight = pRightLeftNode;
-                pRightNode->pLeft = pNode;
-                pRightNode->uchHeight = (unsigned char)(1 + (pNode->uchHeight = (unsigned char)(1 + uchRightLeftHeight)));
-                *ppNode = pRightNode;
-            }
-            else
-            {
-                pRightNode->pLeft = pRightLeftNode->pRight;
-                pNode->pRight = pRightLeftNode->pLeft;
-                pRightLeftNode->pRight = pRightNode;
-                pRightLeftNode->pLeft = pNode;
-                pRightNode->uchHeight = pNode->uchHeight = uchRightLeftHeight;
-                pRightLeftNode->uchHeight = uchRightHeight;
-                *ppNode = pRightLeftNode;
-            }
-        }
-        else
-        {
-            register unsigned char uchHeight = (unsigned char)(KMAX(uchLeftHeight, uchRightHeight) + 1);
-            if (uchHeight == pNode->uchHeight)
-                break;
-            pNode->uchHeight = uchHeight;
-        }
-    }
-
-    KLOGEXITVOID();
-}
-
-
-
-#endif

trunk/kStuff/include/k/kAVLTmpl/kAVLDoWithAll.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLDoWithAll - Do with all nodes routine for AVL trees.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, The Callback Iterator.
  */
 
-#ifndef _kAVLDoWithAll_h_
-#define _kAVLDoWithAll_h_
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
  * Iterates tru all nodes in the given tree.
- * @returns   0 on success. Return from callback on failiure.
- * @param     ppTree   Pointer to the AVL-tree root node pointer.
- * @param     fFromLeft    TRUE:  Left to right.
- *                         FALSE: Right to left.
+ *
+ * @returns   0 on success. Return from callback on failure.
+ * @param     ppTree       Pointer to the AVL-tree root node pointer.
+ * @param     fFromLeft    K_TRUE:  Left to right.
+ *                         K_FALSE: Right to left.
  * @param     pfnCallBack  Pointer to callback function.
- * @param     pvParam      Userparameter passed on to the callback function.
- * @status    completely implemented.
- * @author    knut st. osmundsen
+ * @param     pvUser       User parameter passed on to the callback function.
  */
-unsigned KLIBCALL KAVL_FN(DoWithAll)(PPKAVLNODECORE ppTree, int fFromLeft, PKAVLCALLBACK pfnCallBack, void * pvParam)
+KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLTREEPTR *ppTree, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
 {
-    KLOGENTRY4("unsigned","PPKAVLNODECORE ppTree, int fFromLeft, PKAVLCALLBACK pfnCallBack, void * pvParam", ppTree, fFromLeft, pfnCallBack, pvParam);
-    KAVLSTACK2       AVLStack;
-    PKAVLNODECORE    pNode;
-    unsigned        rc;
+    KAVL_INT(STACK2)   AVLStack;
+    KAVLNODECORE       *pNode;
+    unsigned            rc;
 
-    if (*ppTree == NULL)
+    if (*ppTree == KAVL_NULL)
         return 0;
 
     AVLStack.cEntries = 1;
     AVLStack.achFlags[0] = 0;
-    AVLStack.aEntries[0] = *ppTree;
+    AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
 
     if (fFromLeft)
@@ -47 +58 @@
             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
             {
-                if (pNode->pLeft != NULL)
+                if (pNode->pLeft != KAVL_NULL)
                 {
                     AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = pNode->pLeft;
+                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
                     continue;
                 }
@@ -56 +67 @@
 
             /* center */
-            rc = pfnCallBack(pNode, pvParam);
-            if (rc != 0)
-            {
-                KLOGEXIT(rc);
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
                 return rc;
-            }
 
             /* right */
             AVLStack.cEntries--;
-            if (pNode->pRight != NULL)
+            if (pNode->pRight != KAVL_NULL)
             {
                 AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = pNode->pRight;
+                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
             }
         } /* while */
@@ -82 +90 @@
             if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
             {
-                if (pNode->pRight != NULL)
+                if (pNode->pRight != KAVL_NULL)
                 {
                     AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = pNode->pRight;
+                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
                     continue;
                 }
@@ -91 +99 @@
 
             /* center */
-            rc = pfnCallBack(pNode, pvParam);
-            if (rc != 0)
-            {
-                KLOGEXIT(rc);
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
                 return rc;
-            }
 
             /* left */
             AVLStack.cEntries--;
-            if (pNode->pLeft != NULL)
+            if (pNode->pLeft != KAVL_NULL)
             {
                 AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = pNode->pLeft;
+                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
             }
         } /* while */
     }
 
-    KLOGEXIT(0);
     return 0;
 }
 
-
-#endif
-

trunk/kStuff/include/k/kAVLTmpl/kAVLEnum.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLEnum - Enumeration routine for AVL trees.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Node Enumeration.
  */
 
-#ifndef _kAVLEnum_h_
-#define _kAVLEnum_h_
-
-
-/**
- * Starts an enumeration of all nodes in the given AVL tree.
- * @returns   Pointer to the first node in the tree.
- * @param     ppTree     Pointer to the AVL-tree root node pointer.
- * @param     pEnumData  Pointer to enumeration control data.
- * @param     fFromLeft  TRUE:  Left to right.
- *                       FALSE: Right to left.
- * @status    completely implemented.
- * @author    knut st. osmundsen
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(BeginEnumTree)(PPKAVLNODECORE ppTree, PKAVLENUMDATA pEnumData, int fFromLeft)
-{
-    KLOGENTRY3("PKAVLNODECORE","PPKAVLNODECORE ppTree, PKAVLENUMDATA pEnumData, int fFromLeft", ppTree, pEnumData, fFromLeft);
-    PKAVLNODECORE    pNode;
-    if (*ppTree != NULL)
-    {
-        pEnumData->fFromLeft = (char)fFromLeft;
-        pEnumData->cEntries = 1;
-        pEnumData->aEntries[0] = *ppTree;
-        pEnumData->achFlags[0] = 0;
-    }
-    else
-        pEnumData->cEntries = 0;
-
-    pNode = KAVL_FN(GetNextNode)(pEnumData);
-    KLOGEXIT(pNode);
-    return pNode;
-}
-
 
 /**
@@ -50 +32 @@
  * @author    knut st. osmundsen
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(GetNextNode)(PKAVLENUMDATA pEnumData)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetNextNode)(KAVL_TYPE(,ENUMDATA) *pEnumData)
 {
-    KLOGENTRY1("PKAVLNODECORE","PKAVLENUMDATA pEnumData", pEnumData);
-    PKAVLNODECORE    pNode;
-
     if (pEnumData->fFromLeft)
     {   /* from left */
         while (pEnumData->cEntries > 0)
         {
-            pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
 
             /* left */
@@ -65 +44 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->pLeft != NULL)
+                if (pNode->pLeft != KAVL_NULL)
                 {
                     pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
-                    pEnumData->aEntries[pEnumData->cEntries++] = pNode->pLeft;
+                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
                     continue;
                 }
@@ -77 +56 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                KLOGEXIT(pNode);
                 return pNode;
             }
@@ -83 +61 @@
             /* right */
             pEnumData->cEntries--;
-            if (pNode->pRight != NULL)
+            if (pNode->pRight != KAVL_NULL)
             {
                 pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = pNode->pRight;
+                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
             }
         } /* while */
@@ -94 +72 @@
         while (pEnumData->cEntries > 0)
         {
-            pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
-
+            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
 
             /* right */
@@ -101 +78 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->pRight != NULL)
+                if (pNode->pRight != KAVL_NULL)
                 {
                     pEnumData->achFlags[pEnumData->cEntries] = 0;  /* 0 right, 1 center, 2 left */
-                    pEnumData->aEntries[pEnumData->cEntries++] = pNode->pRight;
+                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
                     continue;
                 }
@@ -113 +90 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                KLOGEXIT(pNode);
                 return pNode;
             }
@@ -119 +95 @@
             /* left */
             pEnumData->cEntries--;
-            if (pNode->pLeft != NULL)
+            if (pNode->pLeft != KAVL_NULL)
             {
                 pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = pNode->pLeft;
+                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
             }
         } /* while */
     }
 
-    KLOGEXIT(NULL);
     return NULL;
 }
 
 
-#endif
+/**
+ * Starts an enumeration of all nodes in the given AVL tree.
+ *
+ * @returns Pointer to the first node in the enumeration.
+ * @param   ppTree      Pointer to the AVL-tree root node pointer.
+ * @param   pEnumData   Pointer to enumeration control data.
+ * @param   fFromLeft   K_TRUE:  Left to right.
+ *                      K_FALSE: Right to left.
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(BeginEnumTree)(KAVLTREEPTR *ppTree, KAVL_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft)
+{
+    if (*ppTree != KAVL_NULL)
+    {
+        pEnumData->fFromLeft = fFromLeft;
+        pEnumData->cEntries = 1;
+        pEnumData->aEntries[0] = KAVL_GET_POINTER(ppTree);
+        pEnumData->achFlags[0] = 0;
+    }
+    else
+        pEnumData->cEntries = 0;
 
+    return KAVL_FN(GetNextNode)(pEnumData);
+}
+

trunk/kStuff/include/k/kAVLTmpl/kAVLGet.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLGet - get routine for AVL trees.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Get a Node.
  */
 
-#ifndef _kAVLGet_h_
-#define _kAVLGet_h_
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
  * Gets a node from the tree (does not remove it!)
+ *
  * @returns   Pointer to the node holding the given key.
  * @param     ppTree  Pointer to the AVL-tree root node pointer.
  * @param     Key     Key value of the node which is to be found.
- * @sketch
- * @status    completely implemented.
- * @author    knut st. osmundsen
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(Get)(PPKAVLNODECORE ppTree, KAVLKEY Key)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(Get)(KAVLTREEPTR *ppTree, KAVLKEY Key)
 {
-    KLOGENTRY2("PKAVLNODECORE","PPKAVLNODECORE ppTree, KAVLKEY Key", ppTree, Key);
-    #ifndef AVL_CMP
-    register PKAVLNODECORE   pNode = *ppTree;
+    KAVLNODECORE *pNode;
+    if (*ppTree == KAVL_NULL)
+        return NULL;
 
-    while (pNode != NULL && AVL_NE(pNode->Key, Key))
+    pNode = KAVL_GET_POINTER(ppTree);
+    while (KAVL_NE(pNode->Key, Key))
     {
-        if (AVL_G(pNode->Key, Key))
-            pNode = pNode->pLeft;
+        if (KAVL_G(pNode->Key, Key))
+        {
+            if (pNode->pLeft == KAVL_NULL)
+                return NULL;
+            pNode = KAVL_GET_POINTER(&pNode->pLeft);
+        }
         else
-            pNode = pNode->pRight;
+        {
+            if (pNode->pRight == KAVL_NULL)
+                return NULL;
+            pNode = KAVL_GET_POINTER(&pNode->pRight);
+        }
     }
-
-    #else
-
-    register int            iDiff;
-    register PKAVLNODECORE   pNode = *ppTree;
-
-    while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-    {
-        if (iDiff > 0)
-            pNode = pNode->pLeft;
-        else
-            pNode = pNode->pRight;
-    }
-
-    #endif
-
-    KLOGEXIT(pNode);
     return pNode;
 }
 
-
-#endif

trunk/kStuff/include/k/kAVLTmpl/kAVLGetBestFit.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLGetBestFit - Get Best Fit routine for AVL trees.
- *                  Intended specially on heaps. The tree should allow duplicate keys.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Get Best Fitting Node.
  */
 
-#ifndef _kAVLGetBestFit_h_
-#define _kAVLGetBestFit_h_
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
  * Finds the best fitting node in the tree for the given Key value.
- * @returns   Pointer to the best fitting node found.
- * @param     ppTree  Pointer to Pointer to the tree root node.
- * @param     Key     The Key of which is to be found a best fitting match for..
- * @param     fAbove  TRUE:  Returned node is have the closest key to Key from above.
- *                    FALSE: Returned node is have the closest key to Key from below.
- * @status    completely implemented.
- * @sketch    The best fitting node is always located in the searchpath above you.
- *            >= (above): The node where you last turned left.
- *            <= (below): the node where you last turned right.
- * @author    knut st. osmundsen
+ *
+ * @returns Pointer to the best fitting node found.
+ * @param   ppTree      Pointer to Pointer to the tree root node.
+ * @param   Key         The Key of which is to be found a best fitting match for..
+ * @param   fAbove      K_TRUE:  Returned node is have the closest key to Key from above.
+ *                      K_FALSE: Returned node is have the closest key to Key from below.
+ * @sketch  The best fitting node is always located in the searchpath above you.
+ *          >= (above): The node where you last turned left.
+ *          <= (below): the node where you last turned right.
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(GetBestFit)(PPKAVLNODECORE ppTree, KAVLKEY Key, KBOOL fAbove)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
 {
-    KLOGENTRY3("PKAVLNODECORE","PPKAVLNODECORE ppTree, KAVLKEY Key, KBOOL fAbove", ppTree, Key, fAbove);
-    #ifdef AVL_CMP
-    register int            iDiff;
-    #endif
-    register PKAVLNODECORE   pNode = *ppTree;
-    PKAVLNODECORE            pNodeLast = NULL;
+    register KAVLNODECORE *pNode;
+    KAVLNODECORE *pNodeLast;
 
+    if (*ppTree == KAVL_NULL)
+        return NULL;
+
+    pNode = KAVL_GET_POINTER(ppTree);
+    pNodeLast = NULL;
     if (fAbove)
     {   /* pNode->Key >= Key */
-        #ifndef AVL_CMP
-        while (pNode != NULL && AVL_NE(pNode->Key, Key))
-        #else
-        while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-        #endif
+        while (KAVL_NE(pNode->Key, Key))
         {
-            #ifndef AVL_CMP
-            if (AVL_G(pNode->Key, Key))
-            #else
-            if (iDiff > 0)
-            #endif
+            if (KAVL_G(pNode->Key, Key))
             {
+                if (pNode->pLeft == KAVL_NULL)
+                    return pNode;
                 pNodeLast = pNode;
-                pNode = pNode->pLeft;
+                pNode = KAVL_GET_POINTER(&pNode->pLeft);
             }
             else
-                pNode = pNode->pRight;
+            {
+                if (pNode->pRight == KAVL_NULL)
+                    return pNodeLast;
+                pNode = KAVL_GET_POINTER(&pNode->pRight);
+            }
         }
     }
     else
     {   /* pNode->Key <= Key */
-        #ifndef AVL_CMP
-        while (pNode != NULL && AVL_NE(pNode->Key, Key))
-        #else
-        while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-        #endif
+        while (KAVL_NE(pNode->Key, Key))
         {
-            #ifndef AVL_CMP
-            if (AVL_L(pNode->Key, Key))
-            #else
-            if (iDiff < 0)
-            #endif
+            if (KAVL_G(pNode->Key, Key))
             {
-                pNodeLast = pNode;
-                pNode = pNode->pRight;
+                if (pNode->pLeft == KAVL_NULL)
+                    return pNodeLast;
+                pNode = KAVL_GET_POINTER(&pNode->pLeft);
             }
             else
-                pNode = pNode->pLeft;
+            {
+                if (pNode->pRight == KAVL_NULL)
+                    return pNode;
+                pNodeLast = pNode;
+                pNode = KAVL_GET_POINTER(&pNode->pRight);
+            }
         }
     }
 
-    KLOGEXIT(pNode == NULL ? pNodeLast /* best fit */ : pNode /* perfect match */);
-    return pNode == NULL ? pNodeLast /* best fit */ : pNode /* perfect match */;
+    /* perfect match or nothing. */
+    return pNode;
 }
 
-
-#endif

trunk/kStuff/include/k/kAVLTmpl/kAVLGetWithParent.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLGetWithParent - get with parent routine for AVL trees.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Get Node With Parent.
  */
 
-#ifndef _kAVLGetWithParent_h_
-#define _kAVLGetWithParent_h_
+/*
+ * Copyright (c) 2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
- * Gets a node from the tree and its parent node (if any) (does not remove any nodes!)
+ * Gets a node from the tree and its parent node (if any).
+ * The tree remains unchanged.
+ *
  * @returns   Pointer to the node holding the given key.
  * @param     ppTree    Pointer to the AVL-tree root node pointer.
@@ -20 +35 @@
  *                      return. When no node is found, this will hold the last searched node.
  * @param     Key       Key value of the node which is to be found.
- * @sketch
- * @status    completely implemented.
- * @author    knut st. osmundsen
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(GetWithParent)(PPKAVLNODECORE ppTree, PPKAVLNODECORE ppParent, KAVLKEY Key)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetWithParent)(KAVLTREEPTR *ppTree, KAVLNODECORE **ppParent, KAVLKEY Key)
 {
-    KLOGENTRY3("PKAVLNODECORE","PPKAVLNODECORE ppTree, PPKAVLNODECORE ppParent, KAVLKEY Key", ppTree, ppParent, Key);
-    #ifndef AVL_CMP
+    register KAVLNODECORE *pNode = KAVL_GET_POINTER_NULL(ppTree);
+    register KAVLNODECORE *pParent = NULL;
 
-    register PKAVLNODECORE   pNode = *ppTree;
-    register PKAVLNODECORE   pParent = NULL;
-
-    while (pNode != NULL && AVL_NE(pNode->Key, Key))
+    while (     pNode != NULL
+           &&   KAVL_NE(pNode->Key, Key))
     {
         pParent = pNode;
-        if (AVL_G(pNode->Key, Key))
-            pNode = pNode->pLeft;
+        if (KAVL_G(pNode->Key, Key))
+            pNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
         else
-            pNode = pNode->pRight;
+            pNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
     }
 
-    #else
-
-    register PKAVLNODECORE   pNode = *ppTree;
-    register PKAVLNODECORE   pParent = NULL;
-    register int            iDiff;
-
-    while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-    {
-        pParent = pNode;
-        if (iDiff > 0)
-            pNode = pNode->pLeft;
-        else
-            pNode = pNode->pRight;
-    }
-
-    #endif
-
     *ppParent = pParent;
-    KLOGEXIT(pNode);
     return pNode;
 }
 
-
-#endif
-

trunk/kStuff/include/k/kAVLTmpl/kAVLRemove2.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLRemove2 - Remove specific node (by pointer) from an AVL tree.
- *
- * Copyright (c) 2001-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Remove A Specific Node.
  */
 
-#ifndef _kAVLRemove2_h_
-#define _kAVLRemove2_h_
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
- * Removes a node from the AVL-tree given by it's pointer.
- * @returns   Pointer to the node.
- * @param     ppTree  Pointer to the AVL-tree root node pointer.
- * @param     Key     Key value of the node which is to be removed.
- * @sketch    Find the node which is to be removed:
- *            LOOP until not found
- *            BEGIN
- *                Add node pointer pointer to the AVL-stack.
- *                IF the keys matches THEN break!
- *                IF remove key < node key THEN
- *                    left
- *                ELSE
- *                    right
- *            END
- *            IF found THEN
- *            BEGIN
- *                IF duplicate keys allowed AND this isn't pNode Then
- *                BEGIN
- *                    Search list (pList) for the node.
- *                    IF found THEN Link it out and return it.
- *                    return NULL (if not found).
- *                END
- *                IF duplicate keys allowed AND this is pNode AND there is nodes in the list Then
- *                    Replace pNode with the first node in the list.
- *                END
- *                IF left node not empty THEN
- *                BEGIN
- *                    Find the right most node in the left tree while adding the pointer to the pointer to it's parent to the stack:
- *                    Start at left node.
- *                    LOOP until right node is empty
- *                    BEGIN
- *                        Add to stack.
- *                        go right.
- *                    END
- *                    Link out the found node.
- *                    Replace the node which is to be removed with the found node.
- *                    Correct the stack entry for the pointer to the left tree.
- *                END
- *                ELSE
- *                BEGIN
- *                    Move up right node.
- *                    Remove last stack entry.
- *                END
- *                Balance tree using stack.
- *            END
- *            return pointer to the removed node (if found).
- * @status    completely implemented.
- * @author    knut st. osmundsen
+ * Removes the specified node from the tree.
+ *
+ * @returns Pointer to the removed node (NULL if not in the tree)
+ * @param   ppTree      Pointer to Pointer to the tree root node.
+ * @param   Key         The Key of which is to be found a best fitting match for..
+ *
+ * @remark  This implementation isn't the most efficient, but this short and
+ *          easier to manage.
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(Remove2)(PPKAVLNODECORE ppTree, PKAVLNODECORE pNode)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
 {
-    KLOGENTRY2("PKAVLNODECORE","PPKAVLNODECORE ppTree, PKAVLNODECORE pNode", ppTree, pNode);
-    KAVLKEY                  Key = pNode->Key;
-    KAVLSTACK                AVLStack;
-    PPKAVLNODECORE           ppDeleteNode = ppTree;
-    register PKAVLNODECORE   pDeleteNode;
-
-    AVLStack.cEntries = 0;
-
-    while ((pDeleteNode = *ppDeleteNode) != NULL)
+#ifdef KAVL_EQUAL_ALLOWED
+    /*
+     * 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);
+    if (!pCurNode)
+        return NULL;
+    if (pCurNode != pNode)
     {
-        kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
-        AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
-        #ifndef AVL_CMP
-        if (AVL_E(pDeleteNode->Key, Key))
-            break;
-
-        if (AVL_G(pDeleteNode->Key, Key))
-            ppDeleteNode = &pDeleteNode->pLeft;
-        else
-            ppDeleteNode = &pDeleteNode->pRight;
-        #else
+        /*
+         * It's not the one we want, but it could be in the duplicate list.
+         */
+        while (pCurNode->pList != KAVL_NULL)
         {
-        int register iDiff;
-        if ((iDiff = AVL_CMP(pDeleteNode->Key, Key)) == 0)
-            break;
-
-        if (iDiff > 0)
-            ppDeleteNode = &pDeleteNode->pLeft;
-        else
-            ppDeleteNode = &pDeleteNode->pRight;
+            KAVLNODECORE *pNext = KAVL_GET_POINTER(&pCurNode->pList);
+            if (pNext == pNode)
+            {
+                KAVL_SET_POINTER_NULL(&pCurNode->pList, KAVL_GET_POINTER_NULL(&pNode->pList));
+                pNode->pList = KAVL_NULL;
+                return pNode;
+            }
+            pCurNode = pNext;
         }
-        #endif
+        return NULL;
     }
 
-    if (pDeleteNode != NULL)
+    /*
+     * Ok, it's the one we want alright.
+     *
+     * Simply remove it if it's the only one with they Key,
+     * if there are duplicates we'll have to unlink it and
+     * insert the first duplicate in our place.
+     */
+    if (pNode->pList == KAVL_NODE)
+        KAVL_FN(Remove)(ppTree, pNode->Key);
+    else
     {
-        #ifdef KAVL_EQUAL_ALLOWED
-        if (pDeleteNode != pNode)
+        KAVLNODECORE *pNewUs = KAVL_GET_POINTER(&pNode->pList);
+
+        pNewUs->uchHeight = pNode->uchHeight;
+
+        if (pNode->pLeft != KAVL_NULL)
+            KAVL_SET_POINTER(&pNewUs->pLeft, KAVL_GET_POINTER(&pNode->pLeft))
+        else
+            pNewUs->pLeft = KAVL_NULL;
+
+        if (pNode->pRight != KAVL_NULL)
+            KAVL_SET_POINTER(&pNewUs->pRight, KAVL_GET_POINTER(&pNode->pRight))
+        else
+            pNewUs->pRight = KAVL_NULL;
+
+        if (pParent)
         {
-            while (pDeleteNode->pList != NULL)
-            {
-                if (pDeleteNode->pList == pNode)
-                {
-                    pDeleteNode->pList = pNode->pList;
-                    pNode->pList = NULL;                                        //debug only?
-                    KLOGEXIT(pNode);
-                    return pNode;
-                }
-                pDeleteNode = pDeleteNode->pList;
-            }
-            KLOGEXIT(NULL);
-            return NULL;
-        }
-
-        if (pDeleteNode->pList != NULL)
-        {
-            pDeleteNode = pDeleteNode->pList;
-            pDeleteNode->pLeft = pNode->pLeft;
-            pDeleteNode->pRight = pNode->pRight;
-            pDeleteNode->uchHeight = pNode->uchHeight;
-            kASSERT(*ppDeleteNode == pNode);
-            *ppDeleteNode = pDeleteNode;
-            pNode->pList = pNode->pLeft = pNode->pRight = NULL;                 //debug only?
-            KLOGEXIT(pNode);
-            return pNode;
-        }
-        #endif
-
-        if (pDeleteNode->pLeft != NULL)
-        {
-            unsigned                iStackEntry = AVLStack.cEntries;
-            PPKAVLNODECORE           ppLeftLeast = &pDeleteNode->pLeft;
-            register PKAVLNODECORE   pLeftLeast;
-
-            while ((pLeftLeast = *ppLeftLeast)->pRight != NULL) /* Left most node. */
-            {
-                kASSERT(AVLStack.cEntries < KAVL_MAX_STACK);
-                AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
-                ppLeftLeast = &pLeftLeast->pRight;
-                pLeftLeast  = pLeftLeast->pRight;
-            }
-
-            /* link out pLeftLeast */
-            *ppLeftLeast = pLeftLeast->pLeft;
-
-            /* link in place of the delete node. */
-            pLeftLeast->pLeft = pDeleteNode->pLeft;
-            pLeftLeast->pRight = pDeleteNode->pRight;
-            pLeftLeast->uchHeight = pDeleteNode->uchHeight;
-            *ppDeleteNode = pLeftLeast;
-            AVLStack.aEntries[iStackEntry] = &pLeftLeast->pLeft;
+            if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
+                KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
+            else
+                KAVL_SET_POINTER(&pParent->pRight, pNewUs);
         }
         else
-        {
-            *ppDeleteNode = pDeleteNode->pRight;
-            AVLStack.cEntries--;
-        }
+            KAVL_SET_POINTER(ppTree, pNewUs);
+    }
+    return pNode;
 
-        KAVL_FN(Rebalance)(SSToDS(&AVLStack));
-    }
+#else
+    /*
+     * Delete it, if we got the wrong one, reinsert it.
+     *
+     * This ASSUMS that the caller is NOT going to hand us a lot
+     * of wrong nodes but just uses this API for his convenience.
+     */
+    KAVLNODECORE *pRemovedNode = KAVL_FN(Remove)(ppTree, pNode->Key);
+    if (pRemovedNode == pNode)
+        return pRemovedNode;
 
-    #ifndef KAVL_EQUAL_ALLOWED                                  //debug only?
-    pNode->pLeft = pNode->pRight = NULL;                        //debug only?
-    #else                                                       //debug only?
-    pNode->pList = pNode->pLeft = pNode->pRight = NULL;         //debug only?
-    #endif                                                      //debug only?
-    KLOGEXIT(pDeleteNode);
-    return pDeleteNode;
+    KAVL_FN(Insert)(ppTree, pRemovedNode);
+    return NULL;
+#endif
 }
 
-#endif

trunk/kStuff/include/k/kAVLTmpl/kAVLRemoveBestFit.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- *
- * kAVLRemoveBestFit - Remove Best Fit routine for AVL trees.
- *                     Intended specially on heaps. The tree should allow duplicate keys.
- *
- * Copyright (c) 1999-2002 knut st. osmundsen (bird@anduin.net)
- *
- * GPL
+ * kAVLTmpl - Templated AVL Trees, Remove Best Fitting Node.
  */
 
-#ifndef _kAVLRemoveBestFit_h_
-#define _kAVLRemoveBestFit_h_
+/*
+ * Copyright (c) 1999-2007 knut st. osmundsen <bird-src-spam@anduin.net>
+ *
+ * This file is part of kStuff.
+ *
+ * kStuff is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU Lesser General Public
+ * License as published by the Free Software Foundation; either
+ * version 2.1 of the License, or (at your option) any later version.
+ *
+ * kStuff is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+ * Lesser General Public License for more details.
+ *
+ * You should have received a copy of the GNU Lesser General Public
+ * License along with kStuff; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ */
 
 
 /**
- * Finds the best fitting node in the tree for the given Key value.
- * And removes it.
- * @returns   Pointer to the best fitting node found.
- * @param     ppTree  Pointer to Pointer to the tree root node.
- * @param     Key     The Key of which is to be found a best fitting match for..
- * @param     fAbove  TRUE:  Returned node is have the closest key to Key from above.
- *                    FALSE: Returned node is have the closest key to Key from below.
- * @status    completely implemented.
- * @sketch    The best fitting node is always located in the searchpath above you.
- *            >= (above): The node where you last turned left.
- *            <= (below): the node where you last turned right.
- * @author    knut st. osmundsen
- * @remark    This implementation should be speeded up slightly!
+ * Finds the best fitting node in the tree for the given Key value and removes the node.
+ *
+ * @returns Pointer to the removed node.
+ * @param   ppTree      Pointer to Pointer to the tree root node.
+ * @param   Key         The Key of which is to be found a best fitting match for..
+ * @param   fAbove      K_TRUE:  Returned node is have the closest key to Key from above.
+ *                      K_FALSE: Returned node is have the closest key to Key from below.
+ *
+ * @remark  This implementation uses GetBestFit and then Remove and might therefore
+ *          not be the most optimal kind of implementation, but it reduces the complexity
+ *          code size, and the likelyhood for bugs.
  */
-PKAVLNODECORE KLIBCALL KAVL_FN(RemoveBestFit)(PPKAVLNODECORE ppTree, KAVLKEY Key, KBOOL fAbove)
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(RemoveBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
 {
-    KLOGENTRY3("PKAVLNODECORE","PPKAVLNODECORE ppTree, KAVLKEY Key, KBOOL fAbove", ppTree, Key, fAbove);
-    #ifdef AVL_CMP
-    register int            iDiff;
-    #endif
-    register PKAVLNODECORE   pNode = *ppTree;
-    PKAVLNODECORE            pNodeLast = NULL;
-
-    if (fAbove)
-    {   /* pNode->Key >= Key */
-        #ifndef AVL_CMP
-        while (pNode != NULL && AVL_NE(pNode->Key, Key))
-        #else
-        while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-        #endif
+    /*
+     * If we find anything we'll have to remove the node and return it.
+     * Now, if duplicate keys are allowed we'll remove a duplicate before
+     * removing the in-tree node as this is way cheaper.
+     */
+    KAVLNODECORE *pNode = KAVL_FN(GetBestFit)(ppTree, Key, fAbove);
+    if (pNode != NULL)
+    {
+#ifdef KAVL_EQUAL_ALLOWED
+        if (pNode->pList != KAVL_NULL)
         {
-            #ifndef AVL_CMP
-            if (AVL_G(pNode->Key, Key))
-            #else
-            if (iDiff > 0)
-            #endif
-            {
-                pNodeLast = pNode;
-                pNode = pNode->pLeft;
-            }
-            else
-                pNode = pNode->pRight;
+            KAVLANODECORE *pRet = KAVL_GET_POINTER(&pNode->pList);
+            KAVL_SET_POINTER_NULL(&pNode->pList, &pRet->pList);
+            return pRet;
         }
+#endif
+        pNode = KAVL_FN(Remove)(ppTree, pNode->Key);
     }
-    else
-    {   /* pNode->Key <= Key */
-        #ifndef AVL_CMP
-        while (pNode != NULL && AVL_NE(pNode->Key, Key))
-        #else
-        while (pNode != NULL && (iDiff = AVL_CMP(pNode->Key, Key)) != 0)
-        #endif
-        {
-            #ifndef AVL_CMP
-            if (AVL_L(pNode->Key, Key))
-            #else
-            if (iDiff < 0)
-            #endif
-            {
-                pNodeLast = pNode;
-                pNode = pNode->pRight;
-            }
-            else
-                pNode = pNode->pLeft;
-        }
-    }
-
-    /*
-     * If we found anything we'll have to remove the node and return it.
-     * If duplicate keys are allowed we'll check for multiple nodes first
-     * and return one of them before doing an expensive remove operation
-     * of the node we found.
-     */
-    if (pNode == NULL)
-        pNode = pNodeLast;
-    if (pNode == NULL)
-    {
-        KLOGEXIT(NULL);
-        return NULL;
-    }
-    #ifdef KAVL_EQUAL_ALLOWED
-    if (pNode->pList)
-    {
-        pNodeLast = pNode->pList;
-        pNode->pList = pNodeLast->pList;
-        KLOGEXIT(pNodeLast);
-        return pNodeLast;
-    }
-    #endif
-    pNode = KAVL_FN(Remove)(ppTree, pNode->Key);
-    KLOGEXIT(pNode);
     return pNode;
 }
 
-
-#endif