summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorAndrew Eidsness2013-03-12 09:08:39 (EDT)
committer Doug Schaefer2013-03-12 12:24:05 (EDT)
commit8883fb1af518482b2a8ca741c62a141b89e42404 (patch)
tree995ca5857def1b41079c16b78bf59ba59a7c893c
parent88411d63e5e806a5dad0723877e537e9ef2cad47 (diff)
downloadorg.eclipse.cdt-8883fb1af518482b2a8ca741c62a141b89e42404.zip
org.eclipse.cdt-8883fb1af518482b2a8ca741c62a141b89e42404.tar.gz
org.eclipse.cdt-8883fb1af518482b2a8ca741c62a141b89e42404.tar.bz2
Bug 402177: Btree.insert returns wrong valuerefs/changes/04/10804/3
The javadoc for BTree.insert says "don't insert if the key was already there, in which case we return the record that matched". However, the implementation was returning the new record even when it was not actually inserted. This is a fix for the problem and a test case to demonstrate the issue. Further Changes: ---------------- I have modified the code style as described in the comments in https://git.eclipse.org/r/#/c/10804. However, I'm still not sure what style is expected. I've looked through the CDT wiki a few times, especially the 'new developer' parts, but haven't found anything relevant. When I asked the question a few weeks ago, the only reply was to use the "eclipse built-in style", which I can't find in my preferences. The default seems to be "K&R Style" (that is what it is set to now, and I don't think that I would have changed it), so that is what I've used here. If I've missed the section in the wiki then a pointer would be greatly appreciated. Otherwise this topic would be a great topic for someone that knows the answers to add to the wiki. Change-Id: If079f235871fcdfbd35f1cba3f64cc3e33edaaec Reviewed-on: https://git.eclipse.org/r/10804 Reviewed-by: Doug Schaefer <dschaefer@qnx.com> IP-Clean: Doug Schaefer <dschaefer@qnx.com> Tested-by: Doug Schaefer <dschaefer@qnx.com>
-rw-r--r--core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/internal/pdom/tests/BTreeTests.java40
-rw-r--r--core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/pdom/db/BTree.java4
2 files changed, 31 insertions, 13 deletions
diff --git a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/internal/pdom/tests/BTreeTests.java b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/internal/pdom/tests/BTreeTests.java
index 967720e..389694a 100644
--- a/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/internal/pdom/tests/BTreeTests.java
+++ b/core/org.eclipse.cdt.core.tests/parser/org/eclipse/cdt/internal/pdom/tests/BTreeTests.java
@@ -31,7 +31,7 @@ import org.eclipse.core.runtime.CoreException;
/**
* Test insertion/deletion of records of a mock record type in a B-tree
- *
+ *
* @author aferguso
*
*/
@@ -65,11 +65,11 @@ public class BTreeTests extends BaseTestCase {
dbFile.deleteOnExit();
}
-
+
public void testBySortedSetMirrorLite() throws Exception {
sortedMirrorTest(8);
}
-
+
/**
* Test random (but reproducible via known seed) sequences of insertions/deletions
* and use TreeSet as a reference implementation to check behaviour against.
@@ -103,13 +103,31 @@ public class BTreeTests extends BaseTestCase {
}
/**
- * Insert/Delete a random number of records into/from the B-tree
+ * Bug 402177: BTree.insert should return the matching record if the new record was not inserted.
+ */
+ public void testEquivalentRecordInsert_Bug402177() throws Exception {
+
+ init(8);
+ try {
+ BTMockRecord value1 = new BTMockRecord(db, 42);
+ BTMockRecord value2 = new BTMockRecord(db, 42);
+
+ long insert1 = btree.insert(value1.getRecord());
+ long insert2 = btree.insert(value2.getRecord());
+ assertEquals(insert1, insert2);
+ } finally {
+ finish();
+ }
+ }
+
+ /**
+ * Insert/Delete a random number of records into/from the B-tree
* @param seed the seed for obtaining the deterministic random testing
* @param checkCorrectnessEachIteration if true, then on every single insertion/deletion check that the B-tree invariants
* still hold
* @throws Exception
*/
- protected void trial(int seed, final boolean checkCorrectnessEachIteration) throws Exception {
+ protected void trial(int seed, final boolean checkCorrectnessEachIteration) throws Exception {
Random random = new Random(seed);
// the probabilty that a particular iterations action will be an insertion
@@ -123,9 +141,9 @@ public class BTreeTests extends BaseTestCase {
final int nIterations = random.nextInt(100000);
final SortedSet expected = new TreeSet();
final List history = new ArrayList();
-
+
init(degree);
-
+
if (DEBUG > 0)
System.out.print("\t "+seed+" "+(nIterations/1000)+"K: ");
for(int i=0; i<nIterations; i++) {
@@ -163,7 +181,7 @@ public class BTreeTests extends BaseTestCase {
assertBTreeMatchesSortedSet("[Trial end] ", btree, expected);
assertBTreeInvariantsHold("[Trial end]");
-
+
finish();
}
@@ -201,7 +219,7 @@ public class BTreeTests extends BaseTestCase {
}
private static class BTMockRecord {
- public static final int VALUE_PTR = 0;
+ public static final int VALUE_PTR = 0;
public static final int RECORD_SIZE = Database.INT_SIZE;
long record;
Database db;
@@ -213,7 +231,7 @@ public class BTreeTests extends BaseTestCase {
this.db = db;
record = db.malloc(BTMockRecord.RECORD_SIZE);
db.putInt(record + VALUE_PTR, value);
- }
+ }
/**
* Get an existing record
@@ -235,7 +253,7 @@ public class BTreeTests extends BaseTestCase {
private class BTMockRecordComparator implements IBTreeComparator {
@Override
public int compare(long record1, long record2) throws CoreException {
- return db.getInt(record1) - db.getInt(record2);
+ return db.getInt(record1) - db.getInt(record2);
}
}
}
diff --git a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/pdom/db/BTree.java b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/pdom/db/BTree.java
index dd0642e..92ae16f 100644
--- a/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/pdom/db/BTree.java
+++ b/core/org.eclipse.cdt.core/parser/org/eclipse/cdt/internal/core/pdom/db/BTree.java
@@ -176,8 +176,8 @@ public class BTree {
} else if (compare < 0) {
lower= middle + 1;
} else {
- // Found it, no insert, just return the record.
- return record;
+ // Found it, no insert, just return the matched record.
+ return checkRec;
}
}
}