diff options
author | Adam <you@example.com> | 2020-05-17 05:51:50 +0200 |
---|---|---|
committer | Adam <you@example.com> | 2020-05-17 05:51:50 +0200 |
commit | e611b132f9b8abe35b362e5870b74bce94a1e58e (patch) | |
tree | a5781d2ec0e085eeca33cf350cf878f2efea6fe5 /private/ntos/rtl/tsplay.c | |
download | NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.gz NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.bz2 NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.lz NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.xz NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.tar.zst NT4.0-e611b132f9b8abe35b362e5870b74bce94a1e58e.zip |
Diffstat (limited to 'private/ntos/rtl/tsplay.c')
-rw-r--r-- | private/ntos/rtl/tsplay.c | 184 |
1 files changed, 184 insertions, 0 deletions
diff --git a/private/ntos/rtl/tsplay.c b/private/ntos/rtl/tsplay.c new file mode 100644 index 000000000..76a263b65 --- /dev/null +++ b/private/ntos/rtl/tsplay.c @@ -0,0 +1,184 @@ +/*++ + +Copyright (c) 1989 Microsoft Corporation + +Module Name: + + tsplay.c + +Abstract: + + Test program for the Splay Procedures + +Author: + + Gary Kimura [GaryKi] 24-May-1989 + +Revision History: + +--*/ + +#include <stdio.h> + +#include "nt.h" +#include "ntrtl.h" + +ULONG RtlRandom ( IN OUT PULONG Seed ); + +typedef struct _TREE_NODE { + CLONG Data; + RTL_SPLAY_LINKS Links; +} TREE_NODE; +typedef TREE_NODE *PTREE_NODE; + +TREE_NODE Buffer[2048]; + +PTREE_NODE +TreeInsert ( + IN PTREE_NODE Root, + IN PTREE_NODE Node + ); + +VOID +PrintTree ( + IN PTREE_NODE Node + ); + +int +_CDECL +main( + int argc, + char *argv[] + ) +{ + PTREE_NODE Root; + ULONG i; + ULONG Seed; + + DbgPrint("Start SplayTest()\n"); + + Root = NULL; + Seed = 0; + for (i=0; i<2048; i++) { + Buffer[i].Data = RtlRandom(&Seed); + Buffer[i].Data = Buffer[i].Data % 512; + RtlInitializeSplayLinks(&Buffer[i].Links); + Root = TreeInsert(Root, &Buffer[i]); + } + + PrintTree(Root); + + DbgPrint("End SplayTest()\n"); + + return TRUE; + +} + +PTREE_NODE +TreeInsert ( + IN PTREE_NODE Root, + IN PTREE_NODE Node + ) + +{ + PRTL_SPLAY_LINKS Temp; + + if (Root == NULL) { + + //DbgPrint("Add as root %u\n", Node->Data); + return Node; + + } + + while (TRUE) { + + if (Root->Data == Node->Data) { + + //DbgPrint("Delete %u\n", Node->Data); + + Temp = RtlDelete(&Root->Links); + if (Temp == NULL) { + return NULL; + } else { + return CONTAINING_RECORD(Temp, TREE_NODE, Links); + } + + } + + if (Root->Data < Node->Data) { + + // + // Go right + // + + if (RtlRightChild(&Root->Links) == NULL) { + + //DbgPrint("Add as right child %u\n", Node->Data); + RtlInsertAsRightChild(&Root->Links, &Node->Links); + return CONTAINING_RECORD(RtlSplay(&Node->Links), TREE_NODE, Links); + + } else { + + Root = CONTAINING_RECORD(RtlRightChild(&Root->Links), TREE_NODE, Links); + + } + + } else { + + // + // Go Left + // + + if (RtlLeftChild(&Root->Links) == NULL) { + + //DbgPrint("Add as left child %u\n", Node->Data); + RtlInsertAsLeftChild(&Root->Links, &Node->Links); + return CONTAINING_RECORD(RtlSplay(&Node->Links), TREE_NODE, Links); + + } else { + + Root = CONTAINING_RECORD(RtlLeftChild(&Root->Links), TREE_NODE, Links); + + } + + } + } +} + +VOID +PrintTree ( + IN PTREE_NODE Node + ) + +{ + PRTL_SPLAY_LINKS Temp; + ULONG LastValue; + + if (Node == NULL) { + return; + } + + // + // find smallest value + // + + while (RtlLeftChild(&Node->Links) != NULL) { + Node = CONTAINING_RECORD(RtlLeftChild(&Node->Links), TREE_NODE, Links); + } + LastValue = Node->Data; + //DbgPrint("%u\n", Node->Data); + + // + // while the is a real successor we print the successor value + // + + while ((Temp = RtlRealSuccessor(&Node->Links)) != NULL) { + Node = CONTAINING_RECORD(Temp, TREE_NODE, Links); + if (LastValue >= Node->Data) { + DbgPrint("TestSplay Error\n"); + } + LastValue = Node->Data; + //DbgPrint("%u\n", Node->Data); + } + +} |