Architecture - osvaldoandrade/ova-lib GitHub Wiki

Architecture

Read this page when you need the library shape before you choose a module. The main points are the public API style, the ownership boundary, the result-lifetime rule, and the concurrency boundary.

One Public API Style

Every module uses the method-table struct pattern. list, queue, stack, heap, map, set, tree, trie, graph, bloom_filter, deque, matrix, vector, solver, lp_problem, and sorter all share this shape.

Each module has a public struct whose fields are function pointers (insert, pop, search, free, …) and a void *impl opaque pointer to the internal implementation. A create_* factory function allocates the implementation, wires the function pointers, and returns a pointer to the public struct. All operations go through those fields: self->insert(self, ...), self->search(self, ...), self->free(self), and so on.

The struct fields are public API, not private implementation detail. If a page hides that fact, it hides part of the contract.

Module Map

Sequence and order: Containers, Lists, Queues and Stacks, Heaps and Priority Queues, Deque, Sorting. Headers: list.h, queue.h, stack.h, heap.h, deque.h, sort.h.

Keyed and membership lookup: Associative Structures, Maps, Sets, Trees, Trie, Bloom Filter. Headers: map.h, set.h, tree.h, trie.h, bloom_filter.h.

Graph structure and graph algorithms: Graphs. Header: graph.h.

Dense numeric state and linear programming: Numerics and Optimization, Matrix and Vector, Linear Programming Solver. Headers: matrix.h, solver.h.

Interface Map

flowchart LR
    subgraph MethodTable["Public struct + method table"]
        L[list]
        Q[queue]
        S[stack]
        H[heap]
        M[map]
        ST[set]
        T[tree]
        TR[trie]
        G[graph]
        BF[bloom_filter]
        D[deque]
        MX[matrix]
        V[vector]
        SV[solver]
        LP[lp_problem]
        SR[sorter]
    end

Ownership Stops at the Payload Boundary

The library allocates and frees its own buffers, nodes, buckets, adjacency storage, and numeric workspaces. It does not free the user payload pointers stored inside those structures.

If you store int *, char *, or application structs inside a list, queue, heap, map, tree, set, trie, or deque, the container will not free those payloads when the container is destroyed. The same rule applies to keys and values in map and tree.

Returned Objects Follow Two Rules

When a call returns a pointer already stored inside the data structure, that pointer is still caller-owned or application-owned. list->get, map->get, tree->search, tree->min, tree->max, set->to_list, and trie->search work that way.

When a call allocates a fresh object for the result, that fresh object belongs to the caller. graph->get_neighbors, traversal result lists, MST edge lists, graph->min_path, tree->range_query, trie->get_words_with_prefix, matrix operations, and simplex tableaux all follow that rule.

Concurrency Exists in One Place

Internal locking exists in HASH_TABLE and nowhere else.

HASH_TABLE wraps put, get, and remove with one mutex. HASH_MAP does not. No other public module adds internal synchronization. If more than one thread shares a list, queue, heap, tree, set, trie, graph, matrix, solver, or deque, synchronization belongs to the caller.