// ------------------------------- // // -------- Start of File -------- // // ------------------------------- // // ----------------------------------------------------------- // // C++ Source Code File Name: testprog.cpp // Compiler Used: MSVC, BCC32, GCC, HPUX aCC, SOLARIS CC // Produced By: glNET Software // File Creation Date: 08/22/2000 // Date Last Modified: 08/22/2001 // Copyright (c) 2001 glNET Software // ----------------------------------------------------------- // // ------------- Program Description and Details ------------- // // ----------------------------------------------------------- // /* This library is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this library; if not, write to the Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA Balanced multiway tree class program used to test the insertion and deletion time of a large number of keys. */ // ----------------------------------------------------------- // #include <iostream.h> #include <time.h> #include "gxdstats.h" #include "gxbtree.h" // Set the Btree order // const BtreeNodeOrder_t MyKeyClassOrder = 8; // const BtreeNodeOrder_t MyKeyClassOrder = 16; // const BtreeNodeOrder_t MyKeyClassOrder = 32; // const BtreeNodeOrder_t MyKeyClassOrder = 64; const BtreeNodeOrder_t MyKeyClassOrder = 128; // const BtreeNodeOrder_t MyKeyClassOrder = 256; // const BtreeNodeOrder_t MyKeyClassOrder = 1024; class MyKeyClass : public DatabaseKeyB { public: MyKeyClass() : DatabaseKeyB((char *)&data) { } MyKeyClass(gxUINT32 i) : DatabaseKeyB((char *)&data) { data = i; } public: // Base class interface size_t KeySize() { return sizeof(data); } int operator==(const DatabaseKeyB& key) const; int operator>(const DatabaseKeyB& key) const; public: // Persistent data member gxUINT32 data; }; int MyKeyClass::operator==(const DatabaseKeyB& key) const { const MyKeyClass *kptr = (const MyKeyClass *)(&key); return data == *((gxUINT32 *)kptr->db_key); } int MyKeyClass::operator>(const DatabaseKeyB& key) const { const MyKeyClass *kptr = (const MyKeyClass *)(&key); return data > *((gxUINT32 *)kptr->db_key); } void PausePrg() { cout << endl; cout << "Press enter to continue..." << endl; cin.get(); } void BtreeStatus(gxBtree &btx) { cout << "Root address = " << btx.Root() << endl; cout << "Number of entries = " << btx.NumKeys() << endl; cout << "Number of nodes = " << btx.NumNodes() << endl; cout << "Btree order = " << btx.NodeOrder() << endl; cout << "Btree height = " << btx.BtreeHeight() << endl; } void BuildTree(gxBtree &btx) { // Adjust this number to set the number of insertions const unsigned long INSERTIONS = 1 * 1000; // 1K test // const unsigned long INSERTIONS = 10 * 1000; // 10K test // const unsigned long INSERTIONS = 100 * 1000; // 100K test // const unsigned long INSERTIONS = 1000 * 1000; // 1MEG test // const unsigned long INSERTIONS = 10000 * 1000; // 10MEG test // const unsigned long INSERTIONS = 100000 * 1000; // 100MEG test // const unsigned long INSERTIONS = 1000000 * 1000; // 1GIG test MyKeyClass key; MyKeyClass compare_key; cout << "Inserting " << INSERTIONS << " keys..." << endl; unsigned long i, key_count = 0; unsigned long curr_count = 0; int rv; int verify_deletions = 0; // Set to ture to verify all deletions double insert_time = 0; // Get CPU clock cycles before entering loop clock_t begin = clock(); for(i = 0; i < INSERTIONS; i++) { key.data = i; clock_t begin_insert = clock(); rv = btx.Insert(key, compare_key, 0); clock_t end_insert = clock(); insert_time += (double)(end_insert - begin_insert) / CLOCKS_PER_SEC; key_count++; curr_count++; if(rv != 1) { cout << endl << "Problem adding key - " << i << endl; return; } if(curr_count == 10000) { curr_count = 0; cout << "Inserted " << i << " keys in " << insert_time << " seconds" << endl; } } // Get CPU clock cycles after loop is completed clock_t end =clock(); // Calculate the elapsed time in seconds. double elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout.precision(3); cout << "Inserted " << key_count << " values in " << elapsed_time << " seconds" << endl; double avg_insert_time = (insert_time/(double)key_count) * 1000; cout << "Average insert time = " << avg_insert_time << " milliseconds" << endl; BtreeStatus(btx); key_count = 0; double search_time = 0; cout << "Verifying the insertions..." << endl; begin = clock(); for(i = 0; i < INSERTIONS; i++) { key.data = i; clock_t begin_search = clock(); rv = btx.Find(key, compare_key, 0); clock_t end_search = clock(); key_count++; search_time += (double)(end_search - begin_search) / CLOCKS_PER_SEC; if(rv != 1) { cout << "Error finding key - " << i << endl; return; } } end =clock(); elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout.precision(3); cout << "Verified " << key_count << " values in " << elapsed_time << " seconds" << endl; double avg_search_time = (search_time/(double)key_count) * 1000; cout << "Average search time = " << avg_search_time << " milliseconds" << endl; cout << "Deleting all the entries..." << endl; key_count = 0; double delete_time = 0; begin = clock(); for(i = 0; i < INSERTIONS; i++) { key.data = i; clock_t begin_delete = clock(); rv = btx.Delete(key, compare_key, 0); clock_t end_delete = clock(); delete_time += (double)(end_delete - begin_delete) / CLOCKS_PER_SEC; key_count++; if(rv != 1) { cout << "Error deleting key - " << i << endl; return; } if(verify_deletions) { // Verify the remaining key locations for(unsigned long j = INSERTIONS-1; j != i; j--) { key.data = j; rv = btx.Find(key, compare_key, 0); if(rv != 1) { cout << "Error finding key - " << j << endl; cout << "After deleting key - " << i << endl; return; } } } } end =clock(); cout.precision(3); elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout << "Deleted " << key_count << " values in " << elapsed_time << " seconds" << endl; double avg_delete_time = (delete_time/(double)key_count) * 1000; cout << "Average delete time = " << avg_delete_time << " milliseconds" << endl; cout << "Re-inserting " << INSERTIONS << " keys..." << endl; key_count = 0; insert_time = 0; begin = clock(); for(i = 0; i < INSERTIONS; i++) { key.data = i; clock_t begin_insert = clock(); rv = btx.Insert(key, compare_key, 0); clock_t end_insert = clock(); insert_time += (double)(end_insert - begin_insert) / CLOCKS_PER_SEC; key_count++; curr_count++; if(rv != 1) { cout << endl << "Problem adding key - " << i << endl; return; } } end =clock(); elapsed_time = (double)(end - begin) / CLOCKS_PER_SEC; cout.precision(3); cout << "Inserted " << key_count << " values in " << elapsed_time << " seconds" << endl; avg_insert_time = (insert_time/(double)key_count) * 1000; cout << "Average insert time = " << avg_insert_time << " milliseconds" << endl; } int main() { const char *fname = "testfile.btx"; MyKeyClass key, compare_key; gxBtree btx(key, MyKeyClassOrder); // Create a new Btree index file btx.Create(fname); if(CheckError(btx.gxDatabasePtr()) != 0) return 1; // Build the Btree BuildTree(btx); cout << "Exiting..." << endl; return 0; } // ----------------------------------------------------------- // // ------------------------------- // // --------- End of File --------- // // ------------------------------- //