001: /**
002: * JDBM LICENSE v1.00
003: *
004: * Redistribution and use of this software and associated documentation
005: * ("Software"), with or without modification, are permitted provided
006: * that the following conditions are met:
007: *
008: * 1. Redistributions of source code must retain copyright
009: * statements and notices. Redistributions must also contain a
010: * copy of this document.
011: *
012: * 2. Redistributions in binary form must reproduce the
013: * above copyright notice, this list of conditions and the
014: * following disclaimer in the documentation and/or other
015: * materials provided with the distribution.
016: *
017: * 3. The name "JDBM" must not be used to endorse or promote
018: * products derived from this Software without prior written
019: * permission of Cees de Groot. For written permission,
020: * please contact cg@cdegroot.com.
021: *
022: * 4. Products derived from this Software may not be called "JDBM"
023: * nor may "JDBM" appear in their names without prior written
024: * permission of Cees de Groot.
025: *
026: * 5. Due credit should be given to the JDBM Project
027: * (http://jdbm.sourceforge.net/).
028: *
029: * THIS SOFTWARE IS PROVIDED BY THE JDBM PROJECT AND CONTRIBUTORS
030: * ``AS IS'' AND ANY EXPRESSED OR IMPLIED WARRANTIES, INCLUDING, BUT
031: * NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
032: * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL
033: * CEES DE GROOT OR ANY CONTRIBUTORS BE LIABLE FOR ANY DIRECT,
034: * INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
035: * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
036: * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
037: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
038: * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
039: * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED
040: * OF THE POSSIBILITY OF SUCH DAMAGE.
041: *
042: * Copyright 2000 (C) Cees de Groot. All Rights Reserved.
043: * Contributions are Copyright (C) 2000 by their associated contributors.
044: *
045: */package jdbm.btree;
046:
047: import jdbm.RecordManager;
048: import jdbm.RecordManagerFactory;
049: import jdbm.helper.LongComparator;
050:
051: import java.util.Enumeration;
052: import java.util.Hashtable;
053:
054: import java.io.IOException;
055:
056: /**
057: * Random insertion/removal test for B+Tree data structure.
058: *
059: * @author <a href="mailto:boisvert@exoffice.com">Alex Boisvert</a>
060: * @version $Id: BTreeBench.java,v 1.5 2005/06/25 23:12:32 doomdark Exp $
061: */
062: public class BTreeBench {
063:
064: static final int ITERATIONS = 1000000;
065:
066: public static void main(String[] args) {
067:
068: RecordManager recman;
069: BTree tree = null;
070:
071: try {
072: recman = RecordManagerFactory.createRecordManager("test");
073: tree = BTree.createInstance(recman, new LongComparator(),
074: null, null, 32);
075:
076: Hashtable hash = new Hashtable();
077:
078: for (int i = 0; i < ITERATIONS; i++) {
079: Long random = new Long(random(0, 64000));
080:
081: if ((i % 5000) == 0) {
082: System.out.println("Iterations=" + i + " Objects="
083: + tree.size());
084: recman.commit();
085: }
086: if (hash.get(random) == null) {
087: //System.out.println( "Insert " + random );
088: hash.put(random, random);
089: tree.insert(random, random, false);
090: } else {
091: //System.out.println( "Remove " + random );
092: hash.remove(random);
093: Object removed = (Object) tree.remove(random);
094: if ((removed == null) || (!removed.equals(random))) {
095: throw new IllegalStateException(
096: "Remove expected " + random + " got "
097: + removed);
098: }
099: }
100: // tree.assertOrdering();
101: compare(tree, hash);
102: }
103:
104: recman.close();
105: } catch (Throwable except) {
106: except.printStackTrace();
107: }
108: }
109:
110: static long random(int min, int max) {
111: return Math.round(Math.random() * (max - min)) + min;
112: }
113:
114: static void compare(BTree tree, Hashtable hash) throws IOException {
115: boolean failed = false;
116: Enumeration enumeration;
117:
118: if (tree.size() != hash.size()) {
119: throw new IllegalStateException("Tree size " + tree.size()
120: + " Hash size " + hash.size());
121: }
122:
123: enumeration = hash.keys();
124: while (enumeration.hasMoreElements()) {
125: Object key = (Object) enumeration.nextElement();
126: Object hashValue = hash.get(key);
127: Object treeValue = tree.find(key);
128: if (!hashValue.equals(treeValue)) {
129: System.out.println("Compare expected " + hashValue
130: + " got " + treeValue);
131: failed = true;
132: }
133: }
134: if (failed) {
135: throw new IllegalStateException("Compare failed");
136: }
137: }
138:
139: }
|