// UNDF: UNDF-2026-XXXXXXXXX
// Unit test for decaf-0001: lle_modules O(M) linear scan in mcpGetFileLength / mcpLoadFile
//
// Defect: mcpGetFileLength() and mcpLoadFile() in ios_mcp_mcp_device.cpp each call
//   std::find(lle_modules.begin(), lle_modules.end(), name)
// This is O(M) per RPL load where M = lle_modules.size().
// With R RPL files loaded at title startup the total cost is O(R * M).
// A Wii U game loads 40-60 RPL modules; with all 40 native modules in lle_modules
// that is 60 * 2 * 40 = 4800 string comparisons at title load time.
//
// Fix: replace std::find on the vector with a lookup on a std::unordered_set built once
// from lle_modules at first call.  O(1) amortised per lookup.
//
// Build:
//   g++ -std=c++17 -O2 -o test_decaf_0001 test_decaf_0001.cpp && ./test_decaf_0001

#include <algorithm>
#include <cassert>
#include <chrono>
#include <cstdio>
#include <string>
#include <string_view>
#include <unordered_set>
#include <vector>

static bool defective_lookup(const std::vector<std::string> &v, const std::string &name)
{
    // Original pattern: O(M) linear scan on every call.
    return std::find(v.begin(), v.end(), name) != v.end();
}

static bool patched_lookup(const std::unordered_set<std::string> &s, const std::string &name)
{
    // Patched pattern: O(1) hash lookup, set built once from the vector at startup.
    return s.count(name) > 0;
}

int main()
{
    // Realistic scenario: M lle_modules entries, R RPL queries per title load.
    // Half the queries are present-at-end (worst case scan), half are absent (full scan).
    const int M = 40;  // lle_modules count (all native modules enabled as LLE)
    const int R = 60;  // RPL files a typical Wii U game loads

    std::vector<std::string> lleVec;
    for (int i = 0; i < M; ++i)
        lleVec.push_back("lle_module_" + std::to_string(i) + ".rpl");

    auto lleSet = std::unordered_set<std::string>(lleVec.begin(), lleVec.end());

    // Build queries: half at end of list (worst-case position), half absent.
    std::vector<std::string> queries;
    for (int i = 0; i < R / 2; ++i)
        queries.push_back(lleVec[M - 1 - (i % M)]);          // last entries -- near-full scan
    for (int i = 0; i < R - R / 2; ++i)
        queries.push_back("hle_lib_" + std::to_string(i) + ".rpl");  // absent -- full scan

    // Correctness -----------------------------------------------------------
    for (const auto &q : queries)
        assert(defective_lookup(lleVec, q) == patched_lookup(lleSet, q));
    assert(defective_lookup(lleVec, "lle_module_0.rpl") == true);
    assert(patched_lookup(lleSet,   "lle_module_0.rpl") == true);
    assert(defective_lookup(lleVec, "absent.rpl")       == false);
    assert(patched_lookup(lleSet,   "absent.rpl")       == false);
    std::printf("Correctness: PASS\n");

    // Op-count model --------------------------------------------------------
    // Defective: each query scans up to M entries (worst case full scan for absent/end entries).
    // Patched: each query costs O(1).
    // With 2 IPC calls per RPL (mcpGetFileLength + mcpLoadFile):
    long long opDef   = (long long)M * R * 2;
    long long opPatch = R * 2;
    double opRatio = (double)opDef / opPatch;
    std::printf("Op-count defective: %lld  patched: %lld  ratio: %.1fx\n", opDef, opPatch, opRatio);
    assert(opRatio >= (double)M);
    std::printf("Op-count ratio >= M=%d: PASS\n", M);

    // Timing ----------------------------------------------------------------
    const int iters = 200000;
    volatile int sink = 0;

    auto t0 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < iters; ++i)
        for (const auto &q : queries)
            sink += defective_lookup(lleVec, q) ? 1 : 0;
    auto t1 = std::chrono::high_resolution_clock::now();

    auto t2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < iters; ++i)
        for (const auto &q : queries)
            sink += patched_lookup(lleSet, q) ? 1 : 0;
    auto t3 = std::chrono::high_resolution_clock::now();

    double msDef   = std::chrono::duration<double, std::milli>(t1 - t0).count();
    double msPatch = std::chrono::duration<double, std::milli>(t3 - t2).count();
    double ratio   = msDef / msPatch;
    std::printf("Defective: %.2f ms  Patched: %.2f ms  ratio: %.1fx\n", msDef, msPatch, ratio);
    assert(ratio >= 1.5);
    std::printf("Performance: %.1fx speedup, PASS (sink=%d)\n", ratio, (int)sink);

    return 0;
}