tsplay.c File Reference

#include <stdio.h>
#include "nt.h"
#include "ntrtl.h"

Go to the source code of this file.

Classes
struct	_TREE_NODE
Typedefs
typedef _TREE_NODE	TREE_NODE
typedef TREE_NODE *	PTREE_NODE
Functions
ULONG	RtlRandom (IN OUT PULONG Seed)
PTREE_NODE	TreeInsert (IN PTREE_NODE Root, IN PTREE_NODE Node)
VOID	PrintTree (IN PTREE_NODE Node)
int _CDECL	main (int argc, char *argv[])
Variables
TREE_NODE	Buffer [2048]

---

Typedef Documentation

typedef TREE_NODE* PTREE_NODE

Definition at line 32 of file tsplay.c. Referenced by main().

typedef struct _TREE_NODE TREE_NODE

---

Function Documentation

int _CDECL main (  int  argc, char *  argv[] )

Definition at line 49 of file tsplay.c. References Buffer, DbgPrint, NULL, PrintTree(), PTREE_NODE, RtlRandom(), Seed, TreeInsert(), and TRUE. { 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; }

VOID PrintTree (  IN PTREE_NODE  Node  )

Definition at line 149 of file tsplay.c. References DbgPrint, NULL, and RtlRealSuccessor(). { 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); } }

ULONG RtlRandom (  IN OUT PULONG  Seed  )

Definition at line 72 of file rtl/random.c. 00078 : 00079 00080 An every better random number generator based on MacLaren and Marsaglia. 00081 00082 Arguments: 00083 00084 Seed - Supplies a pointer to the random number generator seed. 00085 00086 Return Value: 00087 00088 ULONG - returns a random number uniformly distributed over [0..MAXLONG] 00089 00090 --*/ 00091 00092 { 00093 ULONG X; 00094 ULONG Y; 00095 ULONG j; 00096 ULONG Result; 00097 00098 RTL_PAGED_CODE(); 00099 00100 X = UniformMacro(Seed); 00101 Y = UniformMacro(Seed); 00102 00103 j = Y % 128; 00104 00105 Result = RtlpRandomConstantVector[j]; 00106 00107 RtlpRandomConstantVector[j] = X; 00108 00109 return Result; 00110 00111 } }

PTREE_NODE TreeInsert (  IN PTREE_NODE  Root, IN PTREE_NODE  Node )

Definition at line 78 of file tsplay.c. References NULL, RtlDelete(), RtlSplay(), and TRUE. { 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); } } } }

---

Variable Documentation

TREE_NODE Buffer[2048]

Definition at line 34 of file tsplay.c.

---