java-topology/defects/lime3ds-0001/test/test_lime3ds_0001.cpp

// UNDF: UNDF-2026-XXXXXXXXX
// Test: lime3ds-0001 — Room ban list O(N) std::find -> O(1) unordered_set
//
// Defect: HandleJoinRequest checks username and IP bans via std::find over
//         std::vector<std::string>. With B bans and C connection attempts the
//         total work is O(C * B). On a large, heavily-moderated room (B=1000,
//         C=100 simultaneous joins) this is 100,000 string comparisons instead
//         of 200 (100 username + 100 IP hash lookups).
//
// Fix: change internal storage to std::unordered_set<std::string> for O(1)
//      average-case membership checks; convert to/from std::vector only at
//      serialization boundaries (GetBanList / Create / SendModBanListResponse).
//
// Compile: g++ -std=c++17 -O2 -o test_lime3ds_0001 test_lime3ds_0001.cpp && ./test_lime3ds_0001

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

// ---------------------------------------------------------------------------
// Simulate the BEFORE (defect) path: std::vector + std::find
// ---------------------------------------------------------------------------
static bool ban_check_vector(const std::vector<std::string>& ban_list,
                             const std::string& candidate) {
    return std::find(ban_list.begin(), ban_list.end(), candidate) != ban_list.end();
}

// ---------------------------------------------------------------------------
// Simulate the AFTER (fixed) path: std::unordered_set
// ---------------------------------------------------------------------------
static bool ban_check_set(const std::unordered_set<std::string>& ban_set,
                          const std::string& candidate) {
    return ban_set.count(candidate) != 0;
}

// ---------------------------------------------------------------------------
// Correctness test
// ---------------------------------------------------------------------------
static void test_correctness() {
    std::vector<std::string> vec_bans;
    std::unordered_set<std::string> set_bans;

    for (int i = 0; i < 200; ++i) {
        std::string entry = "banned_user_" + std::to_string(i);
        vec_bans.push_back(entry);
        set_bans.insert(entry);
    }

    // Banned entries must be detected by both implementations
    for (int i = 0; i < 200; ++i) {
        std::string entry = "banned_user_" + std::to_string(i);
        assert(ban_check_vector(vec_bans, entry) == true);
        assert(ban_check_set(set_bans, entry) == true);
    }

    // Non-banned entries must be rejected by both
    for (int i = 200; i < 400; ++i) {
        std::string entry = "allowed_user_" + std::to_string(i);
        assert(ban_check_vector(vec_bans, entry) == false);
        assert(ban_check_set(set_bans, entry) == false);
    }

    // insert is idempotent in the set (no duplicate bans)
    set_bans.insert("banned_user_0");
    assert(set_bans.size() == 200);

    // erase by value works on the set
    assert(set_bans.erase("banned_user_0") > 0);
    assert(ban_check_set(set_bans, "banned_user_0") == false);

    printf("Correctness: PASS\n");
}

// ---------------------------------------------------------------------------
// Benchmark: O(N) vs O(1) at B=1000 bans, 100 join checks
// ---------------------------------------------------------------------------
static void test_performance() {
    const int NUM_BANS = 1000;
    const int NUM_CHECKS = 100;
    const int REPEAT = 200;

    std::vector<std::string> vec_bans;
    std::unordered_set<std::string> set_bans;

    for (int i = 0; i < NUM_BANS; ++i) {
        std::string entry = "banned_" + std::to_string(i);
        vec_bans.push_back(entry);
        set_bans.insert(entry);
    }

    // Use non-banned candidates so every search goes the full distance
    std::vector<std::string> candidates;
    for (int i = 0; i < NUM_CHECKS; ++i) {
        candidates.push_back("user_" + std::to_string(i + NUM_BANS));
    }

    // --- defect path (vector + std::find) ---
    auto t0 = std::chrono::high_resolution_clock::now();
    volatile bool sink = false;
    for (int r = 0; r < REPEAT; ++r) {
        for (const auto& c : candidates) {
            sink ^= ban_check_vector(vec_bans, c);
        }
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    double ms_vector =
        std::chrono::duration<double, std::milli>(t1 - t0).count();

    // --- fixed path (unordered_set) ---
    t0 = std::chrono::high_resolution_clock::now();
    for (int r = 0; r < REPEAT; ++r) {
        for (const auto& c : candidates) {
            sink ^= ban_check_set(set_bans, c);
        }
    }
    t1 = std::chrono::high_resolution_clock::now();
    double ms_set = std::chrono::duration<double, std::milli>(t1 - t0).count();

    double ratio = (ms_set > 0.0) ? (ms_vector / ms_set) : 9999.0;

    printf("Performance (B=%d, C=%d, repeat=%d):\n", NUM_BANS, NUM_CHECKS, REPEAT);
    printf("  vector+find : %.3f ms\n", ms_vector);
    printf("  unordered_set: %.3f ms\n", ms_set);
    printf("  speedup      : %.1fx\n", ratio);

    assert(ratio >= 3.0 && "Expected at least 3x speedup from unordered_set at B=1000");
    printf("Performance: PASS\n");
    (void)sink;
}

int main() {
    test_correctness();
    test_performance();
    printf("ALL TESTS PASSED\n");
    return 0;
}