Templates in C (?)

Ich arbeite z.Z. an einem Projekt in C, in dem ich eine typenunabhängige Liste brauche. Eine normale Liste in C (wo Daten und Code voneinander getrennt sind) ist noch möglich - aber typenunabhänig mithilfe von Templates nicht mehr (weil C Templates nun mal nicht kennt).

Deshalb habe ich mir gedacht, dass ich mithilfe eines Makros, welchem ich einen Typ übergebe, eine komplette Liste erstelle. So kann ich in C für jeden Typ einen Satz aus Nodes und Funktionen erstellen, obwohl ich den Code nur einmal schreibe ... denke ich zumindest.

Doch bevor ich mich einem fruchtlosen Versuch verschreibe, wollte ich erst anwesende C-Experten fragen, ob dies überhaupt möglich ist: einem Makro einen String übergeben, damit dieser dann nicht als String, sondern eben als "richtiger" Code interpretiert meine Nodes mit dem neuen Typ und den dazugehörigen Code erstellt (oder wie ich sie nennen würde, "manuelle Templates"). Zwei Sachen jedoch vorneweg:

1. In C++ programmieren geht nicht.
2. Wenn ich das Ganze über Arrays mache, leidet die Laufzeit extrem.

PS: Ach ja, so sieht die Liste etwa aus:

Nodes:

struct TypNode
{
    /*Doppelt verkettete Liste*/
    struct TypNode*Prev;
    struct TypNode*Next;
    /*Gibt es eigentlich eine Möglichkeit, rauszufinden, ob das struct mit
    **muss oder nicht? Schließlich will ich nicht nur selbsterstellte Typen
    **verwenden ...*/
    struct Typ*Value;
};

Die Liste:

struct TypList
{
    /*Nur Verweise auf beide Enden der Liste*/
    struct TypNode*Head;
    struct TypNode*End;
}:

Die Funktionen tun hier nichts zur Sache.

Glühbirne schrieb:

Doch bevor ich mich einem fruchtlosen Versuch verschreibe, wollte ich erst anwesende C-Experten fragen, ob dies überhaupt möglich ist

Möglich ist alles.

#define CREATE_MY_CRAZY_DOUBLE_LINKED_LIST(Type) \
    struct TypNode \
    { \
        /*Doppelt verkettete Liste*/ \
        struct TypNode *Prev; \
        struct TypNode *Next; \
        /* wer struct x will, muss halt "struct x" als Typ so schreiben */ \
        Type *Value; \
    }; \
    und Was { \
        da alles; \
    }; \
    noch *dazugehört();

Mag sein, dass es ein paar Freaks so schreiben, irgendwie wird es schon gehen

Ich hingegen verwende void * : Ersetze in deinem Code alle struct Typ* durch void * .
Dann hast du eine echte generische Liste, die sogar diejenigen von C++ aussticht.

Hast du nur ein Set von Funktionen
Vermeidest du Makros und
nimmst du keine Leistungseinbussen hin.

Was ich geschrieben habe gilt sowohl für Typen als auch Funktionen.

Du meinst wohl eher so:

#define CREATE_MY_CRAZY_DOUBLE_LINKED_LIST(Type)\
struct Type##Node\
{\
\
    struct Type##Node*Prev;\
    struct Type##Node*Next;\
    struct Type*Value;\
};\

Ich hingegen verwende void * : Ersetze in deinem Code alle struct Typ* durch void * .[/quote]

Habe ich auch schon gedacht, aber das ist nicht ganz möglich. Denn ich muss den Käse differenzieren, und das geht nun mal mit einem Zeiger auf void nicht. Umwandlung geht auch nicht, weil das ganze mit meiner Speicherverwaltung hapert ... Junge, was ich dann alles umschreiben müsste.

Vielleicht kann ich ja zwei Makros definieren, einmal für Strukturen, einmal für normale Typen. Dann würde es funktionieren, oder?

linux_c89

Habe ich auch schon gedacht, aber das ist nicht ganz möglich. Denn ich muss den Käse differenzieren, und das geht nun mal mit einem Zeiger auf void nicht.

Mach doch einfach ein int type vornedran und definiere dir ein paar Konstanten

#define LIST_TYPE_FOO 0
#define LIST_TYPE_BAR 1
...

Was genau funktioniert dann mit deiner Speicherverwaltung nicht mehr?

linux_c89 schrieb:

#define LIST_TYPE_FOO 0
#define LIST_TYPE_BAR 1
...

Erkläre. Was soll das bedeuten?

linux_c89 schrieb:

Was genau funktioniert dann mit deiner Speicherverwaltung nicht mehr?

Schwierig zu erklären. Sagen wir so: ich müsste sehr viel mehr Code hinzufügen, um Speicherlecks zu verhindern. Das hat sowohl mit den Elementen zu tun, mit denen ich arbeite, als auch mit der Listenstruktur ... um Laufzeit zu sparen.

rüdiger

So machen die das im Linux-Kernel: http://isis.poly.edu/kulesh/stuff/src/klist/

Wutz

Glühbirne schrieb:

2. Wenn ich das Ganze über Arrays mache, leidet die Laufzeit extrem.

Das bezweifele ich ganz stark.
Auch bei großen Datenbeständen habe ich keine Vorteile von verketteten Listen erkennen können (außer das diese in Akademikerkreisen sehr beliebt sind ob ihrer Dozierbarkeit).

CStoll

Wutz schrieb:

Glühbirne schrieb:

2. Wenn ich das Ganze über Arrays mache, leidet die Laufzeit extrem.

Das bezweifele ich ganz stark.
Auch bei großen Datenbeständen habe ich keine Vorteile von verketteten Listen erkennen können (außer das diese in Akademikerkreisen sehr beliebt sind ob ihrer Dozierbarkeit).

Das kannst du nicht so pauschal sagen - das kommt nämlich ganz darauf an, was du mit dem Inhalt der Datenstruktur vorhast. Arrays sind gut geeignet, wenn du schnell und gezielt auf die Elemente zugreifen willst, Listen haben Vorteile bei Änderungen der Struktur (Einfügen/Löschen). Eine Warteschlange ist z.B. mit einer Liste viel schneller als mit einem Array einzusetzen.

Wutz

Die Standardanforderungen an sequentielle Datenbestände sind immer diegleichen:
insert,update,delete,Selektion,Enumeration,Detection,Sort/Resort,Set,Map/Dictionary u.ä.
Und dabei habe ich bisher mit Arrays auch hinsichtlich Performanz nur gute Erfahrungen gemacht und nichts besseres gefunden und ich mache solche Sachen schon viele Jahre.
Zur genannten Frage wäre zu erwähnen, auch sowas habe ich schon gemacht, allerdings auf statische Art und Weise sondern mit memory-Blocks (d.h. structs) als Array, wobei dann das sizeof(struct) natürlich variabel war. Alle o.g. Standardanwendungsfälle waren schnell implementiert.

CStoll

Wutz schrieb:

Alle o.g. Standardanwendungsfälle waren schnell implementiert.

Meinst du damit den Programmier-Aufwand oder die Laufzeit? Praktisch gesehen gibt es wohl keine Datenstruktur, die alle von dir genannten Anwendungsfälle optimal umsetzen kann, deshalb geht maqn i.d.R. Kompromisse ein. Bei einer Liste kannst du z.B. in konstanter Zeit Elemente einfügen (egal an welcher Stelle), bei einem Array mußt du alle hinter der Einfügeposition liegenden Elemente nach hinten verschieben, was Laufzeit O(n) benötigt (auch wenn du dieses Verschieben hinter einem memmove() verstecken kannst, ist es nicht gratis ;)).

Ich habe dir Erfahrung gemacht, dass man pauschal nicht sagen kann, dass ein Array schneller als eine Liste ist. In einem meiner früheren Programme konnte ich die Ausführungszeit durch das Wechseln von Array zu Liste um das 30-fache bei zwei Prozessoren und aktiviertem Multi-Threading senken. Listen eignen sich hervorragend, um Elemente innerhalb einer Reihe von Elementen zu löschen oder hinzuzufügen. In einem Array ist dies nur bedingt möglich - und in C durch das fehlende Klassendesign und mangelnde Templates auch noch recht grausam.

Aber ich habe es mit dem Makro ausprobiert, und es funktioniert tadelos. Sieht so aus, als ob meine Befürchtungen ungerechtfertigt waren. Templates in C ganz leicht ... hey, mit der Idee sollte man doch was anfangen können, oder?