11101：环形缓冲区

题目

实现固定容量的整数环形缓冲区，支持普通写入、覆盖写入、读取、清空、查询大小和销毁。除创建和销毁外，各项操作都必须在 $O(1)$ 时间内完成。

解析

将动态数组视为首尾相接的空间：

• head 指向最早写入且尚未读取的元素；
• size 表示当前元素数量；
• 下一次普通写入的位置是 (head + size) mod capacity；
• 满时覆盖写入的位置就是 head，随后将 head 向前推进一格。

不能直接计算 head + size，因为两个 size_t 相加仍可能溢出。辅助函数先对偏移量取模，再通过减法完成环绕。

始终维持以下不变式：

0 < capacity
0 <= head < capacity
0 <= size <= capacity

解析

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdlib.h>

typedef struct IntRing IntRing;

struct IntRing {
    int *items;
    size_t capacity;
    size_t head;
    size_t size;
};

static size_t wrapped_add(
    size_t index,
    size_t offset,
    size_t capacity
) {
    offset %= capacity;
    if (offset == 0) {
        return index;
    }
    if (index >= capacity - offset) {
        return index - (capacity - offset);
    }
    return index + offset;
}

static size_t next_index(size_t index, size_t capacity) {
    return index == capacity - 1 ? 0 : index + 1;
}

IntRing *ring_create(size_t capacity) {
    if (capacity == 0 || capacity > SIZE_MAX / sizeof(int)) {
        return NULL;
    }

    IntRing *ring = malloc(sizeof *ring);
    if (ring == NULL) {
        return NULL;
    }

    ring->items = malloc(capacity * sizeof *ring->items);
    if (ring->items == NULL) {
        free(ring);
        return NULL;
    }

    ring->capacity = capacity;
    ring->head = 0;
    ring->size = 0;
    return ring;
}

void ring_destroy(IntRing *ring) {
    if (ring == NULL) {
        return;
    }
    free(ring->items);
    free(ring);
}

bool ring_push(IntRing *ring, int value) {
    if (ring == NULL || ring->size == ring->capacity) {
        return false;
    }

    size_t tail = wrapped_add(
        ring->head,
        ring->size,
        ring->capacity
    );
    ring->items[tail] = value;
    ++ring->size;
    return true;
}

bool ring_push_overwrite(IntRing *ring, int value) {
    if (ring == NULL) {
        return false;
    }
    if (ring->size < ring->capacity) {
        return ring_push(ring, value);
    }

    ring->items[ring->head] = value;
    ring->head = next_index(ring->head, ring->capacity);
    return true;
}

bool ring_pop(IntRing *ring, int *out) {
    if (ring == NULL || out == NULL || ring->size == 0) {
        return false;
    }

    *out = ring->items[ring->head];
    ring->head = next_index(ring->head, ring->capacity);
    --ring->size;

    if (ring->size == 0) {
        ring->head = 0;
    }
    return true;
}

void ring_clear(IntRing *ring) {
    if (ring == NULL) {
        return;
    }
    ring->head = 0;
    ring->size = 0;
}

size_t ring_size(const IntRing *ring) {
    return ring == NULL ? 0 : ring->size;
}

来源与改编

题型改编自 Exercism C Track 的 Circular Buffer，采用 MIT 许可。接口、约束、解析与参考实现均已重新编写，完整说明见习题来源与许可。