Datenstrukturen in C: Beispiel ALLOC_GROW

von Hubert Schmid vom 2013-07-07

Die Programmiersprache C ist – abgesehen von einigen Details – eine echte Teilmenge von C++. Beide Sprachen stehen seit einigen Jahren auf praktisch allen Plattformen zur Verfügung, so dass die Zielplattform kein Grund mehr ist, sich auf Erstere zu beschränken. Dennoch gibt es einige neue Projekte, die sich bewusst für C entscheiden – aus ganz unterschiedlichen Gründen. Ich selbst habe die letzten 15 Jahre keinen produktiven Code mehr in reinem C entwickelt. Trotzdem interessiere ich mich dafür, wie modernes C aussieht. Um einen besseren Eindruck davon zu erhalten, habe ich mir die Quellen von Git angeschaut, das zu deren bekannteren Vertretern zählt.

An dieser Stelle gehe ich nur auf ein Beispiel ein, das sich auf die Verwendung dynamischer Arrays fokussiert. Einerseits wird diese Datenstruktur in Git häufig verwendet, und andererseits ist sie hinreichend einfach, um sie in aller Kürze darzustellen. Orientieren werden ich mich dabei an folgendem C++-Fragment, das die Aufrufparameter des Programms für die weitere Verarbeitung in eine passende Datenstruktur kopiert.

int main(int argc, char* argv[])
{
    auto args = std::vector<std::string>{argv + 1, argv + argc};
    // do something with args
}

Die Standard-Container von C++ zeichnen sich durch zahlreiche, überladene Operationen aus – mit entsprechend kompakten Ergebnissen. Git beschränkt sich dagegen auf ein Minimum. Das Makro ALLOC_GROW ist die einzige Unterstützung für dynamische Arrays. Daher sind im folgenden Listing auch zunächst nur eigene Hilfskonstrukte zu sehen, die später erläutert werden.

int main(int argc, char* argv[])
{
    struct strings args = STRINGS_INIT;
    for (int i = 1; i < argc; ++i)
        strings_append(&args, strdup(argv[i]));
    // do something with args
    strings_destroy(&args, true);
    return 0;
}

Auffallend sind an diesem Listing zunächst zwei Dinge: Erstens erfolgt die Ressourcenfreigabe typisch für C explizit. Und zweitens ist keine Fehlerbehandlung sichtbar. Letzteres liegt daran, dass bei Git das Programm im Fehlerfall konsequent abgebrochen wird. Für ein Kommandozeilenprogramm ist dieses Vorgehen nicht ungewöhnlich, da sich die Fehlerbehandlung dadurch auf ein Minimum reduziert, und das Betriebssystem alle allokierten Ressourcen automatisch freigibt. Der Nachteil ist dagegen die sehr eingeschränkte Wiederverwendbarkeit des Codes.

Zur klareren Darstellung kennzeichne ich die entsprechenden Funktionen mit dem Suffix _or_die, so wie das im folgenden Listing zu sehen ist. Dadurch wird deutlicher, an welchen Stellen die Fehlerbehandlung durch Programmabbruch realisiert ist. In C++ ist das übrigens wesentlich einfacher: Das obige C++-Fragment kümmert sich implizit sowohl um die Ressourcenfreigabe als auch um die Fehlerbehandlung.

int main(int argc, char* argv[])
{
    struct strings args = STRINGS_INIT;
    for (int i = 1; i < argc; ++i)
        strings_append_or_die(&args, strdup_or_die(argv[i]));
    // do something with args
    strings_destroy(&args, true);
    return 0;
}

Die Datenstruktur strings für das dynamische Array enthält wenig überraschend drei Variablen: Einen Zeiger auf das erste Element, die Anzahl existierender Elemente sowie die verfügbare Kapazität. Dabei wird die Kapazität bei Bedarf vergrößert, so dass die amortisierten Kosten pro Einfügeoperation konstant sind. Das Makro STRINGS_INIT kann verwendet werden, um eine leeres, dynamisches Array zu initialisieren. Dabei entspricht es gängiger Praxis, leere Container zu optimieren und keinen Speicher zu allokieren. Denn wie sich zeigen wird, verursacht diese Optimierung keine zusätzliche Komplexität.

struct strings
{
    char** items;
    size_t nr;
    size_t alloc;
};

#define STRINGS_INIT { NULL, 0, 0 }

Im folgenden Listing sind der Konstruktor und der Destruktor dieser Datenstruktur zu sehen. Die Implementierungen sind trivial – die Verwendung ist es nicht: Denn typisch für C wird die Verantwortung für die Ressourcenfreigabe nicht am Typsystem festgemacht. Daher muss der Entwickler im Einzelfall kontrollieren, wer Ressourcen freizugeben hat.

void strings_init(struct strings* strings)
{
    memset(strings, 0, sizeof *strings);
}

void strings_destroy(struct strings* strings, bool free_items)
{
    while (free_items && strings->nr > 0)
        free(strings->items[--strings->nr]);
    free(strings->items);
}

Erst beim Einfügen eines Elements tritt zum ersten Mal das magische Makro ALLOC_GROW in Erscheinung – mit beachtlicher Wirkung: So reichen zwei Anweisungen aus, um die Größe eines dynamischen Arrays anzupassen und ein Element einzufügen. Zumindest für die sehr maschinenorientierte Sprache C finde ich das schon bemerkenswert positiv.

void strings_append_or_die(struct strings* strings, char* value)
{
    ALLOC_GROW_OR_DIE(strings->items, strings->nr + 1, strings->alloc);
    strings->items[strings->nr++] = value;
}

Das Makro erwartet den Datenzeiger, die erforderliche Größe sowie die aktuelle Kapazität. Das erste und letzte Argument werden gegebenenfalls aktualisiert, das heißt es müssen Speicherstellen für diese Argumente verwendet werden. Das zweite Argument wird nur ausgewertet und kann daher ein beliebiger Ausdruck ohne Nebeneffekte sein. Im folgenden Listing ist eine vereinfachte Form des Makros zu sehen, das auf ein paar Optimierungen verzichtet.

#define ALLOC_GROW_OR_DIE(items, nr, alloc)                             \
    do {                                                                \
        if ((nr) > alloc) {                                             \
            alloc = ALLOC_SIZE(alloc, (nr));                            \
            items = realloc_or_die((items), alloc * sizeof(*(items)));  \
        }                                                               \
    } while (false)

Es steckt also keine Magie dahinter: Die Realisierung in Form eines Makros ist lediglich notwendig, um generische Funktionen und Ausgabeparameter zu simulieren. In C++ ließe sich die gleiche Funktionalität genauso gut auch mit einem Funktionstemplate lösen.

Mehr Unterstützung für dynamische Arrays gibt es in Git nicht. Alle anderen Operationen werden direkt auf der Zeiger- und der Anzahl-Variable ausgeführt. Die Kapazität bleibt hingegen üblicherweise unberührt.

Es gibt noch einen wichtigen Unterschied zwischen der C‑ und C++‑Variante: Da die Anzahl der einzufügenden Elemente bereits vorab bekannt ist, allokiert der Konstruktor von std::vector sofort den Speicher für alle Elemente. Die C‑Variante vergrößert den Speicher dagegen inkrementell. Da diese Optimierung häufig sinnvoll ist, wird sie natürlich auch in Git verwendet. In meinem Beispiel muss dafür nur ein weiterer Aufruf des Makros ALLOC_GROW vor der Schleife eingefügt werden. Der restliche Code bleibt unverändert.

    struct strings args = STRINGS_INIT;
    ALLOC_GROW_OR_DIE(args.items, argc - 1, args.alloc);

Man sieht also: Wenn man die Fehlerbehandlung auf den Programmabbruch reduziert, und diszipliniert mit Ressourcenfreigabe umgeht, so lassen sich Programme auch vergleichsweise sinnvoll in C realisieren. Generische Funktionen lassen sich mit Hilfe von Makros realisieren, und bei Datenstrukturen ist weniger manchmal mehr. Zumindest für Git scheint dieses Vorgehen überzeugende Ergebnisse zu liefern.