Table Data Structure Library

A C library implementing a table data structure that maintains stable IDs while keeping elements in contiguous memory for fast iteration.

Overview

This library provides a Table data structure that combines the benefits of:

• Contiguous storage for cache-friendly iteration
• Stable IDs that remain valid after insertions/deletions and buffer reallocations
• O(1) operations for insert, delete, and get (amortized for insert)

This is essentially a slot map or sparse set implementation, commonly used in game engines and ECS (Entity Component System) architectures.

Key Features

• ✅ Stable IDs survive buffer reallocations
• ✅ O(1) insert, delete, and lookup operations
• ✅ Contiguous memory layout for fast iteration
• ✅ ID reuse via free list (no memory leaks from deleted IDs)
• ✅ Automatic growth on insertion
• ✅ Type-generic implementation (works with any struct)

Architecture

The Table uses four parallel vectors:

1. buffer: Stores actual elements in contiguous memory
2. ids: Stores the ID for each element (parallel to buffer)
3. index: Maps ID → buffer index (indirection layer)
4. free_list: Stack of reusable IDs from deleted elements

How It Works

Insert Operation:
- Add element to buffer
- Get ID (new or from free_list)
- Store ID in ids vector
- Update index mapping

Delete Operation:
- Look up buffer index via index vector
- Swap-remove element from buffer
- Update index for swapped element
- Mark ID as free and add to free_list

Get Operation:
- Look up buffer index via index vector
- Return element from buffer

API Reference

Vector API

Vector* vector_new(int capacity, int stride);
void vector_free(Vector* vector);
int vector_push(Vector* vector, void* obj);
void vector_pop(Vector* vector, void* obj);
void* vector_get(Vector* vector, int index);
void vector_insert(Vector* vector, void* obj, int index);
int vector_is_empty(Vector* vector);

Table API

// Create a new table
Table* table_new(int stride, int capacity);

// Free a table
void table_free(Table* table);

// Insert an element, returns stable ID
int table_insert(Table* table, void* obj);

// Delete element by ID
void table_delete(Table* table, int id);

// Get element by ID (returns NULL if deleted)
void* table_get(Table* table, int id);

// Get current number of elements
int table_size(Table* table);

Usage Example

#include "table.h"

typedef struct {
    float x, y;
    int health;
} Enemy;

int main() {
    // Create table for Enemy structs
    Table* enemies = table_new(sizeof(Enemy), 16);
    
    // Insert enemies
    Enemy e1 = {10.0f, 20.0f, 100};
    Enemy e2 = {30.0f, 40.0f, 150};
    
    int id1 = table_insert(enemies, &e1);
    int id2 = table_insert(enemies, &e2);
    
    // Access by ID
    Enemy* e = (Enemy*)table_get(enemies, id1);
    e->health -= 25;
    
    // Delete an enemy
    table_delete(enemies, id2);
    
    // Iterate all enemies (contiguous!)
    for (int i = 0; i < table_size(enemies); i++) {
        Enemy* enemy = (Enemy*)vector_get(&enemies->buffer, i);
        // Process enemy...
    }
    
    // Clean up
    table_free(enemies);
    return 0;
}

Iteration Pattern

Since elements are stored contiguously, iteration is cache-friendly:

// Direct iteration over buffer
for (int i = 0; i < table->buffer.n; i++) {
    MyStruct* obj = (MyStruct*)vector_get(&table->buffer, i);
    // ... process obj
}

// Get the ID for an element during iteration
for (int i = 0; i < table->buffer.n; i++) {
    MyStruct* obj = (MyStruct*)vector_get(&table->buffer, i);
    int* id = (int*)vector_get(&table->ids, i);
    // ... process obj with its ID
}

Complexity

Operation	Time Complexity	Notes
Insert	O(1) amortized	May trigger reallocation
Delete	O(1)	Uses swap-remove
Get	O(1)	Single indirection
Iterate	O(n)	Cache-friendly

Building

gcc -o test_table test_table.c table.c -Wall -Wextra
./test_table

Use Cases

Perfect for:

• Game entity systems (ECS)
• Object pools with stable handles
• Resource managers (textures, sounds, etc.)
• Any scenario requiring stable references with fast iteration

Implementation Details

• Swap-remove: When deleting, the last element is swapped into the deleted position to maintain contiguous storage
• Free list: Deleted IDs are stored in a free list for reuse, preventing ID exhaustion
• Indirection: The extra indirection (ID → index → element) enables stable IDs while keeping data contiguous
• Auto-growth: Vectors automatically double in capacity when full

License

Public domain / MIT (choose your preference)