Index: /trunk/src/org/openstreetmap/josm/data/osm/DataSet.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 7500)
+++ /trunk/src/org/openstreetmap/josm/data/osm/DataSet.java	(revision 7501)
@@ -102,7 +102,7 @@
     private static final int MAX_EVENTS = 1000;
 
-    private Storage<OsmPrimitive> allPrimitives = new Storage<>(new Storage.PrimitiveIdHash(), true);
-    private Map<PrimitiveId, OsmPrimitive> primitivesMap = allPrimitives.foreignKey(new Storage.PrimitiveIdHash());
-    private CopyOnWriteArrayList<DataSetListener> listeners = new CopyOnWriteArrayList<>();
+    private final Storage<OsmPrimitive> allPrimitives = new Storage<>(new Storage.PrimitiveIdHash(), true);
+    private final Map<PrimitiveId, OsmPrimitive> primitivesMap = allPrimitives.foreignKey(new Storage.PrimitiveIdHash());
+    private final CopyOnWriteArrayList<DataSetListener> listeners = new CopyOnWriteArrayList<>();
 
     // provide means to highlight map elements that are not osm primitives
@@ -257,5 +257,5 @@
      * conversion of the whole DataSet by iterating over this data structure.
      */
-    private QuadBuckets<Node> nodes = new QuadBuckets<>();
+    private final QuadBuckets<Node> nodes = new QuadBuckets<>();
 
     private <T extends OsmPrimitive> Collection<T> getPrimitives(Predicate<OsmPrimitive> predicate) {
@@ -287,9 +287,21 @@
 
     /**
+     * Determines if the given node can be retrieved in the data set through its bounding box. Useful for dataset consistency test.
+     * For efficiency reasons this method does not lock the dataset, you have to lock it manually.
+     *
+     * @param n The node to search
+     * @return {@code true} if {@code n} ban be retrieved in this data set, {@code false} otherwise
+     * @since 7501
+     */
+    public boolean containsNode(Node n) {
+        return nodes.contains(n);
+    }
+
+    /**
      * All ways (Streets etc.) in the DataSet.
      *
      * The way nodes are stored only in the way list.
      */
-    private QuadBuckets<Way> ways = new QuadBuckets<>();
+    private final QuadBuckets<Way> ways = new QuadBuckets<>();
 
     /**
@@ -317,7 +329,19 @@
 
     /**
+     * Determines if the given way can be retrieved in the data set through its bounding box. Useful for dataset consistency test.
+     * For efficiency reasons this method does not lock the dataset, you have to lock it manually.
+     *
+     * @param w The way to search
+     * @return {@code true} if {@code w} ban be retrieved in this data set, {@code false} otherwise
+     * @since 7501
+     */
+    public boolean containsWay(Way w) {
+        return ways.contains(w);
+    }
+
+    /**
      * All relations/relationships
      */
-    private Collection<Relation> relations = new ArrayList<>();
+    private final Collection<Relation> relations = new ArrayList<>();
 
     /**
@@ -349,4 +373,16 @@
             lock.readLock().unlock();
         }
+    }
+
+    /**
+     * Determines if the given relation can be retrieved in the data set through its bounding box. Useful for dataset consistency test.
+     * For efficiency reasons this method does not lock the dataset, you have to lock it manually.
+     *
+     * @param r The relation to search
+     * @return {@code true} if {@code r} ban be retrieved in this data set, {@code false} otherwise
+     * @since 7501
+     */
+    public boolean containsRelation(Relation r) {
+        return relations.contains(r);
     }
 
Index: /trunk/src/org/openstreetmap/josm/data/osm/DatasetConsistencyTest.java
===================================================================
--- /trunk/src/org/openstreetmap/josm/data/osm/DatasetConsistencyTest.java	(revision 7500)
+++ /trunk/src/org/openstreetmap/josm/data/osm/DatasetConsistencyTest.java	(revision 7501)
@@ -9,5 +9,4 @@
 
 import org.openstreetmap.josm.Main;
-import org.openstreetmap.josm.data.coor.LatLon;
 import org.openstreetmap.josm.tools.Utils;
 
@@ -105,14 +104,14 @@
     public void searchNodes() {
         long startTime = System.currentTimeMillis();
-        for (Node n : dataSet.getNodes()) {
-            if (!n.isIncomplete() && !n.isDeleted()) {
-                LatLon c = n.getCoor();
-                if (c != null) {
-                    BBox box = c.toBBox(0.0001);
-                    if (!dataSet.searchNodes(box).contains(n)) {
-                        printError("SEARCH NODES", "%s not found using Dataset.searchNodes()", n);
-                    }
-                }
-            }
+        dataSet.getReadLock().lock();
+        try {
+            for (Node n : dataSet.getNodes()) {
+                // Call isDrawable() as an efficient replacement to previous checks (!deleted, !incomplete, getCoor() != null)
+                if (n.isDrawable() && !dataSet.containsNode(n)) {
+                    printError("SEARCH NODES", "%s not found using Dataset.searchNodes()", n);
+                }
+            }
+        } finally {
+            dataSet.getReadLock().unlock();
         }
         printElapsedTime(startTime);
@@ -124,8 +123,13 @@
     public void searchWays() {
         long startTime = System.currentTimeMillis();
-        for (Way w : dataSet.getWays()) {
-            if (!w.isIncomplete() && !w.isDeleted() && w.getNodesCount() >= 2 && !dataSet.searchWays(w.getBBox()).contains(w)) {
-                printError("SEARCH WAYS", "%s not found using Dataset.searchWays()", w);
-            }
+        dataSet.getReadLock().lock();
+        try {
+            for (Way w : dataSet.getWays()) {
+                if (!w.isIncomplete() && !w.isDeleted() && w.getNodesCount() >= 2 && !dataSet.containsWay(w)) {
+                    printError("SEARCH WAYS", "%s not found using Dataset.searchWays()", w);
+                }
+            }
+        } finally {
+            dataSet.getReadLock().unlock();
         }
         printElapsedTime(startTime);