test_btree.cc

用Borland C写的B-Tree算法

/*****************************************************************************
 * btree-mem-C/test_btree.cc
 *
 * COPYRIGHT (c) 1995, 1997 by David Van Wagner ALL RIGHTS RESERVED
 * Source and executables may be distributed under the terms of the GNU
 * General Public License version 2, see the file COPYING for details.
 *
 * [e-mail]
 * http://alumni.cse.ucsc.edu/~davevw/
 *****************************************************************************/

#include <iostream.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>
#include <time.h>
#include "my_assert.h"
#include "btree.h"

#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000000
#endif

int main(int argc, char *argv[])
{
	int count=10000;
	long *data=new long[count];
	int i, j;
	int repeat;
 	BTREE_POS pos, order;
	int debug_i_start, debug_i_end;
	int debug_count=0;
	int debug_slow=0;
	int debug_progress=0;
	int duplicates=0;
	char s[100];
	FILE *fp;

	if (getenv("COUNT") != NULL)
		count = atoi(getenv("COUNT"));

	if (getenv("DEBUG_COUNT") != NULL)
		debug_count=1;

	if (getenv("DEBUG_SLOW") != NULL)
		debug_slow=1;

	if (getenv("DEBUG_PROGRESS") != NULL)
		debug_progress=1;

	if (getenv("DUPLICATES") != NULL)
		duplicates=1;

	if (argc == 1)
		fp=fopen("random.data", "r");
	else
		fp=fopen(argv[1], "r");

	if (argc > 2)
		debug_i_start = atoi(argv[2]);
	else
		debug_i_start = -1;

	if (argc > 3)
		debug_i_end = atoi(argv[3]);
	else
		debug_i_end = debug_i_start;

	if (fp == NULL) {
		perror("btree");
		return 1;
	}

	/* read the data */
	for (i=0; i<count; ++i) {
		if (fgets(s, sizeof(s), fp) == NULL) {
			cerr << "btree: fgets returned NULL, exiting, i=" << i << endl;
			return 1;
		}
		data[i] = atol(s);
	}

	fclose(fp);

	/* test for orders 3 through 39 */
	for (order=3; order<=39; order+=2) {
		/* repeat each test three times */
		for (repeat=0; repeat<1; ++repeat) {
			BTREE_ROOT<long>* tree = new BTREE_ROOT<long>(order);
			clock_t now;
			clock_t then=clock();
		
			assertf(tree->get_count() == 0, "%ld\n", tree->get_count());
/*
			tree->display(1);
*/
		
			for (i=0; i<count; ++i) {
/*
				cerr << i << ' ';
*/
				assert(tree != NULL);
	
				if (i % 100 == 0 && debug_progress
                    || (i >= debug_i_start && i <= debug_i_end) )
				{
                    cout << endl << "BEFORE Adding " << data[i] << " (data["
						<< (int)i << "]):" << endl << flush;
                    if (i >= debug_i_start && i <= debug_i_end)
                        tree->display2(0);
				}

				tree->add(data[i], pos);

                if (debug_progress && (i >= debug_i_start && i <= debug_i_end) )
                {
                    cout << endl << "AFTER Adding " << data[i] << " (data["
						<< (int)i << "]):" << endl << flush;
                    tree->display2(0);
                    cout << "tree->get_count()=" << tree->get_count() << endl;
                }

/*
				tree->print();
				cout << endl << endl;
*/
		
/*
				int levels = tree->levels();
				for (j=1; j<=levels; ++j) {
					tree->display(j);
					cout << endl;
				}
				cout << endl;
*/
		
/*
				tree->display2(0);
				cout << "tree->get_count()=" tree->get_count() << endl;
*/

				if (debug_count)
					assertf2(tree->get_count() == i+1, "%ld != %d\n",
						tree->get_count(), i+1);
			}
		
/*
			tree->display2(0);
*/
			now = clock();
		
			cout << "Inserting " << count <<
				" items in " << int(order) << "-order B-Tree: ";
			cout.setf(ios::showpoint);
			cout.precision(3);
			cout << (double)(now-then)/CLOCKS_PER_SEC << " seconds";

			assertf2(tree->get_count() == count,
				"%ld != %d\n", tree->get_count(), count);

			then = clock();

			for (i=count-1; i>=0; --i) {
				BTREE<long> *ptr;
				BTREE_POS pos;
				ptr = tree->find(data[i], pos);
				assert(ptr != NULL);
				assertf2(pos >= 0, "pos=%d, i=%d\n", pos, i);
				assertf2(pos < order, "pos=%d, i=%d\n", pos, i);

				if ((i % 100 == 0 && debug_progress)
					|| (i >= debug_i_start && i <= debug_i_end) )
				{
					cout << "BEFORE DELETING " << data[i] << "(data[" << (int)i
						<< "])" << endl;
					if (i >= debug_i_start && i <= debug_i_end)
						tree->display2(0);
				}

				tree->remove(data[i]);

				if (i >= debug_i_start && i <= debug_i_end) {
					cout << endl << "AFTER DELETING " << data[i] << endl;
					tree->display2(0);
					cout << endl;
				}

				if (debug_count)
					assertf(tree->get_count() == i, "i=%d\n", i);

				if (!duplicates) {
					/* shouldn't be able to find it again */
					ptr = tree->find(data[i], pos);
					assertf(pos == -1, "%d\n", pos);
				}

				if (debug_slow) {
					/* verify that other entries are there */
					for(j=0; j<i; ++j) {
						BTREE<long> *ptr = tree->find(data[j], pos);
						assert(ptr != NULL);
						assertfn(pos >= 0,
							cerr << "after deleting btree[" << i << "]="
								<< data[i] << ", btree[" << j << "]="
								<< data[j] << "missing" << endl );
					}
				}

			}

			now = clock();

			cout << ", Deleting: ";
			cout.setf(ios::showpoint);
			cout.precision(3);
			cout << (double)(now-then)/CLOCKS_PER_SEC << " secs" << endl;

			assertf(tree->get_count() == 0, "%ld\n", tree->get_count());

			delete tree;
		}
	}

	delete [] data;

	return 0;
}