11102：可增长字节缓冲区

题目

实现支持初始化、销毁、预留容量和追加数据的字节缓冲区。所有失败操作都必须保持原状态与已有内容不变。

解析

缓冲区始终满足：

size <= capacity
capacity == 0 当且仅当 data == NULL

追加前先检查 size + count 是否溢出，再预留所需容量。realloc 的结果先由临时指针接收；只有成功后才更新 data 和 capacity。因此分配失败不会丢失原存储。

容量从 16 开始并尽量翻倍。即将翻倍溢出时直接选择最低所需容量，既避免算术溢出，也避免不必要地拒绝仍可表示的请求。

解析

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

typedef struct {
    unsigned char *data;
    size_t size;
    size_t capacity;
} ByteBuffer;

static bool byte_buffer_valid(const ByteBuffer *buffer) {
    if (buffer == NULL || buffer->size > buffer->capacity) {
        return false;
    }
    return (buffer->capacity == 0) == (buffer->data == NULL);
}

void byte_buffer_init(ByteBuffer *buffer) {
    if (buffer == NULL) {
        return;
    }
    buffer->data = NULL;
    buffer->size = 0;
    buffer->capacity = 0;
}

void byte_buffer_destroy(ByteBuffer *buffer) {
    if (buffer == NULL) {
        return;
    }
    free(buffer->data);
    byte_buffer_init(buffer);
}

static size_t choose_capacity(
    size_t current,
    size_t minimum
) {
    size_t next = current == 0 ? 16 : current;

    while (next < minimum) {
        if (next > SIZE_MAX / 2) {
            return minimum;
        }
        next *= 2;
    }
    return next;
}

bool byte_buffer_reserve(
    ByteBuffer *buffer,
    size_t min_capacity
) {
    if (!byte_buffer_valid(buffer)) {
        return false;
    }
    if (min_capacity <= buffer->capacity) {
        return true;
    }

    size_t next = choose_capacity(
        buffer->capacity,
        min_capacity
    );
    unsigned char *replacement = realloc(buffer->data, next);
    if (replacement == NULL) {
        return false;
    }

    buffer->data = replacement;
    buffer->capacity = next;
    return true;
}

bool byte_buffer_append(
    ByteBuffer *buffer,
    const void *source,
    size_t count
) {
    if (!byte_buffer_valid(buffer)) {
        return false;
    }
    if (count == 0) {
        return true;
    }
    if (source == NULL || count > SIZE_MAX - buffer->size) {
        return false;
    }

    size_t required = buffer->size + count;
    if (!byte_buffer_reserve(buffer, required)) {
        return false;
    }

    memcpy(buffer->data + buffer->size, source, count);
    buffer->size = required;
    return true;
}

来源与改编

题型借鉴 NIST Juliet Test Suite for C/C++ 1.3 中关于分配大小溢出与堆缓冲区越界的测试思路。Juliet 1.3 属于公共领域，并以 CC0 1.0 处理可能存在的境外权利。本题的接口、约束、实现与说明均已重新编写，完整记录见习题来源与许可。