view release on metacpan or  search on metacpan

graph.h  view on Meta::CPAN

            __asm__ volatile("yield" ::: "memory");
#endif
            continue;
        }
        __atomic_add_fetch(&hdr->mutex_waiters, 1, __ATOMIC_RELAXED);
        uint32_t cur = __atomic_load_n(&hdr->mutex, __ATOMIC_RELAXED);
        if (cur != 0) {
            long rc = syscall(SYS_futex, &hdr->mutex, FUTEX_WAIT, cur,
                              &graph_lock_timeout, NULL, 0);
            if (rc == -1 && errno == ETIMEDOUT && cur >= GRAPH_MUTEX_BIT) {
                uint32_t pid = cur & GRAPH_MUTEX_PID;
                if (!graph_pid_alive(pid) &&
                    __atomic_compare_exchange_n(&hdr->mutex, &cur, 0,
                            0, __ATOMIC_ACQ_REL, __ATOMIC_RELAXED)) {
                    /* Recovered — wake one waiter so it can proceed. */
                    syscall(SYS_futex, &hdr->mutex, FUTEX_WAKE, 1, NULL, NULL, 0);
                }
            }
        }
        __atomic_sub_fetch(&hdr->mutex_waiters, 1, __ATOMIC_RELAXED);
        spin = 0;
    }
}

static inline void graph_mutex_unlock(GraphHeader *hdr) {
    __atomic_store_n(&hdr->mutex, 0, __ATOMIC_RELEASE);
    if (__atomic_load_n(&hdr->mutex_waiters, __ATOMIC_RELAXED) > 0)
        syscall(SYS_futex, &hdr->mutex, FUTEX_WAKE, 1, NULL, NULL, 0);
}

/* ================================================================
 * Bitmap helpers
 * ================================================================ */

static inline int graph_bit_set(uint64_t *bm, uint32_t idx) {
    uint64_t word = __atomic_load_n(&bm[idx / 64], __ATOMIC_ACQUIRE);
    return (word >> (idx % 64)) & 1;
}

static inline int32_t graph_bit_alloc(uint64_t *bm, uint32_t bwords, uint32_t max) {
    for (uint32_t w = 0; w < bwords; w++) {
        uint64_t word = __atomic_load_n(&bm[w], __ATOMIC_RELAXED);
        if (word == ~(uint64_t)0) continue;
        int bit = __builtin_ctzll(~word);
        uint32_t idx = w * 64 + bit;
        if (idx >= max) return -1;
        __atomic_fetch_or(&bm[w], (uint64_t)1 << bit, __ATOMIC_RELEASE);
        return (int32_t)idx;
    }
    return -1;
}

static inline void graph_bit_free(uint64_t *bm, uint32_t idx) {
    __atomic_fetch_and(&bm[idx / 64], ~((uint64_t)1 << (idx % 64)), __ATOMIC_RELEASE);
}

/* ================================================================
 * Graph operations (must hold mutex)
 * ================================================================ */

static inline int32_t graph_add_node_locked(GraphHandle *h, int64_t data) {
    int32_t idx = graph_bit_alloc(h->node_bitmap, h->node_bwords, h->hdr->max_nodes);
    if (idx < 0) return -1;
    h->node_data[idx] = data;
    h->node_heads[idx] = GRAPH_NONE;
    __atomic_fetch_add(&h->hdr->node_count, 1, __ATOMIC_RELAXED);
    return idx;
}

static inline int graph_add_edge_locked(GraphHandle *h, uint32_t src, uint32_t dst, int64_t weight) {
    if (src >= h->hdr->max_nodes || dst >= h->hdr->max_nodes) return 0;
    if (!graph_bit_set(h->node_bitmap, src) || !graph_bit_set(h->node_bitmap, dst))
        return 0;
    int32_t eidx = graph_bit_alloc(h->edge_bitmap, h->edge_bwords, h->hdr->max_edges);
    if (eidx < 0) return 0;
    h->edges[eidx].dst = dst;
    h->edges[eidx].weight = weight;
    h->edges[eidx].next = h->node_heads[src];
    h->node_heads[src] = (uint32_t)eidx;
    __atomic_fetch_add(&h->hdr->edge_count, 1, __ATOMIC_RELAXED);
    return 1;
}

static inline int graph_remove_node_locked(GraphHandle *h, uint32_t node) {
    if (node >= h->hdr->max_nodes) return 0;
    if (!graph_bit_set(h->node_bitmap, node)) return 0;
    /* free all outgoing edges */
    uint32_t eidx = h->node_heads[node];
    while (eidx != GRAPH_NONE) {
        uint32_t next = h->edges[eidx].next;
        graph_bit_free(h->edge_bitmap, eidx);
        __atomic_fetch_sub(&h->hdr->edge_count, 1, __ATOMIC_RELAXED);
        eidx = next;
    }
    h->node_heads[node] = GRAPH_NONE;
    graph_bit_free(h->node_bitmap, node);
    __atomic_fetch_sub(&h->hdr->node_count, 1, __ATOMIC_RELAXED);
    return 1;
}

/* Like remove_node_locked, but also splices every other node's adjacency
 * list to drop edges pointing TO `node` (incoming edges). O(N+E). */
static inline int graph_remove_node_full_locked(GraphHandle *h, uint32_t node) {
    if (node >= h->hdr->max_nodes) return 0;
    if (!graph_bit_set(h->node_bitmap, node)) return 0;
    uint32_t max_n = h->hdr->max_nodes;
    for (uint32_t src = 0; src < max_n; src++) {
        if (src == node) continue;
        if (!graph_bit_set(h->node_bitmap, src)) continue;
        uint32_t *slot = &h->node_heads[src];
        uint32_t eidx = *slot;
        while (eidx != GRAPH_NONE) {
            uint32_t next = h->edges[eidx].next;
            if (h->edges[eidx].dst == node) {
                *slot = next;
                graph_bit_free(h->edge_bitmap, eidx);
                __atomic_fetch_sub(&h->hdr->edge_count, 1, __ATOMIC_RELAXED);
            } else {
                slot = &h->edges[eidx].next;
            }
            eidx = next;
        }
    }
    return graph_remove_node_locked(h, node);
}

/* ================================================================
 * Public API (lock + operation + unlock)
 * ================================================================ */

static inline int32_t graph_add_node(GraphHandle *h, int64_t data) {
    graph_mutex_lock(h->hdr);
    int32_t r = graph_add_node_locked(h, data);
    __atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
    graph_mutex_unlock(h->hdr);
    return r;
}

static inline int graph_add_edge(GraphHandle *h, uint32_t src, uint32_t dst, int64_t weight) {
    graph_mutex_lock(h->hdr);
    int r = graph_add_edge_locked(h, src, dst, weight);
    __atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
    graph_mutex_unlock(h->hdr);
    return r;
}

static inline int graph_remove_node(GraphHandle *h, uint32_t node) {
    graph_mutex_lock(h->hdr);
    int r = graph_remove_node_locked(h, node);
    __atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
    graph_mutex_unlock(h->hdr);
    return r;
}

static inline int graph_remove_node_full(GraphHandle *h, uint32_t node) {
    graph_mutex_lock(h->hdr);
    int r = graph_remove_node_full_locked(h, node);
    __atomic_fetch_add(&h->hdr->stat_ops, 1, __ATOMIC_RELAXED);
    graph_mutex_unlock(h->hdr);
    return r;
}

static inline int graph_has_node(GraphHandle *h, uint32_t node) {
    if (node >= h->hdr->max_nodes) return 0;
    return graph_bit_set(h->node_bitmap, node);
}

/* Caller must hold graph_mutex and have verified node is live via bitmap. */
static inline uint32_t graph_degree(GraphHandle *h, uint32_t node) {
    if (node >= h->hdr->max_nodes) return 0;
    uint32_t count = 0;
    uint32_t eidx = h->node_heads[node];
    while (eidx != GRAPH_NONE) {
        count++;
        eidx = h->edges[eidx].next;
    }
    return count;
}

/* ================================================================
 * Create / Open / Close
 * ================================================================ */

#define GRAPH_ERR(fmt, ...) do { if (errbuf) snprintf(errbuf, GRAPH_ERR_BUFLEN, fmt, ##__VA_ARGS__); } while(0)

static inline uint64_t graph_total_size(uint32_t max_nodes, uint32_t max_edges) {
    uint32_t nb = (max_nodes + 63) / 64;
    uint32_t eb = (max_edges + 63) / 64;
    uint64_t node_data_off   = sizeof(GraphHeader);
    uint64_t node_heads_off  = node_data_off + (uint64_t)max_nodes * sizeof(int64_t);
    uint64_t node_bitmap_off = node_heads_off + (uint64_t)max_nodes * sizeof(uint32_t);
    uint64_t edge_data_off   = node_bitmap_off + (uint64_t)nb * 8;
    uint64_t edge_bitmap_off = edge_data_off + (uint64_t)max_edges * sizeof(GraphEdge);
    return edge_bitmap_off + (uint64_t)eb * 8;
}

static inline void graph_init_header(void *base, uint32_t max_nodes, uint32_t max_edges,
                                      uint64_t total) {
    uint32_t nb = (max_nodes + 63) / 64;
    uint64_t node_data_off   = sizeof(GraphHeader);
    uint64_t node_heads_off  = node_data_off + (uint64_t)max_nodes * sizeof(int64_t);
    uint64_t node_bitmap_off = node_heads_off + (uint64_t)max_nodes * sizeof(uint32_t);
    uint64_t edge_data_off   = node_bitmap_off + (uint64_t)nb * 8;
    uint64_t edge_bitmap_off = edge_data_off + (uint64_t)max_edges * sizeof(GraphEdge);

    GraphHeader *hdr = (GraphHeader *)base;
    memset(base, 0, (size_t)total);
    hdr->magic           = GRAPH_MAGIC;
    hdr->version         = GRAPH_VERSION;
    hdr->max_nodes       = max_nodes;
    hdr->max_edges       = max_edges;
    hdr->total_size      = total;
    hdr->node_data_off   = node_data_off;
    hdr->node_heads_off  = node_heads_off;
    hdr->node_bitmap_off = node_bitmap_off;
    hdr->edge_data_off   = edge_data_off;
    hdr->edge_bitmap_off = edge_bitmap_off;