Changeset 3168 for trunk/src/win32k/misc/avl.c

Timestamp:

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

Author:

bird

Message:

Synced with \tools\fastdep\avl.*

File:

• trunk/src/win32k/misc/avl.c (modified) (14 diffs)

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;