import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * Bind9IncludeDedupeTest — models bind9 zone_registerinclude() CWE-407 defect.
 *
 * bind9 lib/dns/zone.c zone_registerinclude() suppresses duplicate $INCLUDE
 * filenames by walking the newincludes linked list with strcmp for each call.
 * With N include files this is O(N^2).
 *
 * Fix: maintain a HashSet alongside the list for O(1) membership test.
 *
 * Run: javac Bind9IncludeDedupeTest.java && java Bind9IncludeDedupeTest
 */
public class Bind9IncludeDedupeTest {

    /** O(N^2): list.contains() scan per insertion — models newincludes walk */
    static int registerIncludeDefect(List<String> files, int count) {
        List<String> newincludes = new ArrayList<>();
        for (int i = 0; i < count; i++) {
            String filename = files.get(i);
            // CWE-407: O(N) scan per call, O(N^2) total
            if (!newincludes.contains(filename)) {
                newincludes.add(filename);
            }
        }
        return newincludes.size();
    }

    /** O(N): HashSet for O(1) membership — models isc_ht fix */
    static int registerIncludeFixed(List<String> files, int count) {
        List<String> newincludes = new ArrayList<>();
        Set<String> newincludes_ht = new HashSet<>();
        for (int i = 0; i < count; i++) {
            String filename = files.get(i);
            if (newincludes_ht.add(filename)) {   // O(1)
                newincludes.add(filename);
            }
        }
        return newincludes.size();
    }

    public static void main(String[] args) {
        int n = 2000;  // N unique $INCLUDE filenames
        // Build list — all unique (worst case for the list, no early return)
        List<String> files = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            files.add("/var/named/zones/include-" + i + ".zone");
        }

        // Warm up JIT
        registerIncludeDefect(files, Math.min(n, 50));
        registerIncludeFixed(files, Math.min(n, 50));

        int reps = 5;

        long t0 = System.nanoTime();
        int szDefect = 0;
        for (int r = 0; r < reps; r++) {
            szDefect = registerIncludeDefect(files, n);
        }
        long defectNs = (System.nanoTime() - t0) / reps;

        long t1 = System.nanoTime();
        int szFixed = 0;
        for (int r = 0; r < reps; r++) {
            szFixed = registerIncludeFixed(files, n);
        }
        long fixedNs = (System.nanoTime() - t1) / reps;

        System.out.printf("N=%d unique $INCLUDE filenames%n", n);
        System.out.printf("  defect (O(N^2) list.contains): %6.2f ms  [size=%d]%n",
                defectNs / 1e6, szDefect);
        System.out.printf("  fixed  (O(N)  HashSet):        %6.2f ms  [size=%d]%n",
                fixedNs / 1e6, szFixed);
        double ratio = (double) defectNs / fixedNs;
        System.out.printf("  ratio: %.1fx%n", ratio);

        if (szDefect != szFixed) {
            throw new AssertionError("size mismatch: " + szDefect + " vs " + szFixed);
        }
        if (szDefect != n) {
            throw new AssertionError("expected " + n + " entries, got " + szDefect);
        }
        if (ratio < 5.0) {
            System.out.println("WARN: ratio lower than expected — JIT may have optimized");
        } else {
            System.out.println("PASS");
        }
    }
}