147 lines
4.9 KiB
Java
147 lines
4.9 KiB
Java
package unit;
|
||
|
||
import java.util.*;
|
||
|
||
/**
|
||
* CWE-407 unit test: emacs-0001
|
||
* Models Ffontset_info's Fmember-based font-name deduplication inside a loop.
|
||
*
|
||
* SLOW path: ArrayList.contains() — O(R × F × N), N grows during loop
|
||
* FAST path: HashSet for dedup — O(R × F)
|
||
*
|
||
* Mimics the C pattern:
|
||
* for i over realized fontsets R:
|
||
* for j over font entries F:
|
||
* slot = assq(spec, alist) // find slot by spec
|
||
* if (!names.contains(name)) // ← O(N) Fmember
|
||
* names.add(name) // N grows
|
||
*/
|
||
public class FontsetInfoAlgorithm {
|
||
|
||
// ---- data types --------------------------------------------------------
|
||
|
||
static class Slot {
|
||
String spec;
|
||
List<String> names = new ArrayList<>(); // SLOW: linear dedup
|
||
Set<String> nameSet = new HashSet<>(); // FAST: O(1) dedup
|
||
|
||
Slot(String spec) { this.spec = spec; }
|
||
}
|
||
|
||
// ---- SLOW: list membership for dedup -----------------------------------
|
||
|
||
static long slowOps;
|
||
|
||
static void slowFontsetInfo(int R, int F, List<Slot> alist) {
|
||
slowOps = 0;
|
||
for (int i = 0; i < R; i++) {
|
||
for (int j = 0; j < F; j++) {
|
||
// pick spec deterministically
|
||
Slot slot = alist.get(j % alist.size());
|
||
String name = "font-" + i + "-" + j;
|
||
|
||
// Fmember equivalent: O(N) scan, N grows
|
||
boolean found = false;
|
||
for (String n : slot.names) {
|
||
slowOps++;
|
||
if (n.equals(name)) { found = true; break; }
|
||
}
|
||
if (!found) {
|
||
slot.names.add(name);
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
// ---- FAST: hash set for dedup ------------------------------------------
|
||
|
||
static long fastOps;
|
||
|
||
static void fastFontsetInfo(int R, int F, List<Slot> alist) {
|
||
fastOps = 0;
|
||
for (int i = 0; i < R; i++) {
|
||
for (int j = 0; j < F; j++) {
|
||
Slot slot = alist.get(j % alist.size());
|
||
String name = "font-" + i + "-" + j;
|
||
|
||
fastOps++; // one hash lookup
|
||
if (slot.nameSet.add(name)) {
|
||
// name was absent — successfully added
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
// ---- helpers -----------------------------------------------------------
|
||
|
||
static List<Slot> makeAlist(int A) {
|
||
List<Slot> alist = new ArrayList<>();
|
||
for (int a = 0; a < A; a++) alist.add(new Slot("spec-" + a));
|
||
return alist;
|
||
}
|
||
|
||
static void reset(List<Slot> alist) {
|
||
for (Slot s : alist) { s.names.clear(); s.nameSet.clear(); }
|
||
}
|
||
|
||
// ---- main --------------------------------------------------------------
|
||
|
||
public static void main(String[] args) {
|
||
System.out.println("=== emacs-0001: FontsetInfoAlgorithm (Fmember dedup) ===");
|
||
|
||
int[] sizes = {10, 50, 100, 200};
|
||
int F = 5; // font entries per char-range slot
|
||
int A = 10; // alist entries (distinct font-specs)
|
||
|
||
System.out.printf("%-10s %-15s %-15s %-10s%n",
|
||
"R (real.)", "slow_ops", "fast_ops", "ratio");
|
||
System.out.println("-".repeat(55));
|
||
|
||
for (int R : sizes) {
|
||
List<Slot> alistSlow = makeAlist(A);
|
||
List<Slot> alistFast = makeAlist(A);
|
||
|
||
slowFontsetInfo(R, F, alistSlow);
|
||
fastFontsetInfo(R, F, alistFast);
|
||
|
||
double ratio = slowOps == 0 ? 1.0 : (double) slowOps / fastOps;
|
||
System.out.printf("%-10d %-15d %-15d %-10.1f%n",
|
||
R, slowOps, fastOps, ratio);
|
||
}
|
||
|
||
// Correctness check
|
||
{
|
||
int R = 20, testA = 4;
|
||
List<Slot> s = makeAlist(testA);
|
||
List<Slot> f = makeAlist(testA);
|
||
slowFontsetInfo(R, F, s);
|
||
fastFontsetInfo(R, F, f);
|
||
// Both should produce same unique name sets
|
||
for (int i = 0; i < testA; i++) {
|
||
Set<String> slowSet = new HashSet<>(s.get(i).names);
|
||
Set<String> fastSet = f.get(i).nameSet;
|
||
if (!slowSet.equals(fastSet)) {
|
||
System.err.println("FAIL: mismatch at slot " + i);
|
||
System.exit(1);
|
||
}
|
||
}
|
||
System.out.println("\nCORRECTNESS: PASS");
|
||
}
|
||
|
||
// Assertion: slow must be significantly more ops than fast for large R
|
||
{
|
||
int bigR = 200;
|
||
List<Slot> s = makeAlist(A);
|
||
List<Slot> f = makeAlist(A);
|
||
slowFontsetInfo(bigR, F, s);
|
||
fastFontsetInfo(bigR, F, f);
|
||
double r = (double) slowOps / fastOps;
|
||
System.out.printf("Ratio at R=%d: %.1fx%n", bigR, r);
|
||
if (r < 5.0) {
|
||
System.err.println("FAIL: expected ratio >= 5x at R=" + bigR);
|
||
System.exit(1);
|
||
}
|
||
System.out.println("RATIO ASSERTION: PASS");
|
||
}
|
||
}
|
||
}
|