klib
1.0.0
Klib ist eine eigenständige und leichte C-Bibliothek, die unter der MIT/X11-Lizenz vertrieben wird. Die meisten Komponenten sind unabhängig von externen Bibliotheken, mit Ausnahme der Standard-C-Bibliothek, und unabhängig voneinander. Um eine Komponente dieser Bibliothek zu verwenden, müssen Sie nur ein paar Dateien in Ihren Quellcodebaum kopieren, ohne sich um Bibliotheksabhängigkeiten kümmern zu müssen.
Klib strebt nach Effizienz und einem geringen Speicherbedarf. Einige Komponenten wie khash.h, kbtree.h, ksort.h und kvec.h gehören sowohl hinsichtlich der Geschwindigkeit als auch der Speichernutzung zu den effizientesten Implementierungen ähnlicher Algorithmen oder Datenstrukturen in allen Programmiersprachen.
Hier ist eine neue Dokumentation verfügbar, die die meisten Informationen in dieser README-Datei enthält.
Für die Implementierung generischer Container verwendet klib in großem Umfang C-Makros. Um diese Datenstrukturen verwenden zu können, müssen wir normalerweise Methoden durch Erweitern eines langen Makros instanziieren. Dadurch sieht der Quellcode ungewöhnlich oder sogar hässlich aus und das Debuggen wird schwieriger. Für eine effiziente generische Programmierung in C ohne Vorlage ist leider die Verwendung von Makros die einzige Lösung. Nur mit Makros können wir einen generischen Container schreiben, der nach seiner Instanziierung in puncto Effizienz mit einem typspezifischen Container konkurrieren kann. Einige generische Bibliotheken in C, wie z. B. Glib, verwenden den Typ void* um Container zu implementieren. Diese Implementierungen sind normalerweise langsamer und verbrauchen mehr Speicher als Klib (siehe diesen Benchmark).
Um klib effektiv nutzen zu können, ist es wichtig zu verstehen, wie es eine generische Programmierung erreicht. Als Beispiel verwenden wir die Hash-Tabellenbibliothek:
#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;
}
In diesem Beispiel instanziiert die zweite Zeile eine Hash-Tabelle mit unsigned als Schlüsseltyp und char als Werttyp. m32 benennt eine solche Art von Hash-Tabelle. Alle mit diesem Namen verbundenen Typen und Funktionen sind Makros, die später erläutert werden. Das Makro kh_init() initiiert eine Hash-Tabelle und kh_destroy() gibt sie frei. kh_put() fügt einen Schlüssel ein und gibt den Iterator (oder die Position) in der Hash-Tabelle zurück. kh_get() und kh_del() erhalten einen Schlüssel bzw. löschen ein Element. Das Makro kh_exist() testet, ob ein Iterator (oder eine Position) mit Daten gefüllt ist.
Eine unmittelbare Frage ist, dass dieser Code nicht wie ein gültiges C-Programm aussieht (z. B. fehlendes Semikolon, Zuweisung zu einem scheinbaren Funktionsaufruf und scheinbar undefinierte m32 -Variable). Um zu verstehen, warum der Code korrekt ist, gehen wir etwas tiefer in den Quellcode von khash.h ein, dessen Grundgerüst wie folgt aussieht:
#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() ist ein riesiges Makro, das alle Strukturen und Methoden definiert. Wenn dieses Makro aufgerufen wird, wird der gesamte darin enthaltene Code vom C-Vorprozess an der Stelle eingefügt, an der es aufgerufen wird. Wenn das Makro mehrmals aufgerufen wird, werden mehrere Kopien des Codes eingefügt. Um Namenskonflikte von Hash-Tabellen mit unterschiedlichen Schlüsselwerttypen zu vermeiden, verwendet die Bibliothek die Token-Verkettung, eine Präprozessorfunktion, mit der wir einen Teil eines Symbols basierend auf dem Parameter des Makros ersetzen können. Am Ende generiert der C-Präprozessor den folgenden Code und gibt ihn an den Compiler weiter (Makro kh_exist(h,k) ist etwas komplex und der Einfachheit halber nicht erweitert):
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;
}
Dies ist das C-Programm, das wir kennen.
Anhand dieses Beispiels können wir erkennen, dass Makros und der C-Präprozessor eine Schlüsselrolle in klib spielen. Klib ist unter anderem deshalb schnell, weil der Compiler den Schlüsselwerttyp zum Zeitpunkt der Kompilierung kennt und den Code auf das gleiche Niveau wie typspezifischen Code optimieren kann. Eine mit void* geschriebene generische Bibliothek erhält keinen solchen Leistungsschub.
Das massive Einfügen von Code bei der Instanziierung erinnert uns möglicherweise an die langsame Kompilierungsgeschwindigkeit und die enorme Binärgröße von C++, wenn STL/Boost verwendet wird. Klib ist in dieser Hinsicht aufgrund seiner geringen Codegröße und Komponentenunabhängigkeit viel besser. Das Einfügen mehrerer hundert Codezeilen wird das Kompilieren offensichtlich nicht langsamer machen.
void* für generische Programmierung möglicherweise ineffizient ist.kvec.hkhash.h und kbtree.h neben vielen anderen Implementierungen. Eine ältere Version des Benchmarks ist ebenfalls verfügbar.
