121 lines
4.5 KiB
Java
121 lines
4.5 KiB
Java
import java.util.*;
|
|
|
|
/**
|
|
* CWE-407 unit test for digikam-0002: GPS marker tiler image ID dedup
|
|
* QList<qlonglong>::contains() during tile splitting: O(I^2) per tile.
|
|
*
|
|
* Simulates splitting a parent tile with I geotagged images into child tiles,
|
|
* where each image insertion checks the growing child list for duplicates.
|
|
*/
|
|
public class DigikamGPSTilerDedupTest {
|
|
|
|
// --- DEFECTIVE: List contains for dedup ---
|
|
static List<Long> splitTileDefective(long[] imageIds, int[] childIndices, int numChildren) {
|
|
@SuppressWarnings("unchecked")
|
|
List<Long>[] children = new List[numChildren];
|
|
for (int i = 0; i < numChildren; i++) {
|
|
children[i] = new ArrayList<>();
|
|
}
|
|
|
|
for (int i = 0; i < imageIds.length; i++) {
|
|
long id = imageIds[i];
|
|
int childIdx = childIndices[i];
|
|
List<Long> child = children[childIdx];
|
|
if (!child.contains(id)) { // O(N) per check
|
|
child.add(id);
|
|
}
|
|
}
|
|
|
|
// Return largest child for verification
|
|
List<Long> largest = children[0];
|
|
for (List<Long> c : children) {
|
|
if (c.size() > largest.size()) largest = c;
|
|
}
|
|
return largest;
|
|
}
|
|
|
|
// --- PATCHED: Set + List for dedup ---
|
|
static List<Long> splitTilePatched(long[] imageIds, int[] childIndices, int numChildren) {
|
|
@SuppressWarnings("unchecked")
|
|
List<Long>[] children = new List[numChildren];
|
|
@SuppressWarnings("unchecked")
|
|
Set<Long>[] childSets = new Set[numChildren];
|
|
for (int i = 0; i < numChildren; i++) {
|
|
children[i] = new ArrayList<>();
|
|
childSets[i] = new HashSet<>();
|
|
}
|
|
|
|
for (int i = 0; i < imageIds.length; i++) {
|
|
long id = imageIds[i];
|
|
int childIdx = childIndices[i];
|
|
if (!childSets[childIdx].contains(id)) { // O(1) per check
|
|
childSets[childIdx].add(id);
|
|
children[childIdx].add(id);
|
|
}
|
|
}
|
|
|
|
List<Long> largest = children[0];
|
|
for (List<Long> c : children) {
|
|
if (c.size() > largest.size()) largest = c;
|
|
}
|
|
return largest;
|
|
}
|
|
|
|
public static void main(String[] args) {
|
|
int I = 5000; // images in parent tile (e.g., geotagged photos in a city)
|
|
int numChildren = 4; // quadtree children
|
|
|
|
Random rng = new Random(42);
|
|
long[] imageIds = new long[I];
|
|
int[] childIndices = new int[I];
|
|
for (int i = 0; i < I; i++) {
|
|
imageIds[i] = i; // unique IDs
|
|
childIndices[i] = rng.nextInt(numChildren);
|
|
}
|
|
// Add duplicates (simulating re-processing)
|
|
long[] allIds = new long[I * 2];
|
|
int[] allChildren = new int[I * 2];
|
|
System.arraycopy(imageIds, 0, allIds, 0, I);
|
|
System.arraycopy(childIndices, 0, allChildren, 0, I);
|
|
System.arraycopy(imageIds, 0, allIds, I, I);
|
|
System.arraycopy(childIndices, 0, allChildren, I, I);
|
|
|
|
// Warm up
|
|
for (int w = 0; w < 3; w++) {
|
|
splitTileDefective(allIds, allChildren, numChildren);
|
|
splitTilePatched(allIds, allChildren, numChildren);
|
|
}
|
|
|
|
// Benchmark defective
|
|
int iterations = 50;
|
|
long startDef = System.nanoTime();
|
|
List<Long> resultDef = null;
|
|
for (int i = 0; i < iterations; i++) {
|
|
resultDef = splitTileDefective(allIds, allChildren, numChildren);
|
|
}
|
|
long defectiveNs = System.nanoTime() - startDef;
|
|
|
|
// Benchmark patched
|
|
long startPat = System.nanoTime();
|
|
List<Long> resultPat = null;
|
|
for (int i = 0; i < iterations; i++) {
|
|
resultPat = splitTilePatched(allIds, allChildren, numChildren);
|
|
}
|
|
long patchedNs = System.nanoTime() - startPat;
|
|
|
|
double ratio = (double) defectiveNs / patchedNs;
|
|
|
|
System.out.println("digikam-0002: GPS marker tiler image ID dedup");
|
|
System.out.println("I=" + I + " images per tile, " + numChildren + " children");
|
|
System.out.println("Defective largest child: " + resultDef.size() + " Patched: " + resultPat.size());
|
|
System.out.printf("Defective: %.3f ms%n", defectiveNs / 1e6);
|
|
System.out.printf("Patched: %.3f ms%n", patchedNs / 1e6);
|
|
System.out.printf("Ratio: %.1fx%n", ratio);
|
|
|
|
assert resultDef.size() == resultPat.size() : "Sizes must match!";
|
|
|
|
boolean pass = ratio > 2.0;
|
|
System.out.println(pass ? "PASS" : "FAIL");
|
|
if (!pass) System.exit(1);
|
|
}
|
|
}
|