import java.util.*;

/**
 * Unit test for Wine wine-0001: ntdll/loader.c find_module_dependency
 * performs O(D) linear scan on a circular singly-linked list to check if a
 * DLL dependency already exists before adding it. Called for every import
 * during fixup_imports, giving O(I*D) per module.
 *
 * Fix: maintain a HashSet alongside the linked list for O(1) dedup.
 *
 * Defect file: dlls/ntdll/loader.c  lines 860-873
 */
public class LoaderDependencyDedupTest {

    // --- Defective: linear scan to find existing dependency ---
    static class DdagNodeDefective {
        List<Object> dependencies = new LinkedList<>();

        boolean hasDependency(Object to) {
            for (Object dep : dependencies) {
                if (dep == to) return true;  // O(D) scan
            }
            return false;
        }

        void addDependency(Object to) {
            if (!hasDependency(to)) {  // O(D) per call
                dependencies.add(to);
            }
        }
    }

    // --- Fixed: hash set for O(1) dedup ---
    static class DdagNodeFixed {
        List<Object> dependencies = new LinkedList<>();
        Set<Object> dependencySet = new HashSet<>();

        void addDependency(Object to) {
            if (dependencySet.add(to)) {  // O(1) dedup
                dependencies.add(to);
            }
        }
    }

    public static void main(String[] args) {
        int N = 500;

        // Simulate modules being imported
        Object[] modules = new Object[N];
        for (int i = 0; i < N; i++) modules[i] = new Object();

        // Defective: add all, then try to add all again (worst case dedup)
        DdagNodeDefective defNode = new DdagNodeDefective();
        DdagNodeFixed fixNode = new DdagNodeFixed();

        // Correctness: both should add N unique deps
        for (Object m : modules) { defNode.addDependency(m); fixNode.addDependency(m); }
        assert defNode.dependencies.size() == N : "Defective size wrong";
        assert fixNode.dependencies.size() == N : "Fixed size wrong";

        // Re-add (all duplicates)
        for (Object m : modules) { defNode.addDependency(m); fixNode.addDependency(m); }
        assert defNode.dependencies.size() == N : "Defective re-add size wrong";
        assert fixNode.dependencies.size() == N : "Fixed re-add size wrong";

        // Warmup
        for (int w = 0; w < 200; w++) {
            DdagNodeDefective d = new DdagNodeDefective();
            DdagNodeFixed f = new DdagNodeFixed();
            for (Object m : modules) { d.addDependency(m); f.addDependency(m); }
            for (Object m : modules) { d.addDependency(m); f.addDependency(m); }
        }

        // Benchmark
        int ITER = 500;
        long t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) {
            DdagNodeDefective d = new DdagNodeDefective();
            for (Object m : modules) d.addDependency(m);
            for (Object m : modules) d.addDependency(m);  // dedup pass
        }
        long defectNs = System.nanoTime() - t0;

        t0 = System.nanoTime();
        for (int i = 0; i < ITER; i++) {
            DdagNodeFixed f = new DdagNodeFixed();
            for (Object m : modules) f.addDependency(m);
            for (Object m : modules) f.addDependency(m);  // dedup pass
        }
        long fixedNs = System.nanoTime() - t0;

        double ratio = (double) defectNs / fixedNs;
        System.out.printf("DLL dependency dedup  N=%d  defect=%.1fms  fixed=%.1fms  ratio=%.1fx%n",
                N, defectNs / 1e6, fixedNs / 1e6, ratio);

        assert ratio > 2.0 : "Expected >2x speedup, got " + ratio;
        System.out.println("PASS");
    }
}