# simple_queue

**Repository Path**: niuhaoyun/simple_queue

## Basic Information

- **Project Name**: simple_queue
- **Description**: 超轻量级、无动态内存分配的通用 FIFO 队列库，适用于嵌入式系统和资源受限环境。
- **Primary Language**: C
- **License**: AGPL-3.0
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 4
- **Created**: 2026-07-02
- **Last Updated**: 2026-07-02

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

# Simple Queue

超轻量级、无动态内存分配的通用 FIFO 队列库，适用于嵌入式系统和资源受限环境。

## 特性

- 📦 **通用类型支持** — 支持任意数据类型（基本类型、结构体等）
- 💾 **无动态内存分配** — 用户自行管理缓冲区，零 malloc/free
- 🔒 **中断安全** — 单生产者单消费者（SPSC）模型下无需加锁
- ⚡ **零拷贝 API** — 直接获取缓冲区地址，避免多余的数据拷贝
- 👁️ **数据窥读** — 支持 peek 操作，不修改队列状态即可查看数据
- 💯 **无空间浪费** — 采用单调递增索引设计，缓冲区全部可用，不浪费元素空间
- ⚙️ **紧凑配置** — 可配置索引变量大小，最小化内存占用
- 🚀 **高性能** — 支持 2 的幂次容量优化（位运算替代取模）和快速拷贝（针对 1/2/4 字节类型）
- 📜 **兼容C89语法** — 所有API函数均符合C89语法规范，可兼容C51等旧式编译器（头文件需自行引入）

## 📖 API 参考

### 基础操作

| 函数 | 说明 |
|------|------|
| `simple_queue_init()` | 初始化队列（绑定用户缓冲区） |
| `simple_queue_deinit()` | 反初始化队列 |
| `simple_queue_write()` | 入队（拷贝方式） |
| `simple_queue_read()` | 出队（拷贝方式，out_data 传 NULL 可仅跳过） |

### 状态查询

| 函数 | 说明 |
|------|------|
| `simple_queue_is_empty()` | 队列是否为空 |
| `simple_queue_is_full()` | 队列是否已满 |
| `simple_queue_get_size()` | 队列总容量 |
| `simple_queue_get_used()` | 已存元素数量 |
| `simple_queue_get_free()` | 剩余可用空间 |
| `simple_queue_reset()` | 重置队列（清空） |

### 窥读与跳过

| 函数 | 说明 |
|------|------|
| `simple_queue_peek()` | 窥读指定数量元素（可设置跳过数量） |
| `simple_queue_skip()` | 跳过指定数量元素（可设置跳过数量） |

### 零拷贝 API

| 函数 | 说明 |
|------|------|
| `simple_queue_get_zero_copy_read_addr()` | 获取当前可读地址 |
| `simple_queue_get_zero_copy_read_num()` | 获取当前连续可读数量 |
| `simple_queue_skip_zero_copy_read_num()` | 跳过已读元素，推进读指针 |
| `simple_queue_get_zero_copy_write_addr()` | 获取当前可写地址 |
| `simple_queue_get_zero_copy_write_num()` | 获取当前连续可写数量 |
| `simple_queue_skip_zero_copy_write_num()` | 跳过已写元素，推进写指针 |

> **注意**：零拷贝 API 返回的是**连续**可读/可写的内存段。当队列发生回环时，数据可能分散在缓冲区头部和尾部，需要分两次获取和处理。

## 🧠 设计原理

### 三种队列实现方式对比

常见的环形队列（FIFO / Ring Buffer）有以下三种实现方式，本库采用**单调递增索引**设计：

| 特性 | count 计数方式 | 传统回环索引 | 单调递增索引（本库） |
|------|---------------|------------|-------------------|
| **索引行为** | 在 `[0, capacity-1]` 范围内回绕 | 在 `[0, capacity-1]` 范围内回绕 | 只增不减，溢出后自然回绕 |
| **空间利用率** | 100% 利用，无浪费 | 浪费 1 个元素（用于区分空/满） | 100% 利用，无浪费 |
| **判空条件** | `count == 0` | `rd == wr` | `rd == wr` |
| **判满条件** | `count == capacity` | `(wr + 1) & mask == rd` | `wr - rd == capacity` |
| **get_used** | `count` | `(wr - rd + capacity) & mask` | `wr - rd` |
| **get_free** | `capacity - count` | `(rd - wr - 1 + capacity) & mask` | `capacity - (wr - rd)` |
| **入队操作** | `wr = (wr + 1) & mask; count++` | `wr = (wr + 1) & mask` | `wr++` |
| **出队操作** | `rd = (rd + 1) & mask; count--` | `rd = (rd + 1) & mask` | `rd++` |
| **位置映射** | 索引本身就是位置 | 索引本身就是位置 | `idx & mask` |
| **SPSC 线程安全** | ❌ 不安全（需加锁） | ✅ 安全 | ✅ 安全 |

下面逐一分析前两种方案的缺陷，以及单调递增索引如何同时解决这些问题。

---

### 方案一：count 计数方式 — SPSC 下不安全

count 方式用一个独立的计数器记录已用元素数量，判空判满直观，但在 SPSC（单生产者单消费者）中断场景下**存在致命缺陷**：

```c
#define MASK (capacity - 1)
bool is_empty(void)  { return count == 0; }
bool is_full(void)   { return count == capacity; }

// 生产者
bool enqueue(uint8_t data) {
    if (is_full()) return false;
    buf[wr & MASK] = data;
    wr = (wr + 1) & MASK;
    count++;  // ❌ 生产者修改 count
    return true;
}

// 消费者
bool dequeue(uint8_t *data) {
    if (is_empty()) return false;
    *data = buf[rd & MASK];
    rd = (rd + 1) & MASK;
    count--;  // ❌ 消费者也修改 count
    return true;
}
```

**问题**：`count++` 和 `count--` 都是非原子操作（读-改-写），生产者和消费者同时修改同一个变量 `count`，在中断抢占下会产生竞争态，导致计数错误。

**补救方案**：使用原子操作或互斥锁保护 `count`。但这会引入额外的性能开销和复杂度，违背了嵌入式轻量级队列的设计初衷。

---

### 方案二：传统回环索引 — 浪费一个元素空间

传统回环索引不用计数器，`rd` 和 `wr` 都在 `[0, capacity-1]` 范围内循环回绕。判空很简单（`rd == wr`），但判满时遇到了问题：

**核心矛盾**：当队列真正装满时，`wr` 的下一个位置恰好是 `rd`，即 `wr == rd`——这与队列为空的条件完全相同，无法区分。

**解决方案**：故意预留一个空位，让队列最多只能存 `capacity - 1` 个元素。判满条件变为 `(wr + 1) & mask == rd`（"再写一个就会和读指针重合"）。

```c
#define MASK (capacity - 1)

bool is_empty(void)  { return rd == wr; }
bool is_full(void)   { return ((wr + 1) & MASK) == rd; }  // 预留一个空位

// 生产者
bool enqueue(uint8_t data) {
    if (is_full()) return false;
    buf[wr & MASK] = data;
    wr = (wr + 1) & MASK;
    return true;
}

// 消费者
bool dequeue(uint8_t *data) {
    if (is_empty()) return false;
    *data = buf[rd & MASK];
    rd = (rd + 1) & MASK;
    return true;
}
```

这个预留的空位就是浪费的存储空间。虽然只浪费一个元素，但在缓冲区本身就很小的嵌入式场景中，这个浪费是不可忽视的。

---

### 方案三：单调递增索引（本库采用）— 同时解决上述两个问题

单调递增索引的核心思想：**`rd` 和 `wr` 只增不减，溢出后自然回绕**。通过 `wr - rd` 的差值来判断队列状态，而不是依赖指针的相对位置。

```c
#define MASK (capacity - 1)

bool is_empty(void) { return rd == wr; }         
bool is_full(void)  { return (wr - rd) == capacity; }

// 生产者
bool enqueue(uint8_t data) {
    if (is_full()) return false;
    buf[wr & MASK] = data;
    wr++;  // 只增不减
    return true;
}

// 消费者
bool dequeue(uint8_t *data) {
    if (is_empty()) return false;
    *data = buf[rd & MASK];
    rd++;  // 只增不减
    return true;
}
```

**为什么不会浪费空间？** 传统方法用 `rd == wr` 同时表示空和满，产生歧义。单调递增方法用差值区分：空时 `wr - rd == 0`，满时 `wr - rd == capacity`，两者永远不会冲突，因此可以 100% 利用缓冲区。

**为什么减法不会产生负数？** 当 `wr` 溢出回绕到 0 而 `rd` 还未溢出时，从数值上看 `wr < rd`，似乎应该得到负数。但无符号整数减法遵循模运算规则：`wr - rd` 的实际结果是 `(wr - rd) mod 2^32`。例如 `wr = 0x00000005`，`rd = 0xFFFFFFF0`，则 `wr - rd = 0x00000015`（即十进制的 21），这正是队列中实际存储的元素数量。无符号整数永远不会产生负数，差值始终正确反映队列状态。

**为什么 SPSC 下中断安全？** 生产者只修改 `wr`，消费者只修改 `rd`，双方永远不会同时修改同一个变量，天然避免了写写冲突。

#### 单调递增索引的优势总结

| 优势 | 说明 |
|------|------|
| **高效简洁** | 索引递增只需 `wr++` / `rd++`，无需位运算或取模 |
| **计算简单** | `get_used` / `get_free` 计算量骤降，无需加 `&capacity` 修正 |
| **零浪费** | 100% 利用缓冲区空间，无需预留一个元素做标记 |
| **原理清晰** | 利用无符号整数溢出特性，差值天然正确 |

---

### 为什么需要 `volatile`？

在 32 位 MCU 上，编译器可能将 `rd` / `wr` 缓存到寄存器中进行优化。声明为 `volatile` 确保：
1. 主线程修改后，中断能读到最新值
2. 中断修改后，主线程检查时不会使用寄存器中的旧值

## ⚙️ 配置选项

在 `simple_queue.h` 中可配置：

```c
#define USE_SIMPLE_QUEUE_ASSERT         0  // 启用断言检查（调试时开启）
#define USE_SIMPLE_QUEUE_PRINTF         0  // 启用日志输出（调试时开启）
#define USE_SIMPLE_QUEUE_FAST_COPY      1  // 快速拷贝（1/2/4 字节类型优化）
#define USE_SIMPLE_QUEUE_CHECK_INIT     0  // 使用时检查队列是否初始化（默认关闭）
// 可修改对接自定义实现，适配不同平台
#define SIMPLE_QUEUE_PRINTF printf        // 日志输出函数
#define SIMPLE_QUEUE_MEMCOPY memcpy       // 内存拷贝函数
#define SIMPLE_QUEUE_MEMSET memset        // 内存填充函数
```

## 🚀 快速开始

### 1. 基础类型入队 / 出队

```c
static queue_t my_queue;
static uint8_t queue_buf[8 * sizeof(int32_t)];
simple_queue_init(&my_queue, queue_buf, sizeof(queue_buf), sizeof(int32_t));

int32_t data = 42;
simple_queue_write(&my_queue, &data);   // 入队

int32_t out;
simple_queue_read(&my_queue, &out);     // 出队，out == 42
```

### 2. 结构体类型入队 / 出队

```c
typedef struct {
    int32_t id;
    float value;
    char name[16];
} sensor_data_t;

static queue_t sensor_queue;
static uint8_t sensor_buf[8 * sizeof(sensor_data_t)];

simple_queue_init(&sensor_queue, sensor_buf, sizeof(sensor_buf), sizeof(sensor_data_t));

// 入队
sensor_data_t in = {1, 3.14f, "temp"};
simple_queue_write(&sensor_queue, &in);

// 出队
sensor_data_t out;
simple_queue_read(&sensor_queue, &out);
// out.id == 1, out.value == 3.14f, out.name == "temp"
```

### 4. 零拷贝读写

```c
typedef struct {
    int32_t id;
    float value;
} sensor_t;

static queue_t my_queue;
static uint8_t queue_buf[8 * sizeof(sensor_t)];
simple_queue_init(&my_queue, queue_buf, sizeof(queue_buf), sizeof(sensor_t));

// 获取连续可写空间，直接写入
sensor_t* write_addr = (sensor_t*)simple_queue_get_zero_copy_write_addr(&my_queue);
queue_base_t write_num = simple_queue_get_zero_copy_write_num(&my_queue);


// 写入数据
for (int i = 0; i < write_num; i++) {
    write_addr[i].id = i;
    write_addr[i].value = i * 1.0f;
}
simple_queue_skip_zero_copy_write_num(&my_queue, write_num); // 推进写指针
// 已写入 8 个元素: {0, 0.0}, {1, 1.0}, ..., {7, 7.0}

// 获取连续可读空间，直接读取
sensor_t* read_addr = (sensor_t*)simple_queue_get_zero_copy_read_addr(&my_queue);
queue_base_t read_num = simple_queue_get_zero_copy_read_num(&my_queue);

// 读取数据
for (int i = 0; i < read_num; i++) {
    process(&read_addr[i]); // 处理读取到的数据
}
simple_queue_skip_zero_copy_read_num(&my_queue, read_num); // 推进读指针
// 读取到 8 个元素: read_addr[0].id == 0, read_addr[1].id == 1, ..., read_addr[7].id == 7
```

### 4. 窥读（Peek）

```c
typedef struct {
    int32_t id;
    float value;
} sensor_t;

static queue_t my_queue;
static uint8_t queue_buf[8 * sizeof(sensor_t)];
simple_queue_init(&my_queue, queue_buf, sizeof(queue_buf), sizeof(sensor_t));

// 先入队一些数据
sensor_t data[4] = {
    {1, 1.0f}, {2, 2.0f}, {3, 3.0f}, {4, 4.0f}
};

// 入队4个元素
for (int i = 0; i < 4; i++) {
    simple_queue_write(&my_queue, &data[i]);
}

// 窥读数据（不移动读指针）
sensor_t peek_data[3];
// 跳过第 1 个元素，窥读接下来的 3 个元素
simple_queue_peek(&my_queue, peek_data, 1, 3);
// peek_data[0] == {2, 2.0f}
// peek_data[1] == {3, 3.0f}
// peek_data[2] == {4, 4.0f}
// 队列中仍有 4 个元素，读指针未移动

// 可以使用 simple_queue_read 传入 NULL 来跳过第一个元素
simple_queue_read(&my_queue, NULL);  
// 队列中剩余 3 个元素，读指针前进 1 个位置
// 也可以使用 simple_queue_skip 来跳过多个元素
simple_queue_skip(&my_queue, 3);
// 队列中剩余 0 个元素，读指针前进 3 个位置
```