java-topology/defects/bzflag-0002/test/test_ban_list_dedup.cpp

// Unit test for bzflag-0002: AccessControlList ban/hostBan/idBan O(B^2) dedup
//
// Defect: ban(), hostBan(), and idBan() each use std::find() on a
// std::vector to detect duplicate bans before inserting. When called from
// merge() processing a master ban list, this makes ban list loading O(B^2).
//
// Fix: Maintain a parallel std::unordered_set index for O(1) duplicate
// detection. Only fall through to std::find for replacement when our
// index confirms a duplicate exists.

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

// Minimal reproduction of BZFlag ban structures
struct in_addr_sim {
    uint32_t s_addr;
};

struct BanInfo {
    in_addr_sim addr;
    unsigned char cidr;
    std::string bannedBy;
    std::string reason;

    BanInfo(in_addr_sim a, unsigned char c) : addr(a), cidr(c) {}

    bool operator==(const BanInfo &rhs) const {
        return addr.s_addr == rhs.addr.s_addr && cidr == rhs.cidr;
    }
};

// BEFORE: original O(B^2) pattern
struct BanListBefore {
    std::vector<BanInfo> banList;

    void ban(in_addr_sim addr, unsigned char cidr) {
        BanInfo toban(addr, cidr);
        auto oldit = std::find(banList.begin(), banList.end(), toban);
        if (oldit != banList.end())
            *oldit = toban;
        else
            banList.push_back(toban);
    }
};

// AFTER: O(1) dedup with unordered_set index
struct BanListAfter {
    std::vector<BanInfo> banList;
    std::unordered_set<uint64_t> banIndex;

    static uint64_t banKey(in_addr_sim addr, unsigned char cidr) {
        return ((uint64_t)addr.s_addr << 8) | cidr;
    }

    void ban(in_addr_sim addr, unsigned char cidr) {
        BanInfo toban(addr, cidr);
        uint64_t key = banKey(addr, cidr);
        if (banIndex.count(key)) {
            auto oldit = std::find(banList.begin(), banList.end(), toban);
            if (oldit != banList.end())
                *oldit = toban;
        } else {
            banIndex.insert(key);
            banList.push_back(toban);
        }
    }
};

void test_correctness() {
    BanListAfter acl;

    // Add unique bans
    for (int i = 0; i < 100; i++) {
        in_addr_sim a;
        a.s_addr = (uint32_t)i;
        acl.ban(a, 32);
    }
    assert(acl.banList.size() == 100);

    // Add duplicate: should replace, not add
    in_addr_sim dup;
    dup.s_addr = 50;
    acl.ban(dup, 32);
    assert(acl.banList.size() == 100);

    // Different CIDR = different ban
    dup.s_addr = 50;
    acl.ban(dup, 24);
    assert(acl.banList.size() == 101);

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

void test_performance() {
    const int NUM_BANS = 5000;

    // Benchmark BEFORE
    BanListBefore before;
    auto t0 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_BANS; i++) {
        in_addr_sim a;
        a.s_addr = (uint32_t)i;
        before.ban(a, 32);
    }
    auto t1 = std::chrono::high_resolution_clock::now();
    double before_ms = std::chrono::duration<double, std::milli>(t1 - t0).count();

    // Benchmark AFTER
    BanListAfter after;
    auto t2 = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < NUM_BANS; i++) {
        in_addr_sim a;
        a.s_addr = (uint32_t)i;
        after.ban(a, 32);
    }
    auto t3 = std::chrono::high_resolution_clock::now();
    double after_ms = std::chrono::duration<double, std::milli>(t3 - t2).count();

    assert(before.banList.size() == (size_t)NUM_BANS);
    assert(after.banList.size() == (size_t)NUM_BANS);

    double ratio = before_ms / after_ms;
    printf("BEFORE: %.1f ms (%d bans)\n", before_ms, NUM_BANS);
    printf("AFTER:  %.1f ms (%d bans)\n", after_ms, NUM_BANS);
    printf("Ratio:  %.1fx speedup\n", ratio);

    assert(ratio > 5.0 && "Expected at least 5x speedup from hash index");
    printf("PASS: performance (%.1fx)\n", ratio);
}

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