极简主义者的C语言容器库

原文来自Our Machinery：
minimalist-container-library-in-c-part-1
minimalist-container-library-in-c-part-2

极简主义

---

“The more code you have in a project, the more you have to worry about.”
“More code, more problems!”
越多的代码意味着你需要担忧的也越多。你的代码将会更难理解。除此之外，你还要更多地考虑优化、重构、文档、调试等等。

“We also try to minimize the use of external libraries.”
尽量减少使用外部库。理由如下：

1. 你没法对外部库的表现做出任何保证，如软件大小、性能、编译时间、平台支持等。只有当开发者的目标非常明确，且正好与外部库的目标完全吻合时，才能避免陷入各种问题（罕见情况）。如果你不只是想让你的软件“仅仅能工作”，那么请慎重使用外部库。

2. 外部库会为你的项目引入大量代码（源码或二进制形式）。而更多的代码，意味着你更难弄明白这些代码究竟在做什么。控制代码量的最终目的是使代码易于修改。显然，外部库的代码是很难修改的。

我们也不能因噎废食。原作者鼓励使用single-file source libraries。因为这些文件都是简洁的，且有很明确的目的。不推荐使用类似boost这样的“怀有巨大野心”的big sprawling libraries.

容器类型

---

容器通常指如队列、列表、栈、数组等用来容纳和索引对象的数据结构。它们通常也被称为Abstract data type(ADT)，即抽象数据类型。

容器类型作为项目的基石会给剩余的代码带来巨大的影响，如算法的选择。改变容器类型通常需要重写大部分代码，对于大型项目来说就是一场灾难。因此，我们有必要仔细思考如何选择容器类型。

在原作者以前的项目中，存在着大量的特化容器类型。它们通常只出现一到两次，而且大多情况并没有带来多少益处，完全可以使用更通用的容器来替代来减少代码量。

因此，依极简主义精神，他们只定义了两种容器类型：

• Arrays( or "stretchy buffers")
• Hash tables

No lists, no trees, no strings, no queues, no sets, etc

使用Arrays数组进行通用数据存储，Hash Table哈希表实现快速查找。使用这两种基础类型，我们可以处理平常我们使用的如string,lis等类型。

Array("stretchy buffers")

数组的实现基于Sean Barrett的stretchy_buffer。

由于C不支持模板方法，所以我们必须借助宏。

基本思想是使用普通的C指针来表示数组。

my_type_t* a = NULL;

与C原生数组不同的是，我们在数组头指针前存储额外的信息来记录数组的大小和容量。

Memory layout of a stretchy buffer

struct array_header_t
{
    uint32_t size;
    uint32_t capacity;
};

利用内存偏移，我们可以容易得到这个结构体：

#define array_header(a) \
    ((array_header_t *)((char *)(a) - sizeof(array_header_t)))

其他细节可以参考stretchy buffer implementation。

缺点：许多函数需要宏实现，不易于debug。无法区别普通指针和stretchy buffer指针。

Hashes

STL的hash表实现为std::unordered_map<K,T>。在C中我们可以借用上面实现的strechy buffer：

key_t *keys;
value_t *values;

但这样会遇到一些问题。如果key类型本身是变长的，如字符串，那么会涉及到大量的内存分配和指针跟踪。为解决这个问题，我们可以事先将key做一次哈希:hash(key)->k，然后用k值做索引。同样的，value值也不一定要存在hash表中，我们可以用stretchy buffer来存储，再将数组索引放到hash表中作为值即可。

使用这种方案，我们就不再需要处理通用类型的问题了。哈希表即可定义为：

struct hash_t
{
    uint32_t num_buckets; //没弄明白其作用，有可能是指key buffer的容量
    uint64_t *keys;
    uint64_t *values;
};

注意：我们仍需要考虑hash函数的碰撞问题。如果要根据值得到键值，则还要再建一张索引表。

更多内容请阅读原文和原作者的其他博文。

由于涉及太底层的东西，我暂时就没有深入学习了。对Engine programming感兴趣的同学一定不要错过。