Index: trunk/include/k/kRbTmpl/kRbAssert.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbAssert.h	(revision 38)
+++ trunk/include/k/kRbTmpl/kRbAssert.h	(revision 38)
@@ -0,0 +1,136 @@
+/* $Id$ */
+/** @file
+ * kRbTmpl - Templated Red-Black Trees, Assert Valid Tree.
+ */
+
+/*
+ * Copyright (c) 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.
+ */
+
+
+/**
+ * Internal helper for KRB_FN(Assert)
+ *
+ * @returns The number of black nodes. -1 is return if the tree is invalid.
+ * @param   pRoot       The root of the (sub-)tree to assert.
+ */
+K_DECL_INLINE(int) KRB_FN(AssertRecurse)(KRBNODE *pRoot)
+{
+    int cLeft;
+    int cRight;
+
+    if (!pRoot)
+        /* leafs are black. */
+        return 1;
+
+#ifdef KRB_EQUAL_ALLOWED
+    /* equal nodes are equal :) */
+    if (pNode->mpList != KRB_NULL)
+    {
+        KRBROOT *pEqual;
+        for (pEqual = KRB_GET_POINTER(&pNode->mpList); pEqual; pEqual = KRB_GET_POINTER_NULL(&pEqual->mpList))
+            kHlpAssertReturn(K_CMP_E(pEqual->mKey, pNode->mKey), -1);
+    }
+#endif
+
+    /* binary tree. */
+    kHlpAssertReturn(pRoot->mpLeft  != KRB_NULL && KRB_CMP_G(KRB_GET_POINTER(&pRoot->mpLeft)->mpKey, pRoot->mKey), -1);
+    kHlpAssertReturn(pRoot->mpRight != KRB_NULL && KRB_CMP_G(pRoot->mKey, KRB_GET_POINTER(&pRoot->mpRigth)->mpKey), -1);
+
+    /* both children of red nodes are black. */
+    kHlpAssertReturn(!KRB_IS_RED(pRoot) || (!KRB_IS_RED(pRoot->mpLeft) && !KRB_IS_RED(pRoot->mpRight)), -1);
+
+    /* all paths to leafs contains the same number of black nodes. */
+    cLeft  = KRB_FN(AssertRecurse)(KRB_GET_POINTER_NULL(&pRoot->mpLeft));
+    cRight = KRB_FN(AssertRecurse)(KRB_GET_POINTER_NULL(&pRoot->mpRight));
+    kHlpAssertMsgReturn(cLeft == cRight || cLeft == -1 || cRight == -1, ("%d vs. %d\n", cLeft, cRight), -1);
+
+    return cLeft + !KRB_IS_RED(pRoot);
+}
+
+
+/**
+ * Asserts the validity of the Red-Black tree.
+ *
+ * This method is using recursion and may therefore consume quite a bit of stack
+ * on a large tree.
+ *
+ * @returns K_TRUE if valid.
+ * @returns K_FALSE if invalid, assertion raised on each violation.
+ * @param   pRoot           Pointer to the Red-Back tree's root structure.
+ */
+KRB_DECL(KBOOL) KRB_FN(Assert)(KRBROOT *pRoot)
+{
+    KBOOL       fRc = K_TRUE;
+#ifdef KRB_CACHE_SIZE
+    unsigned    i;
+#endif
+    KRBNODE    *pNode;
+
+    KRB_READ_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
+    {
+        KRB_READ_UNLOCK(pRoot);
+        return 0;
+    }
+
+#ifdef KRB_CACHE_SIZE
+    /*
+     * Validate the cache.
+     */
+    for (i = 0; i < (KRB_CACHE_SIZE); i++)
+        if (pRoot->maLookthru[i] != KRB_NULL)
+        {
+            KRBNODE pCache = KRB_GET_POINTER(&pRoot->maLookthru[i]);
+
+            /** @todo ranges */
+            kHlpAssertMsgStmt(i == KRB_CACHE_HASH(pCache->Key), ("Invalid cache entry %u, hashed to %u\n", i, KRB_CACHE_HASH(pCache->Key)), fRc = K_FALSE);
+
+            pNode = KRB_GET_POINTER(&pRoot->mpRoot);
+            while (pNode)
+            {
+                if (KRB_CMP_E(pCache->mKey, pNode->mKey))
+                {
+                    kHlpAssertMsgStmt(pNode == pCache, ("Invalid cache entry %u=%p, found %p\n", i, pCache, pNode), fRc = K_FALSE);
+                    break;
+                }
+                if (KRB_CMP_G(pCache->mKey, pNode->mKey))
+                    pNode = KRB_GET_POINTER_NULL(&pNode->mRight);
+                else
+                    pNode = KRB_GET_POINTER_NULL(&pNode->mLeft);
+            }
+            kHlpAssertMsgStmt(pNode, ("Invalid cache entry %u/%p - not found\n", i, pCache), fRc = K_FALSE);
+        }
+#endif
+
+    /*
+     * Recurse thru the tree.
+     */
+    if (KRB_FN(AssertRecurse)(KRB_GET_POINTER(&pRoot->mpRoot)) == -1)
+        fRc = K_FALSE;
+
+    KRB_READ_UNLOCK(pRoot);
+    return fRc;
+}
+
Index: trunk/include/k/kRbTmpl/kRbBase.h
===================================================================
--- trunk/include/k/kRbTmpl/kRbBase.h	(revision 37)
+++ trunk/include/k/kRbTmpl/kRbBase.h	(revision 38)
@@ -147,6 +147,4 @@
 *   Defined Constants And Macros                                               *
 *******************************************************************************/
-#define KAVL_HEIGHTOF(pNode) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
-
 /** @def KRB_GET_POINTER
  * Reads a 'pointer' value.
@@ -262,4 +260,11 @@
 
 
+/** Is the node red or black?
+ * @returns true / false
+ * @param   pNode       Pointer to the node in question.
+ * @remarks All NULL pointers are considered black leaf nodes.
+ */
+#define KRB_IS_RED(pNode)                   ( (pNode) != NULL && (pNode)->mfIsRed )
+
 
 /*******************************************************************************
@@ -315,4 +320,116 @@
 
 /**
+ * Rotates the tree to the left (shift direction) and recolors the nodes.
+ *
+ * @pre
+ *
+ *       2                 4
+ *      / \               / \
+ *     1   4     ==>     2   5
+ *        / \           / \
+ *       3   5         1   3
+ *
+ * @endpre
+ *
+ * @returns The new root node.
+ * @param   pRoot           The root node.
+ *
+ * @remarks This will not update any pointer <tt>to</tt> the root node!
+ */
+K_DECL_INLINE(KRBNODE *) KAVL_FN(RotateLeft)(KRBNODE *pRoot)
+{
+    KRBNODE *pNewRoot = pRoot->mRight;
+    pRoot->mRight     = pNewRoot->mLeft;
+    pNewRoot->mLeft   = pRoot;
+
+    pRoot->mfIsRed    = 1;
+    pNewRoot->mfIsRed = 0;
+    return pNewRoot;
+}
+
+
+/**
+ * Rotates the tree to the right (shift direction) and recolors the nodes.
+ *
+ * @pre
+ *
+ *         4             2
+ *        / \           / \
+ *       2   5   ==>   1   4
+ *      / \               / \
+ *     1   3             3   5
+ *
+ * @endpre
+ *
+ * @returns The new root node.
+ * @param   pRoot           The root node.
+ *
+ * @remarks This will not update any pointer <tt>to</tt> the root node!
+ */
+K_DECL_INLINE(KRBNODE *) KAVL_FN(RotateRight)(KRBNODE *pRoot)
+{
+    KRBNODE *pNewRoot = pRoot->mLeft;
+    pRoot->mLeft      = pNewRoot->mRight;
+    pNewRoot->mRight  = pRoot;
+
+    pRoot->mfIsRed    = 1;
+    pNewRoot->mfIsRed = 0;
+    return pNewRoot;
+}
+
+
+/**
+ * Performs a double left rotation with recoloring.
+ *
+ * @pre
+ *
+ *       2               2                    4
+ *      / \             / \                 /   \
+ *     1   6     ==>   1   4       ==>     2     6
+ *        / \             / \             / \   / \
+ *       4   7           3   6           1   3 5   7
+ *      / \                 / \
+ *     3   5               5   7
+ * @endpre
+ *
+ * @returns The new root node.
+ * @param   pRoot           The root node.
+ *
+ * @remarks This will not update any pointer <tt>to</tt> the root node!
+ */
+K_DECL_INLINE(KRBNODE *) KAVL_FN(DoubleRotateLeft)(KRBNODE *pRoot)
+{
+    pRoot->mRight = KAVL_FN(RotateRight)(pRoot->mRight);
+    return KAVL_FN(RotateLeft)(pRoot);
+}
+
+
+/**
+ * Performs a double right rotation with recoloring.
+ *
+ * @pre
+ *         6                 6                4
+ *        / \               / \             /   \
+ *       2   7             4   7           2     6
+ *      / \      ==>      / \      ==>    / \   / \
+ *     1   4             2   5           1   3 5   7
+ *        / \           / \
+ *       3   5         1   3
+ *
+ * @endpre
+ *
+ * @returns The new root node.
+ * @param   pRoot           The root node.
+ *
+ * @remarks This will not update any pointer <tt>to</tt> the root node!
+ */
+K_DECL_INLINE(KRBNODE *) KAVL_FN(DoubleRotateRight)(KRBNODE *pRoot)
+{
+    pRoot->mLeft = KAVL_FN(RotateLeft)(pRoot->mLeft);
+    return KAVL_FN(RotateRight)(pRoot);
+}
+
+
+/**
  * Inserts a node into the Red-Black tree.
  * @returns   K_TRUE if inserted.
@@ -320,28 +437,16 @@
  * @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;
+    register KRBKEY    Key       = pNode->mKey;
 #ifdef KRB_RANGE
-    register KRBKEY    KeyLast = pNode->mKeyLast;
+    register KRBKEY    KeyLast   = pNode->mKeyLast;
 #endif
 
 #ifdef KRB_RANGE
     if (Key > KeyLast)
-        return false;
+        return K_FALSE;
 #endif
 
