Implementing Thread-Safe Dynamic Arrays

Implementing thread-safe, dynamically resizable arrays in C is indeed a crucial topic for mastering advanced C programming and concurrency control. This knowledge can be essential when dealing with multi-threaded applications where data structures need to be accessed and modified concurrently.

Here's an overview of how you can achieve this:

Thread-Safe Dynamic Arrays in C

Thread-Safe: Ensuring that multiple threads can access and modify the array without causing data corruption.
Dynamic Resizing: Allowing the array to grow or shrink in size as needed.

Key Concepts

Mutex Locks: To ensure that only one thread can modify the array at a time.
Condition Variables: To manage scenarios where a thread needs to wait until a certain condition is met before proceeding.

Implementation Steps

Define the Dynamic Array Structure

Include a pointer to the data array.
Include variables for the current size and capacity.
Include a mutex for synchronization.

#include <stdlib.h>
#include <pthread.h>

typedef struct {
    int *data;
    size_t size;
    size_t capacity;
    pthread_mutex_t lock;
} DynamicArray;

Initialize the Dynamic Array

Allocate memory for the array.
Initialize the size and capacity.
Initialize the mutex.

void initArray(DynamicArray *arr, size_t initialCapacity) {
    arr->data = (int *)malloc(initialCapacity * sizeof(int));
    arr->size = 0;
    arr->capacity = initialCapacity;
    pthread_mutex_init(&arr->lock, NULL);
}

Resize the Array

Double the capacity when the array is full.
Reallocate memory and copy the old data to the new memory location.

void resizeArray(DynamicArray *arr) {
    arr->capacity *= 2;
    arr->data = (int *)realloc(arr->data, arr->capacity * sizeof(int));
}

Add Elements to the Array

Lock the mutex before modifying the array.
Resize the array if needed.
Add the new element and unlock the mutex.

void addElement(DynamicArray *arr, int element) {
    pthread_mutex_lock(&arr->lock);
    if (arr->size == arr->capacity) {
        resizeArray(arr);
    }
    arr->data[arr->size++] = element;
    pthread_mutex_unlock(&arr->lock);
}

Remove Elements from the Array

Lock the mutex before modifying the array.
Remove the element and optionally resize the array down.
Unlock the mutex.

void removeElement(DynamicArray *arr) {
    pthread_mutex_lock(&arr->lock);
    if (arr->size > 0) {
        arr->size--;
        // Optionally resize down if too much unused capacity
    }
    pthread_mutex_unlock(&arr->lock);
}

Clean Up

Free the allocated memory.
Destroy the mutex.

void freeArray(DynamicArray *arr) {
    free(arr->data);
    pthread_mutex_destroy(&arr->lock);
}

Example Usage

Here's a simple example of how you might use this dynamic array in a multi-threaded context:

#include <stdio.h>
#include <pthread.h>

#define NUM_THREADS 4
#define NUM_ELEMENTS 10

void *threadFunc(void *arg) {
    DynamicArray *arr = (DynamicArray *)arg;
    for (int i = 0; i < NUM_ELEMENTS; i++) {
        addElement(arr, i);
    }
    return NULL;
}

int main() {
    DynamicArray arr;
    initArray(&arr, 4);

    pthread_t threads[NUM_THREADS];
    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_create(&threads[i], NULL, threadFunc, &arr);
    }

    for (int i = 0; i < NUM_THREADS; i++) {
        pthread_join(threads[i], NULL);
    }

    for (size_t i = 0; i < arr.size; i++) {
        printf("%d ", arr.data[i]);
    }
    printf("\n");

    freeArray(&arr);
    return 0;
}

Conclusion

Implementing a thread-safe, dynamically resizable array in C involves careful handling of memory allocation and synchronization. By using mutexes and condition variables, you can ensure that your data structures are safe for concurrent access and modifications, providing a robust foundation for multi-threaded applications.