java-topology/defects/sdl2/unit/Sdl2JoystickLookupTest.java

package unit;

import java.util.HashMap;
import java.util.Map;

/**
 * Sdl2JoystickLookupTest — CWE-407 sdl2-0001
 *
 * Models SDL_GetJoystickFromID(SDL_JoystickID instance_id):
 *   slow() = O(n) linked-list walk (current defect)
 *   fast() = O(1) hash map lookup (patch using SDL_HashTable/SDL_HashID)
 *
 * Assert: slowOps > fastOps * Nx at N=128 open joysticks.
 */
public class Sdl2JoystickLookupTest {

    // Simulates SDL_Joystick linked-list node
    static class Joystick {
        final int instanceId;
        Joystick next;
        Joystick(int id) { this.instanceId = id; }
    }

    static long slowOps;
    static long fastOps;

    /**
     * slow: O(n) linked-list walk — models SDL_GetJoystickFromID defect.
     */
    static Joystick getJoystickFromIDSlow(Joystick head, int instanceId) {
        for (Joystick j = head; j != null; j = j.next) {
            slowOps++;
            if (j.instanceId == instanceId) return j;
        }
        return null;
    }

    /**
     * fast: O(1) hash map lookup — models SDL_joystick_by_id patch.
     */
    static Joystick getJoystickFromIDFast(Map<Integer, Joystick> byId, int instanceId) {
        fastOps++;
        return byId.get(instanceId);
    }

    public static void main(String[] args) {
        final int N = 128;      // open joystick count (e.g. Gamecube adapter: 4 ports * 32)
        final int NX = 10;      // minimum required speedup factor
        final int CALLS = 3000; // lookup calls (hidapi update loops: N devices * per-packet)

        // Build linked list (head = most recently opened, like SDL_joysticks)
        // Instance IDs: 1..N
        Joystick head = null;
        Map<Integer, Joystick> byId = new HashMap<>();
        for (int i = 1; i <= N; i++) {
            Joystick j = new Joystick(i);
            j.next = head;
            head = j;
            byId.put(i, j);
        }

        // Target: joystick with instanceId=1 is at tail (worst case for list walk)
        int targetId = 1;

        slowOps = 0;
        fastOps = 0;

        for (int c = 0; c < CALLS; c++) {
            getJoystickFromIDSlow(head, targetId);
        }
        long totalSlowOps = slowOps;

        for (int c = 0; c < CALLS; c++) {
            getJoystickFromIDFast(byId, targetId);
        }
        long totalFastOps = fastOps;

        // Correctness
        Joystick slowResult = getJoystickFromIDSlow(head, targetId);
        Joystick fastResult = getJoystickFromIDFast(byId, targetId);
        boolean correctnessOk = (slowResult != null && fastResult != null
            && slowResult.instanceId == fastResult.instanceId
            && slowResult == fastResult);  // same object

        boolean speedupOk = totalSlowOps > totalFastOps * NX;

        System.out.printf("N=%d joysticks, target instanceId=%d, CALLS=%d%n",
            N, targetId, CALLS);
        System.out.printf("slow (linked-list) ops: %d%n", totalSlowOps);
        System.out.printf("fast (hashmap)     ops: %d%n", totalFastOps);
        System.out.printf("speedup ratio: %.1fx (required >%dx)%n",
            (double) totalSlowOps / totalFastOps, NX);

        int passed = 0, total = 2;
        if (correctnessOk) {
            System.out.println("1/2 PASS correctness: same Joystick object returned");
            passed++;
        } else {
            System.out.printf("1/2 FAIL correctness: slow=%s fast=%s%n",
                slowResult == null ? "null" : slowResult.instanceId,
                fastResult == null ? "null" : fastResult.instanceId);
        }
        if (speedupOk) {
            System.out.printf("2/2 PASS speedup: %d > %d * %d%n",
                totalSlowOps, totalFastOps, NX);
            passed++;
        } else {
            System.out.printf("2/2 FAIL speedup: %d not > %d * %d%n",
                totalSlowOps, totalFastOps, NX);
        }

        System.out.printf("%d/%d PASS%n", passed, total);
        if (passed < total) System.exit(1);
    }
}