Local code intelligence for developers and AI agents. Connect code, docs and infrastructure in a persistent graph, with CBM Lens, MCP tools, agent integrations and change-aware test selection.
C aiderastclaude-codecode-analysiscode-intelligencecodexcursorcypherdeveloper-toolsgemini-cligraph-visualizationkilocodeknowledge-graphmcpmcp-servermodel-context-protocolopencodesqlitetree-sitterwindsurf
/*
* graph_mem.c — read-only in-memory adjacency over a published store's edges.
* See graph_mem.h for the identity, lifetime and budget contract.
*/
#include "store/graph_mem.h"
#include "foundation/constants.h"
#include "foundation/log.h"
#include "foundation/mem.h"
#include "foundation/mem_core.h"
#include "foundation/platform.h"
#include <sqlite3.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
enum {
GM_MAX_TYPES = 64, /* one bit each in cbm_graph_mem_types_t */
GM_VERSION_MAX = 96, /* generation + file state, see store_graph_mem */
GM_CAP_DIVISOR = 4, /* all layers together: at most budget / 4 */
GM_SET_MIN_CAP = 64, /* BFS visited set: initial slots (power of two) */
GM_SET_LOAD_NUM = 7, /* grow the visited set past 7/10 load */
GM_SET_LOAD_DEN = 10,
GM_GROWTH = 2,
GM_COL_TARGET = 1,
GM_COL_TYPE = 2,
};
/* Ids and edge counts must fit the uint32 CSR with room for "+1" offsets. */
#define GM_ID_LIMIT ((int64_t)INT32_MAX - 1)
#define GM_HASH_MUL 2654435761U
struct cbm_graph_mem {
/* Registry state, guarded by the registry mutex. */
struct cbm_graph_mem *next;
char *path;
char version[GM_VERSION_MAX];
int refs;
bool ready; /* built; false while its builder runs */
bool detached; /* unlinked from the registry; freed at the last release */
uint64_t last_use;
uint64_t idle_since_ms; /* when the last reference went away */
size_t bytes; /* reserved estimate while building, actual once ready */
/* The graph, immutable once ready. Offsets cover node ids 0..n_ids-1:
* the out-edges of id u are out_nbr/out_type[out_off[u] .. out_off[u+1]). */
uint32_t n_ids;
uint32_t n_edges;
uint32_t *out_off;
uint32_t *out_nbr; /* target of each out-edge */
uint8_t *out_type;
uint32_t *in_off;
uint32_t *in_nbr; /* source of each in-edge */
uint8_t *in_type;
int type_count;
char *types[GM_MAX_TYPES];
size_t type_len[GM_MAX_TYPES];
};
static cbm_graph_mem_t *g_layers; /* linked (not detached) layers */
static size_t g_total_bytes; /* every live layer, linked or detached */
static uint64_t g_use_clock; /* logical LRU clock */
static uint64_t g_builds;
/* A static SQLite mutex needs no init and works on every platform SQLite
* builds on (SQLITE_THREADSAFE=1). store.c owns APP1. */
static sqlite3_mutex *gm_registry_mutex(void) {
return sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_APP2);
}
#ifdef CBM_ENABLE_TEST_SEAMS
static uint64_t (*g_clock_seam)(void);
static size_t g_cached_bytes_seam;
void cbm_graph_mem_set_clock_for_testing(uint64_t (*now_ms)(void)) {
g_clock_seam = now_ms;
}
void cbm_graph_mem_set_cached_bytes_for_testing(size_t bytes) {
g_cached_bytes_seam = bytes;
}
static uint64_t gm_now_ms(void) {
return g_clock_seam ? g_clock_seam() : cbm_now_ms();
}
#else
static uint64_t gm_now_ms(void) {
return cbm_now_ms();
}
#endif
static void *gm_alloc(size_t bytes) {
return cbm_alloc(CBM_MEM_CLASS_GRAPH_CACHE, bytes ? bytes : 1);
}
static void gm_free_ptr(void *p) {
cbm_free(CBM_MEM_CLASS_GRAPH_CACHE, p);
}
static void gm_free_graph(cbm_graph_mem_t *g) {
gm_free_ptr(g->out_off);
gm_free_ptr(g->out_nbr);
gm_free_ptr(g->out_type);
gm_free_ptr(g->in_off);
gm_free_ptr(g->in_nbr);
gm_free_ptr(g->in_type);
g->out_off = g->out_nbr = g->in_off = g->in_nbr = NULL;
g->out_type = g->in_type = NULL;
for (int i = 0; i < g->type_count; i++) {
gm_free_ptr(g->types[i]);
g->types[i] = NULL;
}
g->type_count = 0;
}
static void gm_destroy(cbm_graph_mem_t *g) {
gm_free_graph(g);
gm_free_ptr(g->path);
gm_free_ptr(g);
}
/* ── Registry (caller holds the mutex) ───────────────────────────── */
static cbm_graph_mem_t *gm_find(const char *path, const char *version) {
for (cbm_graph_mem_t *g = g_layers; g; g = g->next) {
if (strcmp(g->path, path) == 0 && strcmp(g->version, version) == 0) {
return g;
}
}
return NULL;
}
static void gm_unlink(cbm_graph_mem_t *g) {
for (cbm_graph_mem_t **p = &g_layers; *p; p = &(*p)->next) {
if (*p == g) {
*p = g->next;
g->next = NULL;
g->detached = true;
return;
}
}
}
/* Unlink a layer; free it now when nobody holds it, else at its last release. */
static void gm_retire(cbm_graph_mem_t *g) {
gm_unlink(g);
if (g->refs == 0) {
g_total_bytes -= g->bytes;
gm_destroy(g);
}
}
/* Older versions of a path are never asked for again by a new store (one
* opened later reads the current version), so they go now. */
static void gm_retire_other_versions(const char *path, const char *version) {
cbm_graph_mem_t *g = g_layers;
while (g) {
cbm_graph_mem_t *next = g->next;
if (strcmp(g->path, path) == 0 && strcmp(g->version, version) != 0) {
gm_retire(g);
}
g = next;
}
}
/* Make room for `bytes` under the cap by evicting idle layers, oldest first.
* False when it cannot fit: the cap is unset (no budget) or every remaining
* byte is held by a request. */
static bool gm_make_room(size_t bytes) {
size_t budget = cbm_mem_budget();
size_t cap = budget / GM_CAP_DIVISOR;
if (cap == 0 || bytes > cap) {
return false;
}
while (g_total_bytes + bytes > cap) {
cbm_graph_mem_t *victim = NULL;
for (cbm_graph_mem_t *g = g_layers; g; g = g->next) {
if (g->ready && g->refs == 0 && (!victim || g->last_use < victim->last_use)) {
victim = g;
}
}
if (!victim) {
return false;
}
gm_retire(victim);
}
/* The cap bounds the layers; the process as a whole must still fit. */
return cbm_mem_charged() + bytes <= budget;
}
/* Retire every layer no request has held for CBM_GRAPH_MEM_IDLE_EVICT_MS.
* Returns the bytes given back. */
static size_t gm_evict_expired_locked(uint64_t now) {
size_t freed = 0;
cbm_graph_mem_t *g = g_layers;
while (g) {
cbm_graph_mem_t *next = g->next;
if (g->ready && g->refs == 0 && now >= g->idle_since_ms &&
now - g->idle_since_ms >= CBM_GRAPH_MEM_IDLE_EVICT_MS) {
freed += g->bytes;
gm_retire(g);
}
g = next;
}
return freed;
}
static void gm_log_evicted(size_t freed) {
if (freed > 0) {
char bytes[CBM_SZ_32];
(void)snprintf(bytes, sizeof(bytes), "%zu", freed);
cbm_log_info("graph_mem.evict", "reason", "idle", "bytes", bytes);
}
}
/* ── Build ──────────────────────────────────────────────────────── */
static bool gm_bounds(sqlite3 *db, int64_t *max_node, int64_t *max_edge) {
sqlite3_stmt *st = NULL;
if (sqlite3_prepare_v2(db, "SELECT (SELECT max(id) FROM nodes), (SELECT max(id) FROM edges);",
-1, &st, NULL) != SQLITE_OK) {
sqlite3_finalize(st);
return false;
}
bool ok = sqlite3_step(st) == SQLITE_ROW;
if (ok) {
*max_node = sqlite3_column_int64(st, 0);
*max_edge = sqlite3_column_int64(st, 1);
}
sqlite3_finalize(st);
return ok && *max_node >= 0 && *max_edge >= 0 && *max_node < GM_ID_LIMIT &&
*max_edge < GM_ID_LIMIT;
}
/* Upper bound of a layer's bytes: edge ids are unique positive rowids, so the
* edge count never exceeds max(edges.id). */
static size_t gm_estimate(int64_t max_node, int64_t max_edge) {
size_t offsets = ((size_t)max_node + 2) * sizeof(uint32_t);
size_t per_edge = sizeof(uint32_t) + sizeof(uint8_t);
return GM_GROWTH * offsets + GM_GROWTH * (size_t)max_edge * per_edge;
}
static int gm_intern(cbm_graph_mem_t *g, const unsigned char *text, size_t len, int *last) {
if (*last >= 0 && g->type_len[*last] == len && memcmp(g->types[*last], text, len) == 0) {
return *last;
}
for (int i = 0; i < g->type_count; i++) {
if (g->type_len[i] == len && memcmp(g->types[i], text, len) == 0) {
*last = i;
return i;
}
}
if (g->type_count >= GM_MAX_TYPES) {
return -1;
}
char *copy = gm_alloc(len + 1);
if (!copy) {
return -1;
}
memcpy(copy, text, len);
copy[len] = '\0';
g->types[g->type_count] = copy;
g->type_len[g->type_count] = len;
*last = g->type_count;
return g->type_count++;
}
static bool gm_grow_u32(uint32_t **arr, size_t *cap, size_t need) {
if (need <= *cap) {
return true;
}
size_t next = *cap ? *cap : 1;
while (next < need) {
next *= GM_GROWTH;
}
uint32_t *grown = cbm_realloc(CBM_MEM_CLASS_GRAPH_CACHE, *arr, next * sizeof(uint32_t));
if (!grown) {
return false;
}
*arr = grown;
*cap = next;
return true;
}
/* The out-CSR, filled straight from the scan: rows arrive ordered by
* source_id, so each node's list is contiguous and its start offset is the
* edge count when its first row (or a later id's) shows up. */
typedef struct {
size_t off_cap;
size_t edge_cap;
uint32_t next_start; /* smallest id whose start offset is not set yet */
uint32_t max_id; /* largest endpoint seen */
int64_t prev_src;
int last_type;
} gm_scan_t;
static bool gm_scan_row(cbm_graph_mem_t *g, gm_scan_t *sc, sqlite3_stmt *st) {
int64_t src = sqlite3_column_int64(st, 0);
int64_t dst = sqlite3_column_int64(st, GM_COL_TARGET);
const unsigned char *type = sqlite3_column_text(st, GM_COL_TYPE);
if (src < 0 || dst < 0 || src >= GM_ID_LIMIT || dst >= GM_ID_LIMIT || src < sc->prev_src ||
!type || g->n_edges >= (uint32_t)GM_ID_LIMIT) {
return false;
}
int type_id = gm_intern(g, type, (size_t)sqlite3_column_bytes(st, GM_COL_TYPE), &sc->last_type);
if (type_id < 0 || !gm_grow_u32(&g->out_off, &sc->off_cap, (size_t)src + GM_GROWTH)) {
return false;
}
while (sc->next_start <= (uint32_t)src) {
g->out_off[sc->next_start++] = g->n_edges;
}
if (g->n_edges >= sc->edge_cap) {
size_t next = sc->edge_cap ? sc->edge_cap * GM_GROWTH : 1;
uint32_t *nbr = cbm_realloc(CBM_MEM_CLASS_GRAPH_CACHE, g->out_nbr, next * sizeof(uint32_t));
if (!nbr) {
return false;
}
g->out_nbr = nbr;
uint8_t *types = cbm_realloc(CBM_MEM_CLASS_GRAPH_CACHE, g->out_type, next);
if (!types) {
return false;
}
g->out_type = types;
sc->edge_cap = next;
}
g->out_nbr[g->n_edges] = (uint32_t)dst;
g->out_type[g->n_edges] = (uint8_t)type_id;
g->n_edges++;
sc->prev_src = src;
if ((uint32_t)src > sc->max_id) {
sc->max_id = (uint32_t)src;
}
if ((uint32_t)dst > sc->max_id) {
sc->max_id = (uint32_t)dst;
}
return true;
}
/* The in-CSR from the out-CSR: count, prefix-sum, then place each edge using
* in_off[v] as v's cursor, which leaves in_off shifted by one id — shift it
* back. Iterating sources in id order keeps every in-list sorted by source. */
static bool gm_build_inbound(cbm_graph_mem_t *g) {
size_t n_ids = g->n_ids;
g->in_off = cbm_calloc(CBM_MEM_CLASS_GRAPH_CACHE, (n_ids + 1) * sizeof(uint32_t));
g->in_nbr = gm_alloc((size_t)g->n_edges * sizeof(uint32_t));
g->in_type = gm_alloc(g->n_edges);
if (!g->in_off || !g->in_nbr || !g->in_type) {
return false;
}
for (uint32_t e = 0; e < g->n_edges; e++) {
g->in_off[g->out_nbr[e] + 1]++;
}
for (size_t v = 0; v < n_ids; v++) {
g->in_off[v + 1] += g->in_off[v];
}
for (uint32_t u = 0; u < g->n_ids; u++) {
for (uint32_t e = g->out_off[u]; e < g->out_off[u + 1]; e++) {
uint32_t pos = g->in_off[g->out_nbr[e]]++;
g->in_nbr[pos] = u;
g->in_type[pos] = g->out_type[e];
}
}
for (size_t v = n_ids; v > 0; v--) {
g->in_off[v] = g->in_off[v - 1];
}
g->in_off[0] = 0;
return true;
}
static bool gm_build(cbm_graph_mem_t *g, sqlite3 *db, int64_t max_node, int64_t max_edge) {
gm_scan_t sc = {.prev_src = 0, .last_type = -1, .max_id = (uint32_t)max_node};
sc.edge_cap = (size_t)max_edge;
g->out_nbr = gm_alloc(sc.edge_cap * sizeof(uint32_t));
g->out_type = gm_alloc(sc.edge_cap);
if (!g->out_nbr || !g->out_type ||
!gm_grow_u32(&g->out_off, &sc.off_cap, (size_t)max_node + GM_GROWTH)) {
return false;
}
/* ORDER BY the covering UNIQUE index's leading columns: a sequential walk
* of sqlite_autoindex_edges_1, no sort and no table access. */
sqlite3_stmt *st = NULL;
if (sqlite3_prepare_v2(db,
"SELECT source_id, target_id, type FROM edges "
"ORDER BY source_id, target_id, type;",
-1, &st, NULL) != SQLITE_OK) {
sqlite3_finalize(st);
return false;
}
int rc;
bool ok = true;
while ((rc = sqlite3_step(st)) == SQLITE_ROW) {
if (!gm_scan_row(g, &sc, st)) {
ok = false;
break;
}
}
sqlite3_finalize(st);
if (!ok || rc != SQLITE_DONE) {
return false;
}
g->n_ids = sc.max_id + 1;
if (!gm_grow_u32(&g->out_off, &sc.off_cap, (size_t)g->n_ids + 1)) {
return false;
}
while (sc.next_start <= g->n_ids) {
g->out_off[sc.next_start++] = g->n_edges;
}
/* max(edges.id) over-counts after deletions; give the slack back. */
if (g->n_edges < sc.edge_cap) {
size_t keep = g->n_edges ? g->n_edges : 1;
uint32_t *nbr = cbm_realloc(CBM_MEM_CLASS_GRAPH_CACHE, g->out_nbr, keep * sizeof(uint32_t));
uint8_t *types = nbr ? cbm_realloc(CBM_MEM_CLASS_GRAPH_CACHE, g->out_type, keep) : NULL;
if (nbr) {
g->out_nbr = nbr;
}
if (types) {
g->out_type = types;
}
}
return gm_build_inbound(g);
}
static size_t gm_actual_bytes(const cbm_graph_mem_t *g) {
size_t offsets = ((size_t)g->n_ids + 1) * sizeof(uint32_t);
size_t per_edge = sizeof(uint32_t) + sizeof(uint8_t);
size_t bytes = GM_GROWTH * offsets + GM_GROWTH * (size_t)g->n_edges * per_edge;
for (int i = 0; i < g->type_count; i++) {
bytes += g->type_len[i] + 1;
}
return bytes + sizeof(*g) + strlen(g->path) + 1;
}
/* ── Acquire / release ──────────────────────────────────────────── */
/* A ready hit takes a reference; a hit still being built answers NULL (the
* caller uses SQL rather than waiting on another thread's build). */
static cbm_graph_mem_t *gm_take(cbm_graph_mem_t *hit) {
if (!hit->ready) {
return NULL;
}
hit->refs++;
hit->last_use = ++g_use_clock;
return hit;
}
static cbm_graph_mem_t *gm_new_entry(const char *db_path, const char *version, size_t est) {
cbm_graph_mem_t *g = cbm_calloc(CBM_MEM_CLASS_GRAPH_CACHE, sizeof(*g));
if (!g) {
return NULL;
}
g->path = cbm_mem_strdup(CBM_MEM_CLASS_GRAPH_CACHE, db_path);
if (!g->path) {
gm_free_ptr(g);
return NULL;
}
memcpy(g->version, version, strlen(version) + 1);
g->refs = 1;
g->bytes = est;
return g;
}
cbm_graph_mem_t *cbm_graph_mem_acquire(sqlite3 *db, const char *db_path, const char *version) {
if (!db || !db_path || !version || !version[0] || strlen(version) >= GM_VERSION_MAX) {
return NULL;
}
uint64_t now = gm_now_ms();
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
size_t freed = gm_evict_expired_locked(now);
cbm_graph_mem_t *hit = gm_find(db_path, version);
cbm_graph_mem_t *taken = hit ? gm_take(hit) : NULL;
sqlite3_mutex_leave(mu);
gm_log_evicted(freed);
if (hit) {
return taken;
}
int64_t max_node = 0;
int64_t max_edge = 0;
if (!gm_bounds(db, &max_node, &max_edge)) {
return NULL;
}
size_t est = gm_estimate(max_node, max_edge);
sqlite3_mutex_enter(mu);
hit = gm_find(db_path, version);
if (hit) {
taken = gm_take(hit);
sqlite3_mutex_leave(mu);
return taken;
}
gm_retire_other_versions(db_path, version);
bool fits = gm_make_room(est);
cbm_graph_mem_t *g = fits ? gm_new_entry(db_path, version, est) : NULL;
if (g) {
g->next = g_layers;
g_layers = g;
g_total_bytes += est;
}
sqlite3_mutex_leave(mu);
if (!g) {
if (!fits) {
char need[CBM_SZ_32];
(void)snprintf(need, sizeof(need), "%zu", est);
cbm_log_info("graph_mem.skip", "reason", "budget", "bytes", need);
}
return NULL;
}
/* The build runs outside the mutex: other keys stay servable, and a
* request for this key meanwhile takes the SQL path (gm_take). */
uint64_t started_ms = cbm_now_ms();
bool ok = gm_build(g, db, max_node, max_edge);
if (!ok) {
gm_free_graph(g); /* all-or-nothing: no partial layer survives */
}
size_t actual = ok ? gm_actual_bytes(g) : 0;
if (ok) {
char edges[CBM_SZ_32];
char bytes[CBM_SZ_32];
char elapsed[CBM_SZ_32];
(void)snprintf(edges, sizeof(edges), "%u", g->n_edges);
(void)snprintf(bytes, sizeof(bytes), "%zu", actual);
(void)snprintf(elapsed, sizeof(elapsed), "%llu",
(unsigned long long)(cbm_now_ms() - started_ms));
cbm_log_info("graph_mem.build", "edges", edges, "bytes", bytes, "elapsed_ms", elapsed);
}
sqlite3_mutex_enter(mu);
g_total_bytes = g_total_bytes - g->bytes + actual;
g->bytes = actual;
if (ok) {
g->ready = true;
g->last_use = ++g_use_clock;
g_builds++;
} else {
g->refs = 0;
gm_retire(g);
g = NULL;
}
sqlite3_mutex_leave(mu);
return g;
}
void cbm_graph_mem_release(cbm_graph_mem_t *g) {
if (!g) {
return;
}
uint64_t now = gm_now_ms();
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
g->refs--;
if (g->refs == 0) {
g->idle_since_ms = now;
}
if (g->refs == 0 && g->detached) {
g_total_bytes -= g->bytes;
gm_destroy(g);
}
sqlite3_mutex_leave(mu);
}
void cbm_graph_mem_evict_expired(void) {
uint64_t now = gm_now_ms();
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
size_t freed = gm_evict_expired_locked(now);
sqlite3_mutex_leave(mu);
gm_log_evicted(freed);
}
/* ── Queries ────────────────────────────────────────────────────── */
cbm_graph_mem_types_t cbm_graph_mem_type_mask(const cbm_graph_mem_t *g, const char *const *types,
int count) {
cbm_graph_mem_types_t mask = 0;
for (int i = 0; g && types && i < count; i++) {
if (!types[i]) {
continue;
}
size_t len = strlen(types[i]);
for (int t = 0; t < g->type_count; t++) {
if (g->type_len[t] == len && memcmp(g->types[t], types[i], len) == 0) {
mask |= (cbm_graph_mem_types_t)1 << t;
break;
}
}
}
return mask;
}
int cbm_graph_mem_degree(const cbm_graph_mem_t *g, int64_t id, bool inbound,
cbm_graph_mem_types_t mask) {
if (!g || id < 0 || id >= (int64_t)g->n_ids) {
return 0;
}
const uint32_t *off = inbound ? g->in_off : g->out_off;
const uint8_t *type = inbound ? g->in_type : g->out_type;
int n = 0;
for (uint32_t e = off[id]; e < off[id + 1]; e++) {
n += (int)((mask >> type[e]) & 1U);
}
return n;
}
size_t cbm_graph_mem_bytes(const cbm_graph_mem_t *g) {
return g ? g->bytes : 0;
}
/* Visited set for one BFS: open addressing over id + 1 (0 marks a free slot). */
typedef struct {
uint32_t *slots;
size_t cap;
size_t count;
} gm_set_t;
static size_t gm_set_home(uint32_t id, size_t mask) {
return (size_t)(id * GM_HASH_MUL) & mask;
}
static bool gm_set_grow(gm_set_t *s) {
size_t cap = s->cap ? s->cap * GM_GROWTH : GM_SET_MIN_CAP;
uint32_t *slots = cbm_calloc(CBM_MEM_CLASS_GRAPH_CACHE, cap * sizeof(uint32_t));
if (!slots) {
return false;
}
for (size_t i = 0; i < s->cap; i++) {
uint32_t key = s->slots[i];
if (key) {
size_t j = gm_set_home(key - 1, cap - 1);
while (slots[j]) {
j = (j + 1) & (cap - 1);
}
slots[j] = key;
}
}
gm_free_ptr(s->slots);
s->slots = slots;
s->cap = cap;
return true;
}
/* 1 = added, 0 = already present, -1 = out of memory. */
static int gm_set_add(gm_set_t *s, uint32_t id) {
if ((s->count + 1) * GM_SET_LOAD_DEN > s->cap * GM_SET_LOAD_NUM && !gm_set_grow(s)) {
return -1;
}
size_t mask = s->cap - 1;
for (size_t i = gm_set_home(id, mask);; i = (i + 1) & mask) {
if (s->slots[i] == 0) {
s->slots[i] = id + 1;
s->count++;
return 1;
}
if (s->slots[i] == id + 1) {
return 0;
}
}
}
typedef struct {
uint32_t *ids;
size_t count;
size_t cap;
} gm_list_t;
static bool gm_list_push(gm_list_t *l, uint32_t id) {
if (!gm_grow_u32(&l->ids, &l->cap, l->count + 1)) {
return false;
}
l->ids[l->count++] = id;
return true;
}
typedef struct {
cbm_graph_mem_hop_t *rows;
size_t count;
size_t cap;
} gm_hops_t;
static bool gm_hops_push(gm_hops_t *h, uint32_t id, int hop) {
if (h->count == h->cap) {
size_t next = h->cap ? h->cap * GM_GROWTH : GM_SET_MIN_CAP;
cbm_graph_mem_hop_t *rows =
cbm_realloc(CBM_MEM_CLASS_GRAPH_CACHE, h->rows, next * sizeof(cbm_graph_mem_hop_t));
if (!rows) {
return false;
}
h->rows = rows;
h->cap = next;
}
h->rows[h->count].id = id;
h->rows[h->count].hop = hop;
h->count++;
return true;
}
static int gm_hop_id_cmp(const void *pa, const void *pb) {
const cbm_graph_mem_hop_t *a = pa;
const cbm_graph_mem_hop_t *b = pb;
return (a->id > b->id) - (a->id < b->id);
}
/* One BFS level: expand every frontier node over the masked edges. A node is
* first reached at its shortest distance; the start is never re-entered (its
* neighbours were all reached at hop 1), only recorded once at the length of
* the shortest cycle back to it — the CTE's (start, hop>0) row. */
typedef struct {
const uint32_t *off;
const uint32_t *nbr;
const uint8_t *type;
cbm_graph_mem_types_t mask;
uint32_t start;
bool start_back;
gm_set_t seen;
gm_hops_t out;
} gm_walk_t;
static bool gm_expand_level(gm_walk_t *w, const gm_list_t *frontier, gm_list_t *next, int hop) {
for (size_t f = 0; f < frontier->count; f++) {
uint32_t u = frontier->ids[f];
for (uint32_t e = w->off[u]; e < w->off[u + 1]; e++) {
if (((w->mask >> w->type[e]) & 1U) == 0) {
continue;
}
uint32_t v = w->nbr[e];
if (v == w->start) {
if (!w->start_back) {
w->start_back = true;
if (!gm_hops_push(&w->out, v, hop)) {
return false;
}
}
continue;
}
int added = gm_set_add(&w->seen, v);
if (added < 0) {
return false;
}
if (added > 0 && (!gm_hops_push(&w->out, v, hop) || !gm_list_push(next, v))) {
return false;
}
}
}
return true;
}
bool cbm_graph_mem_bfs(const cbm_graph_mem_t *g, int64_t start, bool inbound,
cbm_graph_mem_types_t mask, int max_depth, cbm_graph_mem_hop_t **out,
int *count) {
*out = NULL;
*count = 0;
if (!g || max_depth < 1 || mask == 0 || start < 0 || start >= (int64_t)g->n_ids) {
return true; /* nothing reachable: the CTE yields only the anchor */
}
gm_walk_t w = {
.off = inbound ? g->in_off : g->out_off,
.nbr = inbound ? g->in_nbr : g->out_nbr,
.type = inbound ? g->in_type : g->out_type,
.mask = mask,
.start = (uint32_t)start,
};
gm_list_t frontier = {0};
gm_list_t next = {0};
bool ok = gm_list_push(&frontier, w.start);
for (int hop = 1; ok && hop <= max_depth && frontier.count > 0; hop++) {
size_t level_begin = w.out.count;
next.count = 0;
ok = gm_expand_level(&w, &frontier, &next, hop);
if (ok && w.out.count - level_begin > 1) {
qsort(w.out.rows + level_begin, w.out.count - level_begin, sizeof(cbm_graph_mem_hop_t),
gm_hop_id_cmp);
}
gm_list_t swap = frontier;
frontier = next;
next = swap;
}
gm_free_ptr(frontier.ids);
gm_free_ptr(next.ids);
gm_free_ptr(w.seen.slots);
if (!ok || w.out.count > (size_t)INT32_MAX) {
gm_free_ptr(w.out.rows);
return false;
}
*out = w.out.rows;
*count = (int)w.out.count;
return true;
}
void cbm_graph_mem_hops_free(cbm_graph_mem_hop_t *hops) {
gm_free_ptr(hops);
}
/* ── Registry introspection ─────────────────────────────────────── */
int cbm_graph_mem_cached_count(void) {
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
int n = 0;
for (cbm_graph_mem_t *g = g_layers; g; g = g->next) {
n++;
}
sqlite3_mutex_leave(mu);
return n;
}
size_t cbm_graph_mem_cached_bytes(void) {
#ifdef CBM_ENABLE_TEST_SEAMS
if (g_cached_bytes_seam) {
return g_cached_bytes_seam;
}
#endif
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
size_t bytes = g_total_bytes;
sqlite3_mutex_leave(mu);
return bytes;
}
uint64_t cbm_graph_mem_build_count(void) {
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
uint64_t n = g_builds;
sqlite3_mutex_leave(mu);
return n;
}
void cbm_graph_mem_drop_idle(void) {
sqlite3_mutex *mu = gm_registry_mutex();
sqlite3_mutex_enter(mu);
cbm_graph_mem_t *g = g_layers;
while (g) {
cbm_graph_mem_t *next = g->next;
if (g->ready && g->refs == 0) {
gm_retire(g);
}
g = next;
}
sqlite3_mutex_leave(mu);
}