Changeset 35

Timestamp:

Nov 8, 2009, 8:39:03 PM (16 years ago)

Author:

bird

Message:

Templated red-black trees - kick off.

Location:

trunk/include/k

Files:

• kRbTmpl (copied) (copied from trunk/include/k/kAvlTmpl )
• kRbTmpl/kRbBase.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlBase.h ) (13 diffs)
• kRbTmpl/kRbDestroy.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlDestroy.h ) (4 diffs)
• kRbTmpl/kRbDoWithAll.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlDoWithAll.h ) (9 diffs)
• kRbTmpl/kRbEnum.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlEnum.h ) (14 diffs)
• kRbTmpl/kRbGet.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlGet.h ) (2 diffs)
• kRbTmpl/kRbGetBestFit.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlGetBestFit.h ) (5 diffs)
• kRbTmpl/kRbGetWithParent.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlGetWithParent.h ) (2 diffs)
• kRbTmpl/kRbRemove2.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlRemove2.h ) (6 diffs)
• kRbTmpl/kRbRemoveBestFit.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlRemoveBestFit.h ) (4 diffs)
• kRbTmpl/kRbUndef.h (moved) (moved from trunk/include/k/kAvlTmpl/kAvlUndef.h ) (3 diffs)
• kRbU32.h (copied) (copied from trunk/include/k/kAvlU32.h ) (2 diffs)

trunk/include/k/kRbTmpl/kRbBase.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, The Mandatory Base Code.
+ * kRbTmpl - Templated Red-Black Trees, The Mandatory Base Code.
  */
 
@@ -31 +31 @@
 /** @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
+ *  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 KAVLNODE::pList.
+ *  Then Equal keys will be put in a list pointed to by KRBNODE::pList.
  *  This is by default not defined.
  *
- *  \#define KAVL_CHECK_FOR_EQUAL_INSERT
+ *  \#define KRB_CHECK_FOR_EQUAL_INSERT
  *  Define this to enable insert check for equal nodes.
  *  This is by default not defined.
  *
- *  \#define KAVL_MAX_STACK
+ *  \#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
@@ -50 +49 @@
  *  Must be defined.
  *
- *  \#define KAVL_RANGE
+ *  \#define KRB_RANGE
  *  Define this to enable key ranges.
  *
- *  \#define KAVL_OFFSET
+ *  \#define KRB_OFFSET
  *  Define this to link the tree together using self relative offset
  *  instead of memory pointers, thus making the entire tree relocatable
@@ -59 +58 @@
  *  the exact same distance.
  *
- *  \#define KAVL_LOOKTHRU
+ *  \#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 KAVL_LOOKTHRU_HASH(Key)
+ *  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 KAVL_LOCKED
+ *  \#define KRB_LOCKED
  *  Define this if you wish for the tree to be locked via the
- *  KAVL_WRITE_LOCK,  KAVL_WRITE_UNLOCK, KAVL_READ_LOCK and
- *  KAVL_READ_UNLOCK macros. If not defined the tree will not be subject
+ *  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 KAVL_WRITE_LOCK(pRoot)
+ *  \#define KRB_WRITE_LOCK(pRoot)
  *  Lock the tree for writing.
  *
- *  \#define KAVL_WRITE_UNLOCK(pRoot)
- *  Counteracts KAVL_WRITE_LOCK.
- *
- *  \#define KAVL_READ_LOCK(pRoot)
+ *  \#define KRB_WRITE_UNLOCK(pRoot)
+ *  Counteracts KRB_WRITE_LOCK.
+ *
+ *  \#define KRB_READ_LOCK(pRoot)
  *  Lock the tree for reading.
  *
- *  \#define KAVL_READ_UNLOCK(pRoot)
- *  Counteracts KAVL_READ_LOCK.
- *
- *  \#define KAVLKEY
+ *  \#define KRB_READ_UNLOCK(pRoot)
+ *  Counteracts KRB_READ_LOCK.
+ *
+ *  \#define KRBKEY
  *  Define this to the name of the AVL key type.
  *
- *  \#define KAVL_STD_KEY_COMP
+ *  \#define KRB_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 KAVLNODE
+ *  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 KAVL_RANGE is defined a mKeyLast is also required.
- *  If KAVL_EQUAL_ALLOWED is defined a mpList member is required.
+ *  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 KAVLTREEPTR
+ *  \#define KRBTREEPTR
  *  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 KAVLNODE *.
- *
- *  \#define KAVLROOT
+ *  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 KAVLTREEPTR type. If KAVL_LOOKTHRU is non-zero a
- *  maLookthru[KAVL_LOOKTHRU] member of the KAVLTREEPTR type is also
+ *  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 KAVL_FN
+ *  \#define KRB_FN
  *  Use this to alter the names of the AVL functions.
  *  Must be defined.
  *
- *  \#define KAVL_TYPE(prefix, name)
+ *  \#define KRB_TYPE(prefix, name)
  *  Use this to make external type names and unique. The prefix may be empty.
  *  Must be defined.
  *
- *  \#define KAVL_INT(name)
+ *  \#define KRB_INT(name)
  *  Use this to make internal type names and unique. The prefix may be empty.
  *  Must be defined.
  *
- *  \#define KAVL_DECL(rettype)
+ *  \#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
@@ -151 +149 @@
 #define KAVL_HEIGHTOF(pNode) ((KU8)((pNode) != NULL ? (pNode)->mHeight : 0))
 
-/** @def KAVL_GET_POINTER
+/** @def KRB_GET_POINTER
  * Reads a 'pointer' value.
  *
@@ -159 +157 @@
  */
 
-/** @def KAVL_GET_POINTER_NULL
- * Reads a 'pointer' value which can be KAVL_NULL.
+/** @def KRB_GET_POINTER_NULL
+ * Reads a 'pointer' value which can be KRB_NULL.
  *
  * @returns The native pointer.
- * @returns NULL pointer if KAVL_NULL.
+ * @returns NULL pointer if KRB_NULL.
  * @param   pp      Pointer to the pointer to read.
  * @internal
  */
 
-/** @def KAVL_SET_POINTER
+/** @def KRB_SET_POINTER
  * Writes a 'pointer' value.
  * For offset-based schemes offset relative to pp is calculated and assigned to *pp.
@@ -178 +176 @@
  */
 
-/** @def KAVL_SET_POINTER_NULL
- * Writes a 'pointer' value which can be KAVL_NULL.
+/** @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 KAVL_NULL of course.
+ * 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 KAVL_NULL
+ * @param   pp2     Pointer to where to pointer to assign to pp. This can be KRB_NULL
  * @internal
  */
 
-#ifndef KAVLTREEPTR
-# define KAVLTREEPTR                        KAVLNODE *
-#endif
-
-#ifndef KAVLROOT
-# define KAVLROOT                           KAVL_TYPE(,ROOT)
-# define KAVL_NEED_KAVLROOT
-#endif
-
-#ifdef KAVL_LOOKTHRU
-# ifndef KAVL_LOOKTHRU_HASH
-#  define KAVL_LOOKTHRU_HASH(Key)           ( (Key) % (KAVL_LOOKTHRU) )
+#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(KAVL_LOOKTHRU_HASH)
-# error "KAVL_LOOKTHRU_HASH without KAVL_LOOKTHRU!"
-#endif
-
-#ifdef KAVL_LOOKTHRU
-# define KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, Key) \
+#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 { \
-        KAVLTREEPTR **ppEntry = &pRoot->maLookthru[KAVL_LOOKTHRU_HASH(Key)]; \
-        if ((pNode) == KAVL_GET_POINTER_NULL(ppEntry)) \
-            *ppEntry = KAVL_NULL; \
+        KRBTREEPTR **ppEntry = &pRoot->maLookthru[KRB_CACHE_HASH(Key)]; \
+        if ((pNode) == KRB_GET_POINTER_NULL(ppEntry)) \
+            *ppEntry = KRB_NULL; \
     } while (0)
 #else
-# define KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, Key) do { } while (0)
-#endif
-
-#ifndef KAVL_LOCKED
-# define KAVL_WRITE_LOCK(pRoot)             do { } while (0)
-# define KAVL_WRITE_UNLOCK(pRoot)           do { } while (0)
-# define KAVL_READ_LOCK(pRoot)              do { } while (0)
-# define KAVL_READ_UNLOCK(pRoot)            do { } while (0)
-#endif
-
-#ifdef KAVL_OFFSET
-# define KAVL_GET_POINTER(pp)               ( (KAVLNODE *)((KIPTR)(pp) + *(pp)) )
-# define KAVL_GET_POINTER_NULL(pp)          ( *(pp) != KAVL_NULL ? KAVL_GET_POINTER(pp) : NULL )
-# define KAVL_SET_POINTER(pp, p)            ( (*(pp)) = ((KIPTR)(p) - (KIPTR)(pp)) )
-# define KAVL_SET_POINTER_NULL(pp, pp2)     ( (*(pp)) = *(pp2) != KAVL_NULL ? (KIPTR)KAVL_GET_POINTER(pp2) - (KIPTR)(pp) : KAVL_NULL )
+# 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 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
+# 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 KAVL_OFFSET
-# define KAVL_NULL     0
+#ifdef KRB_OFFSET
+# define KRB_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)
+# 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 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)
+#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
 
@@ -274 +272 @@
 {
     unsigned        cEntries;
-    KAVLTREEPTR    *aEntries[KAVL_MAX_STACK];
-} KAVL_INT(STACK);
+    KRBTREEPTR    *aEntries[KRB_MAX_STACK];
+} KRB_INT(STACK);
 
 /**
  * The callback used by the Destroy and DoWithAll functions.
  */
-typedef int (* KAVL_TYPE(PFN,CALLBACK))(KAVLNODE *, void *);
-
-#ifdef KAVL_NEED_KAVLROOT
+typedef int (* KRB_TYPE(PFN,CALLBACK))(KRBNODE *, void *);
+
+#ifdef KRB_NEED_KRBROOT
 /**
- * The AVL root structure.
+ * The Red-Black tree root structure.
  */
 typedef struct
 {
-    KAVLTREEPTR     mpRoot;
-# ifdef KAVL_LOOKTHRU
-    KAVLTREEPTR     maLookthru[KAVL_LOOKTHRU];
+    KRBTREEPTR     mpRoot;
+# ifdef KRB_CACHE_SIZE
+    KRBTREEPTR     maLookthru[KRB_CACHE_SIZE];
 # endif
-} KAVLROOT;
-#endif
+} KRBROOT;
+#endif
+
 
 
 /**
- * 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)
+ * Initializes the root of the Red-Black tree.
+ *
+ * @param     pTree     Pointer to the root structure.
+ */
+KRB_DECL(void) KRB_FN(Init)(KRBROOT *pRoot)
 {
-    while (pStack->cEntries > 0)
-    {
-        KAVLTREEPTR     *ppNode = pStack->aEntries[--pStack->cEntries];
-        KAVLNODE        *pNode = KAVL_GET_POINTER(ppNode);
-        KAVLNODE        *pLeftNode = KAVL_GET_POINTER_NULL(&pNode->mpLeft);
-        KU8              uLeftHeight = KAVL_HEIGHTOF(pLeftNode);
-        KAVLNODE        *pRightNode = KAVL_GET_POINTER_NULL(&pNode->mpRight);
-        KU8              uRightHeight = KAVL_HEIGHTOF(pRightNode);
-
-        if (uRightHeight + 1 < uLeftHeight)
-        {
-            KAVLNODE    *pLeftLeftNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpLeft);
-            KAVLNODE    *pLeftRightNode = KAVL_GET_POINTER_NULL(&pLeftNode->mpRight);
-            KU8          uLeftRightHeight = KAVL_HEIGHTOF(pLeftRightNode);
-
-            if (KAVL_HEIGHTOF(pLeftLeftNode) >= uLeftRightHeight)
-            {
-                KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftNode->mpRight);
-                KAVL_SET_POINTER(&pLeftNode->mpRight, pNode);
-                pLeftNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uLeftRightHeight)));
-                KAVL_SET_POINTER(ppNode, pLeftNode);
-            }
-            else
-            {
-                KAVL_SET_POINTER_NULL(&pLeftNode->mpRight, &pLeftRightNode->mpLeft);
-                KAVL_SET_POINTER_NULL(&pNode->mpLeft, &pLeftRightNode->mpRight);
-                KAVL_SET_POINTER(&pLeftRightNode->mpLeft, pLeftNode);
-                KAVL_SET_POINTER(&pLeftRightNode->mpRight, pNode);
-                pLeftNode->mHeight = pNode->mHeight = uLeftRightHeight;
-                pLeftRightNode->mHeight = uLeftHeight;
-                KAVL_SET_POINTER(ppNode, pLeftRightNode);
-            }
-        }
-        else if (uLeftHeight + 1 < uRightHeight)
-        {
-            KAVLNODE    *pRightLeftNode = KAVL_GET_POINTER_NULL(&pRightNode->mpLeft);
-            KU8          uRightLeftHeight = KAVL_HEIGHTOF(pRightLeftNode);
-            KAVLNODE    *pRightRightNode = KAVL_GET_POINTER_NULL(&pRightNode->mpRight);
-
-            if (KAVL_HEIGHTOF(pRightRightNode) >= uRightLeftHeight)
-            {
-                KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightNode->mpLeft);
-                KAVL_SET_POINTER(&pRightNode->mpLeft, pNode);
-                pRightNode->mHeight = (KU8)(1 + (pNode->mHeight = (KU8)(1 + uRightLeftHeight)));
-                KAVL_SET_POINTER(ppNode, pRightNode);
-            }
-            else
-            {
-                KAVL_SET_POINTER_NULL(&pRightNode->mpLeft, &pRightLeftNode->mpRight);
-                KAVL_SET_POINTER_NULL(&pNode->mpRight, &pRightLeftNode->mpLeft);
-                KAVL_SET_POINTER(&pRightLeftNode->mpRight, pRightNode);
-                KAVL_SET_POINTER(&pRightLeftNode->mpLeft, pNode);
-                pRightNode->mHeight = pNode->mHeight = uRightLeftHeight;
-                pRightLeftNode->mHeight = uRightHeight;
-                KAVL_SET_POINTER(ppNode, pRightLeftNode);
-            }
-        }
-        else
-        {
-            KU8 uHeight = (KU8)(K_MAX(uLeftHeight, uRightHeight) + 1);
-            if (uHeight == pNode->mHeight)
-                break;
-            pNode->mHeight = uHeight;
-        }
-    }
-
+#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
 }
 
 
 /**
- * Initializes the root of the AVL-tree.
- *
- * @param     pTree     Pointer to the root structure.
- */
-KAVL_DECL(void) KAVL_FN(Init)(KAVLROOT *pRoot)
-{
-#ifdef KAVL_LOOKTHRU
-    unsigned i;
-#endif
-
-    pRoot->mpRoot = KAVL_NULL;
-#ifdef KAVL_LOOKTHRU
-    for (i = 0; i < (KAVL_LOOKTHRU); i++)
-        pRoot->maLookthru[i] = KAVL_NULL;
-#endif
-}
-
-
-/**
- * Inserts a node into the AVL-tree.
+ * 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 AVL-tree root structure.
+ * @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.):
@@ -454 +332 @@
  *            Rebalance the tree.
  */
-KAVL_DECL(KBOOL) KAVL_FN(Insert)(KAVLROOT *pRoot, KAVLNODE *pNode)
+KRB_DECL(KBOOL) KRB_FN(Insert)(KRBROOT *pRoot, KRBNODE *pNode)
 {
-    KAVL_INT(STACK)     AVLStack;
-    KAVLTREEPTR        *ppCurNode = &pRoot->mpRoot;
-    register KAVLKEY    Key = pNode->mKey;
-#ifdef KAVL_RANGE
-    register KAVLKEY    KeyLast = pNode->mKeyLast;
-#endif
-
-#ifdef KAVL_RANGE
+    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
 
-    KAVL_WRITE_LOCK(pRoot);
-
-    AVLStack.cEntries = 0;
-    while (*ppCurNode != KAVL_NULL)
+    KRB_WRITE_LOCK(pRoot);
+
+    Stack.cEntries = 0;
+    while (*ppCurNode != KRB_NULL)
     {
-        register KAVLNODE *pCurNode = KAVL_GET_POINTER(ppCurNode);
-
-        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
-        AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
-#ifdef KAVL_EQUAL_ALLOWED
-        if (KAVL_R_IS_IDENTICAL(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
+        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 = KAVL_NULL;
+            pNode->mpLeft = pNode->mpRight = KRB_NULL;
             pNode->mHeight = 0;
-            KAVL_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
-            KAVL_SET_POINTER(&pCurNode->mpList, pNode);
-            KAVL_WRITE_UNLOCK(pRoot);
+            KRB_SET_POINTER_NULL(&pNode->mpList, &pCurNode->mpList);
+            KRB_SET_POINTER(&pCurNode->mpList, pNode);
+            KRB_WRITE_UNLOCK(pRoot);
             return K_TRUE;
         }
 #endif
-#ifdef KAVL_CHECK_FOR_EQUAL_INSERT
-        if (KAVL_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
+#ifdef KRB_CHECK_FOR_EQUAL_INSERT
+        if (KRB_R_IS_INTERSECTING(pCurNode->mKey, Key, pCurNode->mKeyLast, KeyLast))
         {
-            KAVL_WRITE_UNLOCK(pRoot);
+            KRB_WRITE_UNLOCK(pRoot);
             return K_FALSE;
         }
 #endif
-        if (KAVL_G(pCurNode->mKey, Key))
+        if (KRB_CMP_G(pCurNode->mKey, Key))
             ppCurNode = &pCurNode->mpLeft;
         else
@@ -504 +382 @@
     }
 
-    pNode->mpLeft = pNode->mpRight = KAVL_NULL;
-#ifdef KAVL_EQUAL_ALLOWED
-    pNode->mpList = KAVL_NULL;
+    pNode->mpLeft = pNode->mpRight = KRB_NULL;
+#ifdef KRB_EQUAL_ALLOWED
+    pNode->mpList = KRB_NULL;
 #endif
     pNode->mHeight = 1;
-    KAVL_SET_POINTER(ppCurNode, pNode);
-
-    KAVL_FN(Rebalance)(&AVLStack);
-
-    KAVL_WRITE_UNLOCK(pRoot);
+    KRB_SET_POINTER(ppCurNode, pNode);
+
+    KRB_FN(Rebalance)(&Stack);
+
+    KRB_WRITE_UNLOCK(pRoot);
     return K_TRUE;
 }
@@ -519 +397 @@
 
 /**
- * Removes a node from the AVL-tree.
+ * Removes a node from the Red-Black tree.
  * @returns   Pointer to the node.
- * @param     pRoot     Pointer to the AVL-tree root structure.
+ * @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:
@@ -557 +435 @@
  *            return pointer to the removed node (if found).
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(Remove)(KAVLROOT *pRoot, KAVLKEY Key)
+KRB_DECL(KRBNODE *) KRB_FN(Remove)(KRBROOT *pRoot, KRBKEY Key)
 {
-    KAVL_INT(STACK)     AVLStack;
-    KAVLTREEPTR        *ppDeleteNode = &pRoot->mpRoot;
-    register KAVLNODE  *pDeleteNode;
-
-    KAVL_WRITE_LOCK(pRoot);
-
-    AVLStack.cEntries = 0;
+    KRB_INT(STACK)     Stack;
+    KRBTREEPTR        *ppDeleteNode = &pRoot->mpRoot;
+    register KRBNODE  *pDeleteNode;
+
+    KRB_WRITE_LOCK(pRoot);
+
+    Stack.cEntries = 0;
     for (;;)
     {
-        if (*ppDeleteNode == KAVL_NULL)
+        if (*ppDeleteNode == KRB_NULL)
         {
-            KAVL_WRITE_UNLOCK(pRoot);
+            KRB_WRITE_UNLOCK(pRoot);
             return NULL;
         }
-        pDeleteNode = KAVL_GET_POINTER(ppDeleteNode);
-
-        kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
-        AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
-        if (KAVL_E(pDeleteNode->mKey, Key))
+        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 (KAVL_G(pDeleteNode->mKey, Key))
+        if (KRB_CMP_G(pDeleteNode->mKey, Key))
             ppDeleteNode = &pDeleteNode->mpLeft;
         else
@@ -586 +464 @@
     }
 
-    if (pDeleteNode->mpLeft != KAVL_NULL)
+    if (pDeleteNode->mpLeft != KRB_NULL)
     {
         /* find the rightmost node in the left tree. */
-        const unsigned      iStackEntry = AVLStack.cEntries;
-        KAVLTREEPTR        *ppLeftLeast = &pDeleteNode->mpLeft;
-        register KAVLNODE  *pLeftLeast = KAVL_GET_POINTER(ppLeftLeast);
-
-        while (pLeftLeast->mpRight != KAVL_NULL)
+        const unsigned      iStackEntry = Stack.cEntries;
+        KRBTREEPTR        *ppLeftLeast = &pDeleteNode->mpLeft;
+        register KRBNODE  *pLeftLeast = KRB_GET_POINTER(ppLeftLeast);
+
+        while (pLeftLeast->mpRight != KRB_NULL)
         {
-            kHlpAssert(AVLStack.cEntries < KAVL_MAX_STACK);
-            AVLStack.aEntries[AVLStack.cEntries++] = ppLeftLeast;
+            kHlpAssert(Stack.cEntries < KRB_MAX_STACK);
+            Stack.aEntries[Stack.cEntries++] = ppLeftLeast;
             ppLeftLeast = &pLeftLeast->mpRight;
-            pLeftLeast  = KAVL_GET_POINTER(ppLeftLeast);
+            pLeftLeast  = KRB_GET_POINTER(ppLeftLeast);
         }
 
         /* link out pLeftLeast */
-        KAVL_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
+        KRB_SET_POINTER_NULL(ppLeftLeast, &pLeftLeast->mpLeft);
 
         /* link it in place of the delete node. */
-        KAVL_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
-        KAVL_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
+        KRB_SET_POINTER_NULL(&pLeftLeast->mpLeft, &pDeleteNode->mpLeft);
+        KRB_SET_POINTER_NULL(&pLeftLeast->mpRight, &pDeleteNode->mpRight);
         pLeftLeast->mHeight = pDeleteNode->mHeight;
-        KAVL_SET_POINTER(ppDeleteNode, pLeftLeast);
-        AVLStack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
+        KRB_SET_POINTER(ppDeleteNode, pLeftLeast);
+        Stack.aEntries[iStackEntry] = &pLeftLeast->mpLeft;
     }
     else
     {
-        KAVL_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
-        AVLStack.cEntries--;
+        KRB_SET_POINTER_NULL(ppDeleteNode, &pDeleteNode->mpRight);
+        Stack.cEntries--;
     }
 
-    KAVL_FN(Rebalance)(&AVLStack);
-
-    KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
-
-    KAVL_WRITE_UNLOCK(pRoot);
+    KRB_FN(Rebalance)(&Stack);
+
+    KRB_CACHE_INVALIDATE_NODE(pRoot, pDeleteNode, Key);
+
+    KRB_WRITE_UNLOCK(pRoot);
     return pDeleteNode;
 }

trunk/include/k/kRbTmpl/kRbDestroy.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Destroy the tree.
+ * kRbTmpl - Templated Red-Black Trees, Destroy the tree.
  */
 
@@ -37 +37 @@
  *          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 AVL-tree root structure.
+ * @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.
  */
-KAVL_DECL(int) KAVL_FN(Destroy)(KAVLROOT *pRoot, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
+KRB_DECL(int) KRB_FN(Destroy)(KRBROOT *pRoot, KRB_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
 {
-#ifdef KAVL_LOOKTHRU
+#ifdef KRB_CACHE_SIZE
     unsigned    i;
 #endif
     unsigned    cEntries;
-    KAVLNODE   *apEntries[KAVL_MAX_STACK];
+    KRBNODE    *apEntries[KRB_MAX_STACK];
     int         rc;
 
-    KAVL_WRITE_LOCK(pRoot);
-    if (pRoot->mpRoot == KAVL_NULL)
+    KRB_WRITE_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
     {
-        KAVL_WRITE_UNLOCK(pRoot);
+        KRB_WRITE_UNLOCK(pRoot);
         return 0;
     }
 
-#ifdef KAVL_LOOKTHRU
+#ifdef KRB_CACHE_SIZE
     /*
      * Kill the lookthru cache.
      */
-    for (i = 0; i < (KAVL_LOOKTHRU); i++)
-        pRoot->maLookthru[i] = KAVL_NULL;
+    for (i = 0; i < (KRB_CACHE_SIZE); i++)
+        pRoot->maLookthru[i] = KRB_NULL;
 #endif
 
     cEntries = 1;
-    apEntries[0] = KAVL_GET_POINTER(&pRoot->mpRoot);
+    apEntries[0] = KRB_GET_POINTER(&pRoot->mpRoot);
     while (cEntries > 0)
     {
@@ -72 +72 @@
          * Process the subtrees first.
          */
-        KAVLNODE *pNode = apEntries[cEntries - 1];
-        if (pNode->mpLeft != KAVL_NULL)
-            apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
-        else if (pNode->mpRight != KAVL_NULL)
-            apEntries[cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
+        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 KAVL_EQUAL_ALLOWED
+#ifdef KRB_EQUAL_ALLOWED
             /*
              * Process nodes with the same key.
              */
-            while (pNode->pList != KAVL_NULL)
+            while (pNode->pList != KRB_NULL)
             {
-                KAVLNODE *pEqual = KAVL_GET_POINTER(&pNode->pList);
-                KAVL_SET_POINTER(&pNode->pList, KAVL_GET_POINTER_NULL(&pEqual->pList));
-                pEqual->pList = KAVL_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)
                 {
-                    KAVL_WRITE_UNLOCK(pRoot);
+                    KRB_WRITE_UNLOCK(pRoot);
                     return rc;
                 }
@@ -103 +103 @@
             if (--cEntries > 0)
             {
-                KAVLNODE *pParent = apEntries[cEntries - 1];
-                if (KAVL_GET_POINTER(&pParent->mpLeft) == pNode)
-                    pParent->mpLeft = KAVL_NULL;
+                KRBNODE *pParent = apEntries[cEntries - 1];
+                if (KRB_GET_POINTER(&pParent->mpLeft) == pNode)
+                    pParent->mpLeft = KRB_NULL;
                 else
-                    pParent->mpRight = KAVL_NULL;
+                    pParent->mpRight = KRB_NULL;
             }
             else
-                pRoot->mpRoot = KAVL_NULL;
+                pRoot->mpRoot = KRB_NULL;
 
-            kHlpAssert(pNode->mpLeft == KAVL_NULL);
-            kHlpAssert(pNode->mpRight == KAVL_NULL);
+            kHlpAssert(pNode->mpLeft == KRB_NULL);
+            kHlpAssert(pNode->mpRight == KRB_NULL);
             rc = pfnCallBack(pNode, pvUser);
             if (rc)
             {
-                KAVL_WRITE_UNLOCK(pRoot);
+                KRB_WRITE_UNLOCK(pRoot);
                 return rc;
             }
         }
     } /* while */
-    kHlpAssert(pRoot->mpRoot == KAVL_NULL);
+    kHlpAssert(pRoot->mpRoot == KRB_NULL);
 
-    KAVL_WRITE_UNLOCK(pRoot);
+    KRB_WRITE_UNLOCK(pRoot);
     return 0;
 }

trunk/include/k/kRbTmpl/kRbDoWithAll.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, The Callback Iterator.
+ * kRbTmpl - Templated Red-Black Trees, The Callback Iterator.
  */
 
@@ -38 +38 @@
 {
     unsigned        cEntries;
-    KAVLNODE       *aEntries[KAVL_MAX_STACK];
-    char            achFlags[KAVL_MAX_STACK];
-    KAVLROOT        pRoot;
-} KAVL_INT(STACK2);
+    KRBNODE        *aEntries[KRB_MAX_STACK];
+    char            achFlags[KRB_MAX_STACK];
+    KRBROOT        pRoot;
+} KRB_INT(STACK2);
 
 
@@ -48 +48 @@
  *
  * @returns   0 on success. Return from callback on failure.
- * @param     pRoot        Pointer to the AVL-tree root structure.
+ * @param     pRoot        Pointer to the Red-Back tree's root structure.
  * @param     fFromLeft    K_TRUE:  Left to right.
  *                         K_FALSE: Right to left.
@@ -54 +54 @@
  * @param     pvUser       User parameter passed on to the callback function.
  */
-KAVL_DECL(int) KAVL_FN(DoWithAll)(KAVLROOT *pRoot, KBOOL fFromLeft, KAVL_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
+KRB_DECL(int) KRB_FN(DoWithAll)(KRBROOT *pRoot, KBOOL fFromLeft, KRB_TYPE(PFN,CALLBACK) pfnCallBack, void *pvUser)
 {
-    KAVL_INT(STACK2)    AVLStack;
-    KAVLNODE           *pNode;
-#ifdef KAVL_EQUAL_ALLOWED
-    KAVLNODE           *pEqual;
+    KRB_INT(STACK2)     Stack;
+    KRBNODE            *pNode;
+#ifdef KRB_EQUAL_ALLOWED
+    KRBNODE            *pEqual;
 #endif
     int                 rc;
 
-    KAVL_READ_LOCK(pRoot);
-    if (pRoot->mpRoot == KAVL_NULL)
+    KRB_READ_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
     {
-        KAVL_READ_UNLOCK(pRoot);
+        KRB_READ_UNLOCK(pRoot);
         return 0;
     }
 
-    AVLStack.cEntries = 1;
-    AVLStack.achFlags[0] = 0;
-    AVLStack.aEntries[0] = KAVL_GET_POINTER(&pRoot->mpRoot);
+    Stack.cEntries = 1;
+    Stack.achFlags[0] = 0;
+    Stack.aEntries[0] = KRB_GET_POINTER(&pRoot->mpRoot);
 
     if (fFromLeft)
     {   /* from left */
-        while (AVLStack.cEntries > 0)
+        while (Stack.cEntries > 0)
         {
-            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+            pNode = Stack.aEntries[Stack.cEntries - 1];
 
             /* left */
-            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
+            if (!Stack.achFlags[Stack.cEntries - 1]++)
             {
-                if (pNode->mpLeft != KAVL_NULL)
+                if (pNode->mpLeft != KRB_NULL)
                 {
-                    AVLStack.achFlags[AVLStack.cEntries] = 0; /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
+                    Stack.achFlags[Stack.cEntries] = 0; /* 0 first, 1 last */
+                    Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
                     continue;
                 }
@@ -95 +95 @@
             if (rc)
                 return rc;
-#ifdef KAVL_EQUAL_ALLOWED
-            if (pNode->mpList != KAVL_NULL)
-                for (pEqual = KAVL_GET_POINTER(&pNode->mpList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->mpList))
+#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)
                     {
-                        KAVL_READ_UNLOCK(pRoot);
+                        KRB_READ_UNLOCK(pRoot);
                         return rc;
                     }
@@ -109 +109 @@
 
             /* right */
-            AVLStack.cEntries--;
-            if (pNode->mpRight != KAVL_NULL)
+            Stack.cEntries--;
+            if (pNode->mpRight != KRB_NULL)
             {
-                AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
+                Stack.achFlags[Stack.cEntries] = 0;
+                Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
             }
         } /* while */
@@ -119 +119 @@
     else
     {   /* from right */
-        while (AVLStack.cEntries > 0)
+        while (Stack.cEntries > 0)
         {
-            pNode = AVLStack.aEntries[AVLStack.cEntries - 1];
+            pNode = Stack.aEntries[Stack.cEntries - 1];
 
             /* right */
-            if (!AVLStack.achFlags[AVLStack.cEntries - 1]++)
+            if (!Stack.achFlags[Stack.cEntries - 1]++)
             {
-                if (pNode->mpRight != KAVL_NULL)
+                if (pNode->mpRight != KRB_NULL)
                 {
-                    AVLStack.achFlags[AVLStack.cEntries] = 0;  /* 0 first, 1 last */
-                    AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
+                    Stack.achFlags[Stack.cEntries] = 0;  /* 0 first, 1 last */
+                    Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
                     continue;
                 }
@@ -138 +138 @@
             if (rc)
                 return rc;
-#ifdef KAVL_EQUAL_ALLOWED
-            if (pNode->mpList != KAVL_NULL)
-                for (pEqual = KAVL_GET_POINTER(&pNode->mpList); pEqual; pEqual = KAVL_GET_POINTER_NULL(&pEqual->pList))
+#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)
                     {
-                        KAVL_READ_UNLOCK(pRoot);
+                        KRB_READ_UNLOCK(pRoot);
                         return rc;
                     }
@@ -152 +152 @@
 
             /* left */
-            AVLStack.cEntries--;
-            if (pNode->mpLeft != KAVL_NULL)
+            Stack.cEntries--;
+            if (pNode->mpLeft != KRB_NULL)
             {
-                AVLStack.achFlags[AVLStack.cEntries] = 0;
-                AVLStack.aEntries[AVLStack.cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
+                Stack.achFlags[Stack.cEntries] = 0;
+                Stack.aEntries[Stack.cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
             }
         } /* while */
     }
 
-    KAVL_READ_UNLOCK(pRoot);
+    KRB_READ_UNLOCK(pRoot);
     return 0;
 }

trunk/include/k/kRbTmpl/kRbEnum.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Node Enumeration.
+ * kRbTmpl - Templated Red-Black Trees, Node Enumeration.
  */
 
@@ -38 +38 @@
  * to do next.
  */
-typedef struct KAVL_TYPE(,ENUMDATA)
+typedef struct KRB_TYPE(,ENUMDATA)
 {
     KBOOL               fFromLeft;
     KI8                 cEntries;
-    KU8                 achFlags[KAVL_MAX_STACK];
-    KAVLNODE *          aEntries[KAVL_MAX_STACK];
-} KAVL_TYPE(,ENUMDATA), *KAVL_TYPE(P,ENUMDATA);
+    KU8                 achFlags[KRB_MAX_STACK];
+    KRBNODE *           aEntries[KRB_MAX_STACK];
+} KRB_TYPE(,ENUMDATA), *KRB_TYPE(P,ENUMDATA);
 
 
@@ -50 +50 @@
  * Ends an enumeration.
  *
- * The purpose of this function is to unlock the tree should the
- * AVL implementation include locking. It's good practice to call
- * it anyway even if the tree doesn't do any locking.
+ * 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.
  */
-KAVL_DECL(void) KAVL_FN(EndEnum)(KAVL_TYPE(,ENUMDATA) *pEnumData)
+KRB_DECL(void) KRB_FN(EndEnum)(KRB_TYPE(,ENUMDATA) *pEnumData)
 {
-    KAVLROOT pRoot = pEnumData->pRoot;
+    KRBROOT pRoot = pEnumData->pRoot;
     pEnumData->pRoot = NULL;
     if (pRoot)
-        KAVL_READ_UNLOCK(pEnumData->pRoot);
+        KRB_READ_UNLOCK(pEnumData->pRoot);
 }
 
@@ -76 +76 @@
  * @param   pEnumData   Pointer to enumeration control data.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(GetNext)(KAVL_TYPE(,ENUMDATA) *pEnumData)
+KRB_DECL(KRBNODE *) KRB_FN(GetNext)(KRB_TYPE(,ENUMDATA) *pEnumData)
 {
     if (pEnumData->fFromLeft)
@@ -82 +82 @@
         while (pEnumData->cEntries > 0)
         {
-            KAVLNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+            KRBNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
 
             /* left */
@@ -88 +88 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->mpLeft != KAVL_NULL)
+                if (pNode->mpLeft != KRB_NULL)
                 {
                     pEnumData->achFlags[pEnumData->cEntries] = 0; /* 0 left, 1 center, 2 right */
-                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
+                    pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
                     continue;
                 }
@@ -105 +105 @@
             /* right */
             pEnumData->cEntries--;
-            if (pNode->mpRight != KAVL_NULL)
+            if (pNode->mpRight != KRB_NULL)
             {
                 pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
+                pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
             }
         } /* while */
@@ -116 +116 @@
         while (pEnumData->cEntries > 0)
         {
-            KAVLNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
+            KRBNODE *pNode = pEnumData->aEntries[pEnumData->cEntries - 1];
 
             /* right */
@@ -122 +122 @@
             {
                 pEnumData->achFlags[pEnumData->cEntries - 1]++;
-                if (pNode->mpRight != KAVL_NULL)
+                if (pNode->mpRight != KRB_NULL)
                 {
                     pEnumData->achFlags[pEnumData->cEntries] = 0;  /* 0 right, 1 center, 2 left */
-                    pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpRight);
+                    pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpRight);
                     continue;
                 }
@@ -139 +139 @@
             /* left */
             pEnumData->cEntries--;
-            if (pNode->mpLeft != KAVL_NULL)
+            if (pNode->mpLeft != KRB_NULL)
             {
                 pEnumData->achFlags[pEnumData->cEntries] = 0;
-                pEnumData->aEntries[pEnumData->cEntries++] = KAVL_GET_POINTER(&pNode->mpLeft);
+                pEnumData->aEntries[pEnumData->cEntries++] = KRB_GET_POINTER(&pNode->mpLeft);
             }
         } /* while */
@@ -150 +150 @@
      * Call EndEnum.
      */
-    KAVL_FN(EndEnum)(pEnumData);
+    KRB_FN(EndEnum)(pEnumData);
     return NULL;
 }
@@ -156 +156 @@
 
 /**
- * Starts an enumeration of all nodes in the given AVL tree.
+ * Starts an enumeration of all nodes in the given tree.
  *
  * The current implementation of this function will not walk the mpList
@@ -164 +164 @@
  *          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 AVL-tree root structure.
+ * @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.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(BeginEnum)(KAVLROOT *pRoot, KAVL_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft)
+KRB_DECL(KRBNODE *) KRB_FN(BeginEnum)(KRBROOT *pRoot, KRB_TYPE(,ENUMDATA) *pEnumData, KBOOL fFromLeft)
 {
-    KAVL_READ_LOCK(pRoot);
+    KRB_READ_LOCK(pRoot);
     pEnumData->pRoot = pRoot;
-    if (pRoot->mpRoot != KAVL_NULL)
+    if (pRoot->mpRoot != KRB_NULL)
     {
         pEnumData->fFromLeft = fFromLeft;
         pEnumData->cEntries = 1;
-        pEnumData->aEntries[0] = KAVL_GET_POINTER(pRoot->mpRoot);
+        pEnumData->aEntries[0] = KRB_GET_POINTER(pRoot->mpRoot);
         pEnumData->achFlags[0] = 0;
     }
@@ -183 +183 @@
         pEnumData->cEntries = 0;
 
-    return KAVL_FN(GetNext)(pEnumData);
+    return KRB_FN(GetNext)(pEnumData);
 }
 

trunk/include/k/kRbTmpl/kRbGet.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Get a Node.
+ * kRbTmpl - Templated Red-Black Trees, Get a Node.
  */
 
@@ -33 +33 @@
  *
  * @returns Pointer to the node holding the given key.
- * @param   pRoot       Pointer to the AVL-tree root structure.
+ * @param   pRoot       Pointer to the Red-Back tree's root structure.
  * @param   Key         Key value of the node which is to be found.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(Get)(KAVLROOT *pRoot, KAVLKEY Key)
+KRB_DECL(KRBNODE *) KRB_FN(Get)(KRBROOT *pRoot, KRBKEY Key)
 {
-    KAVLNODE *pNode;
-#ifdef KAVL_LOOKTHRU_CACHE
-    KAVLTREEPTR *ppEntry;
+    KRBNODE *pNode;
+#ifdef KRB_CACHE_SIZE
+    KRBTREEPTR *ppEntry;
 #endif
 
-    KAVL_READ_LOCK(pRoot);
-    if (pRoot->mpRoot == KAVL_NULL)
+    KRB_READ_LOCK(pRoot);
+    if (pRoot->mpRoot == KRB_NULL)
     {
-        KAVL_READ_UNLOCK(pRoot);
+        KRB_READ_UNLOCK(pRoot);
         return NULL;
     }
 
-#ifdef KAVL_LOOKTHRU_CACHE
-    ppEntry = &pRoot->maLookthru[KAVL_LOOKTHRU_HASH(Key)];
-    pNode = KAVL_GET_POINTER_NULL(ppEntry);
-    if (!pNode || KAVL_NE(pNode->mKey, Key))
+#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 = KAVL_GET_POINTER(&pRoot->mpRoot);
-        while (KAVL_NE(pNode->mKey, Key))
+        pNode = KRB_GET_POINTER(&pRoot->mpRoot);
+        while (KRB_CMP_NE(pNode->mKey, Key))
         {
-            if (KAVL_G(pNode->mKey, Key))
+            if (KRB_CMP_G(pNode->mKey, Key))
             {
-                if (pNode->mpLeft == KAVL_NULL)
+                if (pNode->mpLeft == KRB_NULL)
                 {
-                    KAVL_READ_UNLOCK(pRoot);
+                    KRB_READ_UNLOCK(pRoot);
                     return NULL;
                 }
-                pNode = KAVL_GET_POINTER(&pNode->mpLeft);
+                pNode = KRB_GET_POINTER(&pNode->mpLeft);
             }
             else
             {
-                if (pNode->mpRight == KAVL_NULL)
+                if (pNode->mpRight == KRB_NULL)
                 {
-                    KAVL_READ_UNLOCK(pRoot);
+                    KRB_READ_UNLOCK(pRoot);
                     return NULL;
                 }
-                pNode = KAVL_GET_POINTER(&pNode->mpRight);
+                pNode = KRB_GET_POINTER(&pNode->mpRight);
             }
         }
 
-#ifdef KAVL_LOOKTHRU_CACHE
-        KAVL_SET_POINTER(ppEntry, pNode);
+#ifdef KRB_CACHE_SIZE
+        KRB_SET_POINTER(ppEntry, pNode);
 #endif
     }
 
-    KAVL_READ_UNLOCK(pRoot);
+    KRB_READ_UNLOCK(pRoot);
     return pNode;
 }

trunk/include/k/kRbTmpl/kRbGetBestFit.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Get Best Fitting Node.
+ * kRbTmpl - Templated Red-Black Trees, Get Best Fitting Node.
  */
 
@@ -33 +33 @@
  *
  * @returns Pointer to the best fitting node found.
- * @param   pRoot           Pointer to the AVL-tree root structure.
+ * @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.
@@ -41 +41 @@
  *          <= (below): the node where you last turned right.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(GetBestFit)(KAVLROOT *pRoot, KAVLKEY Key, KBOOL fAbove)
+KRB_DECL(KRBNODE *) KRB_FN(GetBestFit)(KRBROOT *pRoot, KRBKEY Key, KBOOL fAbove)
 {
-    register KAVLNODE  *pNode;
-    KAVLNODE           *pNodeLast;
+    register KRBNODE  *pNode;
+    KRBNODE           *pNodeLast;
 
-    KAVL_READ_LOCK(pLook);
-    if (pRoot->mpRoot == KAVL_NULL)
+    KRB_READ_LOCK(pLook);
+    if (pRoot->mpRoot == KRB_NULL)
     {
-        KAVL_READ_UNLOCK(pLook);
+        KRB_READ_UNLOCK(pLook);
         return NULL;
     }
 
-    pNode = KAVL_GET_POINTER(&pRoot->mpRoot);
+    pNode = KRB_GET_POINTER(&pRoot->mpRoot);
     pNodeLast = NULL;
     if (fAbove)
     {   /* pNode->mKey >= Key */
-        while (KAVL_NE(pNode->mKey, Key))
+        while (KRB_CMP_NE(pNode->mKey, Key))
         {
-            if (KAVL_G(pNode->mKey, Key))
+            if (KRB_CMP_G(pNode->mKey, Key))
             {
-                if (pNode->mpLeft == KAVL_NULL)
+                if (pNode->mpLeft == KRB_NULL)
                 {
-                    KAVL_READ_UNLOCK(pLook);
+                    KRB_READ_UNLOCK(pLook);
                     return pNode;
                 }
                 pNodeLast = pNode;
-                pNode = KAVL_GET_POINTER(&pNode->mpLeft);
+                pNode = KRB_GET_POINTER(&pNode->mpLeft);
             }
             else
             {
-                if (pNode->mpRight == KAVL_NULL)
+                if (pNode->mpRight == KRB_NULL)
                 {
-                    KAVL_READ_UNLOCK(pLook);
+                    KRB_READ_UNLOCK(pLook);
                     return pNodeLast;
                 }
-                pNode = KAVL_GET_POINTER(&pNode->mpRight);
+                pNode = KRB_GET_POINTER(&pNode->mpRight);
             }
         }
@@ -82 +82 @@
     else
     {   /* pNode->mKey <= Key */
-        while (KAVL_NE(pNode->mKey, Key))
+        while (KRB_CMP_NE(pNode->mKey, Key))
         {
-            if (KAVL_G(pNode->mKey, Key))
+            if (KRB_CMP_G(pNode->mKey, Key))
             {
-                if (pNode->mpLeft == KAVL_NULL)
+                if (pNode->mpLeft == KRB_NULL)
                 {
-                    KAVL_READ_UNLOCK(pLook);
+                    KRB_READ_UNLOCK(pLook);
                     return pNodeLast;
                 }
-                pNode = KAVL_GET_POINTER(&pNode->mpLeft);
+                pNode = KRB_GET_POINTER(&pNode->mpLeft);
             }
             else
             {
-                if (pNode->mpRight == KAVL_NULL)
+                if (pNode->mpRight == KRB_NULL)
                 {
-                    KAVL_READ_UNLOCK(pLook);
+                    KRB_READ_UNLOCK(pLook);
                     return pNode;
                 }
                 pNodeLast = pNode;
-                pNode = KAVL_GET_POINTER(&pNode->mpRight);
+                pNode = KRB_GET_POINTER(&pNode->mpRight);
             }
         }
@@ -107 +107 @@
 
     /* perfect match or nothing. */
-    KAVL_READ_UNLOCK(pLook);
+    KRB_READ_UNLOCK(pLook);
     return pNode;
 }

trunk/include/k/kRbTmpl/kRbGetWithParent.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Get Node With Parent.
+ * kRbTmpl - Templated Red-Black Trees, Get Node With Parent.
  */
 
@@ -34 +34 @@
  *
  * @returns Pointer to the node holding the given key.
- * @param   pRoot       Pointer to the AVL-tree root structure.
+ * @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.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(GetWithParent)(KAVLROOT *pRoot, KAVLNODE **ppParent, KAVLKEY Key)
+KRB_DECL(KRBNODE *) KRB_FN(GetWithParent)(KRBROOT *pRoot, KRBNODE **ppParent, KRBKEY Key)
 {
-    register KAVLNODE *pNode;
-    register KAVLNODE *pParent;
+    register KRBNODE *pNode;
+    register KRBNODE *pParent;
 
-    KAVL_READ_LOCK(pRoot);
+    KRB_READ_LOCK(pRoot);
 
     pParent = NULL;
-    pNode = KAVL_GET_POINTER_NULL(&pRoot->mpRoot);
+    pNode = KRB_GET_POINTER_NULL(&pRoot->mpRoot);
     while (     pNode != NULL
-           &&   KAVL_NE(pNode->mKey, Key))
+           &&   KRB_CMP_NE(pNode->mKey, Key))
     {
         pParent = pNode;
-        if (KAVL_G(pNode->mKey, Key))
-            pNode = KAVL_GET_POINTER_NULL(&pNode->mpLeft);
+        if (KRB_CMP_G(pNode->mKey, Key))
+            pNode = KRB_GET_POINTER_NULL(&pNode->mpLeft);
         else
-            pNode = KAVL_GET_POINTER_NULL(&pNode->mpRight);
+            pNode = KRB_GET_POINTER_NULL(&pNode->mpRight);
     }
 
-    KAVL_UNLOCK(pRoot);
+    KRB_READ_UNLOCK(pRoot);
 
     *ppParent = pParent;

trunk/include/k/kRbTmpl/kRbRemove2.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Remove A Specific Node.
+ * kRbTmpl - Templated Red-Black Trees, Remove A Specific Node.
  */
 
@@ -33 +33 @@
  *
  * @returns Pointer to the removed node (NULL if not in the tree)
- * @param   pRoot       Pointer to the AVL-tree root structure.
+ * @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..
  *
@@ -39 +39 @@
  *          easier to manage.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(Remove2)(KAVLTROOT *pRoot, KAVLNODE *pNode)
+KRB_DECL(KRBNODE *) KRB_FN(Remove2)(KRBROOT *pRoot, KRBNODE *pNode)
 {
-#ifdef KAVL_EQUAL_ALLOWED
+#ifdef KRB_EQUAL_ALLOWED
     /*
      * Find the right node by key and see if it's what we want.
      */
-    KAVLNODE *pParent;
-    KAVLNODE *pCurNode = KAVL_FN(GetWithParent)(pRoot, pNode->mKey, &pParent);
+    KRBNODE *pParent;
+    KRBNODE *pCurNode = KRB_FN(GetWithParent)(pRoot, pNode->mKey, &pParent);
     if (!pCurNode)
         return NULL;
-    KAVL_WRITE_LOCK(pRoot); /** @todo the locking here isn't 100% sane. The only way to archive that is by no calling worker functions. */
+    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)
     {
@@ -55 +55 @@
          * It's not the one we want, but it could be in the duplicate list.
          */
-        while (pCurNode->mpList != KAVL_NULL)
+        while (pCurNode->mpList != KRB_NULL)
         {
-            KAVLNODE *pNext = KAVL_GET_POINTER(&pCurNode->mpList);
+            KRBNODE *pNext = KRB_GET_POINTER(&pCurNode->mpList);
             if (pNext == pNode)
             {
-                KAVL_SET_POINTER_NULL(&pCurNode->mpList, KAVL_GET_POINTER_NULL(&pNode->mpList));
-                pNode->mpList = KAVL_NULL;
-                KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
-                KAVL_WRITE_UNLOCK(pRoot);
+                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;
         }
-        KAVL_WRITE_UNLOCK(pRoot);
+        KRB_WRITE_UNLOCK(pRoot);
         return NULL;
     }
@@ -79 +79 @@
      * insert the first duplicate in our place.
      */
-    if (pNode->mpList == KAVL_NODE)
+    if (pNode->mpList == KRB_NULL)
     {
-        KAVL_WRITE_UNLOCK(pRoot);
-        KAVL_FN(Remove)(pRoot, pNode->mKey);
+        KRB_WRITE_UNLOCK(pRoot);
+        KRB_FN(Remove)(pRoot, pNode->mKey);
     }
     else
     {
-        KAVLNODE *pNewUs = KAVL_GET_POINTER(&pNode->mpList);
+        KRBNODE *pNewUs = KRB_GET_POINTER(&pNode->mpList);
 
         pNewUs->mHeight = pNode->mHeight;
 
-        if (pNode->mpLeft != KAVL_NULL)
-            KAVL_SET_POINTER(&pNewUs->mpLeft, KAVL_GET_POINTER(&pNode->mpLeft))
+        if (pNode->mpLeft != KRB_NULL)
+            KRB_SET_POINTER(&pNewUs->mpLeft, KRB_GET_POINTER(&pNode->mpLeft))
         else
-            pNewUs->mpLeft = KAVL_NULL;
+            pNewUs->mpLeft = KRB_NULL;
 
-        if (pNode->mpRight != KAVL_NULL)
-            KAVL_SET_POINTER(&pNewUs->mpRight, KAVL_GET_POINTER(&pNode->mpRight))
+        if (pNode->mpRight != KRB_NULL)
+            KRB_SET_POINTER(&pNewUs->mpRight, KRB_GET_POINTER(&pNode->mpRight))
         else
-            pNewUs->mpRight = KAVL_NULL;
+            pNewUs->mpRight = KRB_NULL;
 
         if (pParent)
         {
-            if (KAVL_GET_POINTER_NULL(&pParent->mpLeft) == pNode)
-                KAVL_SET_POINTER(&pParent->mpLeft, pNewUs);
+            if (KRB_GET_POINTER_NULL(&pParent->mpLeft) == pNode)
+                KRB_SET_POINTER(&pParent->mpLeft, pNewUs);
             else
-                KAVL_SET_POINTER(&pParent->mpRight, pNewUs);
+                KRB_SET_POINTER(&pParent->mpRight, pNewUs);
         }
         else
-            KAVL_SET_POINTER(&pRoot->mpRoot, pNewUs);
+            KRB_SET_POINTER(&pRoot->mpRoot, pNewUs);
 
-        KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
-        KAVL_WRITE_UNLOCK(pRoot);
+        KRB_CACHE_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
+        KRB_WRITE_UNLOCK(pRoot);
     }
 
@@ -123 +123 @@
      * of wrong nodes but just uses this API for his convenience.
      */
-    KAVLNODE *pRemovedNode = KAVL_FN(Remove)(pRoot, pNode->mKey);
+    KRBNODE *pRemovedNode = KRB_FN(Remove)(pRoot, pNode->mKey);
     if (pRemovedNode == pNode)
         return pRemovedNode;
 
-    KAVL_FN(Insert)(pRoot, pRemovedNode);
+    KRB_FN(Insert)(pRoot, pRemovedNode);
     return NULL;
 #endif

trunk/include/k/kRbTmpl/kRbRemoveBestFit.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Templated AVL Trees, Remove Best Fitting Node.
+ * kRbTmpl - Templated Red-Black Trees, Remove Best Fitting Node.
  */
 
@@ -33 +33 @@
  *
  * @returns Pointer to the removed node.
- * @param   pRoot       Pointer to the AVL-tree root structure.
+ * @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.
@@ -42 +42 @@
  *          code size, and the likelyhood for bugs.
  */
-KAVL_DECL(KAVLNODE *) KAVL_FN(RemoveBestFit)(KAVLROOT *pRoot, KAVLKEY Key, KBOOL fAbove)
+KRB_DECL(KRBNODE *) KRB_FN(RemoveBestFit)(KRBROOT *pRoot, KRBKEY Key, KBOOL fAbove)
 {
     /*
@@ -49 +49 @@
      * removing the in-tree node as this is way cheaper.
      */
-    KAVLNODE *pNode = KAVL_FN(GetBestFit)(pRoot, Key, fAbove);
+    KRBNODE *pNode = KRB_FN(GetBestFit)(pRoot, Key, fAbove);
     if (pNode != NULL)
     {
-#ifdef KAVL_EQUAL_ALLOWED
-        KAVL_WRITE_LOCK(pRoot); /** @todo the locking isn't quite sane here. :-/ */
-        if (pNode->mpList != KAVL_NULL)
+#ifdef KRB_EQUAL_ALLOWED
+        KRB_WRITE_LOCK(pRoot); /** @todo the locking isn't quite sane here. :-/ */
+        if (pNode->mpList != KRB_NULL)
         {
-            KAVLNODE *pRet = KAVL_GET_POINTER(&pNode->mpList);
-            KAVL_SET_POINTER_NULL(&pNode->mpList, &pRet->mpList);
-            KAVL_LOOKTHRU_INVALIDATE_NODE(pRoot, pNode, pNode->mKey);
-            KAVL_WRITE_UNLOCK(pRoot);
+            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;
         }
-        KAVL_WRITE_UNLOCK(pRoot);
+        KRB_WRITE_UNLOCK(pRoot);
 #endif
-        pNode = KAVL_FN(Remove)(pRoot, pNode->mKey);
+        pNode = KRB_FN(Remove)(pRoot, pNode->mKey);
     }
     return pNode;

trunk/include/k/kRbTmpl/kRbUndef.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvlTmpl - Undefines All Macros (both config and temp).
+ * kRbTmpl - Undefines All Macros (both config and temp).
  */
 
 /*
- * Copyright (c) 2006-2007 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ * Copyright (c) 2006-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
  *
  * Permission is hereby granted, free of charge, to any person
@@ -32 +32 @@
  * 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 KAVL_LOOKTHRU
-#undef KAVL_LOOKTHRU_HASH
-#undef KAVL_LOCKED
-#undef KAVL_WRITE_LOCK
-#undef KAVL_WRITE_UNLOCK
-#undef KAVL_READ_LOCK
-#undef KAVL_READ_UNLOCK
-#undef KAVLKEY
-#undef KAVLNODE
-#undef KAVLTREEPTR
-#undef KAVLROOT
-#undef KAVL_FN
-#undef KAVL_TYPE
-#undef KAVL_INT
-#undef KAVL_DECL
+#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 mHeight
+#undef mfIsRed
 #undef mpLeft
 #undef mpRight
@@ -61 +61 @@
 #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
 
 /*
- * The internal macros.
+ * Internal ones.
  */
-#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
+#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
 

trunk/include/k/kRbU32.h

@@ -1 +1 @@
 /* $Id$ */
 /** @file
- * kAvl - AVL Tree Implementation, KU32 keys.
+ * kRb - Red-Black Tree Implementation, KU32 keys.
  */
 
 /*
- * Copyright (c) 2006-2007 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
+ * Copyright (c) 2006-2009 Knut St. Osmundsen <bird-kStuff-spamix@anduin.net>
  *
  * Permission is hereby granted, free of charge, to any person
@@ -29 +29 @@
  */
 
-#ifndef ___k_kAvlU32_h___
-#define ___k_kAvlU32_h___
+#ifndef ___k_kRbU32_h___
+#define ___k_kRbU32_h___
 
-typedef struct KAVLU32
+typedef struct KRBU32
 {
     KU32                mKey;
-    KU8                 mHeight;
-    struct KAVLU32     *mpLeft;
-    struct KAVLU32     *mpRight;
-} KAVLU32, *PKAVLU32, **PPKAVLU32;
+    KBOOL               mfRed;
+    struct KRBU32      *mpLeft;
+    struct KRBU32      *mpRight;
+} KRBU32;
+typedef KRBU32  *PRBU32;
+typedef KRBU32 **PPRBU32;
 
-/*#define KAVL_EQUAL_ALLOWED*/
-#define KAVL_CHECK_FOR_EQUAL_INSERT
-#define KAVL_MAX_STACK          32
-/*#define KAVL_RANGE */
-/*#define KAVL_OFFSET */
-#define KAVL_STD_KEY_COMP
-#define KAVLKEY                 KU32
-#define KAVLNODE            KAVLU32
-#define KAVL_FN(name)           kAvlU32 ## name
-#define KAVL_TYPE(prefix,name)  prefix ## KAVLU32 ## name
-#define KAVL_INT(name)          KAVLU32INT ## name
-#define KAVL_DECL(rettype)      K_DECL_INLINE(rettype)
+/*#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/kAvlTmpl/kAvlBase.h>
-#include <k/kAvlTmpl/kAvlDoWithAll.h>
-#include <k/kAvlTmpl/kAvlEnum.h>
-#include <k/kAvlTmpl/kAvlGet.h>
-#include <k/kAvlTmpl/kAvlGetBestFit.h>
-#include <k/kAvlTmpl/kAvlGetWithParent.h>
-#include <k/kAvlTmpl/kAvlRemove2.h>
-#include <k/kAvlTmpl/kAvlRemoveBestFit.h>
-#include <k/kAvlTmpl/kAvlUndef.h>
+#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