.. Core Utilities documentation master file, created by sphinx-quickstart You can adapt this file completely to your liking, but it should at least contain the root `toctree` directive. Welcome to CSalt++ documentation! ================================= The `csalt++` project is a modern C++ library designed for safety-critical and high-performance applications requiring MISRA C++ compliance. It provides comprehensive error handling and efficient numerical computing with matrices and vectors, with optional compile-time exclusion of dynamic allocation for embedded and safety-critical systems. This library builds upon the ideas developed in the original C version of CSalt, enhancing them with templates, operator overloading, and runtime format adaptation, while maintaining compliance with MISRA C++ guidelines through careful design choices including optional static-only compilation, fixed-size buffers, and predictable behavior. CSalt++ targets performance-critical applications such as automotive systems, aerospace software, medical devices, scientific simulations, and engineering solvers where both safety and performance are paramount. It provides SIMD-accelerated numerical operations with support for x86 instruction sets (AVX2, AVX-512, SSE2, SSE3, SSE4.1) and ARM architectures (NEON, SVE, SVE2). Why CSalt++ ########### C++ offers many improvements over C, but working with numerical data still involves challenges: * On the fly dynamic memory allocation which drives time complexity * Standard exception handling violates MISRA C++ rules (dynamic allocation, non-deterministic behavior) * Most C++ libraries cannot disable dynamic allocation for safety-critical use CSalt++ addresses these issues by offering: * Custom allocators for dynamic memory management * MISRA C++ compliant error hierarchy with zero dynamic allocation * `Expected` for deterministic, exception-free error handling * `STATIC_ONLY` flag to exclude all dynamic allocation at compile time * Dual-mode design: full features with dynamic allocation OR static-only for certification * Predictable, auditable behavior suitable for certification Core Features ############# Error Classes ------------- * **STL-independent exception hierarchy** - Alternative to standard library exceptions with no dynamic allocation * **Three-level taxonomy** - Base Error → 9 categories → 40+ specific types (e.g., Error → ArgumentError → NullPointerError) * **Fixed-size messages** - All errors use 256-byte stack buffers, ensuring predictable memory usage * **Default messages** - Each error type has a predefined message that can be overridden via constructor * **Message composition** - Helper methods for prepending/appending context to standard messages * **Dual-use design** - Works with traditional ``throw``/``catch`` or modern ``Expected`` pattern * **MISRA compliant** - Available in both standard and ``STATIC_ONLY`` modes * **Type-safe handling** - Catch specific errors (``DivByZeroError``), categories (``MathError``), or base (``Error``) Expected Class -------------- * **Errors as values** - Type-safe representation of computations that may succeed (``T``) or fail (``Error``) * **Explicit error handling** - Forces callers to check for errors before accessing values, preventing forgotten checks * **Zero overhead** - No exception unwinding, no dynamic allocation, deterministic performance * **Stack-based storage** - ``sizeof(Expected) = sizeof(bool) + sizeof(T) + sizeof(Error)`` * **Simple API** - ``setValue()``/``setError()`` to construct, ``hasValue()``/``hasError()`` to query, ``value()``/``error()`` to access * **Safe defaults** - ``valueOr()`` method provides fallback values without checking * **Bool conversion** - Use in conditionals: ``if (result) { /* success */ }`` * **MISRA compliant** - Fully compliant in both standard and ``STATIC_ONLY`` modes * **Recommended pattern** - Preferred over exceptions for safety-critical and real-time code Smart Pointers -------------- * **RAII ownership** - ``UniquePtr`` provides deterministic single-owner lifetime management with custom deleters * **Shared ownership** - ``SharedPtr`` provides reference-counted shared ownership with allocator-aware control blocks * **Weak references** - ``WeakPtr`` enables non-owning observation of shared resources without extending lifetime * **Allocator-aware** - All pointer types work with the full allocator hierarchy (heap, arena, buddy, slab) * **No standard library dependency** - Independent implementation compatible with ``STATIC_ONLY`` mode * **Custom deleters** - Full support for user-defined cleanup logic via the deleter template parameter * **Type-safe** - Strongly typed ownership semantics prevent common dangling pointer and double-free bugs Array ----- * **Generic container** - ``Array`` supports any element type via template parameter ``T`` * **Allocator-backed** - Both the container struct and its element buffer are allocated through the provided allocator * **Factory pattern** - Creation via ``Array::init()`` returning ``Expected*>`` prevents uninitialised instances * **Tiered growth** - Automatic buffer growth uses a five-tier strategy to avoid runaway allocation at large sizes * **Bounds-checked access** - ``operator[]`` returns ``Expected`` for safe reads; ``set()`` returns ``Expected`` for safe writes * **In-place algorithms** - ``sort()``, ``reverse()``, ``clear()``, and ``concat()`` operate without additional allocation * **SIMD-accelerated** - ``reverse()`` and ``min()``/``max()`` dispatch to the best available SIMD back-end at compile time * **Search** - ``contains()``, ``binary_search()``, and ``bracketed_binary_search()`` provide O(1)–O(log n) lookup * **Transformations** - ``slice()`` and ``cumulative()`` produce new arrays from existing data Dictionary ---------- * **Generic hash map** - ``Dict`` maps keys of any trivially copyable type ``K`` to values of type ``V`` * **Allocator-backed** - Both the ``Dict`` struct and every internal node are allocated through the provided allocator * **Factory pattern** - Creation via ``Dict::init()`` returning ``Expected*>`` prevents uninitialised instances * **MurmurHash3** - High-quality hash function operating on raw key bytes with configurable seed * **Chained collision resolution** - Singly-linked bucket chains handle hash collisions without probing * **Optional growth** - Automatic resize when load factor exceeds 0.75; can be disabled for fixed-capacity use * **String key support** - ``StringKey`` provides a trivially copyable fixed-size wrapper for string keys * **Templated iteration** - ``foreach()`` accepts any callable with signature ``void(const K&, const V&)`` * **Copy and merge** - ``copy()`` and ``merge()`` factory methods build new dictionaries from existing ones List ---- * **Generic singly linked container** - ``SList`` stores elements of any type ``T`` using a node-based template design * **Allocator-backed** - The list struct, slab storage, and optional overflow nodes are all allocated through the provided allocator * **Factory pattern** - Creation via ``SList::init()`` returning ``Expected*>`` prevents uninitialised instances * **Hybrid node storage** - Initial nodes are drawn from a contiguous slab for improved locality, with optional overflow allocation beyond slab capacity * **Recycled slab nodes** - Removed slab-backed nodes are tracked internally and reused by future push operations * **Configurable overflow** - Overflow allocation can be enabled for dynamic growth or disabled for deterministic fixed-capacity behavior * **Safe list operations** - ``push_*()``, ``pop_*()``, ``get()``, and peek functions return explicit success or error state where appropriate * **List-oriented algorithms** - ``reverse()``, ``clear()``, ``concat()``, ``copy()``, ``contains()``, and ``foreach()`` provide common linked-list functionality * **RAII cleanup** - ``SListDeleter`` works with ``UniquePtr`` to automatically reclaim all list-owned memory Heap ---- * **Generic binary heap** - ``Heap`` provides priority-ordered access to any element type ``T`` with compile-time comparator ``Compare`` * **Array-backed storage** - All element storage, tiered growth, and buffer management are delegated to an owned ``Array`` instance * **Factory pattern** - Creation via ``Heap::init()`` returning ``Expected*>`` prevents uninitialised instances * **Flexible ordering** - Pass ``std::less`` for a max-heap, ``std::greater`` for a min-heap, or any lambda/functor for custom priority ordering * **No operator< requirement** - When a lambda or custom functor is used as the comparator, the element type needs no comparison operators * **Optional growth** - Automatic buffer growth using Array's tiered strategy; can be disabled for deterministic fixed-capacity use * **O(log n) push and pop** - Sift-up and sift-down maintain the heap property on every mutation * **Templated iteration** - ``foreach()`` accepts any callable with signature ``void(const T&)``; for ordered traversal, copy the heap and pop in a loop * **RAII cleanup** - ``HeapDeleter`` works with ``UniquePtr`` to automatically reclaim the heap struct and its backing array AVL Tree -------- * **Generic balanced binary search tree** - ``AVLTree`` provides ordered storage and lookup for any element type ``T`` using a compile-time comparator ``Compare`` * **Allocator-backed** - The tree struct, node slab, and optional overflow nodes are all allocated through the provided allocator * **Factory pattern** - Creation via ``AVLTree::init()`` returning ``Expected*>`` prevents uninitialised instances * **Self-balancing structure** - Maintains AVL height invariants through rotations, ensuring O(log n) insertion, removal, and lookup * **Hybrid node storage** - Initial nodes are allocated from a contiguous slab for improved locality, with optional overflow allocation beyond slab capacity * **Recycled slab nodes** - Removed slab-backed nodes are returned to an internal free list and reused before allocating new nodes * **Configurable overflow** - Overflow allocation can be enabled for dynamic growth or disabled for deterministic fixed-capacity behavior * **Comparator-driven ordering** - Ordering is defined by a three-way comparator, allowing custom sort behavior without requiring ``operator<`` * **Duplicate policy control** - Duplicate insertion can be enabled (multiset behavior) or disabled (set behavior) at initialization * **Safe tree operations** - ``insert()``, ``remove()``, ``find()``, ``min()``, ``max()``, and traversal methods return explicit success or error state where appropriate * **Ordered traversal** - ``foreach()`` provides in-order traversal; ``foreach_range()`` supports efficient range queries with subtree pruning * **RAII cleanup** - ``AVLTreeDeleter`` works with ``UniquePtr`` to automatically reclaim the tree, slab, and any overflow nodes Typical Use Cases ################# * Embedded software * Engineering calculations (FEM, CFD, PDEs) * Adaptive data structures for large numerical grids * Real-time simulation or optimization .. toctree:: :maxdepth: 1 :caption: Modules: Utilities Smart Pointers Error Allocator String Array Dictionary List Heap Tree Indices and tables ================== * :ref:`genindex` * :ref:`modindex` * :ref:`search` Getting Started ############### Clone the repository: .. code-block:: bash git clone https://github.com/Jon-Webb-79/csaltcpp.git cd csalt++ CMake Build Instructions ------------------------ **Debug build (with tests):** .. code-block:: bash cd scripts/bash ./debug.sh **Static build (no tests):** .. code-block:: bash cd scripts/bash ./static.sh **Install system-wide (optional):** .. code-block:: bash sudo ./install.sh Run Unit Tests -------------- .. code-block:: bash cd build/debug ./unit_tests You may optionally run under `valgrind` (Linux only): .. code-block:: bash valgrind ./unit_tests Dependencies ############ Required: * C++ compiler supporting C++17 (tested with GCC 14.2.1 and Clang 16.0.6) * CMake ≥ 3.31.3 * CMocka (for unit tests) Optional: * valgrind (memory leak detection) * Python 3.10+ and Sphinx (for documentation) Work Forward ############ * Complete development of List, BTree, Queue, and Matrix containers * Refactor SIMD fast paths into classes to simplify type based ingestion * Test on a wider array of platforms and compilers to exercise all SIMD instruction sets * Add basic matrix solvers for Dense and Sparse (i.e. COO, CSR, CSC) matrices in ``lin_alg.hpp`` file * Add root solvers, numerical integration, and numerical differentiation in ``numerical.hpp`` file. * Add more advancec matrix solvers such as JFNK method. Development & Contribution ########################## This library is modular and extensible. Contributions are welcome! 1. Fork the repo and create a branch 2. Write or update code 3. Add tests in the `test` directory 4. Ensure tests pass under `debug` mode 5. Update or add Sphinx docstrings 6. Submit a pull request Documentation ############# Build the documentation using Sphinx: .. code-block:: bash cd docs/doxygen python3 -m venv .venv source .venv/bin/activate pip install -r requirements.txt make html Documentation is also hosted online: TBD License ####### CSalt++ is provided under the MIT License. See the `LICENSE` file for details.