klib
1.0.0
Klib é uma biblioteca C leve e independente distribuída sob licença MIT/X11. A maioria dos componentes são independentes de bibliotecas externas, exceto a biblioteca C padrão, e independentes entre si. Para usar um componente desta biblioteca, você só precisa copiar alguns arquivos para sua árvore de código-fonte sem se preocupar com as dependências da biblioteca.
Klib busca eficiência e um pequeno consumo de memória. Alguns componentes, como khash.h, kbtree.h, ksort.h e kvec.h, estão entre as implementações mais eficientes de algoritmos ou estruturas de dados semelhantes em todas as linguagens de programação, em termos de velocidade e uso de memória.
Uma nova documentação está disponível aqui, que inclui a maioria das informações neste arquivo README.
Para a implementação de contêineres genéricos, o klib usa extensivamente macros C. Para usar essas estruturas de dados, geralmente precisamos instanciar métodos expandindo uma macro longa. Isso faz com que o código-fonte pareça incomum ou até feio e dificulta a depuração. Infelizmente, para uma programação genérica eficiente em C que não possui modelo, o uso de macros é a única solução. Somente com macros podemos escrever um contêiner genérico que, uma vez instanciado, compita em eficiência com um contêiner de tipo específico. Algumas bibliotecas genéricas em C, como Glib, usam o tipo void* para implementar contêineres. Essas implementações são geralmente mais lentas e usam mais memória que o klib (veja este benchmark).
Para usar o klib de maneira eficaz, é importante entender como ele realiza a programação genérica. Usaremos a biblioteca de tabelas hash como exemplo:
#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;
}
Neste exemplo, a segunda linha instancia uma tabela hash com unsigned como tipo de chave e char como tipo de valor. m32 nomeia esse tipo de tabela hash. Todos os tipos e funções associados a este nome são macros, que serão explicadas posteriormente. A macro kh_init() inicia uma tabela hash e kh_destroy() a libera. kh_put() insere uma chave e retorna o iterador (ou a posição) na tabela hash. kh_get() e kh_del() obtêm uma chave e excluem um elemento, respectivamente. A macro kh_exist() testa se um iterador (ou uma posição) está preenchido com dados.
Uma questão imediata é que este trecho de código não se parece com um programa C válido (por exemplo, sem ponto e vírgula, atribuição a uma chamada de função aparente e 'variável' m32 aparentemente indefinida). Para entender por que o código está correto, vamos aprofundar um pouco mais no código-fonte de khash.h , cujo esqueleto se parece com:
#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() é uma macro enorme que define todas as estruturas e métodos. Quando esta macro for chamada, todo o código dentro dela será inserido pelo pré-processo C no local onde for chamada. Se a macro for chamada diversas vezes, serão inseridas diversas cópias do código. Para evitar conflito de nomenclatura de tabelas hash com diferentes tipos de valores-chave, a biblioteca usa concatenação de tokens, que é um recurso de pré-processador pelo qual podemos substituir parte de um símbolo com base no parâmetro da macro. No final, o pré-processador C irá gerar o seguinte código e alimentá-lo no compilador (a macro kh_exist(h,k) é um pouco complexa e não expandida para simplificar):
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;
}
Este é o programa C que conhecemos.
A partir deste exemplo, podemos ver que as macros e o pré-processador C desempenham um papel fundamental no klib. Klib é rápido em parte porque o compilador conhece o tipo de valor-chave no tempo de compilação e é capaz de otimizar o código para o mesmo nível do código específico do tipo. Uma biblioteca genérica escrita com void* não obterá esse aumento de desempenho.
A inserção massiva de código na instanciação pode nos lembrar da lenta velocidade de compilação do C++ e do enorme tamanho binário quando STL/boost está em uso. Klib é muito melhor nesse aspecto devido ao seu pequeno tamanho de código e independência de componentes. A inserção de várias centenas de linhas de código não tornará a compilação obviamente mais lenta.
void* para programação genérica pode ser ineficiente.kvec.h .khash.h e kbtree.h entre muitas outras implementações. Uma versão mais antiga do benchmark também está disponível.
