Index: trunk/include/k/kRbTmpl/kRbBase.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbBase.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbBase.h	(revision 35)
@@ -0,0 +1,504 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, The Mandatory Base Code.
+ */
+
+/*
+ * Copyright (c) 2001-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/** @page pg_kAvlTmpl   Template Configuration.
+ *
+ *  This is a templated implementation of Red-Black trees in C.  The template
+ *  parameters relates to the kind of key used and how duplicates are treated.
+ *
+ *  \#define KRB_EQUAL_ALLOWED
+ *  Define this to tell us that equal keys are allowed.
+ *  Then Equal keys will be put in a list pointed to by KRBNODE::pList.
+ *  This is by default not defined.
+ *
+ *  \#define KRB_CHECK_FOR_EQUAL_INSERT
+ *  Define this to enable insert check for equal nodes.
+ *  This is by default not defined.
+ *
+ *  \#define KRB_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 KRB_RANGE
+ *  Define this to enable key ranges.
+ *
+ *  \#define KRB_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 KRB_CACHE_SIZE
+ *  Define this to employ a lookthru cache (direct) to speed up lookup for
+ *  some usage patterns. The value should be the number of members of the array.
+ *
+ *  \#define KRB_CACHE_HASH(Key)
+ *  Define this to specify a more efficient translation of the key into
+ *  a lookthru array index. The default is key % size.
+ *  For some key types this is required as the default will not compile.
+ *
+ *  \#define KRB_LOCKED
+ *  Define this if you wish for the tree to be locked via the
+ *  KRB_WRITE_LOCK,  KRB_WRITE_UNLOCK, KRB_READ_LOCK and
+ *  KRB_READ_UNLOCK macros. If not defined the tree will not be subject
+ *  do any kind of locking and the problem of concurrency is left the user.
+ *
+ *  \#define KRB_WRITE_LOCK(pRoot)
+ *  Lock the tree for writing.
+ *
+ *  \#define KRB_WRITE_UNLOCK(pRoot)
+ *  Counteracts KRB_WRITE_LOCK.
+ *
+ *  \#define KRB_READ_LOCK(pRoot)
+ *  Lock the tree for reading.
+ *
+ *  \#define KRB_READ_UNLOCK(pRoot)
+ *  Counteracts KRB_READ_LOCK.
+ *
+ *  \#define KRBKEY
+ *  Define this to the name of the AVL key type.
+ *
+ *  \#define KRB_STD_KEY_COMP
+ *  Define this to use the standard key compare macros. If not set all the
+ *  compare operations for KRBKEY have to be defined: KRB_CMP_G, KRB_CMP_E, KRB_CMP_NE,
+ *  KRB_R_IS_IDENTICAL, KRB_R_IS_INTERSECTING and KRB_R_IS_IN_RANGE. The
+ *  latter three are only required when KRB_RANGE is defined.
+ *
+ *  \#define KRBNODE
+ *  Define this to the name (typedef) of the AVL node structure. This
+ *  structure must have a mpLeft, mpRight, mKey and mHeight member.
+ *  If KRB_RANGE is defined a mKeyLast is also required.
+ *  If KRB_EQUAL_ALLOWED is defined a mpList member is required.
+ *  It's possible to use other member names by redefining the names.
+ *
+ *  \#define KRBTREEPTR
+ *  Define this to the name (typedef) of the tree pointer type. This is
+ *  required when KRB_OFFSET is defined. When not defined it defaults
+ *  to KRBNODE *.
+ *
+ *  \#define KRBROOT
+ *  Define this to the name (typedef) of the AVL root structure. This
+ *  is optional. However, if specified it must at least have a mpRoot
+ *  member of KRBTREEPTR type. If KRB_CACHE_SIZE is non-zero a
+ *  maLookthru[KRB_CACHE_SIZE] member of the KRBTREEPTR type is also
+ *  required.
+ *
+ *  \#define KRB_FN
+ *  Use this to alter the names of the AVL functions.
+ *  Must be defined.
+ *
+ *  \#define KRB_TYPE(prefix, name)
+ *  Use this to make external type names and unique. The prefix may be empty.
+ *  Must be defined.
+ *
+ *  \#define KRB_INT(name)
+ *  Use this to make internal type names and unique. The prefix may be empty.
+ *  Must be defined.
+ *
+ *  \#define KRB_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.
+ *
+ *  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) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
+
+/** @def KRB_GET_POINTER
+ * Reads a 'pointer' value.
+ *
+ * @returns The native pointer.
+ * @param   pp      Pointer to the pointer to read.
+ * @internal
+ */
+
+/** @def KRB_GET_POINTER_NULL
+ * Reads a 'pointer' value which can be KRB_NULL.
+ *
+ * @returns The native pointer.
+ * @returns NULL pointer if KRB_NULL.
+ * @param   pp      Pointer to the pointer to read.
+ * @internal
+ */
+
+/** @def KRB_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 KRB_SET_POINTER_NULL
+ * Writes a 'pointer' value which can be KRB_NULL.
+ *
+ * For offset-based schemes offset relative to pp is calculated and assigned to *pp,
+ * if p is not KRB_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 KRB_NULL
+ * @internal
+ */
+
+#ifndef KRBTREEPTR
+# define KRBTREEPTR                         KRBNODE *
+#endif
+
+#ifndef KRBROOT
+# define KRBROOT                            KRB_TYPE(,ROOT)
+# define KRB_NEED_KRBROOT
+#endif
+
+#ifdef KRB_CACHE_SIZE
+# ifndef KRB_CACHE_HASH
+#  define KRB_CACHE_HASH(Key)               ( (Key) % (KRB_CACHE_SIZE) )
+# endif
+#elif defined(KRB_CACHE_HASH)
+# error "KRB_CACHE_HASH without KRB_CACHE_SIZE!"
+#endif
+
+#ifdef KRB_CACHE_SIZE
+# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) \
+    do { \
+        KRBTREEPTR **ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; \
+        if ((pNode) == KRB_GET_POINTER_NULL(ppEntry)) \
+            *ppEntry = KRB_NULL; \
+    } while (0)
+#else
+# define KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0)
+#endif
+
+#ifndef KRB_LOCKED
+# define KRB_WRITE_LOCK(pRoot)              do { } while (0)
+# define KRB_WRITE_UNLOCK(pRoot)            do { } while (0)
+# define KRB_READ_LOCK(pRoot)               do { } while (0)
+# define KRB_READ_UNLOCK(pRoot)             do { } while (0)
+#endif
+
+#ifdef KRB_OFFSET
+# define KRB_GET_POINTER(pp)                ( (KRBNODE *)((KIPTR)(pp) + *(pp)) )
+# define KRB_GET_POINTER_NULL(pp)           ( *(pp) != KRB_NULL ? KRB_GET_POINTER(pp) : NULL )
+# define KRB_SET_POINTER(pp, p)             ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
+# define KRB_SET_POINTER_NULL(pp, pp2)      ( (*(pp)) = *(pp2) != KRB_NULL ? (KIPTR)KRB_GET_POINTER(pp2) - (KIPTR)(pp) : KRB_NULL )
+#else
+# define KRB_GET_POINTER(pp)                ( *(pp) )
+# define KRB_GET_POINTER_NULL(pp)           ( *(pp) )
+# define KRB_SET_POINTER(pp, p)             ( (*(pp)) = (p) )
+# define KRB_SET_POINTER_NULL(pp, pp2)      ( (*(pp)) = *(pp2) )
+#endif
+
+
+/** @def KRB_NULL
+ * The NULL 'pointer' equivalent.
+ */
+#ifdef KRB_OFFSET
+# define KRB_NULL     0
+#else
+# define KRB_NULL     NULL
+#endif
+
+#ifdef KRB_STD_KEY_COMP
+# define KRB_CMP_G(key1, key2)              ( (key1) >  (key2) )
+# define KRB_CMP_E(key1, key2)              ( (key1) == (key2) )
+# define KRB_CMP_NE(key1, key2)             ( (key1) != (key2) )
+# ifdef KRB_RANGE
+#  define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)       ( (key1B) == (key2B) && (key1E) == (key2E) )
+#  define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)    ( (key1B) <= (key2E) && (key1E) >= (key2B) )
+#  define KRB_R_IS_IN_RANGE(key1B, key1E, key2)                KRB_R_IS_INTERSECTING(key1B, key2, key1E, key2)
+# endif
+#endif
+
+#ifndef KRB_RANGE
+# define KRB_R_IS_INTERSECTING(key1B, key2B, key1E, key2E)     KRB_CMP_E(key1B, key2B)
+# define KRB_R_IS_IDENTICAL(key1B, key2B, key1E, key2E)        KRB_CMP_E(key1B, key2B)
+#endif
+
+
+
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/**
+ * Stack used to avoid recursive calls during insert and removal.
+ */
+typedef struct
+{
+    unsigned        cEntries;
+    KRBTREEPTR    *aEntries[KRB_MAX_STACK];
+} KRB_INT(STACK);
+
+/**
+ * The callback used by the Destroy and DoWithAll functions.
+ */
+typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE *, void *);
+
+#ifdef KRB_NEED_KRBROOT
+/**
+ * The Red-Black tree root structure.
+ */
+typedef struct
+{
+    KRBTREEPTR     mpRoot;
+# ifdef KRB_CACHE_SIZE
+    KRBTREEPTR     maLookthru[KRB_CACHE_SIZE];
+# endif
+} KRBROOT;
+#endif
+
+
+
+/**
+ * Initializes the root of the Red-Black tree.
+ *
+ * @param     pTree     Pointer to the root structure.
+ */
+KRB_DECL(void) KRB_FN(Init)(KRBROOT *pRoot)
+{
+#ifdef KRB_CACHE_SIZE
+    unsigned i;
+#endif
+
+    pRoot->mpRoot = KRB_NULL;
+#ifdef KRB_CACHE_SIZE
+    for (i = 0; i < (KRB_CACHE_SIZE); i++)
+        pRoot->maLookthru[i] = KRB_NULL;
+#endif
+}
+
+
+/**
+ * Inserts a node into the Red-Black tree.
+ * @returns   K_TRUE if inserted.
+ *            K_FALSE if node exists in tree.
+ * @param     pRoot     Pointer to the Red-Back tree's root structure.
+ * @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.
+ */
+KRB_DECL(KBOOL) KRB_FN(Insert)(KRBROOT *pRoot, KRBNODE *pNode)
+{
+    KRB_INT(STACK)     Stack;
+    KRBTREEPTR        *ppCurNode = &pRoot->mpRoot;
+    register KRBKEY    Key = pNode->mKey;
+#ifdef KRB_RANGE
+    register KRBKEY    KeyLast = pNode->mKeyLast;
+#endif
+
+#ifdef KRB_RANGE
+    if (Key > KeyLast)
+        return false;
+#endif
+
+    KRB_WRITE_LOCK(pRoot);
+
+    Stack.cEntries = 0;
+    while (*ppCurNode != KRB_NULL)
+    {
+        register KRBNODE *pCurNode = KRB_GET_POINTER(ppCurNode);
+
+        kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
+        Stack.aEntries[Stack.cEntries++] = ppCurNode;
+#ifdef KRB_EQUAL_ALLOWED
+        if (KRB_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
+        {
+            /*
+             * If equal then we'll use a list of equal nodes.
+             */
+            pNode->mpLeft = pNode->mpRight = KRB_NULL;
+            pNode->mHeight = 0;
+            KRB_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
+            KRB_SET_POINTER(&pCurNode->mpList, pNode);
+            KRB_WRITE_UNLOCK(pRoot);
+            return K_TRUE;
+        }
+#endif
+#ifdef KRB_CHECK_FOR_EQUAL_INSERT
+        if (KRB_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
+        {
+            KRB_WRITE_UNLOCK(pRoot);
+            return K_FALSE;
+        }
+#endif
+        if (KRB_CMP_G(pCurNode->mKey, Key))
+            ppCurNode = &pCurNode->mpLeft;
+        else
+            ppCurNode = &pCurNode->mpRight;
+    }
+
+    pNode->mpLeft = pNode->mpRight = KRB_NULL;
+#ifdef KRB_EQUAL_ALLOWED
+    pNode->mpList = KRB_NULL;
+#endif
+    pNode->mHeight = 1;
+    KRB_SET_POINTER(ppCurNode, pNode);
+
+    KRB_FN(Rebalance)(&Stack);
+
+    KRB_WRITE_UNLOCK(pRoot);
+    return K_TRUE;
+}
+
+
+/**
+ * Removes a node from the Red-Black tree.
+ * @returns   Pointer to the node.
+ * @param     pRoot     Pointer to the Red-Back tree's root structure.
+ * @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).
+ */
+KRB_DECL(KRBNODE *) KRB_FN(Remove)(KRBROOT *pRoot, KRBKEY Key)
+{
+    KRB_INT(STACK)     Stack;
+    KRBTREEPTR        *ppDeleteNode = &pRoot->mpRoot;
+    register KRBNODE  *pDeleteNode;
+
+    KRB_WRITE_LOCK(pRoot);
+
+    Stack.cEntries = 0;
+    for (;;)
+    {
+        if (*ppDeleteNode == KRB_NULL)
+        {
+            KRB_WRITE_UNLOCK(pRoot);
+            return NULL;
+        }
+        pDeleteNode = KRB_GET_POINTER(ppDeleteNode);
+
+        kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
+        Stack.aEntries[Stack.cEntries++] = ppDeleteNode;
+        if (KRB_CMP_E(pDeleteNode->mKey, Key))
+            break;
+
+        if (KRB_CMP_G(pDeleteNode->mKey, Key))
+            ppDeleteNode = &pDeleteNode->mpLeft;
+        else
+            ppDeleteNode = &pDeleteNode->mpRight;
+    }
+
+    if (pDeleteNode->mpLeft != KRB_NULL)
+    {
+        /* find the rightmost node in the left tree. */
+        const unsigned      iStackEntry = Stack.cEntries;
+        KRBTREEPTR        *ppLeftLeast = &pDeleteNode->mpLeft;
+        register KRBNODE  *pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
+
+        while (pLeftLeast->mpRight != KRB_NULL)
+        {
+            kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
+            Stack.aEntries[Stack.cEntries++] = ppLeftLeast;
+            ppLeftLeast = &pLeftLeast->mpRight;
+            pLeftLeast  = KRB_GET_POINTER(ppLeftLeast);
+        }
+
+        /* link out pLeftLeast */
+        KRB_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
+
+        /* link it in place of the delete node. */
+        KRB_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
+        KRB_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
+        pLeftLeast->mHeight = pDeleteNode->mHeight;
+        KRB_SET_POINTER(ppDeleteNode, pLeftLeast);
+        Stack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
+    }
+    else
+    {
+        KRB_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
+        Stack.cEntries--;
+    }
+
+    KRB_FN(Rebalance)(&Stack);
+
+    KRB_CACHE_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
+
+    KRB_WRITE_UNLOCK(pRoot);
+    return pDeleteNode;
+}
+
Index: trunk/include/k/kRbTmpl/kRbDestroy.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbDestroy.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbDestroy.h	(revision 35)
@@ -0,0 +1,129 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Destroy the tree.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * Destroys the specified tree, starting with the root node and working our way down.
+ *
+ * @returns 0 on success.
+ * @returns Return value from callback on failure. On failure, the tree will be in
+ *          an unbalanced condition and only further calls to the Destroy should be
+ *          made on it. Note that the node we fail on will be considered dead and
+ *          no action is taken to link it back into the tree.
+ * @param   pRoot           Pointer to the Red-Back tree's root structure.
+ * @param   pfnCallBack     Pointer to callback function.
+ * @param   pvUser          User parameter passed on to the callback function.
+ */
+KRB_DECL(int) KRB_FN(Destroy)(KRBROOT *pRoot, KRB_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
+{
+#ifdef KRB_CACHE_SIZE
+    unsigned    i;
+#endif
+    unsigned    cEntries;
+    KRBNODE    *apEntries[KRB_MAX_STACK];
+    int         rc;
+
+    KRB_WRITE_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
+    {
+        KRB_WRITE_UNLOCK(pRoot);
+        return 0;
+    }
+
+#ifdef KRB_CACHE_SIZE
+    /*
+     * Kill the lookthru cache.
+     */
+    for (i = 0; i < (KRB_CACHE_SIZE); i++)
+        pRoot->maLookthru[i] = KRB_NULL;
+#endif
+
+    cEntries = 1;
+    apEntries[0] = KRB_GET_POINTER(&pRoot->mpRoot);
+    while (cEntries > 0)
+    {
+        /*
+         * Process the subtrees first.
+         */
+        KRBNODE *pNode = apEntries[cEntries - 1];
+        if (pNode->mpLeft != KRB_NULL)
+            apEntries[cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
+        else if (pNode->mpRight != KRB_NULL)
+            apEntries[cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
+        else
+        {
+#ifdef KRB_EQUAL_ALLOWED
+            /*
+             * Process nodes with the same key.
+             */
+            while (pNode->pList != KRB_NULL)
+            {
+                KRBNODE *pEqual = KRB_GET_POINTER(&pNode->pList);
+                KRB_SET_POINTER(&pNode->pList, KRB_GET_POINTER_NULL(&pEqual->pList));
+                pEqual->pList = KRB_NULL;
+
+                rc = pfnCallBack(pEqual, pvUser);
+                if (rc)
+                {
+                    KRB_WRITE_UNLOCK(pRoot);
+                    return rc;
+                }
+            }
+#endif
+
+            /*
+             * Unlink the node.
+             */
+            if (--cEntries > 0)
+            {
+                KRBNODE *pParent = apEntries[cEntries - 1];
+                if (KRB_GET_POINTER(&pParent->mpLeft) == pNode)
+                    pParent->mpLeft = KRB_NULL;
+                else
+                    pParent->mpRight = KRB_NULL;
+            }
+            else
+                pRoot->mpRoot = KRB_NULL;
+
+            kHlpAssert(pNode->mpLeft == KRB_NULL);
+            kHlpAssert(pNode->mpRight == KRB_NULL);
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
+            {
+                KRB_WRITE_UNLOCK(pRoot);
+                return rc;
+            }
+        }
+    } /* while */
+    kHlpAssert(pRoot->mpRoot == KRB_NULL);
+
+    KRB_WRITE_UNLOCK(pRoot);
+    return 0;
+}
+
Index: trunk/include/k/kRbTmpl/kRbDoWithAll.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbDoWithAll.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbDoWithAll.h	(revision 35)
@@ -0,0 +1,166 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, The Callback Iterator.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/**
+ * Stack used by DoWithAll to avoid recusive function calls.
+ */
+typedef struct
+{
+    unsigned        cEntries;
+    KRBNODE        *aEntries[KRB_MAX_STACK];
+    char            achFlags[KRB_MAX_STACK];
+    KRBROOT        pRoot;
+} KRB_INT(STACK2);
+
+
+/**
+ * Iterates thru all nodes in the given tree.
+ *
+ * @returns   0 on success. Return from callback on failure.
+ * @param     pRoot        Pointer to the Red-Back tree's root structure.
+ * @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.
+ */
+KRB_DECL(int) KRB_FN(DoWithAll)(KRBROOT *pRoot, KBOOL fFromLeft, KRB_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
+{
+    KRB_INT(STACK2)     Stack;
+    KRBNODE            *pNode;
+#ifdef KRB_EQUAL_ALLOWED
+    KRBNODE            *pEqual;
+#endif
+    int                 rc;
+
+    KRB_READ_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
+    {
+        KRB_READ_UNLOCK(pRoot);
+        return 0;
+    }
+
+    Stack.cEntries = 1;
+    Stack.achFlags[0] = 0;
+    Stack.aEntries[0] = KRB_GET_POINTER(&pRoot->mpRoot);
+
+    if (fFromLeft)
+    {   /* from left */
+        while (Stack.cEntries > 0)
+        {
+            pNode = Stack.aEntries[Stack.cEntries - 1];
+
+            /* left */
+            if (!Stack.achFlags[Stack.cEntries - 1]++)
+            {
+                if (pNode->mpLeft != KRB_NULL)
+                {
+                    Stack.achFlags[Stack.cEntries] = 0; /* 0 first, 1 last */
+                    Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
+                    continue;
+                }
+            }
+
+            /* center */
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
+                return rc;
+#ifdef KRB_EQUAL_ALLOWED
+            if (pNode->mpList != KRB_NULL)
+                for (pEqual = KRB_GET_POINTER(&pNode->mpList); pEqual; pEqual = KRB_GET_POINTER_NULL(&pEqual->mpList))
+                {
+                    rc = pfnCallBack(pEqual, pvUser);
+                    if (rc)
+                    {
+                        KRB_READ_UNLOCK(pRoot);
+                        return rc;
+                    }
+                }
+#endif
+
+            /* right */
+            Stack.cEntries--;
+            if (pNode->mpRight != KRB_NULL)
+            {
+                Stack.achFlags[Stack.cEntries] = 0;
+                Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
+            }
+        } /* while */
+    }
+    else
+    {   /* from right */
+        while (Stack.cEntries > 0)
+        {
+            pNode = Stack.aEntries[Stack.cEntries - 1];
+
+            /* right */
+            if (!Stack.achFlags[Stack.cEntries - 1]++)
+            {
+                if (pNode->mpRight != KRB_NULL)
+                {
+                    Stack.achFlags[Stack.cEntries] = 0;  /* 0 first, 1 last */
+                    Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
+                    continue;
+                }
+            }
+
+            /* center */
+            rc = pfnCallBack(pNode, pvUser);
+            if (rc)
+                return rc;
+#ifdef KRB_EQUAL_ALLOWED
+            if (pNode->mpList != KRB_NULL)
+                for (pEqual = KRB_GET_POINTER(&pNode->mpList); pEqual; pEqual = KRB_GET_POINTER_NULL(&pEqual->pList))
+                {
+                    rc = pfnCallBack(pEqual, pvUser);
+                    if (rc)
+                    {
+                        KRB_READ_UNLOCK(pRoot);
+                        return rc;
+                    }
+                }
+#endif
+
+            /* left */
+            Stack.cEntries--;
+            if (pNode->mpLeft != KRB_NULL)
+            {
+                Stack.achFlags[Stack.cEntries] = 0;
+                Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
+            }
+        } /* while */
+    }
+
+    KRB_READ_UNLOCK(pRoot);
+    return 0;
+}
+
Index: trunk/include/k/kRbTmpl/kRbEnum.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbEnum.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbEnum.h	(revision 35)
@@ -0,0 +1,187 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Node Enumeration.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/*******************************************************************************
+*   Structures and Typedefs                                                    *
+*******************************************************************************/
+/**
+ * Enumeration control data.
+ *
+ * This is initialized by BeginEnum and used by GetNext to figure out what
+ * to do next.
+ */
+typedef struct KRB_TYPE(,ENUMDATA)
+{
+    KBOOL               fFromLeft;
+    KI8                 cEntries;
+    KU8                 achFlags[KRB_MAX_STACK];
+    KRBNODE *           aEntries[KRB_MAX_STACK];
+} KRB_TYPE(,ENUMDATA), *KRB_TYPE(P,ENUMDATA);
+
+
+/**
+ * Ends an enumeration.
+ *
+ * The purpose of this function is to unlock the tree should the Red-Black tree
+ * implementation include locking.  It's good practice to call it anyway even if
+ * the tree doesn't do any locking.
+ *
+ * @param   pEnumData   Pointer to enumeration control data.
+ */
+KRB_DECL(void) KRB_FN(EndEnum)(KRB_TYPE(,ENUMDATA) *pEnumData)
+{
+    KRBROOT pRoot = pEnumData->pRoot;
+    pEnumData->pRoot = NULL;
+    if (pRoot)
+        KRB_READ_UNLOCK(pEnumData->pRoot);
+}
+
+
+/**
+ * Get the next node in the tree enumeration.
+ *
+ * The current implementation of this function willl not walk the mpList
+ * chain like the DoWithAll function does. This may be changed later.
+ *
+ * @returns Pointer to the next node in the tree.
+ *          NULL is returned when the end of the tree has been reached,
+ *          it is not necessary to call EndEnum in this case.
+ * @param   pEnumData   Pointer to enumeration control data.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(GetNext)(KRB_TYPE(,ENUMDATA) *pEnumData)
+{
+    if (pEnumData->fFromLeft)
+    {   /* from left */
+        while (pEnumData->cEntries > 0)
+        {
+            KRBNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+
+            /* left */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                if (pNode->mpLeft != KRB_NULL)
+                {
+                    pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
+                    pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
+                    continue;
+                }
+            }
+
+            /* center */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                return pNode;
+            }
+
+            /* right */
+            pEnumData->cEntries--;
+            if (pNode->mpRight != KRB_NULL)
+            {
+                pEnumData->achFlags[pEnumData->cEntries] = 0;
+                pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
+            }
+        } /* while */
+    }
+    else
+    {   /* from right */
+        while (pEnumData->cEntries > 0)
+        {
+            KRBNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+
+            /* right */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 0)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                if (pNode->mpRight != KRB_NULL)
+                {
+                    pEnumData->achFlags[pEnumData->cEntries] = 0;  /* 0 right, 1 center, 2 left */
+                    pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
+                    continue;
+                }
+            }
+
+            /* center */
+            if (pEnumData->achFlags[pEnumData->cEntries - 1] == 1)
+            {
+                pEnumData->achFlags[pEnumData->cEntries - 1]++;
+                return pNode;
+            }
+
+            /* left */
+            pEnumData->cEntries--;
+            if (pNode->mpLeft != KRB_NULL)
+            {
+                pEnumData->achFlags[pEnumData->cEntries] = 0;
+                pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
+            }
+        } /* while */
+    }
+
+    /*
+     * Call EndEnum.
+     */
+    KRB_FN(EndEnum)(pEnumData);
+    return NULL;
+}
+
+
+/**
+ * Starts an enumeration of all nodes in the given tree.
+ *
+ * The current implementation of this function will not walk the mpList
+ * chain like the DoWithAll function does. This may be changed later.
+ *
+ * @returns Pointer to the first node in the enumeration.
+ *          If NULL is returned the tree is empty calling EndEnum isn't
+ *          strictly necessary (although it will do no harm).
+ * @param   pRoot           Pointer to the Red-Back tree's root structure.
+ * @param   pEnumData       Pointer to enumeration control data.
+ * @param   fFromLeft       K_TRUE:  Left to right.
+ *                          K_FALSE: Right to left.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(BeginEnum)(KRBROOT *pRoot, KRB_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft)
+{
+    KRB_READ_LOCK(pRoot);
+    pEnumData->pRoot = pRoot;
+    if (pRoot->mpRoot != KRB_NULL)
+    {
+        pEnumData->fFromLeft = fFromLeft;
+        pEnumData->cEntries = 1;
+        pEnumData->aEntries[0] = KRB_GET_POINTER(pRoot->mpRoot);
+        pEnumData->achFlags[0] = 0;
+    }
+    else
+        pEnumData->cEntries = 0;
+
+    return KRB_FN(GetNext)(pEnumData);
+}
+
Index: trunk/include/k/kRbTmpl/kRbGet.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbGet.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbGet.h	(revision 35)
@@ -0,0 +1,89 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Get a Node.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * Gets a node from the tree (does not remove it!)
+ *
+ * @returns Pointer to the node holding the given key.
+ * @param   pRoot       Pointer to the Red-Back tree's root structure.
+ * @param   Key         Key value of the node which is to be found.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(Get)(KRBROOT *pRoot, KRBKEY Key)
+{
+    KRBNODE *pNode;
+#ifdef KRB_CACHE_SIZE
+    KRBTREEPTR *ppEntry;
+#endif
+
+    KRB_READ_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
+    {
+        KRB_READ_UNLOCK(pRoot);
+        return NULL;
+    }
+
+#ifdef KRB_CACHE_SIZE
+    ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)];
+    pNode = KRB_GET_POINTER_NULL(ppEntry);
+    if (!pNode || KRB_CMP_NE(pNode->mKey, Key))
+#endif
+    {
+        pNode = KRB_GET_POINTER(&pRoot->mpRoot);
+        while (KRB_CMP_NE(pNode->mKey, Key))
+        {
+            if (KRB_CMP_G(pNode->mKey, Key))
+            {
+                if (pNode->mpLeft == KRB_NULL)
+                {
+                    KRB_READ_UNLOCK(pRoot);
+                    return NULL;
+                }
+                pNode = KRB_GET_POINTER(&pNode->mpLeft);
+            }
+            else
+            {
+                if (pNode->mpRight == KRB_NULL)
+                {
+                    KRB_READ_UNLOCK(pRoot);
+                    return NULL;
+                }
+                pNode = KRB_GET_POINTER(&pNode->mpRight);
+            }
+        }
+
+#ifdef KRB_CACHE_SIZE
+        KRB_SET_POINTER(ppEntry, pNode);
+#endif
+    }
+
+    KRB_READ_UNLOCK(pRoot);
+    return pNode;
+}
+
Index: trunk/include/k/kRbTmpl/kRbGetBestFit.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbGetBestFit.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbGetBestFit.h	(revision 35)
@@ -0,0 +1,112 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Get Best Fitting Node.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * Finds the best fitting node in the tree for the given Key value.
+ *
+ * @returns Pointer to the best fitting node found.
+ * @param   pRoot           Pointer to the Red-Back tree's root structure.
+ * @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.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(GetBestFit)(KRBROOT *pRoot, KRBKEY Key, KBOOL fAbove)
+{
+    register KRBNODE  *pNode;
+    KRBNODE           *pNodeLast;
+
+    KRB_READ_LOCK(pLook);
+    if (pRoot->mpRoot == KRB_NULL)
+    {
+        KRB_READ_UNLOCK(pLook);
+        return NULL;
+    }
+
+    pNode = KRB_GET_POINTER(&pRoot->mpRoot);
+    pNodeLast = NULL;
+    if (fAbove)
+    {   /* pNode->mKey >= Key */
+        while (KRB_CMP_NE(pNode->mKey, Key))
+        {
+            if (KRB_CMP_G(pNode->mKey, Key))
+            {
+                if (pNode->mpLeft == KRB_NULL)
+                {
+                    KRB_READ_UNLOCK(pLook);
+                    return pNode;
+                }
+                pNodeLast = pNode;
+                pNode = KRB_GET_POINTER(&pNode->mpLeft);
+            }
+            else
+            {
+                if (pNode->mpRight == KRB_NULL)
+                {
+                    KRB_READ_UNLOCK(pLook);
+                    return pNodeLast;
+                }
+                pNode = KRB_GET_POINTER(&pNode->mpRight);
+            }
+        }
+    }
+    else
+    {   /* pNode->mKey <= Key */
+        while (KRB_CMP_NE(pNode->mKey, Key))
+        {
+            if (KRB_CMP_G(pNode->mKey, Key))
+            {
+                if (pNode->mpLeft == KRB_NULL)
+                {
+                    KRB_READ_UNLOCK(pLook);
+                    return pNodeLast;
+                }
+                pNode = KRB_GET_POINTER(&pNode->mpLeft);
+            }
+            else
+            {
+                if (pNode->mpRight == KRB_NULL)
+                {
+                    KRB_READ_UNLOCK(pLook);
+                    return pNode;
+                }
+                pNodeLast = pNode;
+                pNode = KRB_GET_POINTER(&pNode->mpRight);
+            }
+        }
+    }
+
+    /* perfect match or nothing. */
+    KRB_READ_UNLOCK(pLook);
+    return pNode;
+}
+
Index: trunk/include/k/kRbTmpl/kRbGetWithParent.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbGetWithParent.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbGetWithParent.h	(revision 35)
@@ -0,0 +1,65 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Get Node With Parent.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * 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   pRoot       Pointer to the Red-Back tree's root structure.
+ * @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.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(GetWithParent)(KRBROOT *pRoot, KRBNODE **ppParent, KRBKEY Key)
+{
+    register KRBNODE *pNode;
+    register KRBNODE *pParent;
+
+    KRB_READ_LOCK(pRoot);
+
+    pParent = NULL;
+    pNode = KRB_GET_POINTER_NULL(&pRoot->mpRoot);
+    while (     pNode != NULL
+           &&   KRB_CMP_NE(pNode->mKey, Key))
+    {
+        pParent = pNode;
+        if (KRB_CMP_G(pNode->mKey, Key))
+            pNode = KRB_GET_POINTER_NULL(&pNode->mpLeft);
+        else
+            pNode = KRB_GET_POINTER_NULL(&pNode->mpRight);
+    }
+
+    KRB_READ_UNLOCK(pRoot);
+
+    *ppParent = pParent;
+    return pNode;
+}
+
Index: trunk/include/k/kRbTmpl/kRbRemove2.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbRemove2.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbRemove2.h	(revision 35)
@@ -0,0 +1,133 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Remove A Specific Node.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * Removes the specified node from the tree.
+ *
+ * @returns Pointer to the removed node (NULL if not in the tree)
+ * @param   pRoot       Pointer to the Red-Back tree's root structure.
+ * @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.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(Remove2)(KRBROOT *pRoot, KRBNODE *pNode)
+{
+#ifdef KRB_EQUAL_ALLOWED
+    /*
+     * Find the right node by key and see if it's what we want.
+     */
+    KRBNODE *pParent;
+    KRBNODE *pCurNode = KRB_FN(GetWithParent)(pRoot, pNode->mKey, &pParent);
+    if (!pCurNode)
+        return NULL;
+    KRB_WRITE_LOCK(pRoot); /** @todo the locking here isn't 100% sane. The only way to archive that is by no calling worker functions. */
+    if (pCurNode != pNode)
+    {
+        /*
+         * It's not the one we want, but it could be in the duplicate list.
+         */
+        while (pCurNode->mpList != KRB_NULL)
+        {
+            KRBNODE *pNext = KRB_GET_POINTER(&pCurNode->mpList);
+            if (pNext == pNode)
+            {
+                KRB_SET_POINTER_NULL(&pCurNode->mpList, KRB_GET_POINTER_NULL(&pNode->mpList));
+                pNode->mpList = KRB_NULL;
+                KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
+                KRB_WRITE_UNLOCK(pRoot);
+                return pNode;
+            }
+            pCurNode = pNext;
+        }
+        KRB_WRITE_UNLOCK(pRoot);
+        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->mpList == KRB_NULL)
+    {
+        KRB_WRITE_UNLOCK(pRoot);
+        KRB_FN(Remove)(pRoot, pNode->mKey);
+    }
+    else
+    {
+        KRBNODE *pNewUs = KRB_GET_POINTER(&pNode->mpList);
+
+        pNewUs->mHeight = pNode->mHeight;
+
+        if (pNode->mpLeft != KRB_NULL)
+            KRB_SET_POINTER(&pNewUs->mpLeft, KRB_GET_POINTER(&pNode->mpLeft))
+        else
+            pNewUs->mpLeft = KRB_NULL;
+
+        if (pNode->mpRight != KRB_NULL)
+            KRB_SET_POINTER(&pNewUs->mpRight, KRB_GET_POINTER(&pNode->mpRight))
+        else
+            pNewUs->mpRight = KRB_NULL;
+
+        if (pParent)
+        {
+            if (KRB_GET_POINTER_NULL(&pParent->mpLeft) == pNode)
+                KRB_SET_POINTER(&pParent->mpLeft, pNewUs);
+            else
+                KRB_SET_POINTER(&pParent->mpRight, pNewUs);
+        }
+        else
+            KRB_SET_POINTER(&pRoot->mpRoot, pNewUs);
+
+        KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
+        KRB_WRITE_UNLOCK(pRoot);
+    }
+
+    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.
+     */
+    KRBNODE *pRemovedNode = KRB_FN(Remove)(pRoot, pNode->mKey);
+    if (pRemovedNode == pNode)
+        return pRemovedNode;
+
+    KRB_FN(Insert)(pRoot, pRemovedNode);
+    return NULL;
+#endif
+}
+
Index: trunk/include/k/kRbTmpl/kRbRemoveBestFit.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbRemoveBestFit.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbRemoveBestFit.h	(revision 35)
@@ -0,0 +1,70 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Remove Best Fitting Node.
+ */
+
+/*
+ * Copyright (c) 1999-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/**
+ * Finds the best fitting node in the tree for the given Key value and removes the node.
+ *
+ * @returns Pointer to the removed node.
+ * @param   pRoot       Pointer to the Red-Back tree's root structure.
+ * @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.
+ */
+KRB_DECL(KRBNODE *) KRB_FN(RemoveBestFit)(KRBROOT *pRoot, KRBKEY 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.
+     */
+    KRBNODE *pNode = KRB_FN(GetBestFit)(pRoot, Key, fAbove);
+    if (pNode != NULL)
+    {
+#ifdef KRB_EQUAL_ALLOWED
+        KRB_WRITE_LOCK(pRoot); /** @todo the locking isn't quite sane here. :-/ */
+        if (pNode->mpList != KRB_NULL)
+        {
+            KRBNODE *pRet = KRB_GET_POINTER(&pNode->mpList);
+            KRB_SET_POINTER_NULL(&pNode->mpList, &pRet->mpList);
+            KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
+            KRB_WRITE_UNLOCK(pRoot);
+            return pRet;
+        }
+        KRB_WRITE_UNLOCK(pRoot);
+#endif
+        pNode = KRB_FN(Remove)(pRoot, pNode->mKey);
+    }
+    return pNode;
+}
+
Index: trunk/include/k/kRbTmpl/kRbUndef.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbUndef.h	(revision 35)
+++ trunk/include/k/kRbTmpl/kRbUndef.h	(revision 35)
@@ -0,0 +1,79 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Undefines All Macros (both config and temp).
+ */
+
+/*
+ * Copyright (c) 2006-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+/*
+ * The configuration.
+ */
+#undef KRB_EQUAL_ALLOWED
+#undef KRB_CHECK_FOR_EQUAL_INSERT
+#undef KRB_MAX_STACK
+#undef KRB_RANGE
+#undef KRB_OFFSET
+#undef KRB_STD_KEY_COMP
+#undef KRB_CACHE_SIZE
+#undef KRB_CACHE_HASH
+#undef KRB_LOCKED
+#undef KRB_WRITE_LOCK
+#undef KRB_WRITE_UNLOCK
+#undef KRB_READ_LOCK
+#undef KRB_READ_UNLOCK
+#undef KRBKEY
+#undef KRBNODE
+#undef KRBTREEPTR
+#undef KRBROOT
+#undef KRB_FN
+#undef KRB_TYPE
+#undef KRB_INT
+#undef KRB_DECL
+#undef mKey
+#undef mKeyLast
+#undef mfIsRed
+#undef mpLeft
+#undef mpRight
+#undef mpList
+#undef mpRoot
+#undef maLookthru
+#undef KRB_CMP_G
+#undef KRB_CMP_E
+#undef KRB_CMP_NE
+#undef KRB_R_IS_IDENTICAL
+#undef KRB_R_IS_INTERSECTING
+#undef KRB_R_IS_IN_RANGE
+
+/*
+ * Internal ones.
+ */
+#undef KRB_IS_RED
+#undef KRB_NULL
+#undef KRB_GET_POINTER
+#undef KRB_GET_POINTER_NULL
+#undef KRB_SET_POINTER
+#undef KRB_SET_POINTER_NULL
+
Index: trunk/include/k/kRbU32.h
===================================================================
--- trunk/include/k/kRbU32.h	(revision 35)
+++ trunk/include/k/kRbU32.h	(revision 35)
@@ -0,0 +1,68 @@
+/* $Id$ */
+/** @file
+ * kRb - Red-Black Tree Implementation, KU32 keys.
+ */
+
+/*
+ * Copyright (c) 2006-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ *
+ * Permission is hereby granted, free of charge, to any person
+ * obtaining a copy of this software and associated documentation
+ * files (the "Software"), to deal in the Software without
+ * restriction, including without limitation the rights to use,
+ * copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following
+ * conditions:
+ *
+ * The above copyright notice and this permission notice shall be
+ * included in all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+ * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES
+ * OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+ * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT
+ * HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
+ * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR
+ * OTHER DEALINGS IN THE SOFTWARE.
+ */
+
+#ifndef ___k_kRbU32_h___
+#define ___k_kRbU32_h___
+
+typedef struct KRBU32
+{
+    KU32                mKey;
+    KBOOL               mfRed;
+    struct KRBU32      *mpLeft;
+    struct KRBU32      *mpRight;
+} KRBU32;
+typedef KRBU32  *PRBU32;
+typedef KRBU32 **PPRBU32;
+
+/*#define KRB_EQUAL_ALLOWED*/
+#define KRB_CHECK_FOR_EQUAL_INSERT
+/*#define KRB_RANGE */
+/*#define KRB_OFFSET */
+#define KRB_MAX_STACK           48
+#define KRB_STD_KEY_COMP
+#define KRBKEY                  KU32
+#define KRBNODE                 KRBU32
+#define KRB_FN(name)            kRbU32 ## name
+#define KRB_TYPE(prefix,name)   prefix ## KRBU32 ## name
+#define KRB_INT(name)           KRBU32INT ## name
+#define KRB_DECL(rettype)       K_DECL_INLINE(rettype)
+
+#include <k/kRbTmpl/kRbBase.h>
+#include <k/kRbTmpl/kRbDoWithAll.h>
+#include <k/kRbTmpl/kRbEnum.h>
+#include <k/kRbTmpl/kRbGet.h>
+#include <k/kRbTmpl/kRbGetBestFit.h>
+#include <k/kRbTmpl/kRbGetWithParent.h>
+#include <k/kRbTmpl/kRbRemove2.h>
+#include <k/kRbTmpl/kRbRemoveBestFit.h>
+#include <k/kRbTmpl/kRbUndef.h>
+
+#endif
+
