Erwin Datenstrukturbibliothek und Werkzeuge

Deutsch English

„STL für C (und C++)“

Keine Templates, kein void*, kein Pufferüberlauf. Die Erwin-Bibliothek ist als ultimative Datenstruktursammlung gedacht zur Benutzung in C und C++. Beliebige Schlüssel- und Werttypen werden mittels Template-Dateien implementiert, die aber keine C++-Templates benutzen, sondern stattdessen mit einem Perl-Skript instantiiert werden. Auf diese Weise ist die Benutzung sowohl von C als auch von C++ aus möglich. Es wird neben der C-Schnittstelle eine C++-Schnittstelle erzeugt (falls gewünscht), die dennoch die Vorteile von C++ ausnutzt.Erwin enthält auch einige nützliche Werkzeuge, die in Perl geschrieben sind. Der folgende Überblick zeigt die Datenstrukturen und Werkzeuge, sowie typische Benutzungsbeispiele.


Vektoren

Vektoren verhalten sich etwa wie normale Felder, aber die Größe kann dynamisch verändert werden und sie nehmen eine Indexprüfung vor, so daß Pufferüberläufe, die für die meisten Sicherheitsprobleme in sicherheitskritischer Software verantwortlich sind, vermieden werden.

VectorInt x;
x.append (a).append(b);
x.sort()                    // stabil sortieren: Mergesort
x.append(c).heap_create();  // Priority-Queues: Heaps
vector_forall (m, i, v) {   // viele Iteratoren
    ...
}

VChar y;
y.format (FO_QUOTE_C_STRING, "var=%s", var);
    // Formatieren wie mit fprintf + Erweiterungen:
    // Quotierungen: C, HTML, URL, benutzerdefiniert
fputs (y, stderr); // VChar verhält sich wie „char const *“

Listen

Normalerwise sollten heute Vektoren den Listen vorgezogen werden, weil das Cache-Verhalten wesentlich besser ist, was auf modernen Mikroprozessoren wichtig ist. Auf der anderen Seite gibt es einen Grund, manchmal doch Listen zu benutzen: das Löschen beliebiger Elemente unter Beibehaltung der Reihenfolge benötigt konstante Zeit.

ListInt m;
m.append (a);
list_forall (m, i, v) {
    ...
}

Maps

Hocheffiziente Implementierung dynamischen Hashens.

MapIntInt m;
m[5]= 6;
map_forall_keys_sorted_by_value (m, i) { // viele Iteratoren...
}

Assertions

Von GTK abgeguckt. Von einem Perl-Skript werden Makros erzeugt, wenn sie gebraucht werden, indem der Quellcode durchsucht wird. Diagnoseausgaben von Werten im Falle einer fehlgeschlagenen Zusicherung werden unterstützt.

return_if_fail (x >= 0);
break_if_fail_pt (y != 0, "Division durch 0 verhindert");
return7_if_out_of_bounds (a, 50);  //  0..49 ist gültig

Symbole

Gehashte Strings, die als statische Daten benutzbar sind wie jeder andere primitive Datentyp in C. Die Deklarationen werden aus dem Quellcode hergeleitet, indem Vorkommen von Symbolnamen gesucht werden.

char const *s;
...
if (s == sym_table) { // „==“ geht; sym_table automatisch deklariert
    ...
}

Automatisch erzeugtes C-Interface um C++-Bibliotheken

struct XyzType {
    void blah (int &x) const;
    ...
}
...
xyz_type_t const *self;   // erzeugtes typedef / #define
int a;
...
xyz_type_blah (self, &a); // erzeugte Sprungbrettfunktion

C++-Erweiterungen

Die Geschwätzigkeit von C++ wird ein wenig vermindert durch das Generieren vieler Funktionen. Dadurch wird die Slot/Property-Programmierung sehr einfach gemacht.

struct XyzType {
public:
    //! implementation: redirect
    int blah (int &x) const;     // NULL-sicherer Aufruf von v_blah()
protected:
    //! implementation: trivial
    virtual int v_blah (int &x) const; // liefert standardmäßig 0 zurück
}

Handbucherzeugung

Referenzhandbücher für C- und C++-Bibliotheken können automatisch aus dem Quelltext extrahiert werden. Für diese Aufgabe gibt es schon mehrere Projekte, aber wegen der Notwendigkeit das Parsens spezieller Syntax der Erwin-Template-Dateien und der Verknüpfung von C- und C++-Schnittstelle sah ich mich gezwungen, einen eigenen Dokumentierer für Erwin zu schreiben. Es gibt einen c2html-Modus zum farbigen C-Formatieren und ebenso einen text2html-Modus, um Texte nach HTML umzuwandeln.Weitere Beispiele finden sich im Erwin Referenzhandbuch.


Stabilität

Die Bibliothek wurde über mehrere Jahre hinweg für private sowie kommerzielle und universitäre Nutzung entwickelt. Sie befindet sich in regem Gebrauch in allen diesen Bereichen. Die Haupt-Datenstrukturen haben sich inzwischen sehr stabilisiert, und Fehler werden heute relativ selten gefunden, da daß man die Bibliothek als sehr statil und robust bezeichnen kann. Desweiteren ist die Benutzerschnittstelle fest -- es ist einfach unmöglich sämtliche Software zu ändern, die Erwin benutzt, so daß die Schnittstelle genau so bleiben wird, wie sie ist, wobei natürlich Fehler behoben und Neuerungen eingebaut werden.


Download

Quellcode

Debian

Debian-Pakete zum manuellen Download liegen hier.

Alternativ können Sir die folgende Zeile in /etc/apt/sources.list einfügen:

deb  http://debian.theiling.de/  etch  contrib main non-free

Im Moment gibt es in diesem Lager Pakete für die Etch-Distribution und die i386-Architektur.

Mit folgendem Befehl installieren Sie dann Erwin-Binärpakete:

apt-get update
apt-get install erwin
apt-get install erwin-doc

Inhalt

Index

28. August 2008
Anmerkungen? Vorschläge? Verbesserungen? Schreib mir was.
zpentrabvagiktu@theiling.de
Schwerpunktpraxis