testcore.cpp

独立于AVL库的存储媒体 虽现在有不少可用的AVL树库

/////////////////////////////////////////////////////////////////////////////
// Name:        testcore.cpp
// Version:		1.0.0
// Purpose:     AVL Sample Program - Test 1
// Author:      Wu Yuh Song
// Modified by:
// Created:     08/25/1999
// Copyright:   (c) Wu Yuh Song
// Licence:   	Wu Yuh Song's Library Licence, Version 1
/////////////////////////////////////////////////////////////////////////////



#include "StdAfx.h"	//remove this line if you are not using MS VC++


#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ___AVL_LINKLIST_SUPPORT___


#include "../AVL_Libraries/avl.h"
#include "../AVL_Libraries/avl_node.h"



#define UPPER_LIMIT 999999

template class avl_node_hnd_mem<int,int>;
template class AVL< avl_node_hnd_mem<int,int> >;

int big_rand(int modulo)
{
	int t;
	t = rand()*rand();

	if ( t < 0)
		 t = -t;
	t = t % modulo;
	
	return t;

}


void shuffle( void* pBuf, int size, int number)
{
	int k, m;
	void* swap = new char[size];
	
	for ( k = 0; k < number; k++) {
		m = big_rand(number);
		memcpy(swap, ((char*)pBuf)+k*size, size);
		memcpy(((char*)pBuf)+k*size, ((char*)pBuf)+m*size, size);
		memcpy(((char*)pBuf)+m*size, swap, size);
	}

	delete [] swap;

}

int _avl_test_main()
{
	AVL< avl_node_hnd_mem<int,int> > avl_tree;   

	int k, s, interval;
	int number;

	int* buf; 
	int iteration = 0;
		


	srand((unsigned)time(NULL));
	
	

   	avl_node_hnd_mem<int,int> tmpNode;	
   	tmpNode.NewNode();
   	avl_node_hnd_mem<int,int> hndNode;

	while(1) {
		printf ( "\n\nIteration : %d\n", iteration++);

		number = big_rand(UPPER_LIMIT-1)+1;
		
		buf = new int[2*number];
		

		//create table
		for( k = 0; k < number; k++) {
			buf[(k<<1) + 0] = k;
			buf[(k<<1) + 1] = 0;
		}	

		shuffle( buf, sizeof(int)*2, number);

		printf ( "\tTable size : %d\n", number);

		bool bContinue = true;

		while(bContinue) {
			int path = rand() % 4;
			
			switch(path) {
			case 0:				//Insert contents of the table into avl tree
				printf ( "\tInserting");
				
				shuffle( buf, sizeof(int)*2, number);

				s = interval = number/10;
	
				for ( k = 0; k < number; k++) {
					
					if ( rand() % 2 )
						continue;

					hndNode.NewNode();
					hndNode.SetKey(buf[(k<<1) + 0]);
					hndNode.SetValue(buf[(k<<1) + 0]);						
					
					if( !avl_tree.Insert(hndNode) ) 
						hndNode.DeleteNode();
					
					buf[(k<<1) + 1] = 1;		//indicate it has been inserted

					if ( k+1 >= s) {
						printf(".");
						fflush(stdout);					
						s+=interval;
					}
				}
				printf( "\n");	

				break;
			case 1:	//search
				printf ( "\tSearching");
				
				shuffle( buf, sizeof(int)*2, number);

				s = interval = number/10;

				for ( k = 0; k < number; k++) {
					bool b;
					hndNode.SetToNode(tmpNode);
					hndNode.SetKey(buf[(k<<1) + 0]);
					b = avl_tree.Search(hndNode) ;

					if ( b && !buf[(k<<1) + 1] ) {
						printf ( "\tError : Found dangling node (key = %d).\n", buf[(k<<1) + 0]);
						assert(false);
						return -1;
					}
					else if( !b && buf[(k<<1) + 1] ) {
						printf ( "\tError : Failed to search for node (key = %d).\n", buf[(k<<1) + 0]);
						assert(false);
						return -1;
					}


					if ( k+1 >= s) {
						printf(".");
						fflush(stdout);					
						s+=interval;
					}

				}
				printf ("\n");
				break;
			case 2: //delete

				printf ( "\tDeleting");

				shuffle( buf, sizeof(int)*2, number);

				s = interval = number/10;
	
				for ( k = 0; k < number; k++) {
					
					if ( rand() % 2 )
						continue;

					hndNode.SetToNode(tmpNode);
					hndNode.SetKey(buf[(k<<1) + 0]);

					if( avl_tree.Delete(hndNode) ) {
						hndNode.DeleteNode();					
						buf[(k<<1) + 1] = 0;		//indicate it has been deleted
					}

					if ( k+1 >= s) {
						printf(".");
						fflush(stdout);					
						s+=interval;
					}
				}
				printf( "\n");	

				break;
			case 3:		//terminate
				printf ( "\tChecking integrity...\n");
				if ( !avl_tree.CheckIntegrity() ) {

					char msg[512];
	
					avl_tree.GetErrorMessage( avl_tree.GetLastError(), msg, sizeof(msg) );
					printf("\t%s.\n", msg);		

					assert(false);
					return (-1);
				}

				printf ( "\tDeleting remaining nodes");
				s = interval = number/10;
				for ( k = 0; k < number; k++) {
					if ( buf[(k<<1) + 1] ) {
						hndNode.SetToNode(tmpNode);
						hndNode.SetKey( buf[(k<<1) + 0] );
						if ( !avl_tree.Delete(hndNode)) {
							printf ( "\tFailed to free node (key = %d).\n", buf[(k<<1) + 0] );
							assert(false);
							return -1;
						}
						hndNode.DeleteNode ();
						buf[(k<<1) + 1] = 0;
					}

					if ( k+1 >= s) {
						printf(".");
						fflush(stdout);					
						s+=interval;
					}
				}
				printf ( "\n");

				printf ( "\tChecking integrity...\n");
				if ( !avl_tree.CheckIntegrity() ) {

					char msg[512];
	
					avl_tree.GetErrorMessage( avl_tree.GetLastError(), msg, sizeof(msg) );
					printf("\t%s.\n", msg);


					assert(false);
					return (-1);
				}
				
				if ( avl_tree.GetNodeNumber() ) {
					printf ( "\tTree destruction failed. Zombie nodes detected.\n");
					assert(false);
					return (-1);
				}

				bContinue = false;
				
			}
		}	

		delete[] buf;			

		FILE *fp = fopen("stop.event","r");
		if ( fp) {
			printf( "\n\nDetected stop event. Now stopping...\n");
			break;
		}
	}

	tmpNode.DeleteNode();

	return 0;   
	

}