Changeset 35 for trunk/include/k/kRbU32.h

Timestamp:

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

Author:

bird

Message:

Templated red-black trees - kick off.

File:

• trunk/include/k/kRbU32.h (copied) (copied from trunk/include/k/kAvlU32.h ) (2 diffs)

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