1
/*******************************************************************************
2
* Copyright (c) 2006, 2007 Symbian Software Systems and others.
3
* All rights reserved. This program and the accompanying materials
4
* are made available under the terms of the Eclipse Public License v1.0
5
* which accompanies this distribution, and is available at
6
* http://www.eclipse.org/legal/epl-v10.html
9
* Symbian - Initial implementation
10
* Markus Schorn (Wind River Systems)
11
*******************************************************************************/
12
package org.eclipse.cdt.internal.pdom.tests;
15
import java.util.ArrayList;
16
import java.util.Iterator;
17
import java.util.List;
18
import java.util.Random;
19
import java.util.SortedSet;
20
import java.util.TreeSet;
22
import junit.framework.Test;
24
import org.eclipse.cdt.core.testplugin.util.BaseTestCase;
25
import org.eclipse.cdt.internal.core.pdom.db.BTree;
26
import org.eclipse.cdt.internal.core.pdom.db.ChunkCache;
27
import org.eclipse.cdt.internal.core.pdom.db.Database;
28
import org.eclipse.cdt.internal.core.pdom.db.IBTreeComparator;
29
import org.eclipse.cdt.internal.core.pdom.db.IBTreeVisitor;
30
import org.eclipse.core.runtime.CoreException;
33
* Test insertion/deletion of records of a mock record type in a B-tree
38
public class BTreeTests extends BaseTestCase {
39
protected File dbFile;
40
protected Database db;
41
protected BTree btree;
42
protected int rootRecord;
43
protected IBTreeComparator comparator;
45
protected boolean debugMode = false;
47
public static Test suite() {
48
return suite(BTreeTests.class);
51
// setUp is not used since we need to parameterize this method,
52
// and invoke it multiple times per Junit test
53
protected void init(int degree) throws Exception {
54
dbFile = File.createTempFile("pdomtest", "db");
55
db = new Database(dbFile, new ChunkCache(), 0, false);
56
db.setExclusiveLock();
57
rootRecord = Database.DATA_AREA;
58
comparator = new BTMockRecordComparator();
59
btree = new BTree(db, rootRecord, degree, comparator);
62
// tearDown is not used for the same reason as above
63
protected void finish() throws Exception {
65
dbFile.deleteOnExit();
69
public void testBySortedSetMirrorLite() throws Exception {
74
* Test random (but reproducible via known seed) sequences of insertions/deletions
75
* and use TreeSet as a reference implementation to check behaviour against.
78
protected void sortedMirrorTest(int noTrials) throws Exception {
79
Random seeder = new Random(90210);
81
for(int i=0; i<noTrials; i++) {
82
int seed = seeder.nextInt();
83
System.out.println("Iteration #"+i);
89
* Test random (but reproducible via known seed) sequence of insertions
90
* and use TreeSet as a reference implementation to check behaviour against.
93
public void testInsertion() throws Exception {
94
Random seeder = new Random();
96
for(int i=0; i<6; i++) {
97
int seed = seeder.nextInt();
98
System.out.println("Iteration #"+i);
99
trialImp(seed, false, new Random(seed*2), 1);
104
* Insert/Delete a random number of records into/from the B-tree
105
* @param seed the seed for obtaining the deterministic random testing
106
* @param checkCorrectnessEachIteration if true, then on every single insertion/deletion check that the B-tree invariants
110
protected void trial(int seed, final boolean checkCorrectnessEachIteration) throws Exception {
111
Random random = new Random(seed);
113
// the probabilty that a particular iterations action will be an insertion
114
double pInsert = Math.min(0.5 + random.nextDouble(), 1);
116
trialImp(seed, checkCorrectnessEachIteration, random, pInsert);
119
private void trialImp(int seed, final boolean checkCorrectnessEachIteration, Random random, double pInsert) throws Exception {
120
final int degree = 2 + random.nextInt(11);
121
final int nIterations = random.nextInt(100000);
122
final SortedSet expected = new TreeSet();
123
final List history = new ArrayList();
127
System.out.print("\t "+seed+" "+(nIterations/1000)+"K: ");
128
for(int i=0; i<nIterations; i++) {
129
if(random.nextDouble()<pInsert) {
130
Integer value = new Integer(random.nextInt(Integer.MAX_VALUE));
131
boolean newEntry = expected.add(value);
133
BTMockRecord btValue = new BTMockRecord(db, value.intValue());
134
history.add(btValue);
136
System.out.println("Add: "+value+" @ "+btValue.record);
137
btree.insert(btValue.getRecord());
140
if(!history.isEmpty()) {
141
int index = random.nextInt(history.size());
142
BTMockRecord btValue = (BTMockRecord) history.get(index);
143
history.remove(index);
144
expected.remove(new Integer(btValue.intValue()));
146
System.out.println("Remove: "+btValue.intValue()+" @ "+btValue.record);
147
btree.delete(btValue.getRecord());
151
System.out.print(".");
153
if(checkCorrectnessEachIteration) {
154
assertBTreeMatchesSortedSet("[iteration "+i+"] ", btree, expected);
155
assertBTreeInvariantsHold("[iteration "+i+"] ");
158
System.out.println();
160
assertBTreeMatchesSortedSet("[Trial end] ", btree, expected);
161
assertBTreeInvariantsHold("[Trial end]");
166
public void assertBTreeInvariantsHold(String msg) throws CoreException {
167
String errorReport = btree.getInvariantsErrorReport();
168
if(!errorReport.equals("")) {
169
fail("Invariants do not hold: "+errorReport);
173
public void assertBTreeMatchesSortedSet(final String msg, BTree actual, SortedSet expected) throws CoreException {
174
final Iterator i = expected.iterator();
175
btree.accept(new IBTreeVisitor(){
177
public int compare(long record) throws CoreException {
180
public boolean visit(long record) throws CoreException {
182
BTMockRecord btValue = new BTMockRecord(record, db);
184
Integer exp = ((Integer)i.next());
185
assertEquals(msg+" Differ at index: "+k, btValue.intValue(), exp.intValue());
188
fail("Sizes different");
197
private static class BTMockRecord {
198
public static final int VALUE_PTR = 0;
199
public static final int RECORD_SIZE = Database.INT_SIZE;
206
public BTMockRecord(Database db, int value) throws CoreException {
208
record = db.malloc(BTMockRecord.RECORD_SIZE);
209
db.putInt(record + VALUE_PTR, value);
213
* Get an existing record
215
public BTMockRecord(long record, Database db) {
217
this.record = record;
220
public int intValue() throws CoreException {
221
return db.getInt(record);
224
public long getRecord() {
229
private class BTMockRecordComparator implements IBTreeComparator {
230
public int compare(long record1, long record2) throws CoreException {
231
return db.getInt(record1) - db.getInt(record2);