Added tree traversal routines for tree data structures.
authorCasper Hornstrup <chorns@users.sourceforge.net>
Sat, 23 Mar 2002 19:44:46 +0000 (19:44 +0000)
committerCasper Hornstrup <chorns@users.sourceforge.net>
Sat, 23 Mar 2002 19:44:46 +0000 (19:44 +0000)
svn path=/trunk/; revision=2774

reactos/include/ddk/exfuncs.h
reactos/include/ddk/extypes.h
reactos/ntoskrnl/ex/btree.c
reactos/ntoskrnl/ex/stree.c
reactos/ntoskrnl/ntoskrnl.def
reactos/ntoskrnl/ntoskrnl.edf

index 270eae2..45d75de 100644 (file)
@@ -845,6 +845,12 @@ ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
   IN PVOID  Key,
   IN PVOID  * Value);
 
+BOOLEAN STDCALL
+ExTraverseBinaryTree(IN PBINARY_TREE  Tree,
+  IN TRAVERSE_METHOD  Method,
+  IN PTRAVERSE_ROUTINE  Routine,
+  IN PVOID  Context);
+
 BOOLEAN STDCALL
 ExInitializeSplayTree(IN PSPLAY_TREE  Tree,
   IN PKEY_COMPARATOR  Compare,
@@ -873,6 +879,12 @@ BOOLEAN STDCALL
 ExWeightOfSplayTree(IN PSPLAY_TREE  Tree,
   OUT PULONG  Weight);
 
+BOOLEAN STDCALL
+ExTraverseSplayTree(IN PSPLAY_TREE  Tree,
+  IN TRAVERSE_METHOD  Method,
+  IN PTRAVERSE_ROUTINE  Routine,
+  IN PVOID  Context);
+
 BOOLEAN STDCALL
 ExInitializeHashTable(IN PHASH_TABLE  HashTable,
   IN ULONG  HashTableSize,
index cc47af3..f5296aa 100644 (file)
@@ -1,4 +1,4 @@
-/* $Id: extypes.h,v 1.8 2002/03/23 13:53:21 chorns Exp $ */
+/* $Id: extypes.h,v 1.9 2002/03/23 19:44:45 chorns Exp $ */
 
 #ifndef __INCLUDE_DDK_EXTYPES_H
 #define __INCLUDE_DDK_EXTYPES_H
@@ -160,8 +160,20 @@ typedef VOID STDCALL
 
 /* BEGIN REACTOS ONLY */
 
-typedef LONG STDCALL (*PKEY_COMPARATOR)(PVOID  Key1,
-  PVOID  Key2);
+typedef enum _TRAVERSE_METHOD {
+  TraverseMethodPreorder,
+  TraverseMethodInorder,
+  TraverseMethodPostorder
+} TRAVERSE_METHOD;
+
+typedef LONG STDCALL
+(*PKEY_COMPARATOR)(IN PVOID  Key1,
+  IN PVOID  Key2);
+
+typedef BOOLEAN STDCALL
+(*PTRAVERSE_ROUTINE)(IN PVOID  Context,
+  IN PVOID  Key,
+  IN PVOID  Value);
 
 struct _BINARY_TREE_NODE;
 
index 574e6f4..98ab9a9 100644 (file)
@@ -41,11 +41,16 @@ typedef struct _BINARY_TREE_NODE
   PVOID  Value;
 } BINARY_TREE_NODE, *PBINARY_TREE_NODE;
 
+typedef struct _TRAVERSE_CONTEXT {
+  PTRAVERSE_ROUTINE Routine;
+  PVOID Context;
+} TRAVERSE_CONTEXT, *PTRAVERSE_CONTEXT;
+
 /* FUNCTIONS ****************************************************************/
 
 #define ExpBinaryTreeRootNode(Tree)(((PBINARY_TREE) (Tree))->RootNode)
-#define ExpIsExternalBinaryTreeNode(Node)(((Node)->LeftChild == NULL) && ((Node)->RightChild == NULL))
-#define ExpIsInternalBinaryTreeNode(Node)(!ExpIsExternalBinaryTreeNode(Node))
+#define ExpBinaryTreeIsExternalNode(Node)(((Node)->LeftChild == NULL) && ((Node)->RightChild == NULL))
+#define ExpBinaryTreeIsInternalNode(Node)(!ExpBinaryTreeIsExternalNode(Node))
 #define ExpBinaryTreeNodeKey(Node)((Node)->Key)
 #define ExpBinaryTreeNodeValue(Node)((Node)->Value)
 #define ExpBinaryTreeParentNode(Node)((Node)->Parent)
@@ -228,7 +233,7 @@ ExpSearchBinaryTree(PBINARY_TREE  Tree,
 
   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 
-  if (ExpIsExternalBinaryTreeNode(Node))
+  if (ExpBinaryTreeIsExternalNode(Node))
     {
       return Node;
     }
@@ -260,7 +265,7 @@ VOID
 ExpRemoveAboveExternalBinaryTreeNode(PBINARY_TREE Tree,
   PBINARY_TREE_NODE Node)
 {
-  assertmsg(ExpIsExternalBinaryTreeNode(Node), ("Node is not external"));
+  assertmsg(ExpBinaryTreeIsExternalNode(Node), ("Node is not external"));
 
   if (Node == ExpBinaryTreeRootNode(Tree))
                {
@@ -294,7 +299,7 @@ ExpDeleteBinaryTree(PBINARY_TREE Tree,
 {
   /* FIXME: Possibly do this iteratively due to the small kernel-mode stack */
 
-  if (ExpIsInternalBinaryTreeNode(Node))
+  if (ExpBinaryTreeIsInternalNode(Node))
     {
       ExpDeleteBinaryTree(Tree, ExpBinaryTreeLeftChildNode(Node));
       ExpDeleteBinaryTree(Tree, ExpBinaryTreeRightChildNode(Node));
@@ -304,6 +309,99 @@ ExpDeleteBinaryTree(PBINARY_TREE Tree,
 }
 
 
+/*
+ * Traverse a binary tree using preorder traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+BOOLEAN
+ExpTraverseBinaryTreePreorder(PTRAVERSE_CONTEXT Context,
+  PBINARY_TREE_NODE Node)
+{
+  if (ExpBinaryTreeIsInternalNode(Node))
+               {
+                 /* Call the traversal routine */
+                 if (!(*Context->Routine)(Context->Context,
+                   ExpBinaryTreeNodeKey(Node),
+                   ExpBinaryTreeNodeValue(Node)))
+                   {
+                     return FALSE;
+                   }
+
+      /* Traverse left subtree */
+      ExpTraverseBinaryTreePreorder(Context, ExpBinaryTreeLeftChildNode(Node));
+
+      /* Traverse right subtree */
+      ExpTraverseBinaryTreePreorder(Context, ExpBinaryTreeRightChildNode(Node));
+               }
+
+  return TRUE;
+}
+
+
+/*
+ * Traverse a binary tree using inorder traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+BOOLEAN
+ExpTraverseBinaryTreeInorder(PTRAVERSE_CONTEXT Context,
+  PBINARY_TREE_NODE Node)
+{
+  if (ExpBinaryTreeIsInternalNode(Node))
+               {
+      /* Traverse left subtree */
+      ExpTraverseBinaryTreeInorder(Context, ExpBinaryTreeLeftChildNode(Node));
+
+                 /* Call the traversal routine */
+                 if (!(*Context->Routine)(Context->Context,
+                   ExpBinaryTreeNodeKey(Node),
+                   ExpBinaryTreeNodeValue(Node)))
+                   {
+                     return FALSE;
+                   }
+
+      /* Traverse right subtree */
+      ExpTraverseBinaryTreeInorder(Context, ExpBinaryTreeRightChildNode(Node));
+               }
+
+  return TRUE;
+}
+
+
+/*
+ * Traverse a binary tree using postorder traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+BOOLEAN
+ExpTraverseBinaryTreePostorder(PTRAVERSE_CONTEXT Context,
+  PBINARY_TREE_NODE Node)
+{
+  if (ExpBinaryTreeIsInternalNode(Node))
+               {
+      /* Traverse left subtree */
+      ExpTraverseBinaryTreePostorder(Context, ExpBinaryTreeLeftChildNode(Node));
+
+      /* Traverse right subtree */
+      ExpTraverseBinaryTreePostorder(Context, ExpBinaryTreeRightChildNode(Node));
+
+                 /* Call the traversal routine */
+                 return (*Context->Routine)(Context->Context,
+                   ExpBinaryTreeNodeKey(Node),
+                   ExpBinaryTreeNodeValue(Node));
+               }
+
+  return TRUE;
+}
+
+
 /*
  * Default key compare function. Compares the integer values of the two keys.
  */
@@ -420,7 +518,7 @@ ExInsertBinaryTree(IN PBINARY_TREE  Tree,
     {
       Node = ExpSearchBinaryTree(Tree, Key, Node);
 
-                 if (ExpIsExternalBinaryTreeNode(Node))
+                 if (ExpBinaryTreeIsExternalNode(Node))
                    {
           break;
                    }
@@ -450,7 +548,7 @@ ExSearchBinaryTree(IN PBINARY_TREE  Tree,
   ExpLockBinaryTree(Tree, &OldIrql);
   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 
-  if (ExpIsInternalBinaryTreeNode(Node))
+  if (ExpBinaryTreeIsInternalNode(Node))
     {
            *Value = ExpBinaryTreeNodeValue(Node);
       ExpUnlockBinaryTree(Tree, &OldIrql);
@@ -479,7 +577,7 @@ ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
 
   Node = ExpSearchBinaryTree(Tree, Key, ExpBinaryTreeRootNode(Tree));
 
-  if (ExpIsExternalBinaryTreeNode(Node))
+  if (ExpBinaryTreeIsExternalNode(Node))
                {
       ExpUnlockBinaryTree(Tree, &OldIrql);
       return FALSE;
@@ -487,11 +585,11 @@ ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
        else
                {
       *Value = ExpBinaryTreeNodeValue(Node);
-                 if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeLeftChildNode(Node)))
+                 if (ExpBinaryTreeIsExternalNode(ExpBinaryTreeLeftChildNode(Node)))
                                {
           Node = ExpBinaryTreeLeftChildNode(Node);
                                }
-      else if (ExpIsExternalBinaryTreeNode(ExpBinaryTreeRightChildNode(Node)))
+      else if (ExpBinaryTreeIsExternalNode(ExpBinaryTreeRightChildNode(Node)))
                                {
           Node = ExpBinaryTreeRightChildNode(Node);
                                }
@@ -505,7 +603,7 @@ ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
           do
             {
               Node = ExpBinaryTreeLeftChildNode(Node);
-            } while (ExpIsInternalBinaryTreeNode(Node));
+            } while (ExpBinaryTreeIsInternalNode(Node));
         }
 
       ExpRemoveAboveExternalBinaryTreeNode(Tree, Node);
@@ -514,4 +612,51 @@ ExRemoveBinaryTree(IN PBINARY_TREE  Tree,
                }
 }
 
+
+/*
+ * Traverse a binary tree using either preorder, inorder or postorder
+ * traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ */
+BOOLEAN STDCALL
+ExTraverseBinaryTree(IN PBINARY_TREE  Tree,
+  IN TRAVERSE_METHOD  Method,
+  IN PTRAVERSE_ROUTINE  Routine,
+  IN PVOID  Context)
+{
+  TRAVERSE_CONTEXT tc;
+  BOOLEAN Status;
+  KIRQL OldIrql;
+
+  tc.Routine = Routine;
+  tc.Context = Context;
+
+  ExpLockBinaryTree(Tree, &OldIrql);
+
+  switch (Method)
+    {
+      case TraverseMethodPreorder:
+        Status = ExpTraverseBinaryTreePreorder(&tc, ExpBinaryTreeRootNode(Tree));
+        break;
+
+      case TraverseMethodInorder:
+        Status = ExpTraverseBinaryTreeInorder(&tc, ExpBinaryTreeRootNode(Tree));
+        break;
+
+      case TraverseMethodPostorder:
+        Status = ExpTraverseBinaryTreePostorder(&tc, ExpBinaryTreeRootNode(Tree));
+        break;
+
+      default:
+        Status = FALSE;
+        break;
+    }
+
+  ExpUnlockBinaryTree(Tree, &OldIrql);
+
+  return Status;
+}
+
 /* EOF */
index f7396fb..1a79ce0 100644 (file)
 
 typedef struct _SPLAY_TREE_NODE
 {
-  /* Children on this branch has smaller keys than this node */
+  /* Children on this branch that has smaller keys than this node */
   struct _SPLAY_TREE_NODE  * SmallerChild;
 
-  /* Children on this branch has larger keys than this node */
+  /* Children on this branch that has larger keys than this node */
   struct _SPLAY_TREE_NODE  * LargerChild;
 
   /* Points to a node with identical key */
@@ -59,6 +59,11 @@ typedef struct _SPLAY_TREE_NODE
   LONG  Weight;
 } SPLAY_TREE_NODE, *PSPLAY_TREE_NODE;
 
+typedef struct _TRAVERSE_CONTEXT {
+  PTRAVERSE_ROUTINE Routine;
+  PVOID Context;
+} TRAVERSE_CONTEXT, *PTRAVERSE_CONTEXT;
+
 #define SPLAY_INDEX 0
 #define SEARCH_INDEX 1
 #define INSERT_INDEX 2
@@ -185,7 +190,7 @@ ExpDestroySplayTreeNode(PSPLAY_TREE Tree,
 
 /*
  * Splay using the key 'Key' (which may or may not be in the tree). The starting
- * root is Node. Weight fields are maintained.
+ * root is Node.
  * The lock for the tree must be acquired when this routine is called.
  * This routine does not maintain weight information.
  */
@@ -229,7 +234,7 @@ ExpSplayTreeNoWeight(PSPLAY_TREE Tree,
                                if (ExpSplayTreeSmallerChildNode(Node) == NULL)
                                  break;
                        }
-               
+
                      ExpSplayTreeSmallerChildNode(r) = Node;           /* Link smaller */
                      r = Node;
                      Node = ExpSplayTreeSmallerChildNode(Node);
@@ -238,7 +243,7 @@ ExpSplayTreeNoWeight(PSPLAY_TREE Tree,
                    {
                      if (ExpSplayTreeLargerChildNode(Node) == NULL)
                              break;
-               
+
                      ChildEquality = (*Tree->Compare)(Key, ExpSplayTreeNodeKey(ExpSplayTreeLargerChildNode(Node)));
                      if (ExpSplayTreeNodeMore(ChildEquality))
                        {
@@ -250,7 +255,7 @@ ExpSplayTreeNoWeight(PSPLAY_TREE Tree,
                                if (ExpSplayTreeLargerChildNode(Node) == NULL)
                                  break;
                        }
-               
+
                      ExpSplayTreeLargerChildNode(l) = Node;            /* Link larger */
                      l = Node;
                      Node = ExpSplayTreeLargerChildNode(Node);         
@@ -275,7 +280,7 @@ ExpSplayTreeNoWeight(PSPLAY_TREE Tree,
 
 /*
  * Splay using the key 'Key' (which may or may not be in the tree). The starting
- * root is Node. Weight fields are maintained.
+ * root is Node.
  * The lock for the tree must be acquired when this routine is called.
  * This routine maintains weight information.
  */
@@ -943,6 +948,141 @@ ExpSplayTreeMaxTreeWeight(PSPLAY_TREE Tree,
 #endif
 
 
+/*
+ * Traverse a splay tree using preorder traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+BOOLEAN
+ExpTraverseSplayTreePreorder(PTRAVERSE_CONTEXT Context,
+  PSPLAY_TREE_NODE Node)
+{
+  PSPLAY_TREE_NODE n; 
+
+  if (Node == NULL)
+    return TRUE;
+
+  /* Call the traversal routine */
+  if (!(*Context->Routine)(Context->Context,
+    ExpSplayTreeNodeKey(Node),
+    ExpSplayTreeNodeValue(Node)))
+    {
+      return FALSE;
+    }
+
+       for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
+               {
+                 /* Call the traversal routine */
+                 if (!(*Context->Routine)(Context->Context,
+                   ExpSplayTreeNodeKey(n),
+                   ExpSplayTreeNodeValue(n)))
+                   {
+                     return FALSE;
+                   }
+               }
+
+  /* Traverse 'smaller' subtree */
+  ExpTraverseSplayTreePreorder(Context, ExpSplayTreeSmallerChildNode(Node));
+
+  /* Traverse 'larger' subtree */
+  ExpTraverseSplayTreePreorder(Context, ExpSplayTreeLargerChildNode(Node));
+
+  return TRUE;
+}
+
+
+/*
+ * Traverse a splay tree using inorder traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+BOOLEAN
+ExpTraverseSplayTreeInorder(PTRAVERSE_CONTEXT Context,
+  PSPLAY_TREE_NODE Node)
+{
+  PSPLAY_TREE_NODE n;
+
+  if (Node == NULL)
+    return TRUE;
+
+  /* Traverse 'smaller' subtree */
+  ExpTraverseSplayTreeInorder(Context, ExpSplayTreeSmallerChildNode(Node));
+
+  /* Call the traversal routine */
+  if (!(*Context->Routine)(Context->Context,
+    ExpSplayTreeNodeKey(Node),
+    ExpSplayTreeNodeValue(Node)))
+    {
+      return FALSE;
+    }
+
+       for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
+               {
+                 /* Call the traversal routine */
+                 if (!(*Context->Routine)(Context->Context,
+                   ExpSplayTreeNodeKey(n),
+                   ExpSplayTreeNodeValue(n)))
+                   {
+                     return FALSE;
+                   }
+               }
+
+  /* Traverse right subtree */
+  ExpTraverseSplayTreeInorder(Context, ExpSplayTreeLargerChildNode(Node));
+
+  return TRUE;
+}
+
+
+/*
+ * Traverse a splay tree using postorder traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ * The lock for the tree must be acquired when this routine is called.
+ */
+BOOLEAN
+ExpTraverseSplayTreePostorder(PTRAVERSE_CONTEXT Context,
+  PSPLAY_TREE_NODE Node)
+{
+  PSPLAY_TREE_NODE n;
+
+  if (Node == NULL)
+    return TRUE;
+
+  /* Traverse 'smaller' subtree */
+  ExpTraverseSplayTreePostorder(Context, ExpSplayTreeSmallerChildNode(Node));
+
+  /* Traverse 'larger' subtree */
+  ExpTraverseSplayTreePostorder(Context, ExpSplayTreeLargerChildNode(Node));
+
+  /* Call the traversal routine */
+  if (!(*Context->Routine)(Context->Context,
+    ExpSplayTreeNodeKey(Node),
+    ExpSplayTreeNodeValue(Node)))
+    {
+      return FALSE;
+    }
+
+       for (n = ExpSplayTreeNodeSame(Node); n; n = ExpSplayTreeNodeSame(n))
+               {
+                 /* Call the traversal routine */
+                 if (!(*Context->Routine)(Context->Context,
+                   ExpSplayTreeNodeKey(n),
+                   ExpSplayTreeNodeValue(n)))
+                   {
+                     return FALSE;
+                   }
+               }
+
+  return TRUE;
+}
+
+
 /*
  * Default key compare function. Compares the integer values of the two keys.
  */
@@ -1160,4 +1300,57 @@ ExWeightOfSplayTree(IN PSPLAY_TREE  Tree,
   return TRUE;
 }
 
+
+/*
+ * Traverse a splay tree using either preorder, inorder or postorder
+ * traversal method.
+ * Returns FALSE, if the traversal was terminated prematurely or
+ * TRUE if the callback routine did not request that the traversal
+ * be terminated prematurely.
+ */
+BOOLEAN STDCALL
+ExTraverseSplayTree(IN PSPLAY_TREE  Tree,
+  IN TRAVERSE_METHOD  Method,
+  IN PTRAVERSE_ROUTINE  Routine,
+  IN PVOID  Context)
+{
+  TRAVERSE_CONTEXT tc;
+  BOOLEAN Status;
+  KIRQL OldIrql;
+
+  tc.Routine = Routine;
+  tc.Context = Context;
+
+  ExpLockSplayTree(Tree, &OldIrql);
+
+  if (ExpSplayTreeRootNode(Tree) == NULL)
+               {
+      ExpUnlockSplayTree(Tree, &OldIrql);
+      return TRUE;
+               }
+
+  switch (Method)
+    {
+      case TraverseMethodPreorder:
+        Status = ExpTraverseSplayTreePreorder(&tc, ExpSplayTreeRootNode(Tree));
+        break;
+
+      case TraverseMethodInorder:
+        Status = ExpTraverseSplayTreeInorder(&tc, ExpSplayTreeRootNode(Tree));
+        break;
+
+      case TraverseMethodPostorder:
+        Status = ExpTraverseSplayTreePostorder(&tc, ExpSplayTreeRootNode(Tree));
+        break;
+
+      default:
+        Status = FALSE;
+        break;
+    }
+
+  ExpUnlockSplayTree(Tree, &OldIrql);
+
+  return Status;
+}
+
 /* EOF */
index ad0cd3e..8297e8a 100644 (file)
@@ -1,4 +1,4 @@
-; $Id: ntoskrnl.def,v 1.131 2002/03/23 13:53:22 chorns Exp $
+; $Id: ntoskrnl.def,v 1.132 2002/03/23 19:44:46 chorns Exp $
 ;
 ; reactos/ntoskrnl/ntoskrnl.def
 ;
@@ -98,12 +98,14 @@ ExDeleteBinaryTree@4
 ExInsertBinaryTree@12
 ExSearchBinaryTree@12
 ExRemoveBinaryTree@12
+ExTraverseBinaryTree@16
 ExInitializeSplayTree@16
 ExDeleteSplayTree@4
 ExInsertSplayTree@12
 ExSearchSplayTree@12
 ExRemoveSplayTree@12
 ExWeightOfSplayTree@8
+ExTraverseSplayTree@16
 ExInitializeHashTable@16
 ExDeleteHashTable@4
 ExInsertHashTable@16
index 2d7d945..f1a1c1f 100644 (file)
@@ -1,4 +1,4 @@
-; $Id: ntoskrnl.edf,v 1.117 2002/03/23 13:53:22 chorns Exp $
+; $Id: ntoskrnl.edf,v 1.118 2002/03/23 19:44:46 chorns Exp $
 ;
 ; reactos/ntoskrnl/ntoskrnl.def
 ;
@@ -98,12 +98,14 @@ ExDeleteBinaryTree=ExDeleteBinaryTree@4
 ExInsertBinaryTree=ExInsertBinaryTree@12
 ExSearchBinaryTree=ExSearchBinaryTree@12
 ExRemoveBinaryTree=ExRemoveBinaryTree@12
+ExTraverseBinaryTree=ExTraverseBinaryTree@16
 ExInitializeSplayTree=ExInitializeSplayTree@16
 ExDeleteSplayTree=ExDeleteSplayTree@4
 ExInsertSplayTree=ExInsertSplayTree@12
 ExSearchSplayTree=ExSearchSplayTree@12
 ExRemoveSplayTree=ExRemoveSplayTree@12
 ExWeightOfSplayTree=ExWeightOfSplayTree@8
+ExTraverseSplayTree=ExTraverseSplayTree@16
 ExInitializeHashTable=ExInitializeHashTable@16
 ExDeleteHashTable=ExDeleteHashTable@4
 ExInsertHashTable=ExInsertHashTable@16