# kfifo

**Repository Path**: Createtree/kfifo

## Basic Information

- **Project Name**: kfifo
- **Description**: lock-free single producer single consumer byte fifo
- **Primary Language**: Unknown
- **License**: Apache-2.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2026-05-25
- **Last Updated**: 2026-05-25

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# kfifo

`kfifo` 是一个面向嵌入式数据接收场景的无锁字节队列。它使用调用者提供的静态内存作为环形缓冲区，不依赖动态内存分配，适合串口、SPI、CAN、DMA 回调、采样缓存等数据流处理。

## 特性

- 单生产者、单消费者无锁设计，适合“中断/回调写入，主循环/任务读取”的场景。
- 支持完全静态内存创建，不调用 `malloc` 和 `free`。
- 默认只支持 2 的幂容量，使用 `index & mask` 计算环形索引，避免运行期除法或取模。
- 可通过 `KFIFO_SUPPORT_NON_POWER_OF_TWO=1` 编译宏切换为非 2 的幂容量支持，此时使用取模计算索引。
- 默认配置下 `kfifo_t` 只保存 `mask`，非 2 的幂支持配置下只保存 `size`，不会同时保存两套字段。
- `in` / `out` 使用 16 位计数器，匹配当前 `uint16_t` 容量和读写长度接口，减少结构体空间占用。
- 环形缓冲区可用满容量，不额外浪费一个字节区分空满。
- 写入和读取都支持部分成功，方便处理缓冲区空间不足或数据不足。
- 支持 `peek` 预读，不移动读指针。
- 提供 Makefile、CMake 和单元测试文件。

## 功能

- `kfifo_constructor()`：使用外部静态数组初始化队列。
- `KFIFO_STATIC_CREATE()`：一行宏完成静态对象和静态缓冲区创建。
- `kfifo_write()`：写入字节流。
- `kfifo_read()`：读取字节流。
- `kfifo_peek()`：预读字节流，不消费数据。
- `kfifo_reset()`：清空队列。
- `kfifo_get_size()`：获取队列容量。
- `kfifo_get_used()`：获取已用字节数。
- `kfifo_get_free()`：获取剩余字节数。
- `kfifo_is_empty()`：判断队列是否为空。
- `kfifo_is_full()`：判断队列是否已满。

## 适用场景

- 串口 RX 中断中写入数据，主循环中解析协议帧。
- DMA 半满/全满回调中搬运数据，任务中批量处理。
- 传感器采样回调中写入采样值，后台任务中滤波或上传。
- 通信模块接收缓存，例如 BLE、LoRa、CAN 网关数据暂存。

## 并发模型

本模块的无锁范围是单生产者、单消费者：

- 只有一个执行上下文调用 `kfifo_write()`。
- 只有一个执行上下文调用 `kfifo_read()` 或 `kfifo_peek()`。
- `kfifo_reset()` 和 `kfifo_destructor()` 需要在没有并发读写时调用。

若存在多个生产者或多个消费者，需要在外部增加互斥、临界区，或改用支持 MPMC 的队列。

## 文件说明

- `kfifo.h`：公共类型、宏和 API 声明。
- `kfifo.c`：队列实现。
- `kfifo_test.c`：单元测试。
- `Makefile`：基于 GCC/AR 的简单构建入口。
- `CMakeLists.txt`：CMake 构建入口。

## 使用方法

### 默认模式：2 的幂容量

默认模式不支持非 2 的幂容量。推荐使用 `64`、`128`、`256`、`512` 等容量：

```c
#include "kfifo.h"

KFIFO_STATIC_CREATE(rx_fifo, 128U);

void uart_rx_callback(uint8_t byte)
{
    uint16_t write_len = 0;

    (void)kfifo_write(&rx_fifo, &byte, 1U, &write_len);
}

void main_loop(void)
{
    uint8_t buffer[32];
    uint16_t read_len = 0;

    if (KFIFO_STATUS_EMPTY != kfifo_read(&rx_fifo,
                                         buffer,
                                         sizeof(buffer),
                                         &read_len))
    {
        /* 处理 buffer[0..read_len-1] */
    }
}
```

使用外部静态缓冲区初始化：

```c
static kfifo_t rx_fifo;
static uint8_t rx_buffer[256];

void app_init(void)
{
    (void)kfifo_constructor(&rx_fifo, rx_buffer, sizeof(rx_buffer));
}
```

### 非 2 的幂容量支持

如果确实需要 `30`、`100`、`300` 这类非 2 的幂容量，请在编译时打开宏：

```sh
make clean
make test CFLAGS="-std=c99 -Wall -Wextra -pedantic -DKFIFO_SUPPORT_NON_POWER_OF_TWO=1"
```

CMake：

```sh
cmake -S . -B build -DKFIFO_SUPPORT_NON_POWER_OF_TWO=ON
cmake --build build
ctest --test-dir build --output-on-failure
```

打开该宏后，队列内部保存 `size` 并使用 `% size` 计算索引；关闭该宏时，队列内部保存 `mask` 并使用 `& mask` 计算索引。

## 返回值说明

- `KFIFO_STATUS_OK`：操作完全成功。
- `KFIFO_STATUS_PARTIAL`：只完成了部分读写。
- `KFIFO_STATUS_EMPTY`：读取或预读时队列为空。
- `KFIFO_STATUS_FULL`：写入时队列已满。
- `KFIFO_STATUS_INVALID_PARAM`：参数非法。
- `KFIFO_STATUS_NOT_INITED`：对象尚未初始化。
- `KFIFO_STATUS_INITED`：对象已经初始化。

写入和读取接口都会通过 `pWriteLen` 或 `pReadLen` 返回实际处理长度。该参数可以传入 `NULL`，表示不关心实际长度。

## 构建与测试

使用 Makefile：

```sh
make
make test
make clean
```

使用 CMake：

```sh
cmake -S . -B build
cmake --build build
ctest --test-dir build --output-on-failure
```

如果在 Windows 上使用 MinGW/GNU make，而 CMake 默认选择了不可用的 `NMake Makefiles`，可以显式指定生成器和编译器：

```sh
cmake -S . -B build -G "Unix Makefiles" -DCMAKE_MAKE_PROGRAM=make -DCMAKE_C_COMPILER=gcc
cmake --build build
ctest --test-dir build --output-on-failure
```

只构建库、不构建测试：

```sh
cmake -S . -B build -DKFIFO_BUILD_TESTS=OFF
cmake --build build
```

## 设计说明

队列内部使用递增的 `in` 和 `out` 计数器记录写入位置和读取位置。由于生产者只修改 `in`，消费者只修改 `out`，在单生产者、单消费者模型下不需要锁。

默认配置下容量必须是 2 的幂，模块只保存 `mask = size - 1`，访问缓冲区时使用 `index & mask`。这条路径速度更快，结构体也更小，适合作为嵌入式默认方案。

打开 `KFIFO_SUPPORT_NON_POWER_OF_TWO=1` 后，模块保存 `size` 并使用 `index % size`。这条路径更灵活，但通常会带来更高的索引计算开销。

`kfifo.c` 中提供了 `KFIFO_MEMORY_BARRIER()` 宏，默认在 GCC 下使用编译器内存屏障。若目标平台有更严格的内存顺序要求，可以在编译选项或平台头文件中自定义该宏。

## 使用建议

- 优先选择 2 的幂容量，例如 `128U` 或 `256U`。
- 缓冲区大小建议按“最大突发数据量 + 消费延迟期间新增数据量”估算。
- 中断中调用 `kfifo_write()` 时，建议只做数据搬运，协议解析放到主循环或任务中。
- 如果写入返回 `KFIFO_STATUS_FULL` 或 `KFIFO_STATUS_PARTIAL`，说明消费速度不足或缓存太小，需要根据业务决定丢弃、统计溢出或扩大缓存。
- 不要在读写并发过程中调用 `kfifo_reset()`。

## 用例：串口协议解析

```c
#include "kfifo.h"

KFIFO_STATIC_CREATE(uart_fifo, 512U);

void uart_rx_isr(uint8_t byte)
{
    uint16_t write_len = 0;

    if (KFIFO_STATUS_OK != kfifo_write(&uart_fifo, &byte, 1U, &write_len))
    {
        /* 可在这里统计溢出次数 */
    }
}

void protocol_task(void)
{
    uint8_t data[64];
    uint16_t read_len = 0;

    while (!kfifo_is_empty(&uart_fifo))
    {
        (void)kfifo_read(&uart_fifo, data, sizeof(data), &read_len);

        if (read_len > 0U)
        {
            /* parse_protocol(data, read_len); */
        }
    }
}
```

## 许可证

本项目使用 Apache License 2.0 开源许可证发布。完整许可证内容见 `LICENSE` 文件，主要源码文件也包含 `SPDX-License-Identifier: Apache-2.0` 声明，便于自动化工具识别许可证。

## 更新日志

### v0.0.1 - 2026.05.25

- 创建 `kfifo` 无锁单生产者、单消费者字节队列。
- 支持静态内存创建和外部静态缓冲区初始化。
- 增加读、写、预读、重置和状态查询接口。
- 默认配置改为仅支持 2 的幂容量，非 2 的幂容量通过 `KFIFO_SUPPORT_NON_POWER_OF_TWO` 宏选择。
- 优化 `kfifo_t` 结构体字段，只保存当前配置需要的 `mask` 或 `size`。
- 将 `in` / `out` 计数器调整为 16 位，减少结构体空间占用。
- 增加单元测试 `kfifo_test.c`。
- 增加 Makefile、CMakeLists.txt 和中文 README 文档。