Function lookup_pkg

src/store/store.c:3915–3930

Look up package name for a node ID in the parallel arrays. nids must be * sorted ascending (the node query orders by id) — a linear scan here is * O(E×N) across the edge loop and spun for >10 minutes on Linux-kernel-sized * graphs (~1.4M defs × ~1.4M CALLS edges). */

 * O(E×N) across the edge loop and spun for >10 minutes on Linux-kernel-sized
 * graphs (~1.4M defs × ~1.4M CALLS edges). */
static const char *lookup_pkg(const int64_t *nids, char **npkgs, int nn, int64_t id) {
    int lo = 0;
    int hi = nn - SKIP_ONE;
    while (lo <= hi) {
        int mid = lo + (hi - lo) / PAIR_LEN;
        if (nids[mid] == id) {
            return npkgs[mid];
        }
        if (nids[mid] < id) {
            lo = mid + SKIP_ONE;
        } else {
            hi = mid - SKIP_ONE;
        }
    }
    return NULL;
}

/* Accumulate a cross-package boundary into parallel arrays. */
static void accum_boundary(const char *src_pkg, const char *tgt_pkg, char **bfroms, char **btos,