Pure C11 StandardsData Structures2024

C11 Core System

A highly optimized algorithmic engine designed in pure C11. This project simulates an enterprise-level recipe and supply management system subject to strict constraints on execution time and heap memory usage. Data structures such as custom hash tables with separate chaining, dynamic arrays, and a Min-Heap were implemented purely from scratch.

C11 Algorithmic Data Structures
Project Sheet
Role
Computer Science Tutor & Engineer
Type
C Systems Engine
Period
2024

Engine Internals

No libraries, no garbage collector. Just hand-written data structures and a strict discipline over memory ownership.

hashmap.c
1typedef struct Entry {2    char        *key;        // owned: strdup'd recipe id3    void        *value;      // owned: caller payload4    struct Entry *next;      // separate chaining5} Entry;67// O(1) average insert -- prepend into the bucket list8int hm_insert(HashMap *m, const char *key, void *val) {9    size_t h = fnv1a(key) % m->cap;10    Entry *e = malloc(sizeof *e);11    if (!e) return -1;12    e->key  = strdup(key);13    e->value = val;14    e->next = m->buckets[h];15    m->buckets[h] = e;16    m->len++;17    return 0;18}
O(1)

Hash Map - Separate Chaining

Linear product scans could not meet the timing budget. I chose separate chaining over open addressing to keep performance stable under a high load factor, sidestepping costly rehashing while the table is under pressure.

heap.c
1// array-backed min-heap of expiring batches2void heap_push(Heap *h, Batch b) {3    size_t i = h->len++;4    h->data[i] = b;                 // O(log n) sift-up5    while (i && h->data[PARENT(i)].exp > h->data[i].exp) {6        SWAP(h->data[PARENT(i)], h->data[i]);7        i = PARENT(i);8    }9}1011Batch heap_pop(Heap *h) {12    Batch top = h->data[0];         // earliest expiry13    h->data[0] = h->data[--h->len];14    sift_down(h, 0);                // O(log n)15    return top;16}
O(log n)

Array Min-Heap - Expiring Batches

Keeping expiring batches fully sorted would tax every insert. The array-backed heap shifts that cost to logarithmic access and extraction, with contiguous nodes in memory to avoid the fragmentation a linked-list approach would cause.

Complexity Profile

Recipe lookup
Hash MapO(1)
Recipe insert
Hash MapO(1)
Batch push
Min-HeapO(log n)
Extract-min
Min-HeapO(log n)
shorter bars = lower asymptotic cost

Ownership & Memory

HashMapowns →buckets[]
↳Entryowns →key + next
↳free()walks chain, frees each node
Valgrind Verified
==valgrind== HEAP SUMMARY:
   all heap blocks were freed
   0 bytes in 0 blocks lost
==valgrind== ERROR SUMMARY: 0 errors

With no garbage collector, every pointer was a potential leak. A strict ownership discipline over each allocation held up across repeated randomized stress suites, closing out under Valgrind with no reported memory leaks.

Key Contributions & Achievements

01

Designed and implemented a custom Hash Map with chaining to handle string-based recipe lookups in O(1) average time.

02

Engineered an array-based Min-Heap structure to manage expiring supply batches dynamically and extract items in O(log n) time.

03

Successfully delivered stable C11 code that passes extensive randomized algorithmic stress-testing suites perfectly, adhering to strict bounds for both time and space complexity.

04

Managed all heap memory allocations manually, ensuring absolutely zero memory leaks via precise garbage collection strategies across deeply nested pointer structures.

Core & Environment

C11 StandardsGCC CompilerValgrindAlgorithms & Data Structures

Get in Touch

Tell me about your project and I will get back to you fast. No fluff, no obligation.

Let's Discuss Your Project

Pick a time that works for you. We'll hop on a 30-minute discovery call to discuss your goals. There's absolutely zero obligation, and you'll receive free technical guidance regardless.

Chat on WhatsApp