Data Structures for Embedded C Development

Data Structures for Embedded C Development#

Introduction to Data Structures for Embedded Applications#

Data structures are essential components in embedded applications, as they provide a systematic way of organizing and managing data efficiently. Embedded systems often operate under constraints such as limited memory, processing power, and real-time requirements, making the choice and design of data structures critical to their performance and reliability.

Why Data Structures Matter in Embedded Applications:#

  1. Efficient Resource Utilization:

    • Embedded systems usually have limited RAM and storage. Data structures help in optimizing memory usage and reducing overhead.

  2. Real-time Performance:

    • Embedded systems often need to meet strict timing requirements. Properly chosen data structures ensure predictable and fast access to data.

  3. Power Efficiency:

    • Efficient data manipulation minimizes processor cycles, helping to conserve battery life in portable devices.

  4. Hardware Interfacing:

    • Data structures facilitate the management of I/O buffers, queues, and other mechanisms that interface with hardware components.

Commonly Used Data Structures in Embedded Applications:#

Arrays:#

  • Fixed-size collections of elements, widely used for their simplicity and predictable access times.

  • Ideal for look-up tables, signal processing buffers, and fixed data sets.

Linked Lists:#

  • Useful for dynamic memory management when insertion and deletion operations are frequent.

  • Often used in scheduling tasks or dynamic buffer management.

Queues:#

  • FIFO structures commonly used in real-time systems for task scheduling, message passing, and I/O buffers.

  • Variants include circular queues and priority queues.

Stacks:#

  • LIFO structures used in embedded applications for managing tasks, recursive function calls, and temporary data storage.

Trees:#

  • Binary trees, AVL trees, and heaps are used for hierarchical data representation and efficient searching.

  • Examples include Huffman trees for compression and decision trees for control systems.

Hash Tables:#

  • Provide fast key-value mapping, useful for lookup operations in limited-memory systems.

Bitmaps and Bitfields:#

  • Memory-efficient structures for managing flags, states, or compact data representation.

Key Considerations for Embedded Systems:#

  • Memory Constraints: Prefer lightweight structures that minimize overhead.

  • Predictability: Use structures with deterministic behavior for real-time applications.

  • Algorithm Complexity: Favor simplicity to ease debugging and ensure reliability.

  • Scalability: Design for specific hardware limits while accommodating future enhancements.

Arrays#

  • Usage: Store a fixed-size collection of elements of the same type.

  • Why?: Efficient indexing, deterministic memory allocation.

  • Example: Storing sensor readings or lookup tables.

#include <stdio.h>
 
#define NUM_SENSORS 5
 
int main() {
    int temperatureReadings[NUM_SENSORS] = {25, 27, 26, 28, 30};
 
    for (int i = 0; i < NUM_SENSORS; i++) {
        printf("Sensor %d: %d°C\n", i + 1, temperatureReadings[i]);
    }
    return 0;
}

Linked Lists#

  • Usage: When the size of the dataset varies and dynamic memory management is allowed.

  • Why?: Useful for managing buffers (e.g., queues, stacks) or implementing dynamic data structures.

  • Example: FreeRTOS task lists or dynamic event queues.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int taskId;
    struct Node* next;
} Node;
 
void addTask(Node** head, int taskId) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->taskId = taskId;
    newNode->next = *head;
    *head = newNode;
}
 
void printTasks(Node* head) {
    while (head) {
        printf("Task ID: %d\n", head->taskId);
        head = head->next;
    }
}
 
int main() {
    Node* taskList = NULL;
    addTask(&taskList, 1);
    addTask(&taskList, 2);
    addTask(&taskList, 3);
    printTasks(taskList);
 
    return 0;
}

Stacks#

  • Usage: Manage last-in-first-out (LIFO) operations.

  • Why?: Useful for tracking function calls, backtracking, or temporary data.

  • Example: Backtracking in a maze-solving algorithm.

#include <stdio.h>
#define MAX_STACK_SIZE 10
 
typedef struct {
    int top;
    int stack[MAX_STACK_SIZE];
} Stack;
 
void push(Stack* s, int value) {
    if (s->top == MAX_STACK_SIZE - 1) {
        printf("Stack Overflow\n");
        return;
    }
    s->stack[++s->top] = value;
}
 
int pop(Stack* s) {
    if (s->top == -1) {
        printf("Stack Underflow\n");
        return -1;
    }
    return s->stack[s->top--];
}
 
int main() {
    Stack s = {.top = -1};
    push(&s, 10);
    push(&s, 20);
    printf("Popped: %d\n", pop(&s));
    return 0;
}

Queues#

  • Usage: First-in-first-out (FIFO) structure for task scheduling or inter-process communication.

  • Why?: Reliable and predictable data flow.

  • Example: Inter-process communication.

#include <stdio.h>
#define MAX_QUEUE_SIZE 10
 
typedef struct {
    int front, rear, size;
    int queue[MAX_QUEUE_SIZE];
} Queue;
 
void enqueue(Queue* q, int value) {
    if (q->size == MAX_QUEUE_SIZE) {
        printf("Queue Full\n");
        return;
    }
    q->rear = (q->rear + 1) % MAX_QUEUE_SIZE;
    q->queue[q->rear] = value;
    q->size++;
}
 
int dequeue(Queue* q) {
    if (q->size == 0) {
        printf("Queue Empty\n");
        return -1;
    }
    int value = q->queue[q->front];
    q->front = (q->front + 1) % MAX_QUEUE_SIZE;
    q->size--;
    return value;
}
 
int main() {
    Queue q = {.front = 0, .rear = -1, .size = 0};
    enqueue(&q, 5);
    enqueue(&q, 10);
    printf("Dequeued: %d\n", dequeue(&q));
    return 0;
}

Circular Buffers (Ring Buffers)#

  • Usage: Fixed-size queue where the head and tail pointers wrap around.

  • Why?: Efficient memory usage with constant time insertion/removal.

  • Example: UART communication buffers or audio streaming.

#include <stdio.h>
#define BUFFER_SIZE 5
 
typedef struct {
    int buffer[BUFFER_SIZE];
    int head, tail, size;
} CircularBuffer;
 
void write(CircularBuffer* cb, int value) {
    if (cb->size == BUFFER_SIZE) {
        printf("Buffer Full\n");
        return;
    }
    cb->buffer[cb->head] = value;
    cb->head = (cb->head + 1) % BUFFER_SIZE;
    cb->size++;
}
 
int read(CircularBuffer* cb) {
    if (cb->size == 0) {
        printf("Buffer Empty\n");
        return -1;
    }
    int value = cb->buffer[cb->tail];
    cb->tail = (cb->tail + 1) % BUFFER_SIZE;
    cb->size--;
    return value;
}
 
int main() {
    CircularBuffer cb = {.head = 0, .tail = 0, .size = 0};
    write(&cb, 1);
    write(&cb, 2);
    printf("Read: %d\n", read(&cb));
    return 0;
}

Binary Trees#

  • Usage: Represent hierarchical data or enable fast searching.

  • Why?: Good for sorting and searching when memory is not a tight constraint.

  • Example: Decision trees or protocol parsers.

#include <stdio.h>
#include <stdlib.h>
 
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;
 
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}
 
void inorderTraversal(Node* root) {
    if (root) {
        inorderTraversal(root->left);
        printf("%d ", root->data);
        inorderTraversal(root->right);
    }
}
 
int main() {
    Node* root = createNode(10);
    root->left = createNode(5);
    root->right = createNode(15);
 
    inorderTraversal(root);
    return 0;
}

Hash Tables#

  • Usage: Map keys to values for fast lookups.

  • Why?: Efficient key-value data storage and retrieval.

  • Example: Storing configuration data or managing lookup tables.

#include <stdio.h>
#include <string.h>
 
#define TABLE_SIZE 10
 
typedef struct {
    char key[20];
    int value;
} HashTable;
 
HashTable table[TABLE_SIZE] = {0};
 
int hash(const char* key) {
    int hashValue = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hashValue += key[i];
    }
    return hashValue % TABLE_SIZE;
}
 
void insert(const char* key, int value) {
    int index = hash(key);
    strcpy(table[index].key, key);
    table[index].value = value;
}
 
int lookup(const char* key) {
    int index = hash(key);
    if (strcmp(table[index].key, key) == 0) {
        return table[index].value;
    }
    return -1;
}
 
int main() {
    insert("DeviceID", 42);
    printf("DeviceID: %d\n", lookup("DeviceID"));
    return 0;
}

Bitfields#

  • Usage: Represent tightly packed binary data or flags.

  • Why?: Conserve memory and improve processing efficiency.

  • Example: Hardware register representations or flags for state machines.

#include <stdio.h>
 
// Define the bitfield structure
typedef struct {
    unsigned int systemReady : 1;    // Bit 0
    unsigned int overheatWarning : 1; // Bit 1
    unsigned int lowVoltageWarning : 1; // Bit 2
    unsigned int powerFailure : 1;    // Bit 3
    unsigned int reserved : 4;        // Bits 4-7 (Unused)
} StatusRegister;
 
int main() {
    // Create an instance of the register
    StatusRegister reg = {0}; // Initialize all bits to 0
 
    // Set the "System Ready" and "Low Voltage Warning" bits
    reg.systemReady = 1;
    reg.lowVoltageWarning = 1;
 
    // Display the current status
    printf("System Ready: %u\n", reg.systemReady);
    printf("Overheat Warning: %u\n", reg.overheatWarning);
    printf("Low Voltage Warning: %u\n", reg.lowVoltageWarning);
    printf("Power Failure: %u\n", reg.powerFailure);
 
    // Simulate a power failure
    reg.powerFailure = 1;
    printf("\nAfter Power Failure:\n");
    printf("Power Failure: %u\n", reg.powerFailure);
 
    return 0;
}

State Machines#

  • Usage: Implement finite states and transitions for predictable behavior.

  • Why?: Commonly used in control systems and event-driven programming.

  • Example: Example: State Machine for a Traffic Light Controller

States#

  • RED: Stop for vehicles.

  • GREEN: Allow vehicles to pass.

  • YELLOW: Prepare to stop.

Transitions:#

stateDiagram-v2
 [*] --> Red
    Red --> Green
    Green-->Yellow
    Yellow-->Red

#include <stdio.h>
 
// Define states
typedef enum {
    STATE_RED,
    STATE_GREEN,
    STATE_YELLOW
} TrafficLightState;
 
// Function prototypes for state actions
void redStateAction();
void greenStateAction();
void yellowStateAction();
 
int main() {
    TrafficLightState currentState = STATE_RED; // Initial state
 
    // Simulate the state transitions
    for (int i = 0; i < 6; i++) { // Loop through 6 cycles
        switch (currentState) {
            case STATE_RED:
                redStateAction();
                currentState = STATE_GREEN; // Transition to GREEN
                break;
            
            case STATE_GREEN:
                greenStateAction();
                currentState = STATE_YELLOW; // Transition to YELLOW
                break;
 
            case STATE_YELLOW:
                yellowStateAction();
                currentState = STATE_RED; // Transition to RED
                break;
 
            default:
                printf("Invalid state!\n");
                return -1; // Exit on error
        }
    }
 
    return 0;
}
 
// Actions for each state
void redStateAction() {
    printf("RED: Stop for 5 seconds.\n");
}
 
void greenStateAction() {
    printf("GREEN: Go for 5 seconds.\n");
}
 
void yellowStateAction() {
    printf("YELLOW: Slow down for 2 seconds.\n");
}

Fixed-Size Buffers#

  • Usage: Store data with a predefined maximum size.

  • Why?: Prevent dynamic memory allocation overhead.

  • Example: UART Receive Buffer

#include <stdio.h>
#include <stdbool.h>
 
#define BUFFER_SIZE 8
 
// Fixed-size circular buffer structure
typedef struct {
    char buffer[BUFFER_SIZE];
    int head;
    int tail;
    int size;
} FixedSizeBuffer;
 
// Initialize the buffer
void initBuffer(FixedSizeBuffer* buf) {
    buf->head = 0;
    buf->tail = 0;
    buf->size = 0;
}
 
// Check if the buffer is full
bool isBufferFull(FixedSizeBuffer* buf) {
    return buf->size == BUFFER_SIZE;
}
 
// Check if the buffer is empty
bool isBufferEmpty(FixedSizeBuffer* buf) {
    return buf->size == 0;
}
 
// Add a character to the buffer
bool writeBuffer(FixedSizeBuffer* buf, char data) {
    if (isBufferFull(buf)) {
        printf("Buffer Full! Unable to add '%c'.\n", data);
        return false;
    }
    buf->buffer[buf->head] = data;
    buf->head = (buf->head + 1) % BUFFER_SIZE;
    buf->size++;
    return true;
}
 
// Read a character from the buffer
bool readBuffer(FixedSizeBuffer* buf, char* data) {
    if (isBufferEmpty(buf)) {
        printf("Buffer Empty! No data to read.\n");
        return false;
    }
    *data = buf->buffer[buf->tail];
    buf->tail = (buf->tail + 1) % BUFFER_SIZE;
    buf->size--;
    return true;
}
 
// Simulate UART data reception
void simulateUART(FixedSizeBuffer* buf, const char* inputData) {
    for (int i = 0; inputData[i] != '\0'; i++) {
        writeBuffer(buf, inputData[i]);
    }
}
 
// Display the buffer contents
void printBuffer(FixedSizeBuffer* buf) {
    printf("Buffer Contents: ");
    for (int i = 0; i < buf->size; i++) {
        printf("%c ", buf->buffer[(buf->tail + i) % BUFFER_SIZE]);
    }
    printf("\n");
}
 
int main() {
    FixedSizeBuffer uartBuffer;
    initBuffer(&uartBuffer);
 
    // Simulate incoming UART data
    simulateUART(&uartBuffer, "HELLO");
 
    // Display buffer state
    printBuffer(&uartBuffer);
 
    // Read data from the buffer
    char data;
    while (readBuffer(&uartBuffer, &data)) {
        printf("Read: %c\n", data);
    }
 
    // Attempt to read from an empty buffer
    readBuffer(&uartBuffer, &data);
 
    return 0;
}

Best Practices#

  1. Memory Efficiency: Use static allocation wherever possible to avoid fragmentation.

  2. Deterministic Behavior: Avoid data structures that could introduce unpredictable latencies (e.g., dynamic memory management in real-time systems).

  3. Concurrency: Use thread-safe or interrupt-safe mechanisms like locks or atomic operations when accessing shared data structures.

  4. Testing: Ensure data structures are thoroughly tested for boundary cases and memory usage.