Array indexed buddy allocator + hash table array indexed stringlist in C99

buddy.c

#include <stdio.h>
#include <assert.h>
#include <string.h>
#include <stdbool.h>
#include <stdlib.h>
#include <time.h>

// mt

typedef struct block_s block_t;
struct block_s
{
    size_t prev;
    size_t next;
    size_t padding[6]; // padding for more memory space and alignment
};

#define MAX_DEPTH 16

static block_t mem_pool[(1 << MAX_DEPTH) + 1];
static size_t heads[MAX_DEPTH + 1]; // ordered array indexed linked lists

#ifdef _DEBUG
typedef struct debug_glob_s debug_glob_t;
struct debug_glob_s
{
    size_t sizes[(1 << MAX_DEPTH) + 1];
    size_t depths[(1 << MAX_DEPTH) + 1];
};

static debug_glob_t debug_glob;
#endif

static void init_debug()
{
#ifdef _DEBUG
    memset(&debug_glob, 0, sizeof(debug_glob));
#endif
}

static void insert_node_debug(size_t node_num, size_t num_bytes, size_t depth)
{
    assert(depth <= MAX_DEPTH);
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

#ifdef _DEBUG
    assert(debug_glob.sizes[node_num] == 0);
    assert(debug_glob.depths[node_num] == 0);

    debug_glob.sizes[node_num] = num_bytes;
    debug_glob.depths[node_num] = depth;
#endif
}

static void remove_node_debug(size_t node_num, size_t num_bytes, size_t depth)
{
    assert(depth <= MAX_DEPTH);
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

#ifdef _DEBUG
    assert(debug_glob.sizes[node_num] == num_bytes);
    assert(debug_glob.depths[node_num] == depth);

    debug_glob.sizes[node_num] = 0;
    debug_glob.depths[node_num] = 0;
#endif
}

static size_t get_buddy(size_t depth, size_t node_num)
{
    assert(depth < MAX_DEPTH); // there is no buddy at the top
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

    return ((node_num - 1) ^ ((size_t)1 << depth)) + 1; // buddy index is the XOR of the current index and 2^depth
}

static size_t get_depth(size_t num_bytes)
{
    size_t cur_num = sizeof(block_t);
    size_t depth = 0;
    while (cur_num != 0 && cur_num < num_bytes)
    {
        cur_num <<= 1;
        depth++;
    }

    return depth;
}

static bool node_in_head(size_t depth, size_t node_num)
{
    assert(depth <= MAX_DEPTH);
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

    for (size_t i = heads[depth]; i != 0; i = mem_pool[i].next)
    {
        if (i == node_num)
        {
            return true;
        }

        // since list is sorted, we can stop early if i exceeds what we are searching for
        if (i > node_num)
        {
            break;
        }
    }

    return false;
}

static void remove_from_head(size_t depth, size_t node_num)
{
    assert(depth <= MAX_DEPTH);
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

    assert(node_in_head(depth, node_num));

    for (size_t i = heads[depth]; i != 0; i = mem_pool[i].next)
    {
        // since list is sorted, if i exceeds what we are looking for, then we can exit
        if (i > node_num)
        {
            break;
        }

        if (i != node_num)
        {
            continue;
        }

        if (i == heads[depth])
        {
            heads[depth] = mem_pool[heads[depth]].next;
        }

        mem_pool[mem_pool[i].prev].next = mem_pool[i].prev ? mem_pool[i].next : 0;
        mem_pool[mem_pool[i].next].prev = mem_pool[i].next ? mem_pool[i].prev : 0;
        return;
    }

    assert(false);
}

static void add_to_head(size_t depth, size_t node_num)
{
    assert(depth <= MAX_DEPTH);
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

    size_t i = heads[depth];
    size_t prev = 0;

    while (i != 0)
    {
        assert(i != node_num);

        // sort in accending order
        if (i > node_num)
        {
            break;
        }

        prev = i;
        i = mem_pool[i].next;
    }

    // n is largest num in list
    if (i == 0 && heads[depth] != 0)
    {
        // append to prev
        assert(prev != 0);
        mem_pool[node_num].prev = prev;
        mem_pool[node_num].next = i;
        mem_pool[prev].next = node_num;
        return;
    }

    // nothing in list, or i is greater than us
    if (heads[depth] == i)
    {
        heads[depth] = node_num;
    }

    // prepend to i
    mem_pool[node_num].next = i;
    mem_pool[node_num].prev = mem_pool[i].prev;
    mem_pool[mem_pool[i].prev].next = i && mem_pool[i].prev ? node_num : 0;
    mem_pool[i].prev = i ? node_num : 0;
}

void mt_print_heads()
{
    for (size_t d = 0; d < MAX_DEPTH + 1; d++)
    {
        size_t i = heads[d];

        printf("0x%02zX 0x%05zX", d, i);
        while (i != 0)
        {
            i = mem_pool[i].next;
            printf(" 0x%05zX", i);
        }

        printf("\n");
    }
}

void* mt_get_for_index(size_t index)
{
    assert(index > 0 && index < (1 << MAX_DEPTH) + 1);
#ifdef _DEBUG
    assert(debug_glob.sizes[index] != 0);
#endif

    return (void*)&mem_pool[index];
}

size_t mt_get_for_pointer(const void* p)
{
    size_t node_num = (block_t*)p - mem_pool;
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);
#ifdef _DEBUG
    assert(debug_glob.sizes[node_num] != 0);
#endif

    return node_num;
}

void* mt_alloc(size_t num_bytes)
{
    if (num_bytes == 0)
    {
        printf("zero alloc!\n");
        return NULL;
    }

    size_t depth_for_size = get_depth(num_bytes);
    size_t depth = depth_for_size;

    if (depth > MAX_DEPTH)
    {
        printf("depth too deep for size %zu\n", num_bytes);
        return NULL;
    }

    // find a free list that isnt empty
    while (heads[depth] == 0)
    {
        depth++;
        if (depth >= MAX_DEPTH)
        {
            break;
        }
    }

    if (depth > MAX_DEPTH || heads[depth] == 0)
    {
        printf("no free list for size %zu\n", num_bytes);
        return NULL;
    }

    size_t old_head = 0;
    while (depth >= depth_for_size)
    {
        old_head = heads[depth];

        // remove head node from list
        remove_from_head(depth, old_head);

        if (depth != depth_for_size)
        {
            // split the current node into two and add to below list
            add_to_head(depth - 1, old_head);
            add_to_head(depth - 1, get_buddy(depth - 1, old_head));
        }
        else if (depth == 0)
        {
            break; // prevent underflow and infinite loop
        }

        depth--;
    }

    insert_node_debug(old_head, num_bytes, depth_for_size);

#ifdef _DEBUG
    memset(&mem_pool[old_head], 0xCC, num_bytes);
#endif
    return mt_get_for_index(old_head);
}

void mt_free(void* p, size_t num_bytes)
{
    if (p == NULL || num_bytes == 0)
    {
        printf("Invalid free\n");
        return;
    }

    // get the index of the block
    size_t node_num = mt_get_for_pointer(p);
    size_t depth = get_depth(num_bytes);

    assert(depth <= MAX_DEPTH);
    assert(node_num > 0 && node_num < (1 << MAX_DEPTH) + 1);

#ifdef _DEBUG
    memset(p, 0, num_bytes);
#endif

    remove_node_debug(node_num, num_bytes, depth);

    // try to coalesce the block with its buddy
    while (depth < MAX_DEPTH)
    {
        size_t buddy = get_buddy(depth, node_num);

        if (!node_in_head(depth, buddy))
        {
            break;
        }

        // remove buddy from its free list
        remove_from_head(depth, buddy);

        // coalesce the current block with its buddy
        if (buddy < node_num)
        {
            node_num = buddy;
        }

        depth++;
    }

    // add the coalesced block to the appropriate free list
    add_to_head(depth, node_num);
}

void mt_init()
{
#ifdef _DEBUG
    memset(mem_pool, 0, sizeof(mem_pool));
    memset(heads, 0, sizeof(heads));
#endif

    // all heads are empty
    for (int i = 0; i < MAX_DEPTH; i++)
    {
        heads[i] = 0;
    }

    // we have only 1 free node, and its the largest one
    heads[MAX_DEPTH] = 1;
    mem_pool[1].prev = 0;
    mem_pool[1].next = 0;

    // zero node is placeholder/marker for end of list
    mem_pool[0].prev = 0;
    mem_pool[0].next = 0;

    init_debug();
}

// sl

#define HASH_TABLE_SIZE_BITS 14

enum
{
    STRING_LIST_HASH_STATUS_FREE,
    STRING_LIST_HASH_STATUS_MOVABLE,
    STRING_LIST_HASH_STATUS_HEAD,
};

typedef struct string_list_node_s string_list_node_t;
struct string_list_node_s
{
    struct
    {
        size_t next : HASH_TABLE_SIZE_BITS;
        size_t status : 2;
    };
    union
    {
        size_t prev;
        size_t astr;
    };
};

static string_list_node_t hash_table[1 << HASH_TABLE_SIZE_BITS];

#define STRING_REF_STR_PADDING 4
typedef struct string_ref_s string_ref_t;
struct string_ref_s
{
    struct
    {
        size_t len : 8;
        size_t ref_count : 24;
    };
    char str[STRING_REF_STR_PADDING];
};

static string_ref_t* get_ref_string(size_t astr)
{
    return (string_ref_t*)mt_get_for_index(astr);
}

static size_t hash_code(const char* str, size_t len)
{
    // len contains nullchar
    assert(str[len - 1] == '\0');

    assert(str != NULL);

    if (len >= 0xFF)
    {
        return ((len >> 2) % ((1 << HASH_TABLE_SIZE_BITS) - 1)) + 1;
    }

    size_t hash;
    for (hash = 0; len != 0; --len)
    {
        hash = 31 * hash + *str++;
    }

    return (hash % ((1 << HASH_TABLE_SIZE_BITS) - 1)) + 1;
}

static bool is_str_ref(const string_ref_t* ref, const char* str, size_t len)
{
    return (ref->len == len && !memcmp(ref->str, str, len));
}

static void free_for_len(size_t astr, size_t len)
{
    string_ref_t* ref = get_ref_string(astr);
    assert(ref != NULL);

    size_t head = hash_code(ref->str, len);

    assert(head != 0);
    assert(hash_table[head].status == STRING_LIST_HASH_STATUS_HEAD);

    mt_free(ref, len + (sizeof(string_ref_t) - STRING_REF_STR_PADDING));

    size_t remove = 0;
    size_t next = hash_table[head].next;
    assert(next != 0);
    assert(hash_table[next].status != STRING_LIST_HASH_STATUS_FREE);

    // check if this is the head
    if (hash_table[head].astr == astr)
    {
        // now check if this is the only thing in the list
        if (next == head)
        {
            // we will be removing the head
            remove = head;
        }
        else
        {
            assert(hash_table[next].status == STRING_LIST_HASH_STATUS_MOVABLE);

            // swap astrs
            hash_table[head].astr = hash_table[next].astr;

            // make the next in-line to be head
            hash_table[head].next = hash_table[next].next;
            remove = next;
        }
    }
    else
    {
        assert(hash_table[next].status == STRING_LIST_HASH_STATUS_MOVABLE);

        // search in the list for our guy
        size_t prev = head;

        while (hash_table[next].astr != astr)
        {
            prev = next;
            next = hash_table[next].next;

            assert(next != 0);
            assert(next != head); // freeing something that doesnt exist in the list
            assert(hash_table[next].status == STRING_LIST_HASH_STATUS_MOVABLE);
        }

        // remove what we found
        hash_table[prev].next = hash_table[next].next;
        remove = next;
    }

    assert(remove != 0);
    assert(hash_table[remove].status != STRING_LIST_HASH_STATUS_FREE);

    hash_table[remove].status = STRING_LIST_HASH_STATUS_FREE;

    // add to free list
    next = hash_table[0].next;

    hash_table[remove].next = next;
    hash_table[remove].prev = 0;

    hash_table[next].prev = remove;
    hash_table[0].next = remove;
}

static size_t alloc_string_ref(const char* str, size_t len)
{
    string_ref_t* ref = (string_ref_t*)mt_alloc(len + (sizeof(string_ref_t) - STRING_REF_STR_PADDING));

    if (ref == NULL)
    {
        printf("no memory avail\n");
        return 0;
    }

    memcpy(ref->str, str, len);
    ref->ref_count = 1;
    ref->len = len;

    size_t astr = mt_get_for_pointer(ref);
    assert(astr != 0);

    return astr;
}

static size_t find_str_in_list(size_t head, const char* str, size_t len)
{
    assert(hash_table[head].status == STRING_LIST_HASH_STATUS_HEAD);

    string_ref_t* ref = get_ref_string(hash_table[head].astr);
    assert(ref != NULL);

    // check for hash collision
    if (is_str_ref(ref, str, len))
    {
        return hash_table[head].astr;
    }

    // hash collision, check list for entries
    size_t prev = head;
    for (size_t next = hash_table[head].next; next != head; next = hash_table[next].next)
    {
        assert(next != 0);
        assert(hash_table[next].status == STRING_LIST_HASH_STATUS_MOVABLE);

        ref = get_ref_string(hash_table[next].astr);
        assert(ref != NULL);

        // check if its it
        if (is_str_ref(ref, str, len))
        {
            // move this to head of list as an optimization
            // make it so old head is second in list
            hash_table[prev].next = hash_table[next].next;
            hash_table[next].next = hash_table[head].next;
            hash_table[head].next = next;

            // swap vals with head
            size_t astr = hash_table[next].astr;
            hash_table[next].astr = hash_table[head].astr;
            hash_table[head].astr = astr;

            return astr;
        }

        prev = next;
    }

    return 0;
}

static void add_ref_to_string(string_ref_t* ref)
{
    assert(ref != NULL);

    ref->ref_count++;

    assert(ref->ref_count != 0);
}

static size_t get_ref_len(const string_ref_t* ref)
{
    assert(ref != NULL);

    size_t len = ref->len == 0 ? 0xFF : ref->len - 1;

    while (ref->str[len] != '\0')
    {
        len += 256;
    }

    return len;
}

static size_t find_for_len(const char* str, size_t len)
{
    size_t head = hash_code(str, len);
    assert(head != 0);

    // no entry for hash, not in list
    if (hash_table[head].status != STRING_LIST_HASH_STATUS_HEAD)
    {
        return 0;
    }

    // find it
    return find_str_in_list(head, str, len);
}

static size_t get_for_len(const char* str, size_t len)
{
    size_t hash = hash_code(str, len);
    assert(hash != 0);

    // check if a list exists
    if (hash_table[hash].status == STRING_LIST_HASH_STATUS_HEAD)
    {
        size_t astr = find_str_in_list(hash, str, len);
        if (astr != 0)
        {
            add_ref_to_string(get_ref_string(astr));
            return astr;
        }

        // not in list, add it.
        size_t next_free = hash_table[0].next;
        if (next_free == 0)
        {
            printf("no free nodes in free list\n");
            return 0;
        }

        // alloc our stuff
        astr = alloc_string_ref(str, len);
        if (astr == 0)
        {
            return 0;
        }

        // now remove from free list
        hash_table[0].next = hash_table[next_free].next;
        hash_table[hash_table[next_free].next].prev = 0;

        hash_table[next_free].status = STRING_LIST_HASH_STATUS_MOVABLE;

        // make this astr the head
        hash_table[next_free].astr = hash_table[hash].astr;
        hash_table[hash].astr = astr;

        // add node to head list
        hash_table[next_free].next = hash_table[hash].next;
        hash_table[hash].next = next_free;

        return astr;
    }

    // its movable, which means we need to move the current node somewhere else so we can use the spot
    if (hash_table[hash].status == STRING_LIST_HASH_STATUS_MOVABLE)
    {
        size_t next_free = hash_table[0].next;

        if (next_free == 0)
        {
            printf("no free nodes in free list\n");
            return 0;
        }

        size_t next = hash_table[hash].next;

        size_t prev = next;
        while (hash_table[prev].next != hash)
        {
            prev = hash_table[prev].next;
        }

        assert(prev != 0);

        // alloc our stuff
        size_t astr = alloc_string_ref(str, len);
        if (astr == 0)
        {
            return 0;
        }

        // remove from free list
        hash_table[0].next = hash_table[next_free].next;
        hash_table[hash_table[next_free].next].prev = 0;

        hash_table[prev].next = next_free;

        hash_table[next_free].status = STRING_LIST_HASH_STATUS_MOVABLE;
        hash_table[next_free].next = next;
        hash_table[next_free].astr = hash_table[hash].astr;

        // now make a head out of this
        hash_table[hash].status = STRING_LIST_HASH_STATUS_HEAD;
        hash_table[hash].next = hash;
        hash_table[hash].astr = astr;

        return astr;
    }

    assert(hash_table[hash].status == STRING_LIST_HASH_STATUS_FREE);

    // its free! lets use it
    // alloc our stuff
    size_t astr = alloc_string_ref(str, len);
    if (astr == 0)
    {
        return 0;
    }

    // remove this node from free list
    hash_table[hash_table[hash].prev].next = hash_table[hash].next;
    hash_table[hash_table[hash].next].prev = hash_table[hash].prev;

    // create a new list out of head
    hash_table[hash].status = STRING_LIST_HASH_STATUS_HEAD;
    hash_table[hash].next = hash;
    hash_table[hash].astr = astr;

    return astr;
}

void sl_remove_ref(size_t astr)
{
    string_ref_t* ref = get_ref_string(astr);
    assert(ref != NULL);

    size_t len = get_ref_len(ref) + 1;
    assert(len != 0);

    assert(ref->ref_count != 0);

    --ref->ref_count;

    if (ref->ref_count == 0)
    {
        free_for_len(astr, len);
    }
}

void sl_add_ref(size_t astr)
{
    string_ref_t* ref = get_ref_string(astr);
    assert(ref != NULL);

    add_ref_to_string(ref);
}

size_t sl_find(const char* str)
{
    return find_for_len(str, strlen(str) + 1);
}

size_t sl_get(const char* str)
{
    return get_for_len(str, strlen(str) + 1);
}

const char* sl_convert(size_t astr)
{
    if (astr == 0)
    {
        return NULL;
    }

    return get_ref_string(astr)->str;
}

void sl_init()
{
    // init free list, 0 is head
    hash_table[0].status = STRING_LIST_HASH_STATUS_FREE;
    size_t prev = 0;

    for (size_t hash = 1; hash < (1 << HASH_TABLE_SIZE_BITS); hash++)
    {
        hash_table[hash].status = STRING_LIST_HASH_STATUS_FREE;
        hash_table[hash].prev = prev;

        hash_table[prev].next = hash;

        prev = hash;
    }

    hash_table[0].prev = prev;
}

// main/tests

void test_case_1()
{
    printf("Test Case 1: Basic Allocation and Freeing\n");

    void* ptr1 = mt_alloc(sizeof(block_t));
    assert(ptr1 != NULL);
    mt_free(ptr1, sizeof(block_t));
}

void test_case_2()
{
    printf("Test Case 2: Allocate two blocks, then free them in reverse order\n");

    void* ptr1 = mt_alloc(32);
    void* ptr2 = mt_alloc(32);
    assert(ptr1 != NULL && ptr2 != NULL);
    mt_free(ptr2, 32);
    mt_free(ptr1, 32);
}

void test_case_3()
{
    printf("Test Case 3: Minimum allocation size\n");

    void* ptr1 = mt_alloc(1);
    assert(ptr1 != NULL);
    mt_free(ptr1, 1);
}

void test_case_4()
{
    printf("Test Case 4: Maximum allocation size within the pool\n");

    void* ptr1 = mt_alloc((1 << MAX_DEPTH) * sizeof(block_t));
    assert(ptr1 != NULL);
    mt_free(ptr1, (1 << MAX_DEPTH) * sizeof(block_t));
}

void test_case_5()
{
    printf("Test Case 5: Allocate two adjacent blocks and free them to test coalescing\n");

    void* ptr1 = mt_alloc(64);
    void* ptr2 = mt_alloc(64);
    assert(ptr1 != NULL && ptr2 != NULL);
    mt_free(ptr1, 64);
    mt_free(ptr2, 64);
}

void test_case_6()
{
    printf("Test Case 6: Random order of allocation and freeing\n");

    void* ptr1 = mt_alloc(16);
    void* ptr2 = mt_alloc(64);
    void* ptr3 = mt_alloc(128);
    void* ptr4 = mt_alloc(32);
    assert(ptr1 != NULL && ptr2 != NULL && ptr3 != NULL && ptr4 != NULL);
    mt_free(ptr3, 128);
    mt_free(ptr1, 16);
    mt_free(ptr4, 32);
    mt_free(ptr2, 64);
}

void test_case_7()
{
    printf("Test Case 7: Fragmentation handling\n");

    void* ptr1 = mt_alloc(16);
    void* ptr2 = mt_alloc(32);
    void* ptr3 = mt_alloc(64);
    void* ptr4 = mt_alloc(128);
    assert(ptr1 != NULL && ptr2 != NULL && ptr3 != NULL && ptr4 != NULL);
    mt_free(ptr2, 32);
    mt_free(ptr4, 128);
    void* ptr5 = mt_alloc(64);
    assert(ptr5 != NULL);
    mt_free(ptr1, 16);
    mt_free(ptr3, 64);
    mt_free(ptr5, 64);
}

void test_case_8()
{
    printf("Test Case 8: Request a block larger than the available memory\n");
    void* ptr1 = mt_alloc(((1 << MAX_DEPTH) * sizeof(block_t)) + 1);
    assert(ptr1 == NULL);
}

void test_case_10()
{
    printf("Test Case 10: Multiple coalescing levels\n");

    void* ptr1 = mt_alloc(64);
    void* ptr2 = mt_alloc(64);
    void* ptr3 = mt_alloc(64);
    void* ptr4 = mt_alloc(64);
    assert(ptr1 != NULL && ptr2 != NULL && ptr3 != NULL && ptr4 != NULL);
    mt_free(ptr1, 64);
    mt_free(ptr2, 64);
    mt_free(ptr3, 64);
    mt_free(ptr4, 64);
}

void test_case_11()
{
    printf("Test Case 11: Stress Test\n");

    for (int i = 0; i < 1000; i++)
    {
        void* ptr = mt_alloc((i % 256) + 1);
        assert(ptr != NULL);
        mt_free(ptr, (i % 256) + 1);
    }
}

void test_case_12()
{
    printf("Test Case 12: Boundary alignment test\n");

    void* ptr1 = mt_alloc(128);
    assert(ptr1 != NULL);
    mt_free(ptr1, 128);
}

void test_case_13()
{
    printf("Test Case: Random Allocation and Freeing\n");
#define num_ops 1024

    void* pointers[num_ops] = { 0 };
    size_t sizes[num_ops] = { 0 };
    size_t num_allocated = 0;

    srand((unsigned int)time(NULL));

    for (int i = 0; i < num_ops; i++)
    {
        if (rand() % 2 == 0 || num_allocated == 0)
        {
            // randomly decide to allocate memory
            size_t size = (rand() % (1 << MAX_DEPTH)) + 1;
            void* ptr = mt_alloc(size);

            if (ptr != NULL)
            {
                pointers[num_allocated] = ptr;
                sizes[num_allocated] = size;
                num_allocated++;
            }
        }
        else
        {
            // randomly decide to free memory
            size_t index = rand() % num_allocated;
            void* ptr = pointers[index];
            size_t size = sizes[index];

            mt_free(ptr, size);

            // move the last allocated pointer to the freed position to keep array compact
            pointers[index] = pointers[num_allocated - 1];
            sizes[index] = sizes[num_allocated - 1];
            num_allocated--;
        }
    }

    // free any remaining allocations
    for (size_t i = 0; i < num_allocated; i++)
    {
        mt_free(pointers[i], sizes[i]);
    }

    printf("Random allocation and freeing test completed.\n");
}

void test_stringlist_basic()
{
    // Test basic string allocation
    size_t ref1 = get_for_len("hello", 6);
    assert(ref1 != 0);

    string_ref_t* str_ref1 = get_ref_string(ref1);
    assert(str_ref1 != NULL);
    assert(str_ref1->ref_count == 1);
    assert(str_ref1->len == 6);
    assert(memcmp(str_ref1->str, "hello", 6) == 0);

    // Test same string lookup returns the same reference
    size_t ref2 = get_for_len("hello", 6);
    assert(ref2 == ref1);
    assert(str_ref1->ref_count == 2); // ref count should increment

    // Test freeing a reference
    sl_remove_ref(ref1);
    assert(str_ref1->ref_count == 1);

    // Test completely freeing the string (ref count reaches 0)
    sl_remove_ref(ref2);
    assert(str_ref1->ref_count == 0);

    // Verify string is freed and not accessible anymore
    size_t ref3 = find_for_len("hello", 6);
    assert(ref3 == 0); // should not find "hello" since it was freed
}

void test_stringlist_collision_handling()
{
    // Test collision handling with different strings
    size_t ref1 = get_for_len("hello", 6);
    assert(ref1 != 0);
    size_t ref2 = get_for_len("world", 6);
    assert(ref2 != 0);

    // Ensure they do not collide incorrectly
    assert(ref1 != ref2);

    string_ref_t* str_ref1 = get_ref_string(ref1);
    string_ref_t* str_ref2 = get_ref_string(ref2);

    assert(memcmp(str_ref1->str, "hello", 6) == 0);
    assert(memcmp(str_ref2->str, "world", 6) == 0);

    sl_remove_ref(ref1);
    sl_remove_ref(ref2);
}

void test_stringlist_long_strings()
{
    // Test long string that exceeds 255 bytes
    char long_str[300];
    for (size_t i = 0; i < 300; i++)
    {
        long_str[i] = 'a' + (i % 26);
    }
    long_str[299] = '\0';

    size_t ref = get_for_len(long_str, sizeof(long_str));
    assert(ref != 0);

    string_ref_t* str_ref = get_ref_string(ref);
    assert(str_ref != NULL);

    // Verify the string contents
    assert(memcmp(str_ref->str, long_str, sizeof(long_str)) == 0);

    sl_remove_ref(ref);
}

void test_stringlist_refcount()
{
    // Allocate a string and verify its ref count
    size_t ref1 = get_for_len("refcount", 9);
    assert(ref1 != 0);

    string_ref_t* str_ref = get_ref_string(ref1);
    assert(str_ref->ref_count == 1);

    // Get the same string again, which should increment the ref count
    size_t ref2 = get_for_len("refcount", 9);
    assert(ref2 == ref1);
    assert(str_ref->ref_count == 2);

    // Remove one reference and verify the count decreases
    sl_remove_ref(ref1);
    assert(str_ref->ref_count == 1);

    // Remove the last reference and ensure it's freed
    sl_remove_ref(ref2);
    assert(str_ref->ref_count == 0);
}

// Helper function to generate a random string of a given length
void generate_random_string(char* str, size_t length)
{
    static const char charset[] = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789";
    if (length)
    {
        --length;
        for (size_t i = 0; i < length; ++i)
        {
            int key = rand() % (int)(sizeof(charset) - 1);
            str[i] = charset[key];
        }
        str[length] = '\0';
    }
}

// Stress test case for the stringlist system
void stringlist_stress_test()
{
    printf("Starting stringlist stress test...\n");

    srand((unsigned int)time(NULL));

    // Array to store references to strings
#define MAX_STR_LEN 512
#define NUM_STRINGS 5000
    size_t string_refs[NUM_STRINGS];
    size_t string_lens[NUM_STRINGS];

    // Phase 1: Allocate and add random strings to the system
    for (int i = 0; i < NUM_STRINGS; i++)
    {
        size_t str_len = (rand() % MAX_STR_LEN) + 1;  // Random string length between 1 and MAX_STR_LEN
        char* random_string = (char*)mt_alloc(str_len + 1);

        if (random_string == NULL)
        {
            string_refs[i] = 0;
            continue;
        }

        generate_random_string(random_string, str_len + 1);

        string_lens[i] = str_len + 1;
        string_refs[i] = get_for_len(random_string, str_len + 1);

        if (string_refs[i] == 0)
        {
            printf("Error: Failed to allocate string: %s\n", random_string);
        }

        mt_free(random_string, str_len + 1);
    }

    printf("Allocated %d strings.\n", NUM_STRINGS);

    // Phase 2: Randomly remove references
    for (int i = 0; i < NUM_STRINGS; i++)
    {
        // Randomly decide whether to free this string
        if (rand() % 2 == 0 && string_refs[i] != 0)
        {
            sl_remove_ref(string_refs[i]);
            string_refs[i] = 0;
        }
    }

    printf("Freed random half of the strings.\n");

    // Phase 3: Reallocate some of the freed strings
    for (int i = 0; i < NUM_STRINGS; i++)
    {
        if (string_refs[i] == 0)
        {
            size_t str_len = (rand() % MAX_STR_LEN) + 1;
            char* random_string = (char*)mt_alloc(str_len + 1);

            if (random_string == NULL)
            {
                continue;
            }

            generate_random_string(random_string, str_len + 1);

            string_refs[i] = get_for_len(random_string, str_len + 1);

            if (string_refs[i] == 0)
            {
                printf("Error: Failed to reallocate string: %s\n", random_string);
            }

            mt_free(random_string, str_len + 1);
        }
    }

    printf("Reallocated half of the freed strings.\n");

    // Phase 4: Final cleanup, remove all remaining strings
    for (int i = 0; i < NUM_STRINGS; i++)
    {
        if (string_refs[i] != 0)
        {
            sl_remove_ref(string_refs[i]);
        }
    }

    printf("Cleaned up all remaining strings.\n");
    printf("Stringlist stress test completed.\n");
}

int main()
{
    clock_t start_time = clock();

    mt_init();
    sl_init();

    test_case_4();

    void* a = mt_alloc(32);
    void* b = mt_alloc(32);
    void* c = mt_alloc(64);
    memset(a, 'a', 32);
    memset(b, 'b', 32);
    memset(c, 'c', 64);

    test_case_1();
    test_case_2();
    test_case_3();
    test_case_5();
    test_case_6();
    test_case_7();
    test_case_8();
    test_case_10();
    test_case_11();
    test_case_12();
    test_case_13();

    assert(!memcmp(a, "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 32));
    assert(!memcmp(b, "bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbbb", 32));
    assert(!memcmp(c, "cccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc", 64));

    mt_free(a, 32);
    mt_free(b, 32);
    mt_free(c, 64);

    clock_t end_time = clock();

    printf("All tests completed.\n");

    double time_elapsed = (double)(end_time - start_time) / CLOCKS_PER_SEC;
    printf("Test completed in %f seconds.\n", time_elapsed);

    mt_print_heads();

    test_stringlist_basic();
    test_stringlist_collision_handling();
    test_stringlist_long_strings();
    test_stringlist_refcount();
    stringlist_stress_test();

    mt_print_heads();
}