Erwin Data Structures Library + Tools

Deutsch English

‘STL for C (and C++)’

No templates, no void*, no buffer overflow. The Erwin library is meant to be the ultimate data structure library for mixed usage of C and C++. Arbitrary key and value types are implemented by template files that don't use C++ templates, but are instantiated by a Perl script. This way, mixed usage in C and C++ is possible. However, a C++ interface is generated to support the advantages of the C++ language.Erwin contains a number of tools, too, all of them written in Perl. The following list shows the data structures and tools, together with some typical examples.


Vectors

Vectors behave much like standard arrays, but their size can be changed dynamically and they use array bound checking to prevent buffer overflows (or buffer overruns), which are the source of most security problems in safety critical applications.

VectorInt x;
x.append (a).append(b);
x.sort()                    // a stable sort: mergesort
x.append(c).heap_create();  // priority queues: heaps
vector_forall (m, i, v) {   // many iterators
    ...
}

VChar y;
y.format (FO_QUOTE_C_STRING, "var=%s", var);
    // formatting like fprintf, providing extensions like
    // several quotations: C, HTML, URL, user defined
fputs (y, stderr); // VChar behaves like ‘char const *’

Lists

Usually, vectors should today be preferred over lists, because their cache behaviour, which is important on modern microprocessors, is much better. On the other hand, the one feature that makes lists important is that sort order keeping deletion of an arbitrary element takes constant time.

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

Maps

Highly efficient implementation of dynamic hashing.

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

Assertions

Inspired by GTK. Macros are generated by a Perl script on demand by gathering them from the source code. Diagnostic printing of values in case of assertion failure is supported.

return_if_fail (x >= 0);
break_if_fail_pt (y != 0, "Division by zero avoided");
return7_if_out_of_bounds (a, 50);  // 0..49 is valid 

Symbols

Hashed strings, usable as static data just like any other constant in C. The declarations are gathered from the source code and generated by a Perl script.

char const *s;
...
if (s == sym_table) { // ‘==’ works; sym_table auto-declared
    ...
}

Autogenerated C Interface for C++ Libraries

struct XyzType {
    void blah (int &x) const;
    ...
}
...
xyz_type_t const *self;   // auto-generated typedef / #define
int a;
...
xyz_type_blah (self, &a); // auto-generated wrapper function

C++ Extensions

The talkativeness of C++ is reduced a bit by having functions implemented by a script. Slots/Properties are supported.

struct XyzType {
public:
    //! implementation: redirect
    int blah (int &x) const;     // NULL-safe call to v_blah(x)
protected:
    //! implementation: trivial
    virtual int v_blah (int &x) const; // returns 0 by default.
}

Documentation Extraction

Documentation from C and C++ libraries can be automatically extracted. Several projects exist for this, but due to the need to parse special syntax files and Erwin template files and to document the correspondence between C++ and auto-generated C headers, Erwin has its own documentation extractor. It also provides a c2html markup interface and a text2html formatter.See the Erwin Reference Documentation for an example.


Stability

The library was developed over several years for private, commercial and university projects. It is used extensively in all three areas now. The main data structures have stabilised well and bugs are found rarely nowadays, so the library is considered to be very stable and robust. Furthermore, the API is fixed -- it is simply impossible to adjust all the existing software to Erwin, so it will stay the way it is apart from, of course, bug fixes and features additions.


Download

Source Code

Debian

For manual download, Debian packages are here.

Alternatively, you can add the following line to /etc/apt/sources.list:

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

Currently, this repository stores binary packages for distribution Etch and architecture i386.

To install Erwin binary packages, type:

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

Content

Index

August 28th, 2008
Comments? Suggestions? Corrections? You can drop me a line.
zpentrabvagiktu@theiling.de
Schwerpunktpraxis