java-topology/defects/frrouting/unit/FrroutingOspfVertexParentTest.java

package unit;

import java.util.*;

/**
 * Unit test for frrouting-0002: ospf_vertex_add_parent() CWE-407.
 *
 * Defect:  ospf_vertex_add_parent() calls listnode_lookup(vp->parent->children, v)
 *          to guard against duplicate children (ospf_spf.c:275).
 *          listnode_lookup() is O(C) — linear scan over all current children.
 *          In a hub-spoke topology with V spoke vertices all sharing one hub
 *          parent, the guard is checked V times and the children list grows by
 *          one each time, giving O(1+2+…+V) = O(V²) total comparisons.
 *
 * Fix:     Keep a parallel hash set (children_index) on each vertex.
 *          Replace listnode_lookup() with hash_lookup() — O(1) per call,
 *          O(V) total.
 *
 * Model:
 *   DefectiveHub  — guards children with ArrayList.contains()  (O(C) per add)
 *   FixedHub      — guards children with HashSet.contains()    (O(1) per add)
 *
 * Measurement: count element-level equality checks.
 */
public class FrroutingOspfVertexParentTest {

    // ── Minimal vertex stub ──────────────────────────────────────────────────

    static class Vertex {
        final int id;
        Vertex(int id) { this.id = id; }

        @Override public boolean equals(Object o) {
            if (!(o instanceof Vertex)) return false;
            return ((Vertex) o).id == id;
        }
        @Override public int hashCode() { return Integer.hashCode(id); }
        @Override public String toString() { return "V(" + id + ")"; }
    }

    // ── Result ───────────────────────────────────────────────────────────────

    public static class Result {
        final int childrenAdded;
        public final long comparisons;
        Result(int childrenAdded, long comparisons) {
            this.childrenAdded = childrenAdded;
            this.comparisons   = comparisons;
        }
    }

    // ── DEFECTIVE: listnode_lookup → ArrayList.contains() ───────────────────
    //
    // Mirrors the actual C code in ospf_vertex_add_parent():
    //   if (listnode_lookup(vp->parent->children, v) == NULL)
    //       listnode_add(vp->parent->children, v);
    //
    // Each listnode_lookup() walks the list — O(C) where C = current list size.

    public static Result addParentDefective(int spokeCount) {
        List<Vertex> children = new ArrayList<>();
        long comparisons = 0;

        for (int i = 0; i < spokeCount; i++) {
            Vertex spoke = new Vertex(i);

            // listnode_lookup: scan entire children list
            boolean found = false;
            for (Vertex existing : children) {
                comparisons++;
                if (existing.equals(spoke)) {
                    found = true;
                    break;
                }
            }
            if (!found) {
                children.add(spoke);
            }
        }
        return new Result(children.size(), comparisons);
    }

    // ── FIXED: hash_lookup → HashSet.contains() ──────────────────────────────
    //
    // Mirrors the patched C code:
    //   if (hash_lookup(vp->parent->children_index, v) == NULL) {
    //       listnode_add(vp->parent->children, v);
    //       hash_get(vp->parent->children_index, v, hash_alloc_intern);
    //   }
    //
    // Each hash_lookup() is O(1) — counted as 1 comparison.

    public static Result addParentFixed(int spokeCount) {
        List<Vertex> children = new ArrayList<>();
        Set<Vertex> childrenIndex = new HashSet<>();
        long comparisons = 0;

        for (int i = 0; i < spokeCount; i++) {
            Vertex spoke = new Vertex(i);

            comparisons++;   // O(1) hash lookup
            if (!childrenIndex.contains(spoke)) {
                children.add(spoke);
                childrenIndex.add(spoke);
            }
        }
        return new Result(children.size(), comparisons);
    }

    // ── Tests ────────────────────────────────────────────────────────────────

    static void testCorrectnessMatch() {
        int n = 50;
        Result def = addParentDefective(n);
        Result fix = addParentFixed(n);
        assert def.childrenAdded == fix.childrenAdded
            : "defective and fixed must add the same number of children; "
              + "defective=" + def.childrenAdded + " fixed=" + fix.childrenAdded;
        assert def.childrenAdded == n
            : "all " + n + " distinct spokes should be added; got " + def.childrenAdded;
        System.out.println("PASS testCorrectnessMatch");
    }

    static void testDefectiveGrowsQuadratically() {
        // Each time V doubles the comparison count should roughly quadruple.
        long prev = -1;
        for (int v : new int[]{50, 100, 200}) {
            long c = addParentDefective(v).comparisons;
            if (prev > 0) {
                double ratio = (double) c / prev;
                assert ratio > 2.5
                    : "defective comparisons should grow >2.5x when V doubles; "
                      + "got ratio=" + ratio + " (prev=" + prev + " curr=" + c + ")";
            }
            prev = c;
        }
        System.out.println("PASS testDefectiveGrowsQuadratically");
    }

    static void testFixedGrowsLinearly() {
        // Fixed: exactly one hash lookup per spoke regardless of how many
        // children the hub already has.
        for (int v : new int[]{50, 100, 200}) {
            long c = addParentFixed(v).comparisons;
            assert c == v
                : "fixed must make exactly V comparisons (one per spoke); "
                  + "got c=" + c + " for V=" + v;
        }
        System.out.println("PASS testFixedGrowsLinearly");
    }

    static void testRatioAtScaleIsLarge() {
        // At V=400 spokes the defective path does ~80 000 comparisons
        // while the fixed path does 400.  Ratio must be >10.
        int v = 400;
        long defC = addParentDefective(v).comparisons;
        long fixC = addParentFixed(v).comparisons;
        double ratio = (double) defC / fixC;
        assert ratio > 10
            : "at V=400, defective should be >10x worse; ratio=" + ratio
              + " (defective=" + defC + " fixed=" + fixC + ")";
        System.out.printf(
            "PASS testRatioAtScaleIsLarge  (defective=%d, fixed=%d, ratio=%.1fx)%n",
            defC, fixC, ratio);
    }

    static void testNoDuplicatesAdded() {
        // Verify guard works: add same spoke twice, should still end up with 1 child.
        List<Vertex> children = new ArrayList<>();
        Set<Vertex> childrenIndex = new HashSet<>();
        long comparisons = 0;

        Vertex spoke = new Vertex(42);
        for (int attempt = 0; attempt < 5; attempt++) {
            comparisons++;
            if (!childrenIndex.contains(spoke)) {
                children.add(spoke);
                childrenIndex.add(spoke);
            }
        }
        assert children.size() == 1
            : "duplicate-guard must prevent adding same vertex twice; size=" + children.size();
        System.out.println("PASS testNoDuplicatesAdded");
    }

    public static void main(String[] args) {
        testCorrectnessMatch();
        testDefectiveGrowsQuadratically();
        testFixedGrowsLinearly();
        testRatioAtScaleIsLarge();
        testNoDuplicatesAdded();
        System.out.println("All frrouting-0002 tests passed.");
    }
}