node_path_share

一个高性能、内存高效的路径共享系统，通过反向前驱链表+引用计数机制最大化减少重复路径的内存占用，适配导航路径、文件系统、版本控制、图算法等多场景。

✨ 核心特性

• 极致内存效率：全局节点段共享，高重叠路径场景下内存占用可降至传统方案的1/10~1/100
• 高性能查询优化：中点缓存机制，将路径遍历复杂度从O(N)优化至O(N/2)
• 精细化内存复用：栈式空闲列表机制，复用删除产生的内存空洞，减少内存碎片
• 全链路安全校验：完善的合法性校验，避免无效内存访问、越界操作等未定义行为
• 灵活可扩展：模板化设计，支持任意自定义节点数据类型，无业务侵入
• 全场景接口覆盖：提供路径创建、分支、插入、删除、修改、交换、整合全生命周期操作

🚀 快速开始

// 1. 引入头文件
#include "node_path_share.h"

// 2. 使用命名空间
using namespace node_path;

// 3. 初始化路径共享系统
path_share ps;

// 4. 创建单节点起始路径
path_index main_path = ps.create_path(1001);

// 5. 批量追加节点
ps.add_path_node(main_path, {1002, 1003, 1004, 1005});

// 6. 基于主路径创建分支
path_index branch_path = ps.create_branch(main_path, 2, 2001);

// 7. 获取完整路径
path result;
ps.get_path(branch_path, result);

// 8. 快速查询/修改节点
node_index node = ps(main_path, 3);  // 获取路径指定位置节点
ps(main_path, 2, 1006);             // 修改路径指定位置节点

📦 核心数据结构

基础类型定义

namespace node_path {
    // 基础数据类型
    using data_type_base_unsigned = uint64_t;
    using data_type_base_signed = int64_t;
    
    // 节点相关类型
    using node_index = data_type_base_unsigned;      // 节点唯一编号
    using node_pos = data_type_base_unsigned;        // 节点物理存储位置
    using node_pos_get = data_type_base_unsigned;    // 节点在路径中的逻辑位置
    using node_ref = data_type_base_unsigned;        // 节点共享引用计数
    
    // 路径相关类型
    using path_index = data_type_base_unsigned;      // 路径唯一编号
    using path_pos = data_type_base_unsigned;        // 路径信息物理存储位置
    using path_len = data_type_base_unsigned;        // 路径长度
}

全局常量定义

// 无效值常量
constexpr node_index NODE_INVALID_INDEX = 0xFFFFFFFFFFFFFFFF;
constexpr node_pos NODE_INVALID_POS = 0xFFFFFFFFFFFFFFFF;
constexpr path_index PATH_INVALID_INDEX = 0xFFFFFFFFFFFFFFFF;
constexpr path_len PATH_INVALID_LEN = 0xFFFFFFFFFFFFFFFF;

// 根节点位置
constexpr node_pos NODE_ROOT_POS = 0xFFFFFFFFFFFFFFFE;

📖 完整接口文档

1. 路径创建与分支

函数接口	功能说明	参数说明	返回值
path_index create_path(node_index index)	创建单节点起始路径	index：起始节点编号	新路径编号，创建失败返回 PATH_INVALID_INDEX
path_index create_branch(path_index path, node_pos_get make_pos, node_index index)	基于已有路径的指定位置创建分支路径	path：原路径编号 make_pos：分支节点的逻辑位置 index：分支新增的节点编号	新分支路径编号，创建失败返回 PATH_INVALID_INDEX

2. 路径查询接口

函数接口	功能说明	参数说明	返回值
bool get_path(path_index path_index, path& save) const	获取指定路径的完整节点列表	path_index：目标路径编号 save：输出参数，存储完整路径	成功返回true，失败返回false
bool get_path_all(std::vector& save) const	获取系统中所有路径的完整数据	save：输出参数，存储所有路径	成功返回true，失败返回false
node_index get_path_node_index(path_index path, node_pos_get pos) const noexcept	获取路径指定位置的节点编号	path：目标路径编号 pos：节点在路径中的逻辑位置	节点编号，失败返回 NODE_INVALID_INDEX
bool get_path_node_index_mul(path_index path, const std::vector& pos_mul, std::vector& save) const	批量获取路径多个指定位置的节点编号	path：目标路径编号 pos_mul：待查询的逻辑位置列表（需升序） save：输出参数，存储查询结果	成功返回true，失败返回false
path_len get_path_len(path_index path) const noexcept	获取指定路径的长度	path：目标路径编号	路径长度，失败返回 PATH_INVALID_LEN
size_t get_path_quantity() const noexcept	获取系统中当前的路径总数	无	路径总数

3. 路径修改接口

函数接口	功能说明	参数说明	返回值
bool add_path_node(path_index path, const std::vector& add_node)	批量追加节点到路径末尾	path：目标路径编号 add_node：待追加的节点列表	成功返回true，失败返回false
bool add_path_node_single(path_index path, node_index add_node)	追加单个节点到路径末尾	path：目标路径编号 add_node：待追加的节点编号	成功返回true，失败返回false
bool insert_path_node(path_index path, node_pos_get pos, node_index index)	在路径指定位置插入节点	path：目标路径编号 pos：插入的逻辑位置 index：待插入的节点编号	成功返回true，失败返回false
bool change_path_node(path_index path, node_pos_get pos, node_index index) noexcept	修改路径指定位置的节点编号	path：目标路径编号 pos：修改的逻辑位置 index：新的节点编号	成功返回true，失败返回false
bool del_path_node(path_index path, std::vector& del_node)	批量删除路径中指定位置的节点	path：目标路径编号 del_node：待删除的逻辑位置列表	成功返回true，失败返回false
bool del_path_node_single(path_index path, node_pos_get del_node)	删除路径中指定位置的单个节点	path：目标路径编号 del_node：待删除的逻辑位置	成功返回true，失败返回false
bool exchange_path_part(const path_part& path_one, const path_part& path_sec)	交换两个路径的指定片段（支持同一路径非重叠片段交换）	path_one：第一个路径片段 path_sec：第二个路径片段	成功返回true，失败返回false

4. 路径删除接口

函数接口	功能说明	参数说明	返回值
bool del_path(path_index path)	删除指定路径，自动释放无引用的节点内存	path：待删除的路径编号	成功返回true，失败返回false
void clear()	清空整个共享系统，释放所有路径和节点数据	无	无

5. 系统管理接口

函数接口	功能说明	参数说明	返回值
bool unify()	全局整合所有路径，最大化节点共享效率，处理内存碎片	无	成功返回true，失败返回false
path_state_statistic get_stastic() const noexcept	获取系统状态统计信息（路径数、内存占用、内存使用率等）	无	系统状态统计结构体

6. 运算符重载（便捷调用）

运算符接口	功能说明	等效原生接口
node_index operator()(path_index path, node_pos_get pos) noexcept	快速获取路径指定位置的节点编号	get_path_node_index
bool operator()(path_index path, node_pos_get pos, node_index index) noexcept	快速修改路径指定位置的节点编号	change_path_node
bool operator()(path_index path_index, path& save) const	快速获取完整路径	get_path

📝 完整使用示例

示例1：基础路径增删改查

using namespace node_path;

// 初始化系统
path_share ps;

// 创建路径 [100]
path_index path = ps.create_path(100);

// 追加节点，路径变为 [100, 200, 300, 400]
ps.add_path_node(path, {200, 300, 400});

// 插入节点，路径变为 [100, 200, 250, 300, 400]
ps.insert_path_node(path, 2, 250);

// 修改节点，路径变为 [100, 200, 250, 350, 400]
ps(path, 3, 350);

// 删除节点，路径变为 [100, 200, 350, 400]
ps.del_path_node_single(path, 2);

// 批量查询节点
std::vector positions = {0, 2, 3};
std::vector result;
ps.get_path_node_index_mul(path, positions, result);
// result = [100, 350, 400]

// 获取完整路径
path full_path;
ps(path, full_path);

示例2：路径分支与共享优化

using namespace node_path;

path_share ps;

// 创建主路径 [1,2,3,4,5,6,7,8,9,10]
path_index main_path = ps.create_path(1);
ps.add_path_node(main_path, {2,3,4,5,6,7,8,9,10});

// 创建3条分支路径，共享主路径前缀
path_index branch1 = ps.create_branch(main_path, 4, 101);  // [1,2,3,4,5,101]
path_index branch2 = ps.create_branch(main_path, 6, 201);  // [1,2,3,4,5,6,7,201]
path_index branch3 = ps.create_branch(main_path, 2, 301);  // [1,2,3,301]

// 查看系统状态
path_state_statistic stat = ps.get_stastic();
std::cout << "路径总数：" << stat.quantity_path << std::endl;
std::cout << "内存使用率：" << stat.rate_memory_used * 100 << "%" << std::endl;

// 全局整合，最大化共享效率
ps.unify();

// 删除主路径，分支路径不受影响
ps.del_path(main_path);

⚡ 性能指标

操作类型	时间复杂度	性能说明
单节点路径创建	O(1)	单节点创建开销极小
路径分支创建	O(K)	K为分支位置到路径起点的距离，共享节点无拷贝
单节点随机查询	O(N/2)	中点缓存优化，比纯反向链表快50%
批量节点查询	O(N/2 + K)	K为查询数量，一次遍历完成所有查询
路径编号查找	O(log M)	M为路径总数，二分查找实现
末尾节点追加	O(1)	无共享场景下无额外开销
节点插入/修改/删除	O(K)	K为操作位置到路径末尾的距离，仅拷贝需独立化的节点
路径删除	O(N)	N为路径长度，仅释放无引用的节点
全局共享整合	O(M*N)	M为路径总数，N为平均路径长度，建议低频调用

🎯 适用场景

• 智能导航系统：城市道路网络中大量重叠导航路径的存储与管理
• 分布式文件系统：目录树结构的高效存储、硬链接管理
• 版本控制系统：Git等版本工具的分支路径、提交链管理
• 图数据库/图算法：图遍历路径缓存、最短路径预计算
• 工作流引擎：审批流、业务流程的路径管理与版本控制
• 嵌入式/边缘设备：内存资源受限的场景，极致的内存利用率

⚠️ 注意事项

• 本系统非线程安全，多线程并发场景下需自行添加读写锁保护
• 写操作（插入、修改、删除）会触发节点独立化，路径重叠率越高，写放大越明显
• 超长路径的随机访问性能有限，更适合批量查询、顺序访问场景
• 自定义节点数据需业务层自行维护编号与数据的映射关系
• 定期调用 unify() 可最大化共享效率，处理内存碎片，建议空闲时段执行
• 批量查询接口要求传入的位置列表为升序排列，否则会导致查询结果错误

📄 许可证

本项目采用 MIT License 开源许可证，可自由使用、修改和分发。

🤝 贡献指南

欢迎提交 Issue 反馈问题，也欢迎提交 Pull Request 参与代码贡献！

1. Fork 本仓库
2. 创建你的功能分支
3. 提交你的修改
4. 推送到分支
5. 创建 Pull Request