klib
1.0.0
Klib — это автономная и легкая библиотека C, распространяемая по лицензии MIT/X11. Большинство компонентов не зависят от внешних библиотек, за исключением стандартной библиотеки C, и независимы друг от друга. Чтобы использовать компонент этой библиотеки, вам нужно всего лишь скопировать пару файлов в дерево исходного кода, не беспокоясь о зависимостях библиотеки.
Klib стремится к эффективности и небольшому объему памяти. Некоторые компоненты, такие как khash.h, kbtree.h, ksort.h и kvec.h, являются одними из наиболее эффективных реализаций подобных алгоритмов или структур данных на всех языках программирования с точки зрения как скорости, так и использования памяти.
Здесь доступна новая документация, которая включает большую часть информации в этом файле README.
Для реализации универсальных контейнеров 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.hkhash.h и kbtree.h среди многих других реализаций. Также доступна более старая версия теста.
