Dynamic Memory Allocation in C: Building a Theater Seat Reservation System

Introduction: Why Dynamic Memory Allocation Matters

Dynamic memory allocation is a cornerstone of efficient C programming. It allows programs to request memory at runtime, adapting to varying data sizes—essential for modern applications like streaming services, gaming servers, or even AI model training. In this tutorial, we'll build a theater seat reservation system inspired by the classic COP 3502C assignment. You'll practice using malloc, free, and structs to manage a large theater with up to 100,000 rows.

Understanding the Theater Problem

Imagine you're running a movie theater with an ULTIMATE projector (Unacceptably Luminescent Tech Igniting Many Airplanes Though Eco-friendly). The demand is huge—think of the latest blockbuster like Avengers: Secret Wars or a viral concert film. Your software must handle rows beyond the old 400-seat limit. Each row can have up to 100 successful purchases, but seats are numbered 1 to 100,000. You need to track who owns which seat and allow consecutive seat purchases.

Key Concepts: Structs and Dynamic Arrays

We'll use two structs: order (stores a seat range and owner name) and theaterrow (holds a dynamic array of orders). The array starts small (size 10) and grows as needed—just like how a streaming platform scales its servers during peak hours.

typedef struct order {
    int s_seat;
    int e_seat;
    char* name;
} order;

typedef struct theaterrow {
    order** list_orders;
    int max_size;
    int cur_size;
} theaterrow;

Step 1: Creating Orders Dynamically

The make_order function allocates memory for an order and its name. Always use strcpy after allocating space for the name string.

order* make_order(int start, int end, char* this_name) {
    order* new_order = (order*)malloc(sizeof(order));
    new_order->s_seat = start;
    new_order->e_seat = end;
    new_order->name = (char*)malloc(strlen(this_name) + 1);
    strcpy(new_order->name, this_name);
    return new_order;
}

Step 2: Initializing a Row

make_empty_row allocates the row struct and its order array with initial capacity 10.

theaterrow* make_empty_row() {
    theaterrow* row = (theaterrow*)malloc(sizeof(theaterrow));
    row->max_size = INITSIZE;
    row->cur_size = 0;
    row->list_orders = (order**)malloc(INITSIZE * sizeof(order*));
    return row;
}

Step 3: Detecting Conflicts

Two orders conflict if their seat ranges overlap. This is like checking if two friends try to book the same seats for a concert—imagine Taylor Swift's Eras Tour or a FIFA World Cup final.

int conflict(order* order1, order* order2) {
    if (order1->s_seat > order2->e_seat || order1->e_seat < order2->s_seat)
        return 0;
    return 1;
}

Step 4: Checking If an Order Can Be Added

can_add_order iterates through existing orders and returns 1 only if no conflict exists.

int can_add_order(theaterrow* this_row, order* this_order) {
    for (int i = 0; i < this_row->cur_size; i++) {
        if (conflict(this_row->list_orders[i], this_order))
            return 0;
    }
    return 1;
}

Step 5: Adding an Order (with Dynamic Resizing)

When adding an order, if the array is full, we double its capacity using realloc. This is similar to how a social media app allocates more servers as user count grows.

int add_order(theaterrow* this_row, order* this_order) {
    if (!can_add_order(this_row, this_order))
        return 0;
    if (this_row->cur_size == this_row->max_size) {
        this_row->max_size *= 2;
        this_row->list_orders = (order**)realloc(this_row->list_orders,
            this_row->max_size * sizeof(order*));
    }
    this_row->list_orders[this_row->cur_size] = this_order;
    this_row->cur_size++;
    return 1;
}

Step 6: Looking Up a Seat

For LOOKUP, scan the row's orders to find which order contains the seat number. If none, output "None".

char* lookup_seat(theaterrow* this_row, int seat) {
    for (int i = 0; i < this_row->cur_size; i++) {
        order* o = this_row->list_orders[i];
        if (seat >= o->s_seat && seat <= o->e_seat)
            return o->name;
    }
    return NULL;
}

Step 7: Memory Cleanup

Freeing memory is critical. For each row, free each order's name, then the order itself, then the array, then the row.

void free_theater(theaterrow** theater, int num_rows) {
    for (int r = 0; r < num_rows; r++) {
        if (theater[r] != NULL) {
            for (int i = 0; i < theater[r]->cur_size; i++) {
                free(theater[r]->list_orders[i]->name);
                free(theater[r]->list_orders[i]);
            }
            free(theater[r]->list_orders);
            free(theater[r]);
        }
    }
    free(theater);
}

Putting It All Together: Main Loop

Read commands until EXIT. Use a sentinel-driven loop. The theater is an array of pointers to rows, initially NULL. When a BUY for a new row comes, allocate that row.

int main() {
    theaterrow** theater = (theaterrow**)calloc(MAXROWS + 1, sizeof(theaterrow*));
    char command[10];
    while (scanf("%s", command) == 1) {
        if (strcmp(command, "BUY") == 0) {
            int row, start, end;
            char name[51];
            scanf("%d %d %d %s", &row, &start, &end, name);
            if (theater[row] == NULL)
                theater[row] = make_empty_row();
            order* o = make_order(start, end, name);
            if (add_order(theater[row], o))
                printf("SUCCESS\n");
            else {
                free(o->name); free(o);
                printf("FAILURE\n");
            }
        } else if (strcmp(command, "LOOKUP") == 0) {
            int row, seat;
            scanf("%d %d", &row, &seat);
            if (theater[row] != NULL) {
                char* name = lookup_seat(theater[row], seat);
                if (name) printf("%s\n", name);
                else printf("None\n");
            } else printf("None\n");
        } else if (strcmp(command, "EXIT") == 0) {
            break;
        }
    }
    free_theater(theater, MAXROWS + 1);
    return 0;
}

Common Pitfalls and Tips

• Always check if malloc or realloc returns NULL. Handle errors gracefully.
• Use strcpy only after allocating enough space for the string plus the null terminator.
• Remember that realloc may move the memory block; update your pointer.
• For 1-based indexing, allocate arrays of size MAXROWS+1.
• Test edge cases: buying seats that exactly touch existing ranges, overlapping ranges, and rows with many orders.

Real-World Connections

Dynamic memory allocation is used everywhere: from video game engines allocating textures on the fly to AI models loading weights into GPU memory. Even apps like TikTok or Instagram use similar techniques to manage user data. By mastering these skills, you're building a foundation for systems programming, game development, and high-performance computing.

Conclusion

You've learned how to use dynamic memory allocation to build a scalable theater seat reservation system. This tutorial covered structs, pointers, malloc, free, realloc, and conflict detection. Practice by extending the system: add features like canceling orders or printing a row map. Happy coding!