Added a binary tree implementation
authorCasper Hornstrup <chorns@users.sourceforge.net>
Fri, 22 Mar 2002 20:58:23 +0000 (20:58 +0000)
committerCasper Hornstrup <chorns@users.sourceforge.net>
Fri, 22 Mar 2002 20:58:23 +0000 (20:58 +0000)
Added a splay tree implementation
Added a hash table implementation

svn path=/trunk/; revision=2766

reactos/include/ddk/exfuncs.h
reactos/include/ddk/extypes.h
reactos/ntoskrnl/Makefile
reactos/ntoskrnl/ex/btree.c [new file with mode: 0644]
reactos/ntoskrnl/ex/hashtab.c [new file with mode: 0644]
reactos/ntoskrnl/ex/stree.c [new file with mode: 0644]
reactos/ntoskrnl/ntoskrnl.def
reactos/ntoskrnl/ntoskrnl.edf

index 00ab81b..348780c 100644 (file)
@@ -820,4 +820,83 @@ ExHookException (
        unsigned int    exp
        );
 
+/* BEGIN REACTOS ONLY */
+
+BOOLEAN STDCALL
+ExInitializeBinaryTree(IN PBINARY_TREE  Tree,
+  IN PKEY_COMPARATOR  Compare);
+
+VOID STDCALL
+ExDeleteBinaryTree(IN PBINARY_TREE  Tree);
+
+VOID STDCALL
+ExInsertBinaryTree(IN PBINARY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  Value);
+
+BOOLEAN STDCALL
+ExSearchBinaryTree(IN PBINARY_TREE  Tree,
+  IN PVOID  Key,
+  OUT PVOID  * Value);
+
+BOOLEAN STDCALL
+ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  * Value);
+
+BOOLEAN STDCALL
+ExInitializeSplayTree(IN PSPLAY_TREE  Tree,
+  IN PKEY_COMPARATOR  Compare,
+  IN BOOLEAN  Weighted);
+
+VOID STDCALL
+ExDeleteSplayTree(IN PSPLAY_TREE  Tree);
+
+VOID STDCALL
+ExInsertSplayTree(IN PSPLAY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  Value);
+
+BOOLEAN STDCALL
+ExSearchSplayTree(IN PSPLAY_TREE  Tree,
+  IN PVOID  Key,
+  OUT PVOID  * Value);
+
+BOOLEAN STDCALL
+ExRemoveSplayTree(IN PSPLAY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  * Value);
+
+BOOLEAN STDCALL
+ExWeightOfSplayTree(IN PSPLAY_TREE  Tree,
+  OUT PULONG  Weight);
+
+BOOLEAN STDCALL
+ExInitializeHashTable(IN PHASH_TABLE  HashTable,
+  IN ULONG  HashTableSize,
+  IN PKEY_COMPARATOR  Compare  OPTIONAL);
+
+VOID STDCALL
+ExDeleteHashTable(IN PHASH_TABLE  HashTable);
+
+VOID STDCALL
+ExInsertHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  IN PVOID  Value);
+
+BOOLEAN STDCALL
+ExSearchHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  OUT PVOID  * Value);
+
+BOOLEAN STDCALL
+ExRemoveHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  IN PVOID  * Value);
+
+/* END REACTOS ONLY */
+
 #endif /* ndef _NTOS_EXFUNCS_H */
index 778e107..2cf8e69 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: extypes.h,v 1.6 2001/08/30 23:50:53 ekohl Exp $ */
+/* $Id: extypes.h,v 1.7 2002/03/22 20:58:23 chorns Exp $ */
 
 #ifndef __INCLUDE_DDK_EXTYPES_H
 #define __INCLUDE_DDK_EXTYPES_H
@@ -158,6 +158,49 @@ typedef VOID STDCALL
                      PVOID Argument1,
                      PVOID Argument2);
 
+/* BEGIN REACTOS ONLY */
+
+typedef LONG STDCALL (*PKEY_COMPARATOR)(PVOID  Key1,
+  PVOID  Key2);
+
+struct _BINARY_TREE_NODE;
+
+typedef struct _BINARY_TREE
+{
+  struct _BINARY_TREE_NODE  * RootNode;
+  PKEY_COMPARATOR  Compare;
+  PAGED_LOOKASIDE_LIST  LookasideList;
+  FAST_MUTEX  Lock;
+} BINARY_TREE, *PBINARY_TREE;
+
+
+struct _SPLAY_TREE_NODE;
+
+typedef struct _SPLAY_TREE
+{
+  struct _SPLAY_TREE_NODE  * RootNode;
+  PKEY_COMPARATOR  Compare;
+  BOOLEAN  Weighted;
+  PAGED_LOOKASIDE_LIST  LookasideList;
+  FAST_MUTEX  Lock;
+  PVOID  Reserved[4];
+} SPLAY_TREE, *PSPLAY_TREE;
+
+
+typedef struct _HASH_TABLE
+{
+  // Lock for this structure
+  FAST_MUTEX  Lock;
+
+  // Size of hash table in number of bits
+  ULONG  HashTableSize;
+
+  // Pointer to array of hash buckets with splay trees
+  PSPLAY_TREE  HashTrees;
+} HASH_TABLE, *PHASH_TABLE;
+
+/* END REACTOS ONLY */
+
 #endif /* __INCLUDE_DDK_EXTYPES_H */
 
 /* EOF */
index 1a82184..58646bf 100644 (file)
@@ -1,4 +1,4 @@
-# $Id: Makefile,v 1.66 2002/03/13 23:37:25 chorns Exp $
+# $Id: Makefile,v 1.67 2002/03/22 20:58:23 chorns Exp $
 #
 # ReactOS Operating System
 #
@@ -223,8 +223,10 @@ OBJECTS_PS = \
 
 # Executive Subsystem (Ex)
 OBJECTS_EX = \
+  ex/btree.o \
        ex/callback.o \
        ex/fmutex.o \
+  ex/hashtab.o \
        ex/init.o \
        ex/interlck.o \
        ex/list.o \
@@ -233,6 +235,7 @@ OBJECTS_EX = \
        ex/power.o \
        ex/resource.o \
        ex/time.o \
+  ex/stree.o \
        ex/sysinfo.o \
        ex/win32k.o \
        ex/work.o \
diff --git a/reactos/ntoskrnl/ex/btree.c b/reactos/ntoskrnl/ex/btree.c
new file mode 100644 (file)
index 0000000..7936f00
--- /dev/null
@@ -0,0 +1,430 @@
+/*
+ *  ReactOS kernel
+ *  Copyright (C) 1998-2002 ReactOS Team
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+/*
+ * PROJECT:         ReactOS kernel
+ * FILE:            btree.c
+ * PURPOSE:         Binary tree support
+ * PROGRAMMER:      Casper S. Hornstrup (chorns@users.sourceforge.net)
+ * UPDATE HISTORY:
+ *      15-03-2002  CSH  Created
+ */
+#include <ddk/ntddk.h>
+#include <internal/ex.h>
+
+#define NDEBUG
+#include <internal/debug.h>
+
+/* DATA **********************************************************************/
+
+typedef struct _BINARY_TREE_NODE
+{
+  struct _BINARY_TREE_NODE  * Parent;
+  struct _BINARY_TREE_NODE  * LeftChild;
+  struct _BINARY_TREE_NODE  * RightChild;
+  PVOID  Key;
+  PVOID  Value;
+} BINARY_TREE_NODE, *PBINARY_TREE_NODE;
+
+/* FUNCTIONS ****************************************************************/
+
+#define ExpBinaryTreeRootNode(Tree)(((PBINARY_TREE) (Tree))->RootNode)
+#define ExpIsExternalBinaryTreeNode(Node)(((Node)->LeftChild == NULL) && ((Node)->RightChild == NULL))
+#define ExpIsInternalBinaryTreeNode(Node)(!ExpIsExternalBinaryTreeNode(Node))
+#define ExpBinaryTreeNodeKey(Node)((Node)->Key)
+#define ExpBinaryTreeNodeValue(Node)((Node)->Value)
+#define ExpBinaryTreeParentNode(Node)((Node)->Parent)
+#define ExpBinaryTreeLeftChildNode(Node)((Node)->LeftChild)
+#define ExpBinaryTreeRightChildNode(Node)((Node)->RightChild)
+#define ExpBinaryTreeNodeEqual(Equality)((Equality) == 0)
+#define ExpBinaryTreeNodeLess(Equality)((Equality) < 0)
+#define ExpBinaryTreeNodeMore(Equality)((Equality) > 0)
+
+
+/*
+ * Allocate resources for a new node and initialize it.
+ */
+inline PBINARY_TREE_NODE
+ExpCreateBinaryTreeNode(PBINARY_TREE Tree,
+  PBINARY_TREE_NODE Parent,
+  PVOID Value)
+{
+  PBINARY_TREE_NODE Node;
+
+  Node = (PBINARY_TREE_NODE) ExAllocateFromPagedLookasideList(&Tree->LookasideList);
+
+  if (Node)
+               {
+           ExpBinaryTreeParentNode(Node)     = Parent;
+      ExpBinaryTreeLeftChildNode(Node)  = NULL;
+      ExpBinaryTreeRightChildNode(Node) = NULL;
+      ExpBinaryTreeNodeValue(Node)      = Value;
+               }
+
+  return Node;
+}
+
+
+/*
+ * Release resources for the node.
+ */
+inline VOID
+ExpDestroyBinaryTreeNode(PBINARY_TREE Tree,
+  PBINARY_TREE_NODE  Node)
+{
+  ExFreeToPagedLookasideList(&Tree->LookasideList, Node);
+}
+
+
+/*
+ * Replaces a child node of a node with a new node.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+inline VOID
+ExpBinaryTreeReplaceChildNode(PBINARY_TREE_NODE Child,
+  PBINARY_TREE_NODE NewChild)
+{
+  if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) == Child)
+    {
+      ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
+    }
+       else
+               {
+      ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Child)) = NewChild;
+               }
+}
+
+
+/*
+ * Returns the sibling node of a node.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+inline PBINARY_TREE_NODE
+ExpSiblingBinaryTreeNode(PBINARY_TREE Tree,
+  PBINARY_TREE_NODE Node)
+{
+  if (Node == ExpBinaryTreeRootNode(Tree))
+               {
+      return NULL;
+               }
+  else
+    {
+      if (ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node)) == Node)
+                   {          
+          return ExpBinaryTreeRightChildNode(ExpBinaryTreeParentNode(Node));
+        }
+                       else
+                         {
+               return ExpBinaryTreeLeftChildNode(ExpBinaryTreeParentNode(Node));
+        }
+               }
+}
+
+
+/*
+ * Expands an external node to an internal node.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+VOID
+ExpExpandExternalBinaryTreeNode(PBINARY_TREE Tree,
+  PBINARY_TREE_NODE Node)
+{
+  ExpBinaryTreeLeftChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
+
+  if (!ExpBinaryTreeLeftChildNode(Node))
+               {
+      /* FIXME: Throw exception */
+      DbgPrint("ExpCreateBinaryTreeNode() failed\n");
+               }
+
+  ExpBinaryTreeRightChildNode(Node) = ExpCreateBinaryTreeNode(Tree, Node, NULL);
+
+  if (!ExpBinaryTreeRightChildNode(Node))
+               {
+      ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeLeftChildNode(Node));
+      /* FIXME: Throw exception */
+      DbgPrint("ExpCreateBinaryTreeNode() failed\n");
+               }
+}
+
+
+/*
+ * Searches a tree for a node with the specified key. If a node with the
+ * specified key is not found, the external node where it should be is
+ * returned.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+inline PBINARY_TREE_NODE
+ExpSearchBinaryTree(PBINARY_TREE  Tree,
+  PVOID  Key,
+  PBINARY_TREE_NODE  Node)
+{
+  LONG Equality;
+
+  /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
+
+  if (ExpIsExternalBinaryTreeNode(Node))
+    {
+      return Node;
+    }
+
+  Equality = (*Tree->Compare)(Key, ExpBinaryTreeNodeKey(Node));
+
+  if (ExpBinaryTreeNodeEqual(Equality))
+    {
+      return Node;
+    }
+
+  if (ExpBinaryTreeNodeLess(Equality))
+    {
+      return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeLeftChildNode(Node));
+    }
+
+/*  if (ExpBinaryTreeNodeMore(Equality)) */
+    {
+      return ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRightChildNode(Node));
+    }
+}
+
+
+/*
+ * Removes an external node and it's parent node from the tree.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+VOID
+ExpRemoveAboveExternalBinaryTreeNode(PBINARY_TREE Tree,
+  PBINARY_TREE_NODE Node)
+{
+  assertmsg(ExpIsExternalBinaryTreeNode(Node), ("Node is not external"));
+
+  if (Node == ExpBinaryTreeRootNode(Tree))
+               {
+      return;
+               }
+  else
+               {
+      PBINARY_TREE_NODE GrandParent;
+           PBINARY_TREE_NODE NewChild;
+
+      GrandParent = ExpBinaryTreeParentNode(ExpBinaryTreeParentNode(Node));
+           NewChild = ExpSiblingBinaryTreeNode(Tree, Node);
+
+      if (GrandParent != NULL)
+        {
+          ExpBinaryTreeReplaceChildNode(ExpBinaryTreeParentNode(Node), NewChild);
+        }
+
+           ExpDestroyBinaryTreeNode(Tree, ExpBinaryTreeParentNode(Node));
+           ExpDestroyBinaryTreeNode(Tree, Node);
+               }
+}
+
+
+/*
+ * Release resources used by nodes of a binary (sub)tree.
+ */
+VOID
+ExpDeleteBinaryTree(PBINARY_TREE Tree,
+  PBINARY_TREE_NODE Node)
+{
+  /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
+
+  if (ExpIsInternalBinaryTreeNode(Node))
+    {
+      ExpDeleteBinaryTree(Tree, ExpBinaryTreeLeftChildNode(Node));
+      ExpDeleteBinaryTree(Tree, ExpBinaryTreeRightChildNode(Node));
+    }
+
+  ExpDestroyBinaryTreeNode(Tree, Node);
+}
+
+
+/*
+ * Default key compare function. Compares the integer values of the two keys.
+ */
+LONG STDCALL
+ExpBinaryTreeDefaultCompare(PVOID  Key1,
+  PVOID  Key2)
+{
+  if (Key1 == Key2)
+    return 0;
+
+  return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
+}
+
+
+/*
+ * Initializes a binary tree.
+ */
+BOOLEAN STDCALL
+ExInitializeBinaryTree(IN PBINARY_TREE  Tree,
+  IN PKEY_COMPARATOR  Compare)
+{
+  RtlZeroMemory(Tree, sizeof(BINARY_TREE));
+
+  Tree->Compare = (Compare == NULL)
+    ? ExpBinaryTreeDefaultCompare : Compare;
+
+  ExInitializePagedLookasideList(
+    &Tree->LookasideList,           /* Lookaside list */
+    NULL,                           /* Allocate routine */
+    NULL,                           /* Free routine */
+    0,                              /* Flags */
+    sizeof(BINARY_TREE_NODE),       /* Size of each entry */
+    TAG('E','X','B','T'),           /* Tag */
+    0);                             /* Depth */
+
+  ExInitializeFastMutex(&Tree->Lock);
+
+  ExpBinaryTreeRootNode(Tree) = ExpCreateBinaryTreeNode(Tree, NULL, NULL);
+
+  if (ExpBinaryTreeRootNode(Tree) == NULL)
+               {
+      ExDeletePagedLookasideList(&Tree->LookasideList);
+      return FALSE;
+               }
+  else
+               {
+      return TRUE;
+               }
+}
+
+
+/*
+ * Release resources used by a binary tree.
+ */
+VOID STDCALL
+ExDeleteBinaryTree(IN PBINARY_TREE  Tree)
+{
+  /* Remove all nodes */
+  ExpDeleteBinaryTree(Tree, ExpBinaryTreeRootNode(Tree));
+
+  ExDeletePagedLookasideList(&Tree->LookasideList);
+}
+
+
+/*
+ * Insert a value in a binary tree.
+ */
+VOID STDCALL
+ExInsertBinaryTree(IN PBINARY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  Value)
+{
+  PBINARY_TREE_NODE Node;
+
+  /* FIXME: Use SEH for error reporting */
+
+  ExAcquireFastMutex(&Tree->Lock);
+  Node = ExpBinaryTreeRootNode(Tree);
+  do
+    {
+      Node = ExpSearchBinaryTree(Tree, Key, Node);
+
+                 if (ExpIsExternalBinaryTreeNode(Node))
+                   {
+          break;
+                   }
+                       else
+                               {
+          Node = ExpBinaryTreeRightChildNode(Node);
+                               }
+    } while (TRUE);
+  ExpExpandExternalBinaryTreeNode(Tree, Node);
+  ExpBinaryTreeNodeKey(Node)   = Key;
+  ExpBinaryTreeNodeValue(Node) = Value;
+  ExReleaseFastMutex(&Tree->Lock);
+}
+
+
+/*
+ * Search for a value associated with a given key in a binary tree.
+ */
+BOOLEAN STDCALL
+ExSearchBinaryTree(IN PBINARY_TREE  Tree,
+  IN PVOID  Key,
+  OUT PVOID  * Value)
+{
+  PBINARY_TREE_NODE Node;
+
+  ExAcquireFastMutex(&Tree->Lock);
+  Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
+
+  if (ExpIsInternalBinaryTreeNode(Node))
+    {
+           *Value = ExpBinaryTreeNodeValue(Node);
+      ExReleaseFastMutex(&Tree->Lock);
+           return TRUE;
+         }
+       else
+               {
+      ExReleaseFastMutex(&Tree->Lock);
+      return FALSE;
+               }
+}
+
+
+/*
+ * Remove a value associated with a given key from a binary tree.
+ */
+BOOLEAN STDCALL
+ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  * Value)
+{
+  PBINARY_TREE_NODE Node;
+
+  ExAcquireFastMutex(&Tree->Lock);
+  Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
+
+  if (ExpIsExternalBinaryTreeNode(Node))
+               {
+      ExReleaseFastMutex(&Tree->Lock);
+      return FALSE;
+               }
+       else
+               {
+      *Value = ExpBinaryTreeNodeValue(Node);
+                 if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeLeftChildNode(Node)))
+                               {
+          Node = ExpBinaryTreeLeftChildNode(Node);
+                               }
+      else if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeRightChildNode(Node)))
+                               {
+          Node = ExpBinaryTreeRightChildNode(Node);
+                               }
+      else
+        {
+          // Node has internal children
+          PBINARY_TREE_NODE SwapNode;
+
+          SwapNode = Node;
+          Node = ExpBinaryTreeRightChildNode(SwapNode);
+          do
+            {
+              Node = ExpBinaryTreeLeftChildNode(Node);
+            } while (ExpIsInternalBinaryTreeNode(Node));
+        }
+
+      ExpRemoveAboveExternalBinaryTreeNode(Tree, Node);
+      ExReleaseFastMutex(&Tree->Lock);
+      return TRUE;
+               }
+}
+
+/* EOF */
diff --git a/reactos/ntoskrnl/ex/hashtab.c b/reactos/ntoskrnl/ex/hashtab.c
new file mode 100644 (file)
index 0000000..a6d1a7d
--- /dev/null
@@ -0,0 +1,270 @@
+/*
+ *  ReactOS kernel
+ *  Copyright (C) 1998-2002 ReactOS Team
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+/*
+ * PROJECT:         ReactOS kernel
+ * FILE:            hashtab.c
+ * PURPOSE:         Hash table support
+ * PROGRAMMER:      Casper S. Hornstrup (chorns@users.sourceforge.net)
+ * NOTES:           The hash function is from:
+ *                  Bob Jenkins <bob_jenkins@burtleburtle.net>
+ *                  http://burtleburtle.net/bob/hash/doobs.html
+ * UPDATE HISTORY:
+ *      15-03-2002  CSH  Created
+ */
+#include <ddk/ntddk.h>
+#include <internal/ex.h>
+
+#define NDEBUG
+#include <internal/debug.h>
+
+/* FUNCTIONS ****************************************************************/
+
+#define ExpHashTableSize(n) ((ULONG)1 << (n))
+#define ExpHashTableMask(n) (ExpHashTableSize(n) - 1)
+
+#define ExpHashMix(a, b, c) \
+{ \
+  a -= b; a -= c; a ^= (c >> 13); \
+  b -= c; b -= a; b ^= (a << 8);  \
+  c -= a; c -= b; c ^= (b >> 13); \
+  a -= b; a -= c; a ^= (c >> 12); \
+  b -= c; b -= a; b ^= (a << 16); \
+  c -= a; c -= b; c ^= (b >> 5);  \
+  a -= b; a -= c; a ^= (c >> 3);  \
+  b -= c; b -= a; b ^= (a << 10); \
+  c -= a; c -= b; c ^= (b >> 15); \
+}
+
+
+ULONG
+ExpHash(PUCHAR Key,
+  ULONG KeyLength)
+{
+  register ULONG a, b, c, len;
+
+       /* Set up the internal state */
+       len = KeyLength;
+       a = b = 0x9e3779b9;    /* The golden ratio; an arbitrary value */
+       c = 0;
+
+       /* Handle most of the key */
+       while (len >= 12)
+               {
+                 a += (Key[0] + ((ULONG)Key[1]<<8) + ((ULONG)Key[2]<<16) + ((ULONG)Key[3]<<24));
+                 b += (Key[4] + ((ULONG)Key[5]<<8) + ((ULONG)Key[6]<<16) + ((ULONG)Key[7]<<24));
+                 c += (Key[8] + ((ULONG)Key[9]<<8) + ((ULONG)Key[10]<<16)+ ((ULONG)Key[11]<<24));
+                 ExpHashMix(a, b, c);
+                 Key += 12; len -= 12;
+               }
+
+       /* Handle the last 11 bytes */
+       c += KeyLength;
+       switch(len)       /* All the case statements fall through */
+               {
+                       case 11: c += ((ULONG)Key[10] << 24);
+                       case 10: c += ((ULONG)Key[9] << 16);
+                       case 9 : c += ((ULONG)Key[8] << 8);
+                         /* The first byte of c is reserved for the length */
+                       case 8 : b += ((ULONG)Key[7] << 24);
+                       case 7 : b += ((ULONG)Key[6] << 16);
+                       case 6 : b += ((ULONG)Key[5] << 8);
+                       case 5 : b += Key[4];
+                       case 4 : a += ((ULONG)Key[3] << 24);
+                       case 3 : a += ((ULONG)Key[2] << 16);
+                       case 2 : a += ((ULONG)Key[1] << 8);
+                       case 1 : a += Key[0];
+                       /* case 0: nothing left to add */
+               }
+
+       ExpHashMix(a, b, c);
+
+       return c;
+}
+
+
+/*
+ * Insert a value in a hash table.
+ */
+inline VOID STDCALL
+ExpInsertHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  IN PVOID  Value)
+{
+  ULONG Index;
+
+  Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
+
+  ExInsertSplayTree(&HashTable->HashTrees[Index], Key, Value);
+}
+
+
+/*
+ * Search for a value associated with a given key in a hash table.
+ */
+inline BOOLEAN STDCALL
+ExpSearchHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  OUT PVOID  * Value)
+{
+  ULONG Index;
+
+  Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
+
+  return ExSearchSplayTree(&HashTable->HashTrees[Index], Key, Value);
+}
+
+
+/*
+ * Remove a value associated with a given key from a hash table.
+ */
+BOOLEAN STDCALL
+ExpRemoveHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  IN PVOID  * Value)
+{
+  ULONG Index;
+
+  Index = (ExpHash(Key, KeyLength) & ExpHashTableMask(HashTable->HashTableSize));
+
+  return ExRemoveSplayTree(&HashTable->HashTrees[Index], Key, Value);
+}
+
+
+/*
+ * Initializes a hash table.
+ */
+BOOLEAN STDCALL
+ExInitializeHashTable(IN PHASH_TABLE  HashTable,
+  IN ULONG  HashTableSize,
+  IN PKEY_COMPARATOR  Compare  OPTIONAL)
+{
+  BOOLEAN Status;
+  LONG Index;
+
+  RtlZeroMemory(HashTable, sizeof(HASH_TABLE));
+
+  HashTable->HashTableSize = HashTableSize;
+
+  ExInitializeFastMutex(&HashTable->Lock);
+
+  HashTable->HashTrees = ExAllocatePool(PagedPool, ExpHashTableSize(HashTableSize) * sizeof(SPLAY_TREE));
+
+  if (HashTable->HashTrees == NULL)
+               {
+      return FALSE;
+               }
+
+  for (Index = 0; Index < ExpHashTableSize(HashTableSize); Index++)
+    {
+      Status = ExInitializeSplayTree(&HashTable->HashTrees[Index], Compare, FALSE);
+
+      if (!Status)
+                               {
+          LONG i;
+
+          for (i = Index - 1; i >= 0; i--)
+                                               {
+              ExDeleteSplayTree(&HashTable->HashTrees[i]);
+                                               }
+
+          ExFreePool(HashTable->HashTrees);
+
+          return FALSE;
+                               }
+    }
+
+  return TRUE;
+}
+
+
+/*
+ * Release resources used by a hash table.
+ */
+VOID STDCALL
+ExDeleteHashTable(IN PHASH_TABLE  HashTable)
+{
+  ULONG Index;
+
+  for (Index = 0; Index < ExpHashTableSize(HashTable->HashTableSize); Index++)
+               {
+      ExDeleteSplayTree(&HashTable->HashTrees[Index]);
+               }
+
+  ExFreePool(HashTable->HashTrees);
+}
+
+
+/*
+ * Insert a value in a hash table.
+ */
+VOID STDCALL
+ExInsertHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  IN PVOID  Value)
+{
+  /* FIXME: Use SEH for error reporting */
+
+  ExAcquireFastMutex(&HashTable->Lock);
+  ExpInsertHashTable(HashTable, Key, KeyLength, Value);
+  ExReleaseFastMutex(&HashTable->Lock);
+}
+
+
+/*
+ * Search for a value associated with a given key in a hash table.
+ */
+BOOLEAN STDCALL
+ExSearchHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  OUT PVOID  * Value)
+{
+  BOOLEAN Status;
+
+  ExAcquireFastMutex(&HashTable->Lock);
+  Status = ExpSearchHashTable(HashTable, Key, KeyLength, Value);
+  ExReleaseFastMutex(&HashTable->Lock);
+
+  return Status;
+}
+
+
+/*
+ * Remove a value associated with a given key from a hash table.
+ */
+BOOLEAN STDCALL
+ExRemoveHashTable(IN PHASH_TABLE  HashTable,
+  IN PVOID  Key,
+  IN ULONG  KeyLength,
+  IN PVOID  * Value)
+{
+  BOOLEAN Status;
+
+  ExAcquireFastMutex(&HashTable->Lock);
+  Status = ExpRemoveHashTable(HashTable, Key, KeyLength, Value);
+  ExReleaseFastMutex(&HashTable->Lock);
+
+  return Status;
+}
+
+/* EOF */
diff --git a/reactos/ntoskrnl/ex/stree.c b/reactos/ntoskrnl/ex/stree.c
new file mode 100644 (file)
index 0000000..b592546
--- /dev/null
@@ -0,0 +1,1081 @@
+/*
+ *  ReactOS kernel
+ *  Copyright (C) 1998-2002 ReactOS Team
+ *
+ *  This program is free software; you can redistribute it and/or modify
+ *  it under the terms of the GNU General Public License as published by
+ *  the Free Software Foundation; either version 2 of the License, or
+ *  (at your option) any later version.
+ *
+ *  This program is distributed in the hope that it will be useful,
+ *  but WITHOUT ANY WARRANTY; without even the implied warranty of
+ *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ *  GNU General Public License for more details.
+ *
+ *  You should have received a copy of the GNU General Public License
+ *  along with this program; if not, write to the Free Software
+ *  Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+/*
+ * PROJECT:         ReactOS kernel
+ * FILE:            stree.c
+ * PURPOSE:         Splay tree support
+ * PROGRAMMER:      Casper S. Hornstrup (chorns@users.sourceforge.net)
+ * NOTES:           Based on a splay tree implementation by
+ *                  Daniel Stenberg <Daniel.Stenberg@sth.frontec.se>
+ *                  http://www.contactor.se/~dast/stuff/dsplay-1.2.tar.gz
+ * UPDATE HISTORY:
+ *      15-03-2002  CSH  Created
+ */
+#include <ddk/ntddk.h>
+#include <internal/ex.h>
+
+#define NDEBUG
+#include <internal/debug.h>
+
+/* DATA **********************************************************************/
+
+#define WEIGHT 1
+#undef UNIQUE_KEYS
+
+typedef struct _SPLAY_TREE_NODE
+{
+  /* Children on this branch has smaller keys than this node */
+  struct _SPLAY_TREE_NODE  * SmallerChild;
+
+  /* Children on this branch has larger keys than this node */
+  struct _SPLAY_TREE_NODE  * LargerChild;
+
+  /* Points to a node with identical key */
+  struct _SPLAY_TREE_NODE  * Same;
+
+  /* Key of this node */
+  PVOID  Key;
+
+  /* Value of this node */
+  PVOID  Value;
+
+  /* The number of nodes rooted here */
+  LONG  Weight;
+} SPLAY_TREE_NODE, *PSPLAY_TREE_NODE;
+
+#define SPLAY_INDEX 0
+#define SEARCH_INDEX 1
+#define INSERT_INDEX 2
+#define REMOVE_INDEX 3
+
+typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_SPLAY)(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node);
+
+typedef BOOLEAN (*PSPLAY_TREE_SEARCH)(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * ReturnNode);
+
+typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_INSERT)(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE New);
+
+typedef PSPLAY_TREE_NODE (*PSPLAY_TREE_REMOVE)(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * RemovedNode);
+
+/* FUNCTIONS ****************************************************************/
+
+#define ExpSplayTreeRootNode(Tree)(((PSPLAY_TREE) (Tree))->RootNode)
+#define ExpSplayTreeNodeKey(Node)((Node)->Key)
+#define ExpSplayTreeNodeValue(Node)((Node)->Value)
+#define ExpSplayTreeSmallerChildNode(Node)((Node)->SmallerChild)
+#define ExpSplayTreeLargerChildNode(Node)((Node)->LargerChild)
+#define ExpSplayTreeNodeEqual(Equality)((Equality) == 0)
+#define ExpSplayTreeNodeLess(Equality)((Equality) < 0)
+#define ExpSplayTreeNodeMore(Equality)((Equality) > 0)
+#define ExpSplayTreeNodeSame(Node)((Node)->Same)
+#define ExpSplayTreeNodeWeight(Node)((Node)->Weight)
+#define ExpSplayTreeNodeGetWeight(Node)(((Node) == NULL) ? 0 : ((Node)->Weight))
+#define ExpSplayTreeNodeSetWeight(Node, _Weight)((Node)->Weight = (_Weight))
+
+#define KEY_NOTUSED (PVOID)-1
+
+
+/*
+ * Allocate resources for a new node and initialize it.
+ */
+inline PSPLAY_TREE_NODE
+ExpCreateSplayTreeNode(PSPLAY_TREE Tree,
+  PVOID Value)
+{
+  PSPLAY_TREE_NODE Node;
+
+  Node = (PSPLAY_TREE_NODE) ExAllocateFromPagedLookasideList(&Tree->LookasideList);
+
+  if (Node)
+               {
+      ExpSplayTreeSmallerChildNode(Node) = NULL;
+      ExpSplayTreeLargerChildNode(Node)  = NULL;
+      ExpSplayTreeNodeValue(Node)        = Value;
+               }
+
+  return Node;
+}
+
+/*
+ * Release resources for the node.
+ */
+inline VOID
+ExpDestroySplayTreeNode(PSPLAY_TREE Tree,
+  PSPLAY_TREE_NODE Node)
+{
+  ExFreeToPagedLookasideList(&Tree->LookasideList, Node);
+}
+
+
+/*
+ * Splay using the key 'Key' (which may or may not be in the tree). The starting
+ * root is Node. Weight fields are maintained.
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine does not maintain weight information.
+ */
+PSPLAY_TREE_NODE
+ExpSplayTreeNoWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node)
+{
+  PSPLAY_TREE_NODE l;
+  PSPLAY_TREE_NODE r;
+  PSPLAY_TREE_NODE y;
+  LONG ChildEquality;
+  SPLAY_TREE_NODE N;
+  LONG Equality;
+
+  if (Node == NULL)
+    return Node;
+
+  ExpSplayTreeSmallerChildNode(&N) = NULL;
+  ExpSplayTreeLargerChildNode(&N)  = NULL;
+  l = &N;
+  r = &N;
+
+  for (;;)
+    {
+      Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+
+      if (ExpSplayTreeNodeLess(Equality))
+        {
+          if (ExpSplayTreeSmallerChildNode(Node) == NULL)
+                 break;
+
+          ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeSmallerChildNode(Node)));
+          if (ExpSplayTreeNodeLess(ChildEquality))
+            {
+              y = ExpSplayTreeSmallerChildNode(Node);     /* Rotate smaller */
+              ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(y);
+              ExpSplayTreeLargerChildNode(y) = Node;
+
+                               Node = y;
+                               if (ExpSplayTreeSmallerChildNode(Node) == NULL)
+                                 break;
+                       }
+               
+                     ExpSplayTreeSmallerChildNode(r) = Node;           /* Link smaller */
+                     r = Node;
+                     Node = ExpSplayTreeSmallerChildNode(Node);
+                   }
+                 else if (ExpSplayTreeNodeMore(Equality))
+                   {
+                     if (ExpSplayTreeLargerChildNode(Node) == NULL)
+                             break;
+               
+                     ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node)));
+                     if (ExpSplayTreeNodeMore(ChildEquality))
+                       {
+                               y = ExpSplayTreeLargerChildNode(Node);        /* Rotate larger */
+                               ExpSplayTreeLargerChildNode(Node) = ExpSplayTreeSmallerChildNode(y);
+                               ExpSplayTreeSmallerChildNode(y) = Node;
+               
+                               Node = y;
+                               if (ExpSplayTreeLargerChildNode(Node) == NULL)
+                                 break;
+                       }
+               
+                     ExpSplayTreeLargerChildNode(l) = Node;            /* Link larger */
+                     l = Node;
+                     Node = ExpSplayTreeLargerChildNode(Node);         
+                   }
+                 else
+                   {
+                     break;
+                   }
+    }
+
+  ExpSplayTreeLargerChildNode(l)  = NULL;
+  ExpSplayTreeSmallerChildNode(r) = NULL;
+
+  ExpSplayTreeLargerChildNode(l)     = ExpSplayTreeSmallerChildNode(Node);  /* Assemble */
+  ExpSplayTreeSmallerChildNode(r)    = ExpSplayTreeLargerChildNode(Node);
+  ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(&N);
+  ExpSplayTreeLargerChildNode(Node)  = ExpSplayTreeSmallerChildNode(&N);
+
+  return Node;
+}
+
+
+/*
+ * Splay using the key 'Key' (which may or may not be in the tree). The starting
+ * root is Node. Weight fields are maintained.
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine maintains weight information.
+ */
+PSPLAY_TREE_NODE
+ExpSplayTreeWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node)
+{
+  PSPLAY_TREE_NODE l;
+  PSPLAY_TREE_NODE r;
+  PSPLAY_TREE_NODE y;
+  LONG ChildEquality;
+  SPLAY_TREE_NODE N;
+  LONG Equality;
+#ifdef WEIGHT
+  LONG RootWeight;
+  LONG Weight1;
+  LONG Weight2;
+#endif
+
+  if (Node == NULL)
+    return Node;
+
+  ExpSplayTreeSmallerChildNode(&N) = NULL;
+  ExpSplayTreeLargerChildNode(&N)  = NULL;
+  l = &N;
+  r = &N;
+
+#ifdef WEIGHT
+  RootWeight = ExpSplayTreeNodeGetWeight(Node);
+  Weight1 = 0;
+  Weight2 = 0;
+#endif
+
+  for (;;)
+    {
+      Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+
+      if (ExpSplayTreeNodeLess(Equality))
+        {
+          if (ExpSplayTreeSmallerChildNode(Node) == NULL)
+                 break;
+
+          ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeSmallerChildNode(Node)));
+          if (ExpSplayTreeNodeLess(ChildEquality))
+            {
+              y = ExpSplayTreeSmallerChildNode(Node);     /* Rotate smaller */
+              ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(y);
+              ExpSplayTreeLargerChildNode(y) = Node;
+
+#ifdef WEIGHT
+              ExpSplayTreeNodeSetWeight(Node, ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node))
+                + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node)) + 1);
+#endif
+
+                               Node = y;
+                               if (ExpSplayTreeSmallerChildNode(Node) == NULL)
+                                 break;
+                       }
+               
+                     ExpSplayTreeSmallerChildNode(r) = Node;           /* Link smaller */
+                     r = Node;
+                     Node = ExpSplayTreeSmallerChildNode(Node);
+               
+#ifdef WEIGHT
+                     Weight2 += 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(r));
+#endif
+                   }
+                 else if (ExpSplayTreeNodeMore(Equality))
+                   {
+                     if (ExpSplayTreeLargerChildNode(Node) == NULL)
+                             break;
+               
+                     ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node)));
+                     if (ExpSplayTreeNodeMore(ChildEquality))
+                       {
+                               y = ExpSplayTreeLargerChildNode(Node);        /* Rotate larger */
+                               ExpSplayTreeLargerChildNode(Node) = ExpSplayTreeSmallerChildNode(y);
+                               ExpSplayTreeSmallerChildNode(y) = Node;
+               
+#ifdef WEIGHT
+                               ExpSplayTreeNodeSetWeight(Node, ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node))
+                           + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node)) + 1);
+#endif
+               
+                               Node = y;
+                               if (ExpSplayTreeLargerChildNode(Node) == NULL)
+                                 break;
+                       }
+               
+                     ExpSplayTreeLargerChildNode(l) = Node;            /* Link larger */
+                     l = Node;
+                     Node = ExpSplayTreeLargerChildNode(Node);
+               
+#ifdef WEIGHT
+                     Weight1 += 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(l));
+#endif
+               
+                   }
+                 else
+                   {
+                     break;
+                   }
+    }
+
+#ifdef WEIGHT
+  Weight1 += ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node)); /* Now Weight1 and Weight2 are the weights of */
+  Weight2 += ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node));  /* The 'smaller' and 'larger' trees we just built. */
+  ExpSplayTreeNodeSetWeight(Node, Weight1 + Weight2 + 1);
+#endif
+
+  ExpSplayTreeLargerChildNode(l)  = NULL;
+  ExpSplayTreeSmallerChildNode(r) = NULL;
+
+#ifdef WEIGHT
+  /* The following two loops correct the weight fields of the right path from
+   * the left child of the root and the right path from the left child of the
+   * root.
+   */
+  for (y = ExpSplayTreeLargerChildNode(&N); y != NULL; y = ExpSplayTreeLargerChildNode(y)) {
+    ExpSplayTreeNodeSetWeight(y, Weight1);
+    Weight1 -= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(y));
+  }
+  for (y = ExpSplayTreeSmallerChildNode(&N); y != NULL; y = ExpSplayTreeSmallerChildNode(y)) {
+    ExpSplayTreeNodeSetWeight(y, Weight2);
+    Weight2 -= 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(y));
+  }
+#endif
+
+  ExpSplayTreeLargerChildNode(l)     = ExpSplayTreeSmallerChildNode(Node);  /* Assemble */
+  ExpSplayTreeSmallerChildNode(r)    = ExpSplayTreeLargerChildNode(Node);
+  ExpSplayTreeSmallerChildNode(Node) = ExpSplayTreeLargerChildNode(&N);
+  ExpSplayTreeLargerChildNode(Node)  = ExpSplayTreeSmallerChildNode(&N);
+
+  return Node;
+}
+
+
+inline PSPLAY_TREE_NODE
+ExpSplayTree(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node)
+{
+  return (*((PSPLAY_TREE_SPLAY)Tree->Reserved[SPLAY_INDEX]))(Tree, Key, Node);
+}
+
+
+/*
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine does not maintain weight information.
+ */
+BOOLEAN
+ExpSearchSplayTreeNoWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * ReturnNode)
+{
+  LONG Equality;
+
+  if (Node == NULL)
+    return FALSE;
+
+  Node = ExpSplayTree(Tree, Key, Node);
+
+  Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+  if (ExpSplayTreeNodeEqual(Equality))
+    {
+      /* Found the key */
+
+      *ReturnNode = Node;
+                 return TRUE;
+         }
+       else
+         {
+           *ReturnNode = NULL;                 /* No match */
+           return FALSE;                       /* It wasn't there */
+         }
+}
+
+
+/*
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine maintains weight information.
+ */
+BOOLEAN
+ExpSearchSplayTreeWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * ReturnNode)
+{
+  PSPLAY_TREE_NODE x;
+  LONG Equality;
+#ifdef WEIGHT
+  LONG tweight;
+#endif
+
+  if (Node == NULL)
+    return FALSE;
+
+#ifdef WEIGHT
+  tweight = ExpSplayTreeNodeGetWeight(Node);
+#endif
+
+  Node = ExpSplayTree(Tree, Key, Node);
+
+  Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+  if (ExpSplayTreeNodeEqual(Equality))
+    {
+      /* Found the key */
+
+#ifdef WEIGHT
+                 if (x != NULL)
+                   {
+                     ExpSplayTreeNodeSetWeight(x, tweight - 1);
+                   }
+#endif
+
+      *ReturnNode = Node;
+                 return TRUE;
+         }
+       else
+         {
+           *ReturnNode = NULL;                 /* No match */
+           return FALSE;                       /* It wasn't there */
+         }
+}
+
+
+inline BOOLEAN
+ExpSearchSplayTree(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * ReturnNode)
+{
+  return (*((PSPLAY_TREE_SEARCH)Tree->Reserved[SEARCH_INDEX]))(Tree, Key, Node, ReturnNode);
+}
+
+
+/*
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine does not maintain weight information.
+ */
+PSPLAY_TREE_NODE
+ExpInsertSplayTreeNoWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE New)
+{
+  if (New == NULL)
+    return Node;
+
+  if (Node != NULL)
+    {
+      LONG Equality;
+
+      Node = ExpSplayTree(Tree, Key, Node);
+
+      Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+      if (ExpSplayTreeNodeEqual(Equality))
+        {
+
+#ifdef UNIQUE_KEYS
+
+      /* This is how to prevent the same node key getting added twice */
+      return NULL; 
+
+#else
+
+      /* It already exists one of this size */
+
+      ExpSplayTreeNodeSame(New) = Node;
+      ExpSplayTreeNodeKey(New) = Key;
+      ExpSplayTreeSmallerChildNode(New) = ExpSplayTreeSmallerChildNode(Node);
+      ExpSplayTreeLargerChildNode(New) = ExpSplayTreeLargerChildNode(Node);
+
+      ExpSplayTreeSmallerChildNode(Node) = New;
+      ExpSplayTreeNodeKey(Node) = KEY_NOTUSED;
+
+      /* New root node */
+      return New;
+
+#endif
+
+    }
+  }
+
+  if (Node == NULL)
+    {
+      ExpSplayTreeSmallerChildNode(New) = NULL;
+      ExpSplayTreeLargerChildNode(New)  = NULL;
+    }
+  else if (ExpSplayTreeNodeLess((*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node))))
+    {
+      ExpSplayTreeSmallerChildNode(New)  = ExpSplayTreeSmallerChildNode(Node);
+      ExpSplayTreeLargerChildNode(New)   = Node;
+      ExpSplayTreeSmallerChildNode(Node) = NULL;
+    }
+  else
+    {
+      ExpSplayTreeLargerChildNode(New)  = ExpSplayTreeLargerChildNode(Node);
+      ExpSplayTreeSmallerChildNode(New) = Node;
+      ExpSplayTreeLargerChildNode(Node) = NULL;
+    }
+
+  ExpSplayTreeNodeKey(New) = Key;
+
+#ifndef UNIQUE_KEYS
+  /* No identical nodes (yet) */
+  ExpSplayTreeNodeSame(New) = NULL;
+#endif
+
+  return New;
+}
+
+
+/*
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine maintains weight information.
+ */
+PSPLAY_TREE_NODE
+ExpInsertSplayTreeWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE New)
+{
+  if (New == NULL)
+    return Node;
+
+  if (Node != NULL)
+    {
+      LONG Equality;
+
+      Node = ExpSplayTree(Tree, Key, Node);
+
+      Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+      if (ExpSplayTreeNodeEqual(Equality))
+        {
+
+#ifdef UNIQUE_KEYS
+
+      /* This is how to prevent the same node key getting added twice */
+      return NULL; 
+
+#else
+
+      /* It already exists one of this size */
+
+      ExpSplayTreeNodeSame(New) = Node;
+      ExpSplayTreeNodeKey(New) = Key;
+      ExpSplayTreeSmallerChildNode(New) = ExpSplayTreeSmallerChildNode(Node);
+      ExpSplayTreeLargerChildNode(New) = ExpSplayTreeLargerChildNode(Node);
+
+#ifdef WEIGHT
+      ExpSplayTreeNodeSetWeight(New, ExpSplayTreeNodeGetWeight(Node));
+#endif
+
+      ExpSplayTreeSmallerChildNode(Node) = New;
+      ExpSplayTreeNodeKey(Node) = KEY_NOTUSED;
+
+      /* New root node */
+      return New;
+
+#endif
+
+    }
+  }
+
+  if (Node == NULL)
+    {
+      ExpSplayTreeSmallerChildNode(New) = NULL;
+      ExpSplayTreeLargerChildNode(New)  = NULL;
+    }
+  else if (ExpSplayTreeNodeLess((*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node))))
+    {
+      ExpSplayTreeSmallerChildNode(New)  = ExpSplayTreeSmallerChildNode(Node);
+      ExpSplayTreeLargerChildNode(New)   = Node;
+      ExpSplayTreeSmallerChildNode(Node) = NULL;
+
+#ifdef WEIGHT
+      ExpSplayTreeNodeSetWeight(Node, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node)));
+#endif
+
+    }
+  else
+    {
+      ExpSplayTreeLargerChildNode(New)  = ExpSplayTreeLargerChildNode(Node);
+      ExpSplayTreeSmallerChildNode(New) = Node;
+      ExpSplayTreeLargerChildNode(Node) = NULL;
+
+#ifdef WEIGHT
+      ExpSplayTreeNodeSetWeight(Node, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node)));
+#endif
+
+    }
+
+  ExpSplayTreeNodeKey(New) = Key;
+
+#ifdef WEIGHT
+  ExpSplayTreeNodeSetWeight(New, 1 + ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(New))
+    + ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(New)));
+#endif
+
+#ifndef UNIQUE_KEYS
+  /* No identical nodes (yet) */
+  ExpSplayTreeNodeSame(New) = NULL;
+#endif
+
+  return New;
+}
+
+
+inline PSPLAY_TREE_NODE
+ExpInsertSplayTree(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE New)
+{
+  return (*((PSPLAY_TREE_INSERT)Tree->Reserved[INSERT_INDEX]))(Tree, Key, Node, New);
+}
+
+
+/*
+ * Deletes the node with key 'Key' from the tree if it's there.
+ * Return a pointer to the resulting tree.
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine does not maintain weight information.
+ */
+PSPLAY_TREE_NODE
+ExpRemoveSplayTreeNoWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * RemovedNode)
+{
+  PSPLAY_TREE_NODE x;
+  LONG Equality;
+
+  if (Node == NULL)
+    return NULL;
+
+  Node = ExpSplayTree(Tree, Key, Node);
+
+  Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+  if (ExpSplayTreeNodeEqual(Equality))
+    {
+      /* Found the key */
+
+#ifndef UNIQUE_KEYS
+           /* FIRST! Check if there is a list with identical sizes */
+      x = ExpSplayTreeNodeSame(Node);
+           if (x)
+             {
+               /* There is several, pick one from the list */
+
+               /* 'x' is the new root node */
+
+               ExpSplayTreeNodeKey(x)          = ExpSplayTreeNodeKey(Node);
+               ExpSplayTreeLargerChildNode(x)  = ExpSplayTreeLargerChildNode(Node);
+               ExpSplayTreeSmallerChildNode(x) = ExpSplayTreeSmallerChildNode(Node);
+
+          *RemovedNode = Node;
+          return x;
+        }
+#endif
+
+                 if (ExpSplayTreeSmallerChildNode(Node) == NULL)
+                   {
+                     x = ExpSplayTreeLargerChildNode(Node);
+                   }
+                 else
+                   {
+                     x = ExpSplayTree(Tree, Key, ExpSplayTreeSmallerChildNode(Node));
+                     ExpSplayTreeLargerChildNode(x) = ExpSplayTreeLargerChildNode(Node);
+                   }
+                 *RemovedNode = Node;
+               
+                 return x;
+         }
+       else
+         {
+           *RemovedNode = NULL;                /* No match */
+           return Node;                        /* It wasn't there */
+         }
+}
+
+
+/*
+ * Deletes the node with key 'Key' from the tree if it's there.
+ * Return a pointer to the resulting tree.
+ * The lock for the tree must be acquired when this routine is called.
+ * This routine maintains weight information.
+ */
+PSPLAY_TREE_NODE
+ExpRemoveSplayTreeWeight(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * RemovedNode)
+{
+  PSPLAY_TREE_NODE x;
+  LONG Equality;
+
+#ifdef WEIGHT
+  LONG tweight;
+#endif
+
+  if (Node == NULL)
+    return NULL;
+
+#ifdef WEIGHT
+  tweight = ExpSplayTreeNodeGetWeight(Node);
+#endif
+
+  Node = ExpSplayTree(Tree, Key, Node);
+
+  Equality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(Node));
+  if (ExpSplayTreeNodeEqual(Equality))
+    {
+      /* Found the key */
+
+#ifndef UNIQUE_KEYS
+           /* FIRST! Check if there is a list with identical sizes */
+      x = ExpSplayTreeNodeSame(Node);
+           if (x)
+             {
+               /* There is several, pick one from the list */
+       
+               /* 'x' is the new root node */
+       
+               ExpSplayTreeNodeKey(x)          = ExpSplayTreeNodeKey(Node);
+               ExpSplayTreeLargerChildNode(x)  = ExpSplayTreeLargerChildNode(Node);
+               ExpSplayTreeSmallerChildNode(x) = ExpSplayTreeSmallerChildNode(Node);
+
+#ifdef WEIGHT
+          ExpSplayTreeNodeSetWeight(x, ExpSplayTreeNodeGetWeight(Node));
+#endif
+
+          *RemovedNode = Node;
+          return x;
+        }
+#endif
+
+                 if (ExpSplayTreeSmallerChildNode(Node) == NULL)
+                   {
+                     x = ExpSplayTreeLargerChildNode(Node);
+                   }
+                 else
+                   {
+                     x = ExpSplayTree(Tree, Key, ExpSplayTreeSmallerChildNode(Node));
+                     ExpSplayTreeLargerChildNode(x) = ExpSplayTreeLargerChildNode(Node);
+                   }
+                 *RemovedNode = Node;
+               
+#ifdef WEIGHT
+                 if (x != NULL)
+                   {
+                     ExpSplayTreeNodeSetWeight(x, tweight - 1);
+                   }
+#endif
+               
+                 return x;
+         }
+       else
+         {
+           *RemovedNode = NULL;                /* No match */
+           return Node;                        /* It wasn't there */
+         }
+}
+
+
+inline PSPLAY_TREE_NODE
+ExpRemoveSplayTree(PSPLAY_TREE Tree,
+  PVOID Key,
+  PSPLAY_TREE_NODE Node,
+  PSPLAY_TREE_NODE * RemovedNode)
+{
+  return (*((PSPLAY_TREE_REMOVE)Tree->Reserved[REMOVE_INDEX]))(Tree, Key, Node, RemovedNode);
+}
+
+
+/*
+ * The lock for the tree must be acquired when this routine is called.
+ */
+ULONG
+ExpPrintSplayTree(PSPLAY_TREE Tree,
+  PSPLAY_TREE_NODE Node,
+  ULONG Distance)
+{
+  PSPLAY_TREE_NODE n;
+  ULONG d = 0;
+  ULONG i;
+
+  if (Node == NULL)
+    return 0;
+
+  Distance += ExpPrintSplayTree(Tree, ExpSplayTreeLargerChildNode(Node), Distance + 1);
+
+  for (i = 0; i < Distance; i++)
+    {
+      DbgPrint("  ");
+    }
+
+  if (Tree->Weighted)
+    {
+      DbgPrint("%d(%d)[%d]", ExpSplayTreeNodeKey(Node), ExpSplayTreeNodeGetWeight(Node), i);
+    }
+  else
+   {
+     DbgPrint("%d[%d]", ExpSplayTreeNodeKey(Node), i);
+   }
+
+  for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
+    {
+      d += i;
+
+      DbgPrint(" [+]");
+    }
+
+  d += i;
+
+  d += ExpPrintSplayTree(Tree, ExpSplayTreeSmallerChildNode(Node), Distance + 1);
+
+  return d;
+}
+
+
+#define MAX_DIFF 4
+
+#ifdef WEIGHT
+
+/*
+ * The lock for the tree must be acquired when this routine is called.
+ * Returns the new root of the tree.
+ * Use of this routine could improve performance, or it might not.
+ * FIXME: Do some performance tests
+ */
+PSPLAY_TREE_NODE
+ExpSplayTreeMaxTreeWeight(PSPLAY_TREE Tree,
+  PSPLAY_TREE_NODE Node)
+{
+  PSPLAY_TREE_NODE First = Node;
+  LONG Diff;
+
+  do
+    {
+      Diff = ExpSplayTreeNodeGetWeight(ExpSplayTreeSmallerChildNode(Node))
+        - ExpSplayTreeNodeGetWeight(ExpSplayTreeLargerChildNode(Node));
+
+      if (Diff >= MAX_DIFF)
+        {
+          Node = ExpSplayTreeSmallerChildNode(Node);
+        }
+      else if (Diff <= -MAX_DIFF)
+        {
+          Node = ExpSplayTreeLargerChildNode(Node);
+        }
+      else
+        break;
+    } while (abs(Diff) >= MAX_DIFF);
+
+  if (Node != First)
+    return ExpSplayTree(Tree, ExpSplayTreeNodeKey(Node), First);
+  else
+    return First;
+}
+
+#endif
+
+
+/*
+ * Default key compare function. Compares the integer values of the two keys.
+ */
+LONG STDCALL
+ExpSplayTreeDefaultCompare(IN PVOID  Key1,
+  IN PVOID  Key2)
+{
+  if (Key1 == Key2)
+    return 0;
+
+  return (((LONG_PTR) Key1 < (LONG_PTR) Key2) ? -1 : 1);
+}
+
+
+/*
+ * Initializes a splay tree.
+ */
+BOOLEAN STDCALL
+ExInitializeSplayTree(IN PSPLAY_TREE  Tree,
+  IN PKEY_COMPARATOR  Compare,
+  IN BOOLEAN  Weighted)
+{
+  RtlZeroMemory(Tree, sizeof(SPLAY_TREE));
+
+  Tree->Compare = (Compare == NULL)
+    ? ExpSplayTreeDefaultCompare : Compare;
+
+  Tree->Weighted = Weighted;
+
+  if (Weighted)
+    {
+      Tree->Reserved[SPLAY_INDEX]  = (PVOID) ExpSplayTreeWeight;
+      Tree->Reserved[SEARCH_INDEX] = (PVOID) ExpSearchSplayTreeWeight;
+      Tree->Reserved[INSERT_INDEX] = (PVOID) ExpInsertSplayTreeWeight;
+      Tree->Reserved[REMOVE_INDEX] = (PVOID) ExpRemoveSplayTreeWeight;
+    }
+       else
+               {
+      Tree->Reserved[SPLAY_INDEX]  = (PVOID) ExpSplayTreeNoWeight;
+      Tree->Reserved[SEARCH_INDEX] = (PVOID) ExpSearchSplayTreeNoWeight;
+      Tree->Reserved[INSERT_INDEX] = (PVOID) ExpInsertSplayTreeNoWeight;
+      Tree->Reserved[REMOVE_INDEX] = (PVOID) ExpRemoveSplayTreeNoWeight;
+               }
+
+  ExInitializePagedLookasideList(
+    &Tree->LookasideList,           /* Lookaside list */
+    NULL,                           /* Allocate routine */
+    NULL,                           /* Free routine */
+    0,                              /* Flags */
+    sizeof(SPLAY_TREE_NODE),        /* Size of each entry */
+    TAG('E','X','S','T'),           /* Tag */
+    0);                             /* Depth */
+
+  ExInitializeFastMutex(&Tree->Lock);
+
+  return TRUE;
+}
+
+
+/*
+ * Release resources used by a splay tree.
+ */
+VOID STDCALL
+ExDeleteSplayTree(IN PSPLAY_TREE  Tree)
+{
+  PSPLAY_TREE_NODE RemovedNode;
+  PSPLAY_TREE_NODE Node;
+
+  /* Remove all nodes */
+  Node = ExpSplayTreeRootNode(Tree);
+  while (Node != NULL)
+    {
+      Node = ExpRemoveSplayTree(Tree, Node->Key, Node, &RemovedNode);
+
+      if (RemovedNode != NULL)
+                 {
+          ExpDestroySplayTreeNode(Tree, RemovedNode);
+        }
+    }
+
+  ExDeletePagedLookasideList(&Tree->LookasideList);
+}
+
+
+/*
+ * Insert a value in a splay tree.
+ */
+VOID STDCALL
+ExInsertSplayTree(IN PSPLAY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  Value)
+{
+  PSPLAY_TREE_NODE Node;
+  PSPLAY_TREE_NODE NewNode;
+
+  /* FIXME: Use SEH for error reporting */
+
+  NewNode = ExpCreateSplayTreeNode(Tree, Value);
+
+  ExAcquireFastMutex(&Tree->Lock);
+  Node = ExpInsertSplayTree(Tree, Key, ExpSplayTreeRootNode(Tree), NewNode);
+  ExpSplayTreeRootNode(Tree) = Node;
+  ExReleaseFastMutex(&Tree->Lock);
+}
+
+
+/*
+ * Search for a value associated with a given key in a splay tree.
+ */
+BOOLEAN STDCALL
+ExSearchSplayTree(IN PSPLAY_TREE  Tree,
+  IN PVOID  Key,
+  OUT PVOID  * Value)
+{
+  PSPLAY_TREE_NODE Node;
+  BOOLEAN Status;
+
+  ExAcquireFastMutex(&Tree->Lock);
+  Status = ExpSearchSplayTree(Tree, Key, ExpSplayTreeRootNode(Tree), &Node);
+
+  if (Status)
+    {
+      ExpSplayTreeRootNode(Tree) = Node;
+      *Value = ExpSplayTreeNodeValue(Node);
+      ExReleaseFastMutex(&Tree->Lock);
+                 return TRUE;
+         }
+       else
+         {
+      ExReleaseFastMutex(&Tree->Lock);
+           return FALSE;
+         }
+}
+
+
+/*
+ * Remove a value associated with a given key from a splay tree.
+ */
+BOOLEAN STDCALL
+ExRemoveSplayTree(IN PSPLAY_TREE  Tree,
+  IN PVOID  Key,
+  IN PVOID  * Value)
+{
+  PSPLAY_TREE_NODE RemovedNode;
+  PSPLAY_TREE_NODE Node;
+
+  ExAcquireFastMutex(&Tree->Lock);
+  Node = ExpRemoveSplayTree(Tree, Key, ExpSplayTreeRootNode(Tree), &RemovedNode);
+  ExpSplayTreeRootNode(Tree) = Node;
+  ExReleaseFastMutex(&Tree->Lock);
+
+  if (RemovedNode != NULL)
+               {
+      *Value = ExpSplayTreeNodeValue(RemovedNode);
+      ExpDestroySplayTreeNode(Tree, RemovedNode);
+      return TRUE;
+               }
+       else
+               {
+      return FALSE;
+               }
+}
+
+
+/*
+ * Return the weight of the root node in the splay tree.
+ * The returned value is the number of nodes in the tree.
+ */
+BOOLEAN STDCALL
+ExWeightOfSplayTree(IN PSPLAY_TREE  Tree,
+  OUT PULONG  Weight)
+{
+  ExAcquireFastMutex(&Tree->Lock);
+
+       if (!Tree->Weighted)
+               {
+      ExReleaseFastMutex(&Tree->Lock);
+      return FALSE;    
+               }
+
+  *Weight = ExpSplayTreeNodeWeight(ExpSplayTreeRootNode(Tree));
+  ExReleaseFastMutex(&Tree->Lock);
+  return TRUE;
+}
+
+/* EOF */
index ca9137a..851aa72 100644 (file)
@@ -1,4 +1,4 @@
-; $Id: ntoskrnl.def,v 1.129 2002/02/22 17:57:57 ekohl Exp $
+; $Id: ntoskrnl.def,v 1.130 2002/03/22 20:58:23 chorns Exp $
 ;
 ; reactos/ntoskrnl/ntoskrnl.def
 ;
@@ -93,6 +93,22 @@ ExSystemTimeToLocalTime@8
 ExTryToAcquireResourceExclusiveLite@4
 ExUnregisterCallback@4
 ExWindowStationObjectType DATA
+ExInitializeBinaryTree@8
+ExDeleteBinaryTree@4
+ExInsertBinaryTree@12
+ExSearchBinaryTree@12
+ExRemoveBinaryTree@12
+ExInitializeSplayTree@12
+ExDeleteSplayTree@4
+ExInsertSplayTree@12
+ExSearchSplayTree@12
+ExRemoveSplayTree@12
+ExWeightOfSplayTree@8
+ExInitializeHashTable@12
+ExDeleteHashTable@4
+ExInsertHashTable@16
+ExSearchHashTable@16
+ExRemoveHashTable@16
 @ExfInterlockedAddUlong@12
 ;@ExfInterlockedInsertHeadList
 ;@ExfInterlockedInsertTailList
index 2e00fb3..0b28366 100644 (file)
@@ -1,4 +1,4 @@
-; $Id: ntoskrnl.edf,v 1.115 2002/02/22 17:57:57 ekohl Exp $
+; $Id: ntoskrnl.edf,v 1.116 2002/03/22 20:58:23 chorns Exp $
 ;
 ; reactos/ntoskrnl/ntoskrnl.def
 ;
@@ -93,6 +93,22 @@ ExSystemTimeToLocalTime=ExSystemTimeToLocalTime@8
 ExTryToAcquireResourceExclusiveLite=ExTryToAcquireResourceExclusiveLite@4
 ExUnregisterCallback=ExUnregisterCallback@4
 ExWindowStationObjectType DATA
+ExInitializeBinaryTree=ExInitializeBinaryTree@8
+ExDeleteBinaryTree=ExDeleteBinaryTree@4
+ExInsertBinaryTree=ExInsertBinaryTree@12
+ExSearchBinaryTree=ExSearchBinaryTree@12
+ExRemoveBinaryTree=ExRemoveBinaryTree@12
+ExInitializeSplayTree=ExInitializeSplayTree@12
+ExDeleteSplayTree=ExDeleteSplayTree@4
+ExInsertSplayTree=ExInsertSplayTree@12
+ExSearchSplayTree=ExSearchSplayTree@12
+ExRemoveSplayTree=ExRemoveSplayTree@12
+ExWeightOfSplayTree=ExWeightOfSplayTree@8
+ExInitializeHashTable=ExInitializeHashTable@12
+ExDeleteHashTable=ExDeleteHashTable@4
+ExInsertHashTable=ExInsertHashTable@16
+ExSearchHashTable=ExSearchHashTable@16
+ExRemoveHashTable=ExRemoveHashTable@16
 ExfInterlockedAddUlong=@ExfInterlockedAddUlong@12
 ;ExfInterlockedInsertHeadList
 ;ExfInterlockedInsertTailList