java-topology/defects/cocos2d-0001/test/cocos2d-0001-test.cpp

// Unit test for cocos2d-0001: EventDispatcher _toRemovedListeners O(N^2) linear scan
// Defect: std::find on std::vector<EventListener*> _toRemovedListeners inside
//         updateListeners loop. O(L * R) where L = listeners, R = pending removals.
// Fix: Replace std::vector with std::unordered_set for O(1) membership test.

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

// Simulate the defect: vector-based toRemovedListeners with std::find in loop
struct DefectEventDispatcher {
    std::vector<int*> toRemovedListeners;
    std::vector<int*> listeners;

    void removeListener(int* l) {
        if (std::find(toRemovedListeners.begin(), toRemovedListeners.end(), l) != toRemovedListeners.end())
            return;
        toRemovedListeners.push_back(l);
    }

    // Simulates updateListeners: iterate all listeners, check toRemovedListeners membership
    int updateListeners() {
        int removed = 0;
        for (auto iter = listeners.begin(); iter != listeners.end();) {
            int* l = *iter;
            // simulate: check if in toRemovedListeners (linear scan)
            auto matchIter = std::find(toRemovedListeners.begin(), toRemovedListeners.end(), l);
            if (matchIter != toRemovedListeners.end()) {
                toRemovedListeners.erase(matchIter);
                iter = listeners.erase(iter);
                removed++;
            } else {
                ++iter;
            }
        }
        return removed;
    }
};

// Fixed: unordered_set-based toRemovedListeners with O(1) lookup
struct FixedEventDispatcher {
    std::unordered_set<int*> toRemovedListeners;
    std::vector<int*> listeners;

    void removeListener(int* l) {
        if (toRemovedListeners.count(l) > 0)
            return;
        toRemovedListeners.insert(l);
    }

    int updateListeners() {
        int removed = 0;
        for (auto iter = listeners.begin(); iter != listeners.end();) {
            int* l = *iter;
            if (toRemovedListeners.count(l) > 0) {
                toRemovedListeners.erase(l);
                iter = listeners.erase(iter);
                removed++;
            } else {
                ++iter;
            }
        }
        return removed;
    }
};

int main() {
    const int N = 5000;  // listeners (complex mobile game scene)
    const int R = 2500;  // removals (half, scene transition)

    // Allocate dummy listeners
    std::vector<int> pool(N);
    for (int i = 0; i < N; i++) pool[i] = i;

    // === Defect version ===
    DefectEventDispatcher defect;
    for (int i = 0; i < N; i++) defect.listeners.push_back(&pool[i]);
    for (int i = 0; i < R; i++) defect.removeListener(&pool[i * 2]); // remove every other

    auto t0 = std::chrono::high_resolution_clock::now();
    int defectRemoved = defect.updateListeners();
    auto t1 = std::chrono::high_resolution_clock::now();
    double defectUs = std::chrono::duration<double, std::micro>(t1 - t0).count();

    // === Fixed version ===
    FixedEventDispatcher fixed;
    for (int i = 0; i < N; i++) fixed.listeners.push_back(&pool[i]);
    for (int i = 0; i < R; i++) fixed.removeListener(&pool[i * 2]);

    auto t2 = std::chrono::high_resolution_clock::now();
    int fixedRemoved = fixed.updateListeners();
    auto t3 = std::chrono::high_resolution_clock::now();
    double fixedUs = std::chrono::duration<double, std::micro>(t3 - t2).count();

    // Correctness
    assert(defectRemoved == R);
    assert(fixedRemoved == R);
    assert(defect.listeners.size() == (size_t)(N - R));
    assert(fixed.listeners.size() == (size_t)(N - R));
    assert(defect.toRemovedListeners.empty());
    assert(fixed.toRemovedListeners.empty());

    double ratio = defectUs / fixedUs;
    printf("cocos2d-0001: EventDispatcher _toRemovedListeners O(L*R) linear scan\n");
    printf("  N=%d listeners, R=%d removals\n", N, R);
    printf("  defect: %.1f us\n", defectUs);
    printf("  fixed:  %.1f us\n", fixedUs);
    printf("  ratio:  %.1fx\n", ratio);
    printf("  PASS: %s\n", (defectRemoved == R && fixedRemoved == R) ? "true" : "false");

    return (defectRemoved == R && fixedRemoved == R) ? 0 : 1;
}