Data structure bugs

Introduction

Data structure code is mostly pointer and index bookkeeping, and the bugs are the same few again and again. Compiled C often hides them: the program prints a wrong answer, or crashes much later. Each example below stops at the faulty line, with an explanation.

In a language like C these mistakes do not always stop the program, and it can go on producing wrong answers. StepVioz stops at the faulty line and explains it, so you can see what real C would have hidden.

How it works

Popping an empty stack

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
} Node;

void push(Node **top, int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = *top;
    *top = n;
}

int pop(Node **top) {
    Node *n = *top;
    int x = n->value;   // n is NULL when the stack is empty
    *top = n->next;
    free(n);
    return x;
}

int main(void) {
    Node *top = NULL;
    push(&top, 5);
    printf("%d\n", pop(&top));
    printf("%d\n", pop(&top));   // the stack is empty now
    return 0;
}

pop takes Node **top, a pointer to a pointer, so it can change the caller's top itself. The second pop runs on an empty stack: n is NULL, and n->value reads through a NULL pointer. On a real computer this is a segmentation fault.

Fix: check first: if (*top == NULL) { /* report underflow */ }.

Using a node after freeing it

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
} Node;

int main(void) {
    Node *head = NULL;
    for (int v = 3; v >= 1; v--) {
        Node *n = malloc(sizeof(Node));
        n->value = v;
        n->next = head;
        head = n;
    }
    for (Node *p = head; p != NULL; p = p->next) free(p);
    printf("freed\n");
    return 0;
}

This loop looks natural, but p = p->next runs after free(p), so it reads memory that no longer belongs to the program. Compiled C may print nothing wrong for years, and then fail when the memory is reused.

Fix: save the next pointer first:

while (head != NULL) {
    Node *next = head->next;
    free(head);
    head = next;
}

A queue that runs off its array

#include <stdio.h>
#define CAPACITY 3

typedef struct {
    int items[CAPACITY];
    int front, rear;
} Queue;

void enqueue(Queue *q, int x) {
    q->items[q->rear] = x;   // no wrap-round and no full check
    q->rear++;
}

int dequeue(Queue *q) {
    return q->items[q->front++];
}

int main(void) {
    Queue q;
    q.front = 0;
    q.rear = 0;
    enqueue(&q, 1);
    enqueue(&q, 2);
    enqueue(&q, 3);
    printf("served %d\n", dequeue(&q));
    printf("served %d\n", dequeue(&q));
    enqueue(&q, 4);
    printf("served %d\n", dequeue(&q));
    return 0;
}

This queue never wraps round. After 3 enqueues and 2 dequeues, two cells at the front are free, but rear is 3, past the end of a 3-cell array. The fourth enqueue writes outside items. Compiled C would silently overwrite whatever comes next in memory, here the field front, and the queue would serve a wrong value with no error at all.

Fix: a circular queue: rear = (front + count) % CAPACITY, and refuse when count == CAPACITY.

A checklist for your own code

• Empty structure: what happens on pop, dequeue or delete when there is nothing there?
• One item: does removing it update both head and tail (or front and rear)?
• First and last positions: are head and tail handled when they change?
• After free: is any pointer still used?
• Index arithmetic: is every index inside 0 .. capacity-1?

Syntax

// a function that can fail returns whether it worked
int pop(Node **top, int *out) {
    if (*top == NULL) return 0;
    /* ... */
    return 1;
}

Example

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    int value;
    struct node *next;
} Node;

void push(Node **top, int value) {
    Node *n = malloc(sizeof(Node));
    n->value = value;
    n->next = *top;
    *top = n;
}

int pop(Node **top, int *out) {
    if (*top == NULL) return 0;   // nothing to pop: say so
    Node *n = *top;
    *out = n->value;
    *top = n->next;
    free(n);
    return 1;
}

int main(void) {
    Node *top = NULL;
    int x;
    push(&top, 5);
    if (pop(&top, &x)) printf("popped %d\n", x);
    if (!pop(&top, &x)) printf("the stack is empty\n");
    return 0;
}

This is the corrected stack. pop now checks for an empty stack and reports it through its return value, so the caller can decide what to do.

Line by line

1. push takes Node **top, so it can change the caller's pointer.
2. pop first checks for an empty stack and returns 0 if there is nothing to remove.
3. It then saves the node, copies its value through out, moves top on and frees the node, in that order.
4. main pushes 5 and pops it, which works and prints the value.
5. The second pop finds the stack empty, returns 0, and the program prints a message and carries on.

Expected result

popped 5
the stack is empty

In the real world

A large share of the security problems ever found in C and C++ programs are exactly these memory errors, and some have exposed the private data of millions of people. Tools such as AddressSanitizer exist to catch them while a program is being tested.

Common mistakes

• Popping, dequeuing or deleting without first checking that the structure is not empty.
• Reading p->next after free(p).
• Letting an index reach the capacity, which is one past the last valid cell.
• Updating head but forgetting tail, or the other way round, when the last node goes.

Best practices

• Make functions that can fail report it, and check what they return.
• Set a pointer to NULL after freeing it, if it stays in use.
• Run the checklist in this lesson on every structure you write.

Summary

Most data structure bugs come from a missing check for empty, from using a node after freeing it, or from an index that runs past the array. Test the empty, one-item, first and last cases every time.

Mark lesson complete