klib
1.0.0
Klib es una biblioteca C liviana e independiente distribuida bajo licencia MIT/X11. La mayoría de los componentes son independientes de bibliotecas externas, excepto la biblioteca C estándar, y son independientes entre sí. Para utilizar un componente de esta biblioteca, sólo necesita copiar un par de archivos a su árbol de código fuente sin preocuparse por las dependencias de la biblioteca.
Klib se esfuerza por lograr eficiencia y un uso reducido de memoria. Algunos componentes, como khash.h, kbtree.h, ksort.h y kvec.h, se encuentran entre las implementaciones más eficientes de algoritmos o estructuras de datos similares en todos los lenguajes de programación, tanto en términos de velocidad como de uso de memoria.
Hay disponible una nueva documentación aquí que incluye la mayor parte de la información en este archivo README.
Para la implementación de contenedores genéricos, klib utiliza ampliamente macros C. Para utilizar estas estructuras de datos, normalmente necesitamos crear instancias de métodos expandiendo una macro larga. Esto hace que el código fuente parezca inusual o incluso feo y añade dificultad a la depuración. Desafortunadamente, para una programación genérica eficiente en C que carece de plantilla, el uso de macros es la única solución. Sólo con macros podemos escribir un contenedor genérico que, una vez creado una instancia, compita en eficiencia con un contenedor de tipo específico. Algunas bibliotecas genéricas en C, como Glib, utilizan el tipo void* para implementar contenedores. Estas implementaciones suelen ser más lentas y utilizan más memoria que klib (consulte este punto de referencia).
Para utilizar klib de forma eficaz, es importante comprender cómo logra la programación genérica. Usaremos la biblioteca de tablas hash como ejemplo:
#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;
}
En este ejemplo, la segunda línea crea una instancia de una tabla hash con unsigned como tipo de clave y char como tipo de valor. m32 nombra este tipo de tabla hash. Todos los tipos y funciones asociados con este nombre son macros, que se explicarán más adelante. La macro kh_init() inicia una tabla hash y kh_destroy() la libera. kh_put() inserta una clave y devuelve el iterador (o la posición) en la tabla hash. kh_get() y kh_del() obtienen una clave y eliminan un elemento, respectivamente. La macro kh_exist() prueba si un iterador (o una posición) está lleno de datos.
Una pregunta inmediata es que este fragmento de código no parece un programa C válido (por ejemplo, carece de punto y coma, asignación a una llamada de función aparente y 'variable' m32 aparentemente indefinida). Para entender por qué el código es correcto, profundicemos un poco más en el código fuente de khash.h , cuyo esqueleto se ve así:
#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() es una macro enorme que define todas las estructuras y métodos. Cuando se llama a esta macro, todo el código que contiene será insertado por el preproceso de C en el lugar donde se llama. Si la macro se llama varias veces, se insertarán varias copias del código. Para evitar conflictos de nombres entre tablas hash con diferentes tipos clave-valor, la biblioteca utiliza la concatenación de tokens, que es una característica del preprocesador mediante la cual podemos sustituir parte de un símbolo según el parámetro de la macro. Al final, el preprocesador de C generará el siguiente código y lo enviará al compilador (la macro kh_exist(h,k) es un poco compleja y no está ampliada por simplicidad):
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 es el programa C que conocemos.
En este ejemplo, podemos ver que las macros y el preprocesador de C desempeñan un papel clave en klib. Klib es rápido en parte porque el compilador conoce el tipo clave-valor en el momento de la compilación y puede optimizar el código al mismo nivel que el código específico del tipo. Una biblioteca genérica escrita con void* no obtendrá tal aumento de rendimiento.
La inserción masiva de código al crear instancias puede recordarnos la lenta velocidad de compilación de C++ y su enorme tamaño binario cuando se utiliza STL/boost. Klib es mucho mejor a este respecto debido a su pequeño tamaño de código y a la independencia de sus componentes. Insertar varios cientos de líneas de código no hará que la compilación sea obviamente más lenta.
void* para programación genérica puede ser ineficiente.kvec.hkhash.h y kbtree.h , entre muchas otras implementaciones. También está disponible una versión anterior del punto de referencia.
