klib
1.0.0
Klib 是一个独立的轻量级 C 库，在 MIT/X11 许可证下分发。除标准C 库外，大多数组件都独立于外部库，并且彼此独立。要使用该库的组件，您只需将几个文件复制到源代码树中，而不必担心库依赖性。
Klib 致力于提高效率和减少内存占用。就速度和内存使用而言，某些组件（例如 khash.h、kbtree.h、ksort.h 和 kvec.h）是所有编程语言中类似算法或数据结构的最有效实现。
此处提供了新文档，其中包含此自述文件中的大部分信息。
为了实现通用容器，klib 广泛使用 C 宏。为了使用这些数据结构，我们通常需要通过扩展一个长宏来实例化方法。这使得源代码看起来不寻常甚至丑陋，并且增加了调试的难度。不幸的是，对于缺乏模板的 C 语言的高效泛型编程，使用宏是唯一的解决方案。只有使用宏，我们才能编写一个通用容器，一旦实例化，它就可以与特定类型的容器竞争效率。 C 中的一些通用库（例如 Glib）使用void*类型来实现容器。这些实现通常比 klib 更慢并且使用更多内存（请参阅此基准测试）。
为了有效地使用 klib，了解它如何实现泛型编程非常重要。我们将以哈希表库为例：
#include "khash.h"
KHASH_MAP_INIT_INT(m32, char) // instantiate structs and methods
int main() {
int ret, is_missing;
khint_t k;
khash_t(m32) *h = kh_init(m32); // allocate a hash table
k = kh_put(m32, h, 5, &ret); // insert a key to the hash table
if (!ret) kh_del(m32, h, k);
kh_value(h, k) = 10; // set the value
k = kh_get(m32, h, 10); // query the hash table
is_missing = (k == kh_end(h)); // test if the key is present
k = kh_get(m32, h, 5);
kh_del(m32, h, k); // remove a key-value pair
for (k = kh_begin(h); k != kh_end(h); ++k) // traverse
if (kh_exist(h, k)) // test if a bucket contains data
kh_value(h, k) = 1;
kh_destroy(m32, h); // deallocate the hash table
return 0;
}
在此示例中，第二行实例化一个哈希表，其中unsigned作为键类型， char作为值类型。 m32命名了这种类型的哈希表。与该名称关联的所有类型和函数都是宏，稍后将对此进行解释。宏kh_init()启动一个哈希表，然后kh_destroy()释放它。 kh_put()插入一个键并返回哈希表中的迭代器（或位置）。 kh_get()和kh_del()分别获取一个键和删除一个元素。宏kh_exist()测试迭代器（或位置）是否已填充数据。
一个迫在眉睫的问题是这段代码看起来不像一个有效的 C 程序（例如缺少分号、对明显函数调用的赋值以及明显未定义的m32 “变量”）。为了理解为什么代码是正确的，让我们进一步研究khash.h的源代码，其框架如下：
#define KHASH_INIT(name, SCOPE, key_t, val_t, is_map, _hashf, _hasheq)
typedef struct {
int n_buckets, size, n_occupied, upper_bound;
unsigned *flags;
key_t *keys;
val_t *vals;
} kh_##name##_t;
SCOPE inline kh_##name##_t *init_##name() {
return (kh_##name##_t*)calloc(1, sizeof(kh_##name##_t));
}
SCOPE inline int get_##name(kh_##name##_t *h, key_t k)
...
SCOPE inline void destroy_##name(kh_##name##_t *h) {
if (h) {
free(h->keys); free(h->flags); free(h->vals); free(h);
}
}
#define _int_hf(key) (unsigned)(key)
#define _int_heq(a, b) (a == b)
#define khash_t(name) kh_##name##_t
#define kh_value(h, k) ((h)->vals[k])
#define kh_begin(h, k) 0
#define kh_end(h) ((h)->n_buckets)
#define kh_init(name) init_##name()
#define kh_get(name, h, k) get_##name(h, k)
#define kh_destroy(name, h) destroy_##name(h)
...
#define KHASH_MAP_INIT_INT(name, val_t)
KHASH_INIT(name, static, unsigned, val_t, is_map, _int_hf, _int_heq)
KHASH_INIT()是一个巨大的宏，定义了所有的结构和方法。当这个宏被调用时，它里面的所有代码都会被C预处理插入到它被调用的地方。如果多次调用宏，则会插入代码的多个副本。为了避免具有不同键值类型的哈希表的命名冲突，该库使用标记串联，这是一种预处理器功能，我们可以根据宏的参数替换部分符号。最后，C 预处理器将生成以下代码并将其提供给编译器（宏kh_exist(h,k)有点复杂，为简单起见未展开）：
typedef struct {
int n_buckets, size, n_occupied, upper_bound;
unsigned *flags;
unsigned *keys;
char *vals;
} kh_m32_t;
static inline kh_m32_t *init_m32() {
return (kh_m32_t*)calloc(1, sizeof(kh_m32_t));
}
static inline int get_m32(kh_m32_t *h, unsigned k)
...
static inline void destroy_m32(kh_m32_t *h) {
if (h) {
free(h->keys); free(h->flags); free(h->vals); free(h);
}
}
int main() {
int ret, is_missing;
khint_t k;
kh_m32_t *h = init_m32();
k = put_m32(h, 5, &ret);
if (!ret) del_m32(h, k);
h->vals[k] = 10;
k = get_m32(h, 10);
is_missing = (k == h->n_buckets);
k = get_m32(h, 5);
del_m32(h, k);
for (k = 0; k != h->n_buckets; ++k)
if (kh_exist(h, k)) h->vals[k] = 1;
destroy_m32(h);
return 0;
}
这就是我们所知道的C程序。
从这个例子中，我们可以看出宏和C预处理器在klib中起着关键作用。 Klib 速度快的部分原因是编译器在编译时知道键值类型，并且能够将代码优化到与特定类型代码相同的级别。用void*编写的通用库不会获得这样的性能提升。
在实例化时大量插入代码可能会让我们想起C++在使用STL/boost时的缓慢编译速度和巨大的二进制大小。由于代码量小且组件独立，Klib 在这方面要好得多。插入几百行代码不会使编译明显变慢。
void*进行泛型编程可能效率低下的博客文章。kvec.h性能的博客文章。khash.h和kbtree.h在许多其他实现中的性能。还可以使用旧版本的基准测试。
