Index: trunk/kStuff/include/k/kAvlTmpl/kAVLBase.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLBase.h	(revision 3558)
+++ 	(revision )
@@ -1,519 +1,0 @@
-/* $Id$ */
-/** @file
- * 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 in a list pointed to by KAVLNODECORE::pList.
- *  This is by default not defined.
- *
- *  \#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 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 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
-
-
-
-/*******************************************************************************
-*   Structures and Typedefs                                                    *
-*******************************************************************************/
-/*
- * Two stacks that's used to avoid recursive calls.
- */
-typedef struct
-{
-    unsigned        cEntries;
-    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);
-
-
-/**
- * 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;
-        }
-    }
-
-}
-
-
-/**
- * Inserts a node into the AVL-tree.
- * @returns   TRUE if inserted.
- *            FALSE if node exists in tree.
- * @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 tree algorithm.):
- *            LOOP until NULL leaf pointer
- *            BEGIN
- *                Add node pointer pointer to the AVL-stack.
- *                IF new-node-key < node key THEN
- *                    left
- *                ELSE
- *                    right
- *            END
- *            Fill in leaf node and insert it.
- *            Rebalance the tree.
- */
-KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
-{
-    KAVL_INT(STACK)        AVLStack;
-    KAVLTREEPTR            *ppCurNode = ppTree;
-    register KAVLKEY        Key = pNode->Key;
-#ifdef KAVL_RANGE
-    register KAVLKEY        KeyLast = pNode->KeyLast;
-#endif
-    register KAVLNODECORE  *pCurNode;
-
-    AVLStack.cEntries = 0;
-
-#ifdef KAVL_RANGE
-    if (Key > KeyLast)
-        return false;
-#else
-    K_NOREF(Key);
-#endif
-
-    while (*ppCurNode != KAVL_NULL)
-    {
-        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 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);
-            return K_TRUE;
-        }
-#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;
-    }
-
-    pNode->pLeft = pNode->pRight = KAVL_NULL;
-#ifdef KAVL_EQUAL_ALLOWED
-    pNode->pList = KAVL_NULL;
-#endif
-    pNode->uchHeight = 1;
-    KAVL_SET_POINTER(ppCurNode, pNode);
-
-    KAVL_FN(Rebalance)(&AVLStack);
-    return K_TRUE;
-}
-
-
-/**
- * Removes a node from the AVL-tree.
- * @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 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).
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
-{
-    KAVL_INT(STACK)         AVLStack;
-    KAVLTREEPTR             *ppDeleteNode = ppTree;
-    register KAVLNODECORE   *pDeleteNode;
-
-    AVLStack.cEntries = 0;
-
-    for (;;)
-    {
-        if (*ppDeleteNode == KAVL_NULL)
-            return NULL;
-        pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
-
-        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
-        AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
-        if (KAVL_E(pDeleteNode->Key, Key))
-            break;
-
-        if (KAVL_G(pDeleteNode->Key, Key))
-            ppDeleteNode = &pDeleteNode->pLeft;
-        else
-            ppDeleteNode = &pDeleteNode->pRight;
-    }
-
-    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)
-        {
-            kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
-            AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
-            ppLeftLeast = &pLeftLeast->pRight;
-            pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
-        }
-
-        /* 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;
-    }
-    else
-    {
-        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
-        AVLStack.cEntries--;
-    }
-
-    KAVL_FN(Rebalance)(&AVLStack);
-    return pDeleteNode;
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLDoWithAll.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLDoWithAll.h	(revision 3558)
+++ 	(revision )
@@ -1,117 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, The Callback Iterator.
- */
-
-/*
- * 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 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     pvUser       User parameter passed on to the callback function.
- */
-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;
-
-    if (*ppTree == KAVL_NULL)
-        return 0;
-
-    AVLStack.cEntries = 1;
-    AVLStack.achFlags[0] = 0;
-    AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
-
-    if (fFromLeft)
-    {   /* from left */
-        while (AVLStack.cEntries > 0)
-        {
-            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
-
-            /* left */
-            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
-            {
-                if (pNode->pLeft != KAVL_NULL)
-                {
-                    AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
-                    continue;
-                }
-            }
-
-            /* center */
-            rc = pfnCallBack(pNode, pvUser);
-            if (rc)
-                return rc;
-
-            /* right */
-            AVLStack.cEntries--;
-            if (pNode->pRight != KAVL_NULL)
-            {
-                AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
-            }
-        } /* while */
-    }
-    else
-    {   /* from right */
-        while (AVLStack.cEntries > 0)
-        {
-            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
-
-
-            /* right */
-            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
-            {
-                if (pNode->pRight != KAVL_NULL)
-                {
-                    AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
-                    continue;
-                }
-            }
-
-            /* center */
-            rc = pfnCallBack(pNode, pvUser);
-            if (rc)
-                return rc;
-
-            /* left */
-            AVLStack.cEntries--;
-            if (pNode->pLeft != KAVL_NULL)
-            {
-                AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
-            }
-        } /* while */
-    }
-
-    return 0;
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLEnum.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLEnum.h	(revision 3558)
+++ 	(revision )
@@ -1,132 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, Node Enumeration.
- */
-
-/*
- * 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
- *
- */
-
-/**
- * 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
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetNextNode)(KAVL_TYPE(,ENUMDATA) *pEnumData)
-{
-    if (pEnumData->fFromLeft)
-    {   /* from left */
-        while (pEnumData->cEntries > 0)
-        {
-            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
-
-            /* left */
-            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
-            {
-                pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->pLeft != KAVL_NULL)
-                {
-                    pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
-                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
-                    continue;
-                }
-            }
-
-            /* center */
-            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
-            {
-                pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                return pNode;
-            }
-
-            /* right */
-            pEnumData->cEntries--;
-            if (pNode->pRight != KAVL_NULL)
-            {
-                pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
-            }
-        } /* while */
-    }
-    else
-    {   /* from right */
-        while (pEnumData->cEntries > 0)
-        {
-            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
-
-            /* right */
-            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
-            {
-                pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->pRight != KAVL_NULL)
-                {
-                    pEnumData->achFlags[pEnumData->cEntries] = 0;  /* 0 right, 1 center, 2 left */
-                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
-                    continue;
-                }
-            }
-
-            /* center */
-            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
-            {
-                pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                return pNode;
-            }
-
-            /* left */
-            pEnumData->cEntries--;
-            if (pNode->pLeft != KAVL_NULL)
-            {
-                pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
-            }
-        } /* while */
-    }
-
-    return NULL;
-}
-
-
-/**
- * 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);
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLGet.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLGet.h	(revision 3558)
+++ 	(revision )
@@ -1,59 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, Get a Node.
- */
-
-/*
- * 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.
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(Get)(KAVLTREEPTR *ppTree, KAVLKEY Key)
-{
-    KAVLNODECORE *pNode;
-    if (*ppTree == KAVL_NULL)
-        return NULL;
-
-    pNode = KAVL_GET_POINTER(ppTree);
-    while (KAVL_NE(pNode->Key, Key))
-    {
-        if (KAVL_G(pNode->Key, Key))
-        {
-            if (pNode->pLeft == KAVL_NULL)
-                return NULL;
-            pNode = KAVL_GET_POINTER(&pNode->pLeft);
-        }
-        else
-        {
-            if (pNode->pRight == KAVL_NULL)
-                return NULL;
-            pNode = KAVL_GET_POINTER(&pNode->pRight);
-        }
-    }
-    return pNode;
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLGetBestFit.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLGetBestFit.h	(revision 3558)
+++ 	(revision )
@@ -1,92 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, Get Best Fitting Node.
- */
-
-/*
- * 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      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.
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
-{
-    register KAVLNODECORE *pNode;
-    KAVLNODECORE *pNodeLast;
-
-    if (*ppTree == KAVL_NULL)
-        return NULL;
-
-    pNode = KAVL_GET_POINTER(ppTree);
-    pNodeLast = NULL;
-    if (fAbove)
-    {   /* pNode->Key >= Key */
-        while (KAVL_NE(pNode->Key, Key))
-        {
-            if (KAVL_G(pNode->Key, Key))
-            {
-                if (pNode->pLeft == KAVL_NULL)
-                    return pNode;
-                pNodeLast = pNode;
-                pNode = KAVL_GET_POINTER(&pNode->pLeft);
-            }
-            else
-            {
-                if (pNode->pRight == KAVL_NULL)
-                    return pNodeLast;
-                pNode = KAVL_GET_POINTER(&pNode->pRight);
-            }
-        }
-    }
-    else
-    {   /* pNode->Key <= Key */
-        while (KAVL_NE(pNode->Key, Key))
-        {
-            if (KAVL_G(pNode->Key, Key))
-            {
-                if (pNode->pLeft == KAVL_NULL)
-                    return pNodeLast;
-                pNode = KAVL_GET_POINTER(&pNode->pLeft);
-            }
-            else
-            {
-                if (pNode->pRight == KAVL_NULL)
-                    return pNode;
-                pNodeLast = pNode;
-                pNode = KAVL_GET_POINTER(&pNode->pRight);
-            }
-        }
-    }
-
-    /* perfect match or nothing. */
-    return pNode;
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLGetWithParent.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLGetWithParent.h	(revision 3558)
+++ 	(revision )
@@ -1,56 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, Get Node With Parent.
- */
-
-/*
- * 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).
- * The tree remains unchanged.
- *
- * @returns   Pointer to the node holding the given key.
- * @param     ppTree    Pointer to the AVL-tree root node pointer.
- * @param     ppParent  Pointer to a variable which will hold the pointer to the partent node on
- *                      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.
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetWithParent)(KAVLTREEPTR *ppTree, KAVLNODECORE **ppParent, KAVLKEY Key)
-{
-    register KAVLNODECORE *pNode = KAVL_GET_POINTER_NULL(ppTree);
-    register KAVLNODECORE *pParent = NULL;
-
-    while (     pNode != NULL
-           &&   KAVL_NE(pNode->Key, Key))
-    {
-        pParent = pNode;
-        if (KAVL_G(pNode->Key, Key))
-            pNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
-        else
-            pNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
-    }
-
-    *ppParent = pParent;
-    return pNode;
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLRemove2.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLRemove2.h	(revision 3558)
+++ 	(revision )
@@ -1,119 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, Remove A Specific Node.
- */
-
-/*
- * 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 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.
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
-{
-#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)
-    {
-        /*
-         * It's not the one we want, but it could be in the duplicate list.
-         */
-        while (pCurNode->pList != KAVL_NULL)
-        {
-            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;
-        }
-        return 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
-    {
-        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)
-        {
-            if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
-                KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
-            else
-                KAVL_SET_POINTER(&pParent->pRight, pNewUs);
-        }
-        else
-            KAVL_SET_POINTER(ppTree, pNewUs);
-    }
-    return pNode;
-
-#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;
-
-    KAVL_FN(Insert)(ppTree, pRemovedNode);
-    return NULL;
-#endif
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLRemoveBestFit.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLRemoveBestFit.h	(revision 3558)
+++ 	(revision )
@@ -1,63 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Templated AVL Trees, Remove Best Fitting Node.
- */
-
-/*
- * 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 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.
- */
-KAVL_DECL(KAVLNODECORE *) KAVL_FN(RemoveBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
-{
-    /*
-     * 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)
-        {
-            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);
-    }
-    return pNode;
-}
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAVLUndef.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAVLUndef.h	(revision 3558)
+++ 	(revision )
@@ -1,59 +1,0 @@
-/* $Id$ */
-/** @file
- * kAVLTmpl - Undefines All Macros (both config and temp).
- */
-
-/*
- * 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
- *
- */
-
-/*
- * The configuration.
- */
-#undef KAVL_EQUAL_ALLOWED
-#undef KAVL_CHECK_FOR_EQUAL_INSERT
-#undef KAVL_MAX_STACK
-#undef KAVL_RANGE
-#undef KAVL_OFFSET
-#undef KAVL_STD_KEY_COMP
-#undef KAVLKEY
-#undef KAVLNODECORE
-#undef KAVLTREEPTR
-#undef KAVL_FN
-#undef KAVL_TYPE
-#undef KAVL_INT
-#undef KAVL_DECL
-
-/*
- * The internal macros.
- */
-#undef KAVL_HEIGHTOF
-#undef KAVL_GET_POINTER
-#undef KAVL_GET_POINTER_NULL
-#undef KAVL_SET_POINTER
-#undef KAVL_SET_POINTER_NULL
-#undef KAVL_NULL
-#undef KAVL_G
-#undef KAVL_E
-#undef KAVL_NE
-#undef KAVL_R_IS_IDENTICAL
-#undef KAVL_R_IS_INTERSECTING
-#undef KAVL_R_IS_IN_RANGE
-
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlBase.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlBase.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlBase.h	(revision 3559)
@@ -0,0 +1,519 @@
+/* $Id$ */
+/** @file
+ * 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 in a list pointed to by KAVLNODECORE::pList.
+ *  This is by default not defined.
+ *
+ *  \#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 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 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
+
+
+
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/*
+ * Two stacks that's used to avoid recursive calls.
+ */
+typedef struct
+{
+    unsigned        cEntries;
+    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);
+
+
+/**
+ * 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;
+        }
+    }
+
+}
+
+
+/**
+ * Inserts a node into the AVL-tree.
+ * @returns   TRUE if inserted.
+ *            FALSE if node exists in tree.
+ * @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 tree algorithm.):
+ *            LOOP until NULL leaf pointer
+ *            BEGIN
+ *                Add node pointer pointer to the AVL-stack.
+ *                IF new-node-key < node key THEN
+ *                    left
+ *                ELSE
+ *                    right
+ *            END
+ *            Fill in leaf node and insert it.
+ *            Rebalance the tree.
+ */
+KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
+{
+    KAVL_INT(STACK)        AVLStack;
+    KAVLTREEPTR            *ppCurNode = ppTree;
+    register KAVLKEY        Key = pNode->Key;
+#ifdef KAVL_RANGE
+    register KAVLKEY        KeyLast = pNode->KeyLast;
+#endif
+    register KAVLNODECORE  *pCurNode;
+
+    AVLStack.cEntries = 0;
+
+#ifdef KAVL_RANGE
+    if (Key > KeyLast)
+        return false;
+#else
+    K_NOREF(Key);
+#endif
+
+    while (*ppCurNode != KAVL_NULL)
+    {
+        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 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);
+            return K_TRUE;
+        }
+#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;
+    }
+
+    pNode->pLeft = pNode->pRight = KAVL_NULL;
+#ifdef KAVL_EQUAL_ALLOWED
+    pNode->pList = KAVL_NULL;
+#endif
+    pNode->uchHeight = 1;
+    KAVL_SET_POINTER(ppCurNode, pNode);
+
+    KAVL_FN(Rebalance)(&AVLStack);
+    return K_TRUE;
+}
+
+
+/**
+ * Removes a node from the AVL-tree.
+ * @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 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).
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove)(KAVLTREEPTR *ppTree, KAVLKEY Key)
+{
+    KAVL_INT(STACK)         AVLStack;
+    KAVLTREEPTR             *ppDeleteNode = ppTree;
+    register KAVLNODECORE   *pDeleteNode;
+
+    AVLStack.cEntries = 0;
+
+    for (;;)
+    {
+        if (*ppDeleteNode == KAVL_NULL)
+            return NULL;
+        pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
+
+        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
+        AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
+        if (KAVL_E(pDeleteNode->Key, Key))
+            break;
+
+        if (KAVL_G(pDeleteNode->Key, Key))
+            ppDeleteNode = &pDeleteNode->pLeft;
+        else
+            ppDeleteNode = &pDeleteNode->pRight;
+    }
+
+    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)
+        {
+            kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
+            AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
+            ppLeftLeast = &pLeftLeast->pRight;
+            pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
+        }
+
+        /* 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;
+    }
+    else
+    {
+        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->pRight);
+        AVLStack.cEntries--;
+    }
+
+    KAVL_FN(Rebalance)(&AVLStack);
+    return pDeleteNode;
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlDoWithAll.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlDoWithAll.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlDoWithAll.h	(revision 3559)
@@ -0,0 +1,117 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, The Callback Iterator.
+ */
+
+/*
+ * 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 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     pvUser       User parameter passed on to the callback function.
+ */
+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;
+
+    if (*ppTree == KAVL_NULL)
+        return 0;
+
+    AVLStack.cEntries = 1;
+    AVLStack.achFlags[0] = 0;
+    AVLStack.aEntries[0] = KAVL_GET_POINTER(ppTree);
+
+    if (fFromLeft)
+    {   /* from left */
+        while (AVLStack.cEntries > 0)
+        {
+            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+
+            /* left */
+            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
+            {
+                if (pNode->pLeft != KAVL_NULL)
+                {
+                    AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
+                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+                    continue;
+                }
+            }
+
+            /* center */
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
+                return rc;
+
+            /* right */
+            AVLStack.cEntries--;
+            if (pNode->pRight != KAVL_NULL)
+            {
+                AVLStack.achFlags[AVLStack.cEntries] = 0;
+                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+            }
+        } /* while */
+    }
+    else
+    {   /* from right */
+        while (AVLStack.cEntries > 0)
+        {
+            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+
+
+            /* right */
+            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
+            {
+                if (pNode->pRight != KAVL_NULL)
+                {
+                    AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
+                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+                    continue;
+                }
+            }
+
+            /* center */
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
+                return rc;
+
+            /* left */
+            AVLStack.cEntries--;
+            if (pNode->pLeft != KAVL_NULL)
+            {
+                AVLStack.achFlags[AVLStack.cEntries] = 0;
+                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+            }
+        } /* while */
+    }
+
+    return 0;
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlEnum.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlEnum.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlEnum.h	(revision 3559)
@@ -0,0 +1,132 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, Node Enumeration.
+ */
+
+/*
+ * 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
+ *
+ */
+
+/**
+ * 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
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetNextNode)(KAVL_TYPE(,ENUMDATA) *pEnumData)
+{
+    if (pEnumData->fFromLeft)
+    {   /* from left */
+        while (pEnumData->cEntries > 0)
+        {
+            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+
+            /* left */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                if (pNode->pLeft != KAVL_NULL)
+                {
+                    pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
+                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+                    continue;
+                }
+            }
+
+            /* center */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                return pNode;
+            }
+
+            /* right */
+            pEnumData->cEntries--;
+            if (pNode->pRight != KAVL_NULL)
+            {
+                pEnumData->achFlags[pEnumData->cEntries] = 0;
+                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+            }
+        } /* while */
+    }
+    else
+    {   /* from right */
+        while (pEnumData->cEntries > 0)
+        {
+            KAVLNODECORE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+
+            /* right */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                if (pNode->pRight != KAVL_NULL)
+                {
+                    pEnumData->achFlags[pEnumData->cEntries] = 0;  /* 0 right, 1 center, 2 left */
+                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pRight);
+                    continue;
+                }
+            }
+
+            /* center */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                return pNode;
+            }
+
+            /* left */
+            pEnumData->cEntries--;
+            if (pNode->pLeft != KAVL_NULL)
+            {
+                pEnumData->achFlags[pEnumData->cEntries] = 0;
+                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->pLeft);
+            }
+        } /* while */
+    }
+
+    return NULL;
+}
+
+
+/**
+ * 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);
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlGet.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlGet.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlGet.h	(revision 3559)
@@ -0,0 +1,59 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, Get a Node.
+ */
+
+/*
+ * 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.
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(Get)(KAVLTREEPTR *ppTree, KAVLKEY Key)
+{
+    KAVLNODECORE *pNode;
+    if (*ppTree == KAVL_NULL)
+        return NULL;
+
+    pNode = KAVL_GET_POINTER(ppTree);
+    while (KAVL_NE(pNode->Key, Key))
+    {
+        if (KAVL_G(pNode->Key, Key))
+        {
+            if (pNode->pLeft == KAVL_NULL)
+                return NULL;
+            pNode = KAVL_GET_POINTER(&pNode->pLeft);
+        }
+        else
+        {
+            if (pNode->pRight == KAVL_NULL)
+                return NULL;
+            pNode = KAVL_GET_POINTER(&pNode->pRight);
+        }
+    }
+    return pNode;
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlGetBestFit.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlGetBestFit.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlGetBestFit.h	(revision 3559)
@@ -0,0 +1,92 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, Get Best Fitting Node.
+ */
+
+/*
+ * 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      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.
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
+{
+    register KAVLNODECORE *pNode;
+    KAVLNODECORE *pNodeLast;
+
+    if (*ppTree == KAVL_NULL)
+        return NULL;
+
+    pNode = KAVL_GET_POINTER(ppTree);
+    pNodeLast = NULL;
+    if (fAbove)
+    {   /* pNode->Key >= Key */
+        while (KAVL_NE(pNode->Key, Key))
+        {
+            if (KAVL_G(pNode->Key, Key))
+            {
+                if (pNode->pLeft == KAVL_NULL)
+                    return pNode;
+                pNodeLast = pNode;
+                pNode = KAVL_GET_POINTER(&pNode->pLeft);
+            }
+            else
+            {
+                if (pNode->pRight == KAVL_NULL)
+                    return pNodeLast;
+                pNode = KAVL_GET_POINTER(&pNode->pRight);
+            }
+        }
+    }
+    else
+    {   /* pNode->Key <= Key */
+        while (KAVL_NE(pNode->Key, Key))
+        {
+            if (KAVL_G(pNode->Key, Key))
+            {
+                if (pNode->pLeft == KAVL_NULL)
+                    return pNodeLast;
+                pNode = KAVL_GET_POINTER(&pNode->pLeft);
+            }
+            else
+            {
+                if (pNode->pRight == KAVL_NULL)
+                    return pNode;
+                pNodeLast = pNode;
+                pNode = KAVL_GET_POINTER(&pNode->pRight);
+            }
+        }
+    }
+
+    /* perfect match or nothing. */
+    return pNode;
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlGetWithParent.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlGetWithParent.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlGetWithParent.h	(revision 3559)
@@ -0,0 +1,56 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, Get Node With Parent.
+ */
+
+/*
+ * 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).
+ * The tree remains unchanged.
+ *
+ * @returns   Pointer to the node holding the given key.
+ * @param     ppTree    Pointer to the AVL-tree root node pointer.
+ * @param     ppParent  Pointer to a variable which will hold the pointer to the partent node on
+ *                      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.
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(GetWithParent)(KAVLTREEPTR *ppTree, KAVLNODECORE **ppParent, KAVLKEY Key)
+{
+    register KAVLNODECORE *pNode = KAVL_GET_POINTER_NULL(ppTree);
+    register KAVLNODECORE *pParent = NULL;
+
+    while (     pNode != NULL
+           &&   KAVL_NE(pNode->Key, Key))
+    {
+        pParent = pNode;
+        if (KAVL_G(pNode->Key, Key))
+            pNode = KAVL_GET_POINTER_NULL(&pNode->pLeft);
+        else
+            pNode = KAVL_GET_POINTER_NULL(&pNode->pRight);
+    }
+
+    *ppParent = pParent;
+    return pNode;
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlRemove2.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlRemove2.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlRemove2.h	(revision 3559)
@@ -0,0 +1,119 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, Remove A Specific Node.
+ */
+
+/*
+ * 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 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.
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(Remove2)(KAVLTREEPTR *ppTree, KAVLNODECORE *pNode)
+{
+#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)
+    {
+        /*
+         * It's not the one we want, but it could be in the duplicate list.
+         */
+        while (pCurNode->pList != KAVL_NULL)
+        {
+            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;
+        }
+        return 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
+    {
+        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)
+        {
+            if (KAVL_GET_POINTER_NULL(&pParent->pLeft) == pNode)
+                KAVL_SET_POINTER(&pParent->pLeft, pNewUs);
+            else
+                KAVL_SET_POINTER(&pParent->pRight, pNewUs);
+        }
+        else
+            KAVL_SET_POINTER(ppTree, pNewUs);
+    }
+    return pNode;
+
+#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;
+
+    KAVL_FN(Insert)(ppTree, pRemovedNode);
+    return NULL;
+#endif
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlRemoveBestFit.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlRemoveBestFit.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlRemoveBestFit.h	(revision 3559)
@@ -0,0 +1,63 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Templated AVL Trees, Remove Best Fitting Node.
+ */
+
+/*
+ * 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 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.
+ */
+KAVL_DECL(KAVLNODECORE *) KAVL_FN(RemoveBestFit)(KAVLTREEPTR *ppTree, KAVLKEY Key, KBOOL fAbove)
+{
+    /*
+     * 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)
+        {
+            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);
+    }
+    return pNode;
+}
+
Index: trunk/kStuff/include/k/kAvlTmpl/kAvlUndef.h
===================================================================
--- trunk/kStuff/include/k/kAvlTmpl/kAvlUndef.h	(revision 3559)
+++ trunk/kStuff/include/k/kAvlTmpl/kAvlUndef.h	(revision 3559)
@@ -0,0 +1,59 @@
+/* $Id$ */
+/** @file
+ * kAVLTmpl - Undefines All Macros (both config and temp).
+ */
+
+/*
+ * 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
+ *
+ */
+
+/*
+ * The configuration.
+ */
+#undef KAVL_EQUAL_ALLOWED
+#undef KAVL_CHECK_FOR_EQUAL_INSERT
+#undef KAVL_MAX_STACK
+#undef KAVL_RANGE
+#undef KAVL_OFFSET
+#undef KAVL_STD_KEY_COMP
+#undef KAVLKEY
+#undef KAVLNODECORE
+#undef KAVLTREEPTR
+#undef KAVL_FN
+#undef KAVL_TYPE
+#undef KAVL_INT
+#undef KAVL_DECL
+
+/*
+ * The internal macros.
+ */
+#undef KAVL_HEIGHTOF
+#undef KAVL_GET_POINTER
+#undef KAVL_GET_POINTER_NULL
+#undef KAVL_SET_POINTER
+#undef KAVL_SET_POINTER_NULL
+#undef KAVL_NULL
+#undef KAVL_G
+#undef KAVL_E
+#undef KAVL_NE
+#undef KAVL_R_IS_IDENTICAL
+#undef KAVL_R_IS_INTERSECTING
+#undef KAVL_R_IS_IN_RANGE
+
