Veritable Lasagna (v0.14.1)

A Data Structures & Algorithms Library for C

Table of Contents

• Overview
• Features
• Roadmap
• Installation
  • Requirements
  • Option 1: Package Installation
  • Option 2: Embed as Subdirectory
  • Option 3: Manual Build
  • Configuration Options
• Usage Examples
• Testing
• Documentation
• License

---

Introduction

Veritable Lasagna (or VL for short) is a cross-platform library written in C11 that provides efficient implementations of common memory allocators, data structures, and algorithms. The API is inspired by the C++ Standard Template Library (STL), making it intuitive for developers familiar with C++, while maintaining pure C compatibility.

Key design principles:

• Minimum Dependencies: Relies almost entirely on the C standard library
• No Macro Templates: Clean API without macro-based generic programming
• Comprehensive Testing: Rigorous test suite ensures consistent behavior

Features

Veritable Lasagna provides a robust set of components:

Roadmap to v1.0.0

This roadmap outlines what is needed for Veritable Lasagna to be considered feature-complete. After v1.0.0, new features will be released in minor versions, while major releases will introduce significant architectural changes.

• Note: ABI Compatibility between minor version changes is not guaranteed until reaching v1.0.0.

All features must be cross-platform between POSIX and WIN32 systems.

Memory Management

• ✅ Memory blocks with metadata (vl_memory)
• ✅ Memory Pools (vl_pool, vl_async_pool)
• ✅ Arena Allocator (vl_arena)
• ✅ Data (De)Serialization (vl_msgpack)

Data Structures

• ✅ Buffer (vl_buffer)
• ✅ Stack (vl_stack)
• ✅ Queue (vl_queue)
• ✅ Deque (vl_deque)
• ✅ Linked List (vl_linked_list)
• ✅ Ordered Set (vl_set)
• ✅ Hash Table (vl_hashtable)

Algorithms

• ✅ Pseudo-random number generator (vl_rand)
• ✅ Hashing (vl_hash)
• ✅ Comparisons (vl_compare)
• ✅ Sorting
  • ✅ Available to vl_memory and vl_linked_list
  • ✅ Implicit to vl_set
• ✅ Search
  • ✅ Sorted (vl_memory)
  • ✅ Unsorted (vl_memory and vl_linked_list)
  • ✅ Implicit to vl_set and vl_hashtable

Async

• Primitives
  • ✅ Threads (vl_thread)
  • ✅ Atomic Types (vl_atomic)
  • ✅ Mutex (vl_mutex)
  • ✅ SRWLock (vl_srwlock)
  • ✅ Conditional Variable (vl_condition)
  • ✅ Semaphore (vl_semaphore)
• Data Structures
  • ✅ Lockless Async Memory Pool (vl_async_pool)
  • ✅ Lockless Async Queue (vl_async_queue)

Filesystem

• ❌ Directory listing
• ❌ Path handling

Other

• ✅ Runtime Dynamic Library Handling vl_dynlib

Code Samples

The following examples demonstrate how to use some of the most common data structures in Veritable Lasagna.

Linked List Example

Create, populate, and iterate through a linked list of integers:

#include <stdlib.h>
#include <stdio.h>
#include <vl/vl_linked_list.h>

int main(int argc, const char** argv) {
    // Create a new list of integers
    vl_list* list = vlListNew(sizeof(int));

    // Add 10 integers to the list
    for(int i = 0; i < 10; i++) {
        const int listValue = i;
        vlListPushBack(list, &listValue);
    }

    // Iterate through the list and print each value
    VL_LIST_FOREACH(list, curIter) {
        const int val = *((int*)vlListSample(list, curIter));
        printf("Value: %d\n", val);  // Added newline
    }

    // Clean up
    vlListDelete(list);
    return EXIT_SUCCESS;
}

Hash Table Example

Create a hash table mapping character names to their bank balances:

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <vl/vl_hashtable.h>

int main(int argc, const char** argv) {
    // Create a new hash table using string hashing
    vl_hashtable* wealthTable = vlHashTableNew(vlHashString);

    // Sample data
    const int numEntries = 5;
    const char* keys[] = {
        "McLovin",
        "Supercop",
        "Napoleon",
        "Terminator",
        "Loch Ness Monster"
    };
    const float values[] = {12.05f, 5.84f, 910.63f, 711.42f, 3.50f};

    // Populate the hash table
    for(int i = 0; i < numEntries; i++) {
        const char* key = keys[i];
        const float value = values[i];
        const int keyLen = strlen(key) + 1; // +1 to preserve null terminator
                                            // not strictly necessary, but somewhat handy

        // Insert the key and claim memory for the value
        const vl_hash_iter iter = vlHashTableInsert(wealthTable, key, keyLen, sizeof(float));

        // Assign the value to the memory owned by the table
        *((float*)vlHashTableSampleValue(wealthTable, iter, NULL)) = value;
    }

    // Iterate through all entries and print them
    VL_HASHTABLE_FOREACH(wealthTable, curIter) {
        // Get key and value sizes in bytes
        size_t keyLen, valLen;

        // Access the key and value data
        const char* key = (const char*)vlHashTableSampleKey(wealthTable, curIter, &keyLen);
        const float val = *((float*)vlHashTableSampleValue(wealthTable, curIter, &valLen));

        printf("%s has %.2f$ in the bank!\n", key, val);
        // If we didn't preserve the null terminator, length can be stated explicitly:
        // printf("%.*s has %.2f$ in the bank!", (int)keyLen, key, val);
    }

    // Clean up
    vlHashTableDelete(wealthTable);
    return EXIT_SUCCESS;
}

Ordered Set Example

Create a set that automatically sorts integers:

#include <stdlib.h>
#include <stdio.h>
#include <vl/vl_set.h>

int main(int argc, const char** argv) {
    // Sample data - unsorted integers
    const int set_size = 10;
    const int data[] = {6, 2, 9, 1, 3, 0, 4, 7, 5, 8};

    // Create a new set of integers using the integer comparison function
    vl_set* set = vlSetNew(sizeof(int), vlCompareInt);

    // Insert all values into the set (they will be automatically ordered)
    for(int i = 0; i < set_size; i++) {
        vlSetInsert(set, (void*)&(data[i]));
    }

    // Print the size and all values in the set (in sorted order)
    printf("Sorted %d elements:\n", vlSetSize(set));
    VL_SET_FOREACH(set, curIter) {
        const int value = *((int*)vlSetSample(curIter));
        printf("\t%d\n", value);
    }

    // Clean up
    vlSetDelete(set);
    
    return EXIT_SUCCESS;
}

Quick Start

Requirements

To build and use Veritable Lasagna, you'll need:

• A C11-compatible compiler (GCC, Clang, MSVC, etc.)
• CMake 3.22.1 or higher
• For testing: GoogleTest
• For documentation: Doxygen and Graphviz

Installation Options

There are three ways to incorporate Veritable Lasagna into your project:

Option 1 (Recommended): Automated Build & Install from Repo

Install with vcpkg (Cross-Platform)

git clone https://github.com/walkerje/veritable_lasagna.git
vcpkg install --overlay-ports=.\veritable_lasagna\vcpkg veritable-lasagna

Bash (Linux/MSYS/Cygwin/etc) (See install.sh first!)

wget -O - https://raw.githubusercontent.com/walkerje/veritable_lasagna/main/install.sh | bash -s -- --all

• Available options:
  • --build-type=TYPE : Set build type(s): Debug and/or Release (use semicolon for multiple)
  • --all : Build and install both Debug and Release configurations
  • --no-sudo : Don't use sudo for installation
  • --help : Show help message

Note: The installation path is determined by your CMake configuration.

You can reference the installation in your project by using find_package in your own CMakeLists.txt.

# 
# Your project setup...
#

find_package(VLasagna REQUIRED)

#
# Target setup...
#

target_link_libraries(my_target_name VLasagna::Core)

Option 2: Embed as Subdirectory

Start by cloning this project into your project directory or adding it as a git submodule.

• Submodule:

  git submodule add https://github.com/walkerje/veritable_lasagna.git
  git submodule update --init

• Clone:

  git clone https://github.com/walkerje/veritable_lasagna.git

Then, somewhere in your own CMakeLists.txt, have the following:

# 
# Your project setup...
#

add_subdirectory(veritable_lasagna)

#
# Target setup...
#

target_link_libraries(my_target_name VLasagna::Core)

Option 3: Manual Build and Install

Start by cloning this repo to your disk and moving into its directory.

git clone https://github.com/walkerje/veritable_lasagna.git
cd veritable_lasagna

Now create a build directory and use CMake to configure the build.

mkdir build && cd build
cmake -DCMAKE_BUILD_TYPE=Release ..

Finally, build the library.

cmake --build .

Installing this package to your system is as simple specifying the install target.

cmake --build . --target install

See Option 1 for a snippet on finding the installed package from your CMakeLists.txt

Configuration Options

These are the primary configuration options relevant to the library. Many of these are ubiquitous across CMake, but they are described here nonetheless.

Argument	Type	Default	Description
CMAKE_BUILD_TYPE	STRING	Toolchain Specific	Specifies the build configuration type. Common values: • Debug - No optimizations, includes debug info • Release - Full optimizations, no debug info • RelWithDebInfo - Full optimizations with debug info • MinSizeRel - Size optimizations
BUILD_SHARED_LIBS	BOOL	OFF	Global flag affecting the how the library is built: • ON - Libraries are built as shared/dynamic (DLL/SO) • OFF - Libraries are built as static (LIB/A)
BUILD_TESTING	BOOL	OFF	CTest module flag that controls test building: • ON - Configure to build tests via CTest and GTest • OFF - Skips building tests

Building and Running Tests

Veritable Lasagna includes comprehensive test suites powered by GoogleTest and CTest.

To build and run the tests:

# Clone the repository if you haven't already
git clone https://github.com/walkerje/veritable_lasagna.git
cd veritable_lasagna 

# Create build directory and configure with testing enabled
mkdir build && cd build
cmake -DBUILD_TESTING=ON ..

# Build the library and tests
cmake --build .

# Run the tests
cd test && ctest

The test results will show you which tests passed and failed, helping ensure the library works correctly on your system.

Testing & Coverage Build Options (GNU/Clang)

Option	Description	Default	Purpose
VL_ENABLE_COVERAGE	Enables code coverage reporting	OFF	Generates coverage reports showing which lines of code are executed during tests. Requires gcovr.
VL_ENABLE_ASAN	Enables AddressSanitizer	OFF	Detects memory errors like buffer overflows, use-after-free, memory leaks
VL_ENABLE_UBSAN	Enables UndefinedBehaviorSanitizer	OFF	Detects undefined behavior like integer overflow, null pointer dereference
VL_ENABLE_TSAN	Enables ThreadSanitizer	OFF	Detects data races and other threading issues

Usage example:

cmake -DBUILD_TESTING=ON -DVL_ENABLE_ASAN=ON -DVL_ENABLE_COVERAGE=ON

Note:

• These options are only available with GCC and Clang compilers
• Only one sanitizer should be enabled at a time (ASAN, TSAN, or UBSAN)
• Coverage reporting works best with Debug builds
• When using sanitizers, it's recommended to build in Debug mode for better error reporting

Generating Documentation

The project documentation is generated using Doxygen with Graphviz integration for diagrams. The documentation uses a modern theme that's included as a submodule.

Prerequisites

• Doxygen - Documentation generator (download)
• Graphviz - Graph visualization software (download)

To generate the documentation:

# Clone the repository if you haven't already
git clone https://github.com/walkerje/veritable_lasagna.git
cd veritable_lasagna

# Initialize the documentation theme submodule
git submodule update --init

# Generate the documentation
cd docs
doxygen

The generated documentation will be available in the docs/html directory. Open index.html in your browser to view it.

License

Veritable Lasagna is available under the MIT License. See the LICENSE file for details.

Back to Top