Changeset 3168 for trunk/src

Timestamp:

Mar 19, 2000, 5:00:11 PM (25 years ago)

Author:

bird

Message:

Synced with \tools\fastdep\avl.*

Location:

trunk/src/win32k

Files:

• include/avl.h (modified) (5 diffs)
• misc/avl.c (modified) (14 diffs)

trunk/src/win32k/include/avl.h

@@ -1 @@
-/* $Id: avl.h,v 1.2 2000-01-22 18:20:59 bird Exp $
+/* $Id: avl.h,v 1.3 2000-03-19 16:00:10 bird Exp $
  *
  * AVL-Tree (lookalike) declaration.
  *
- * Copyright (c) 1999 knut st. osmundsen
+ * This AVL implementation is configurable from this headerfile. By
+ * for example alterning the AVLKEY typedefinition an the AVL_<L|G|E|N>[E]
+ * macros you are able to create different trees. Currently you may only have
+ * one type of trees within one program (module).
+ *
+ * TREETYPE: unsigned long key.
+ *
+ *
+ * Copyright (c) 1999-2000 knut st. osmundsen
  *
  * Project Odin Software License can be found in LICENSE.TXT
@@ -18 +26 @@
  * AVL configuration. PRIVATE!
  */
-#define AVL_MAX_HEIGHT      19          /* Up to 2^16 nodes. */
+#define AVL_MAX_HEIGHT              19          /* Up to 2^16 nodes. */
+#undef AVL_MAY_TRY_INSERT_EQUAL                 /* No duplicate key! */
+
+
+/*
+ * AVL Compare macros
+ */
+#define AVL_L(key1, key2)  ((key1) <  (key2))
+#define AVL_LE(key1, key2) ((key1) <= (key2))
+#define AVL_G(key1, key2)  ((key1) >  (key2))
+#define AVL_GE(key1, key2) ((key1) >= (key2))
+#define AVL_E(key1, key2)  ((key1) == (key2))
+#define AVL_NE(key1, key2) ((key1) != (key2))
+
 
 /**
@@ -24 +45 @@
  */
 typedef unsigned long AVLKEY;
+
 
 /**
@@ -35 +57 @@
     unsigned char           uchHeight; /* Height of this tree: max(heigth(left), heigth(right)) + 1 */
 } AVLNODECORE, *PAVLNODECORE, **PPAVLNODECORE;
+
 
 /**
@@ -55 +78 @@
 
 
-void            AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode);
+BOOL            AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode);
 PAVLNODECORE    AVLRemove(PPAVLNODECORE ppTree, AVLKEY Key);
 PAVLNODECORE    AVLGet(PPAVLNODECORE ppTree, AVLKEY Key);

trunk/src/win32k/misc/avl.c

@@ -1 @@
-/* $Id: avl.c,v 1.3 2000-01-24 01:45:19 bird Exp $
+/* $Id: avl.c,v 1.4 2000-03-19 16:00:11 bird Exp $
  *
  * AVL-Tree (lookalike) implementation.
@@ -25 +25 @@
 #include <os2.h>
 #include "avl.h"
-#include "dev32.h"
+#if defined(RING0) || defined(RING3)
+    #include "dev32.h"
+#else
+    #define SSToDS(a) (a)
+#endif
+#include "string.h"
 
 #include <builtin.h>
@@ -58 +63 @@
 /**
  * Inserts a node into the AVL-tree.
+ * @returns   TRUE if inserted.
+ *            FALSE if node exists in tree.
  * @param     ppTree  Pointer to the AVL-tree root node pointer.
  * @param     pNode   Pointer to the node which is to be added.
@@ -74 +81 @@
  * @author    knut st. osmundsen
  */
-void AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode)
+BOOL AVLInsert(PPAVLNODECORE ppTree, PAVLNODECORE pNode)
 {
     AVLSTACK                AVLStack;
@@ -87 +94 @@
         assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
         AVLStack.aEntries[AVLStack.cEntries++] = ppCurNode;
-        if (pCurNode->Key > Key)
+        if (AVL_G(pCurNode->Key, Key))
             ppCurNode = &pCurNode->pLeft;
         else
@@ -93 +100 @@
     }
 
+#ifdef AVL_MAY_TRY_INSERT_EQUAL
+    /* check if equal */
+    if (AVLStack.cEntries > 0 && AVL_E((*AVLStack.aEntries[AVLStack.cEntries-1])->Key, pNode->Key))
+        return FALSE;
+#endif
+
     pNode->pLeft = pNode->pRight = NULL;
     pNode->uchHeight = 1;
@@ -98 +111 @@
 
     AVLRebalance(SSToDS(&AVLStack));
+    return TRUE;
 }
 
@@ -154 +168 @@
         assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
         AVLStack.aEntries[AVLStack.cEntries++] = ppDeleteNode;
-        if (pDeleteNode->Key == Key)
+        if (AVL_E(pDeleteNode->Key, Key))
             break;
 
-        if (pDeleteNode->Key > Key)
+        if (AVL_G(pDeleteNode->Key, Key))
             ppDeleteNode = &pDeleteNode->pLeft;
         else
@@ -215 +229 @@
     register PAVLNODECORE  pNode = *ppTree;
 
-    while (pNode != NULL && pNode->Key != Key)
-    {
-        if (pNode->Key > Key)
+    while (pNode != NULL && AVL_NE(pNode->Key, Key))
+    {
+        if (AVL_G(pNode->Key, Key))
             pNode = pNode->pLeft;
         else
@@ -244 +258 @@
     register PAVLNODECORE  pParent = NULL;
 
-    while (pNode != NULL && pNode->Key != Key)
+    while (pNode != NULL && AVL_NE(pNode->Key, Key))
     {
         pParent = pNode;
-        if (pNode->Key > Key)
+        if (AVL_G(pNode->Key, Key))
             pNode = pNode->pLeft;
         else
@@ -285 +299 @@
     AVLStack.cEntries = 0;
 
-    while ((pNode = *ppNode) != NULL && pNode->Key != Key)
+    while ((pNode = *ppNode) != NULL && AVL_NE(pNode->Key, Key))
     {
         assert(AVLStack.cEntries < AVL_MAX_HEIGHT);
         AVLStack.aEntries[AVLStack.cEntries++] = ppNode;
-        if (pNode->Key > Key)
+        if (AVL_G(pNode->Key, Key))
             ppNode = &pNode->pLeft;
         else
@@ -317 +331 @@
         {
             pCurNode = *AVLStack.aEntries[AVLStack.cEntries];
-            if (pCurNode->Key < Key && (*ppLeft == NULL || pCurNode->Key > (*ppLeft)->Key))
+            if (AVL_L(pCurNode->Key, Key) && (*ppLeft == NULL || AVL_G(pCurNode->Key, (*ppLeft)->Key)))
                 *ppLeft = pCurNode;
-            else if (pCurNode->Key > Key && (*ppRight == NULL || pCurNode->Key < (*ppRight)->Key))
+            else if (AVL_G(pCurNode->Key, Key) && (*ppRight == NULL || AVL_L(pCurNode->Key, (*ppRight)->Key)))
                 *ppRight = pCurNode;
         }
@@ -556 +570 @@
     if (fAbove)
     {   /* pNode->Key >= Key */
-        while (pNode != NULL && pNode->Key != Key)
-        {
-            if (pNode->Key > Key)
+        while (pNode != NULL && AVL_NE(pNode->Key, Key))
+        {
+            if (AVL_G(pNode->Key, Key))
             {
                 pNodeLast = pNode;
@@ -569 +583 @@
     else
     {   /* pNode->Key <= Key */
-        while (pNode != NULL && pNode->Key != Key)
-        {
-            if (pNode->Key < Key)
+        while (pNode != NULL && AVL_NE(pNode->Key, Key))
+        {
+            if (AVL_L(pNode->Key, Key))
             {
                 pNodeLast = pNode;