# LyDSS

**Repository Path**: Luyi365/LyDSS

## Basic Information

- **Project Name**: LyDSS
- **Description**: Luyi DataStore Struct —— 一组面向嵌入式的 C 容器实现。
- **Primary Language**: C
- **License**: Apache-2.0
- **Default Branch**: main
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 1
- **Forks**: 0
- **Created**: 2026-10-13
- **Last Updated**: 2026-10-13

## Categories & Tags

**Categories**: Uncategorized

**Tags**: C语言, container, embedded, Data-structures, cmake

## README

# LyDSS

> [!CAUTION]
> - **目前为预览版本，后续迭代会产生破坏性更改。**
> - **暂时未提供并发保护，跨中断或多线程共用时由调用者加临界区。**

**L**u**y**i **D**ata**S**tore **S**truct —— 一组面向嵌入式的 C 容器库。

十一个容器（池、数组、动态数组、乒乓缓冲、栈、队列、链表、流、表、集合、桶）分层清晰，各编译成一个独立静态库，**互不依赖**。

## 主旨

- **面向嵌入式，跨平台、无依赖，合理拥抱新特性**：基线 C11，只依赖 C 标准头文件，不用编译器扩展、POSIX 或第三方库，在能带来清晰收益时引入新语言特性。
- **功能与代码保持极简**：只实现主流场景，绝不为极端个例或少数使用场景引入可能损害整体性能、代码体积或稳定性的代码。

## TODO

- [ ] 增加并发场景
- [ ] 补充位级容器

## 使用指南

### 接入

保持 `inc/` 与 `src/` 的相对位置，把用到的容器源文件 `src/ly<容器>.c` 加入工程编译，并把 `inc/` 加入头文件搜索路径。各容器互不依赖，只拷贝需要的源文件即可。

```c
#include "lydss_api.h"

static LyQueueStatic_t queue_storage;
static int queue_buffer[8];

void app(void)
{
    LyQueue_t *queue = lyqueue_create_static(&queue_storage, queue_buffer, 8, sizeof(int));
    int value = 42;

    lyqueue_send(queue, &value);
    lyqueue_receive(queue, &value);
    lyqueue_delete(queue);
}
```

### 构建与测试

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

### 配置

`inc/lydss_cfg.h` 为每个容器提供一个开关：

```c
#ifndef LYDSS_XXX_ENABLED
#define LYDSS_XXX_ENABLED 1
#endif
```

开关包在 `#ifndef` 里，在构建系统里定义同名宏即可覆盖，不必修改仓库文件。被关掉的容器不参与编译。各容器的默认状态、静态构造开关与专属参数见 `lydss_cfg.h` 中对应模块的配置节。

## 特征对比

图例：✓ 具备 ｜ ✗ 不具备 ｜ ◐ 部分具备或有前提，见脚注。

| | 连续内存 | 有序性 | 可插入 | 记名性 | 关注成员大小 | 关注成员类型 | 环形 | 复用性 | 关联性 | 唯一性 | 支持静态创建 | 拷贝存储 | 接受 NULL 值 | 容量模型 | 查找 / 访问代价 | 释放成员 | 成员地址 |
| :--- | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-: | :-- | :-- | :-: | :-- |
| 池（Pool） | ◐ ¹ | ✗ | ✗ | ✓ | ✗ | ✗ | ✗ | ✓ | ✓ | ✗ | ✓ ⁷ | ✗ | ◐ ⁹ | 定长 | O(n) 名字扫描 | ✗ | 调用者自持 |
| 数组（Array） | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ ⁸ | ✓ | ✗ | 定长 | O(1) 下标 | ✓ ¹² | **终身有效** |
| 动态数组（Vector） | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✗ | ✓ | ✗ | 2 倍自动增长 | O(1) 下标 | ✓ | 重分配后**失效** |
| 乒乓缓冲（PingPong） | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ ⁸ | ✓ | ✗ | 定长，两块等长 | O(1) 整块交付 | ✓ ¹² | **终身有效** |
| 栈（Stack） | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ | ✗ | ✗ | ✓ ⁸ | ✓ | ✗ | 定长 | O(1) 栈顶 | ✓ ¹² | 不暴露 |
| 队列（Queue） | ✓ | ✓ | ✗ | ✗ | ✓ | ✗ | ✓ | ✓ | ✗ | ✗ | ✓ ⁸ | ✓ | ✗ | 定长 | O(1) 端部 | ✓ ¹² | 不暴露 |
| 链表（List） | ✗ | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ | ✗ | ◐ ⁵ | ✗ | ✗ | ✗ | ◐ ⁹ | 无界 | O(1) 端部 / O(n) 遍历 | ✗ | 节点地址稳定 |
| 流（Stream） | ✓ | ✓ | ✗ | ✗ | ◐ ³ | ✗ | ✓ | ✓ | ✗ | ✗ | ✓ ⁸ | ✓ | ✗ | 定长 | O(n) 传输 n 单元 | ✓ ¹² | 不暴露 |
| 表（Table） | ◐ ² | ✗ | ✗ | ✓ | ✗ | ✗ | ✗ | ✗ | ✓ | ✓ | ✗ | ◐ ⁴ | ◐ ⁹ | 负载 0.75 时翻倍 | O(1) 平均 | ✗ | 调用者自持 |
| 集合（Set） | ◐ ² | ✗ | ✗ | ✗ | ✓ | ◐ ⁶ | ✗ | ✗ | ✗ | ✓ | ✗ | ✓ | ✗ ¹¹ | 定长，**不 rehash** | O(1) 平均，可退化 O(n) | ✓ | 不暴露 |
| 桶（Bucket） | ✗ | ✓ | ✓ | ✓ | ✗ | ✗ | ✗ | ✗ | ✓ | ◐ ¹⁰ | ✗ | ◐ ⁴ | ◐ ⁹ | 按节点增长 | O(n) 名字扫描 | ✗ | 节点地址稳定 |

### 列的含义

- **连续内存**：成员本身是否存放在一块连续内存里。
- **有序性**：成员之间是否存在稳定且对外可见的先后关系。
- **可插入**：能否在已有成员**之间**的指定位置放入新成员（只能在端部追加不算）。
- **记名性**：成员是否以字符串名字标识。
- **关注成员大小**：容器是否需要知道单个成员占多少字节。
- **关注成员类型**：容器是否需要知道成员的 C 类型语义。
- **环形**：底层存储是否以环形缓冲实现，读写游标回绕复用空间。
- **复用性**：成员移除后其存储槽位能否被后续成员复用，无需重新分配。
- **关联性**：是否具备「键/名 → 值」的映射语义。
- **唯一性**：容器是否保证成员（或键）不重复。
- **支持静态创建**：能否把成员区绑定到调用者提供的内存上，不调用 `malloc`。
- **拷贝存储**：容器是否为成员建立副本（而非只保留调用者的指针）。
- **接受 NULL 值**：传入 `NULL` 成员是否为合法输入。
- **容量模型**：容量是固定、自动增长还是无上限。
- **查找 / 访问代价**：定位一个成员的渐进复杂度。
- **释放成员**：容器销毁时是否连带释放成员占用的内存。
- **成员地址**：取到的成员地址在后续操作后是否仍然有效。

### 脚注

1. 池的槽位数组是连续的，但登记的对象本身分散在别处。
2. 表和集合的槽位数组连续，挂在槽位上的冲突链节点分散分配。
3. 流的单元类型可配置，默认为字节。
4. 表拷贝键、只存值指针；桶只存名字与项的指针，拷贝元数据。
5. 链表的关联是节点之间的前驱后继关系，不是键到值的映射。
6. 集合本身不识别类型，由调用者通过比较回调注入类型语义。
7. 池的槽位类型布局公开，静态构造时由调用者声明槽位数组。
8. 句柄是不完整类型，静态构造通过尺寸固定的不透明存储类型实现，做法与 FreeRTOS 的 `StaticQueue_t` 相同。
9. 可以存入 `NULL`，但取出或查找也用 `NULL` 表示「不存在 / 为空」，两者无法区分，不建议依赖。
10. 桶有的写入方式保证名字唯一（同名替换），有的不查重。
11. 集合拒绝 `NULL` 成员，返回失败而非断言中止。
12. 静态构造的容器例外：成员区属于调用者，销毁只解除绑定、不释放。标 ✗ 的容器只管理自己的节点，业务对象由调用者负责。

连续存储的容器在创建时拦截 `成员数量 × 成员大小` 的乘法溢出，溢出即创建失败，不会交付短于请求的缓冲区。

---

## 各容器的介绍

### 池（Pool）

- **定位**：名字到对象指针的定长登记表，零额外分配。  
启动阶段把少量全局对象登记进去，之后按名字取用。它不拷贝名字也不拷贝对象，只存指针，登记一个对象的成本就是一次线性扫描。
- **适用**：驱动句柄注册、单例查找表、外设实例的命名索引——数量少、启动后基本只读、名字是编译期字符串常量。

### 数组（Array）

- **定位**：给 C 原生数组补齐运行时元数据的定长存储原语。  
C 的数组一旦退化成指针就丢失了长度和成员大小，跨函数传递必须额外带上这两个值。数组把它们放进句柄一起传。它**刻意不跟踪"用了几个"**，没有追加、插入、删除语义，"已用多少"由上层容器各自表达。
- **适用**：定长缓冲区、查表数据、需要把长度随句柄传递的场合。成员地址在数组销毁前**始终有效**，适合需要长期持有成员地址的场景（硬件寄存器镜像、DMA）。

### 动态数组（Vector）

- **定位**：自持成员区的动态数组。  
已用数量与容量分离：容量按倍数预支、已用数量逐个增长，单次追加摊还 O(1)。它**独立实现**，不建立在数组之上，以保留 `realloc` 原地扩张的能力。
- **适用**：元素数量运行期才确定、以尾部追加为主的收集场景。可预留容量避免中途重分配，收集完成后可把容量收缩到实际用量。

### 乒乓缓冲（PingPong）

- **定位**：两块等长缓冲轮换，一块接受写入（填充块），另一块整块交给消费方（就绪块）。  
生产和消费作用于不同的内存，消费方拿到的永远是完整的一批数据，生产方在此期间不必停下。两块缓冲创建后**不再迁移**，基址可以长期持有并预先配置给 DMA。
- **适用**：ADC/传感器的 DMA 双缓冲采集、音频帧缓冲、按批次处理的数据流——生产节奏固定、消费方需要整批数据。

### 栈（Stack）

- **定位**：定长 LIFO，值拷贝。
- **适用**：递归转迭代时的显式栈、括号/标签配对、撤销历史、状态机的状态回溯、表达式求值。深度可预估时用静态构造，全程无堆分配。

### 队列（Queue）

- **定位**：定长环形 FIFO，值拷贝。  
收发是**全有或全无**语义：整个成员进出成功，或什么都不做。这与流的部分传输是刻意的区别。
- **适用**：事件/命令队列、生产者消费者之间的定长缓冲、按固定结构体收发的消息传递。

### 链表（List）

- **定位**：无界双向链表，只存数据指针。  
节点归容器所有，数据归调用者所有。容量只受可用内存限制。
- **适用**：频繁在中间插入删除；已持有节点因而需要 O(1) 摘除；同一个业务对象要同时挂在多条链上。

### 流（Stream）

- **定位**：定长环形传输通道。  
单元类型可配置，默认为字节。读写返回**实际传输的单元数**，可以少于请求量——这是流的签名特征，表达"通道当前只能吞下这么多"。流和队列都建立在环形缓冲上（业界常见的共享底座，参见 Linux 的 `kfifo`），但处在不同抽象层级：队列是装类型化定长成员的**容器**，流是搬运无类型数据的**通道**。
- **适用**：串口/传感器的收发缓冲、生产与消费速率不匹配的字节管道、协议帧的暂存与拼接。

### 表（Table）

- **定位**：字符串键到值指针的哈希表，链式解决冲突。  
**拷贝键、不拷贝值**：键会复制一份，调用者传入的键可以是临时缓冲；值只保留指针，销毁表不会释放它。负载达到阈值时槽位数翻倍，插入摊还 O(1)，查找平均 O(1)。哈希函数可以自定义，也可使用内置实现。
- **适用**：配置项存取、命令名到处理函数的分发、运行期动态建立的名字到对象映射、键的数量事先未知。

### 集合（Set）

- **定位**：元素唯一的哈希集合，泛型化程度最高。  
集合可以装任意类型的元素，元素以**值副本**存储，元素大小在创建时给定。哈希函数可以自定义或使用内置实现；比较回调必须由调用者提供。
- **适用**：去重、成员判定（"这个 ID 见过吗"）。

### 桶（Bucket）

- **定位**：带元数据的命名双向链表。  
同时具备顺序、命名和每项附带元数据三种能力，是库里语义最丰富的容器。名字和项只存指针，**元数据拷贝存储**。写入分两类：一类保证名字唯一（同名替换）；另一类不查重，但可以指定写入位置。名字、项、元数据可分别修改。
- **适用**：需要"有序 + 可命名 + 带附加信息"的登记表——插件/模块注册表、带优先级的处理链、每项要记住类型或尺寸的对象清单。

---

## 许可

见 [Apache 2.0](LICENSE)。