package unit;

import java.util.*;

/**
 * wireshark-0001: QUIC streams_list wmem_list_find O(S²) → wmem_map O(S)
 *
 * In epan/dissectors/packet-quic.c::quic_streams_add():
 *
 *   if (!wmem_list_find(quic_info->streams_list, GUINT_TO_POINTER(stream_id)))
 *       wmem_list_insert_sorted(...);
 *
 * wmem_list_find() is a linear O(S) scan of a singly-linked list.
 * Called once per new QUIC stream.  HTTP/3 opens one stream per request;
 * a long-lived connection may have S=1,000–10,000 streams.
 * Total dedup cost: O(S²/2).
 *
 * Fix: add wmem_map_t *streams_id_set (hash set) alongside streams_list.
 * Use O(1) map lookup for dedup; keep sorted list for UI display.
 *
 * UNDF: assigned by generate_undf.py
 * Severity: MEDIUM
 */
public class WiresharkQuicStreamsTest {

    static long cmpOps = 0;

    // Simulate wmem_list (singly-linked list with linear find)
    static class WmemList {
        List<Integer> data = new LinkedList<>();

        boolean find(int streamId) {
            for (int id : data) {
                cmpOps++;
                if (id == streamId) return true;
            }
            return false;
        }

        void insertSorted(int streamId) {
            int i = 0;
            for (int id : data) {
                if (id > streamId) break;
                i++;
            }
            ((LinkedList<Integer>) data).add(i, streamId);
        }
    }

    // SLOW: wmem_list_find (O(S) per call)
    static void quicStreamsAddSlow(WmemList list, int streamId) {
        if (!list.find(streamId)) {
            list.insertSorted(streamId);
        }
    }

    // FAST: map-based dedup + list for display
    static void quicStreamsAddFast(List<Integer> list, Set<Integer> idSet, long[] fastOps, int streamId) {
        fastOps[0]++;  // O(1) hash lookup
        if (idSet.add(streamId)) {
            // insert sorted into display list
            int i = Collections.binarySearch(list, streamId);
            if (i < 0) list.add(-(i + 1), streamId);
        }
    }

    public static void main(String[] args) {
        int S = 1000;  // distinct stream IDs (HTTP/3: one per request)
        // Simulate S distinct streams, then verify no duplicate insertion

        // SLOW: list-based dedup
        WmemList slowList = new WmemList();
        cmpOps = 0;
        for (int streamId = 0; streamId < S; streamId++) {
            quicStreamsAddSlow(slowList, streamId);
            // re-announce some streams (duplicates) — common in retransmits
            if (streamId > 0 && streamId % 10 == 0) {
                quicStreamsAddSlow(slowList, streamId - 5);
            }
        }
        long slowCmp = cmpOps;

        // FAST: map-based dedup
        List<Integer> fastList = new ArrayList<>();
        Set<Integer> fastSet = new HashSet<>();
        long[] fastOps = {0};
        for (int streamId = 0; streamId < S; streamId++) {
            quicStreamsAddFast(fastList, fastSet, fastOps, streamId);
            if (streamId > 0 && streamId % 10 == 0) {
                quicStreamsAddFast(fastList, fastSet, fastOps, streamId - 5);
            }
        }
        long fastCmp = fastOps[0];

        // Verify same streams in both
        if (slowList.data.size() != fastList.size()) {
            System.err.printf("FAIL: slow=%d fast=%d distinct streams%n",
                    slowList.data.size(), fastList.size());
            System.exit(1);
        }

        double ratio = (double) slowCmp / Math.max(fastCmp, 1);
        System.out.printf("wireshark-0001 QUIC streams: SLOW=%d cmpOps, FAST~=%d ops, ratio=%.1fx%n",
                slowCmp, fastCmp, ratio);

        if (ratio < 5.0) {
            System.err.printf("FAIL: ratio %.1f < 5x%n", ratio);
            System.exit(1);
        }
        System.out.println("PASS");
    }
}