Verkettete Liste: verschiedene Objekte ablegen und deren Funktionen aufrufen

[namespace invader]

stefan-tiger schrieb:

1. Einfügen von Objekten eines beliebigen Objekts in die verkettete Liste

Wenn es nicht ganz beliebige Objekte sind, z.B. durch eine Union im Listenknoten, die alle Möglichkeiten enthält.

Oder du definierst eine Struktur für den den gemeinsamen Teil aller Listenknoten als "Basisklasse", die dann am Anfang aller speziellen Listenknotenstrukturen steht. Funktionen, die nur allgemein was mit der Liste machen, arbeiten nur damit, während die speziellen Funktionen sich die Zeiger auf den richtigen Typ casten.

2. Durchgehen der Liste und Aufrufen der entsprechenden process() und output() Funktionen

Entweder die Listenknoten enthalten (außerhalb der Union, bzw. im gemeinsamen Teil) Zeiger auf die entsprechende Funktion, oder Zeiger auf eine irgendwo herumliegende vtable-Struktur, die unter anderem Zeiger auf die Funktionen enthält, oder irgendeine Kennzeichnung, mit der dann in entsprechenden Arrays die Funktionen gefunden werden.

[stefan-tiger]

Hallo zusammen,

danke für die Antworten. Ich habe nun eine Lösung umgesetzt die qusai eine Mischung aus fast alles ist was hier angedeuted wurde:

Hier die wichtigen Code-Stücke (sollten selbsterklärend sein, wenn nicht einfach nachfragen):

typedef enum {A,B} type_e;

typedef struct 
{   
  type_e objtype;
  void (*foo)(void); 
} ObjectA_t; 

typedef struct 
{   
  type_e objtype;
  void (*bar)(void); 
} ObjectB_t;

typedef struct Entry_t
{
  struct Entry_t *next;
  int data;
  void *obj;
} Entry_t;

...

void processList(Entry_t* list)
{
  do 
  {
    if(list->obj==0)
      return;

    type_e objtype = *((type_e*)(list->obj));

    if(objtype == A)
    {
      printf("objtype=A\n");
      ((ObjectA_t*)(list->obj))->foo();
    }
    else if(objtype == B)
    {
      printf("objtype=B\n");
      ((ObjectB_t*)(list->obj))->bar();
    }
    else   
    {
      printf("objtype unknown!\n");
    }

  list = list->next;
  } while(list != 0);

}
...

Vielleicht doch noch kurz eine Erläuterung: Das "..." bedeuted dass ich hier in meinem Programm Code habe um die verkettete Liste anzulegen und zu testen. Das ist uninteressat für das geschilderte Problem.
Hinweis: Meine Listen-Elemente sind diese "Entry_t"

Die Zentrale Funktion ist "processList". Jedes Objekt muss man Anfang den enum haben um den Objekt-Typ festzustellen. Dort wird dann entsprechend Verzweigt, sprich die void-Pointer gecastet.
(Null-Zeiger wird ignoriert; kein Objekt in Liste eingehängt)

Freu mich auch über Rückmeldungen.
Das ganze scheint zwar zu funktionieren, kommt mir aber etwas "unsauber" und sehr Fehleranfällig vor.

[noobLolo]

typedef struct 
{   
  type_e objtype;
  void (*foo)(void); 
} ObjectA_t; 

typedef struct 
{   
  type_e objtype;
  void (*bar)(void); 
} ObjectB_t;

wenn die structs vom aufbau her identisch sind kannst es dir schenken die zweimal anzulegen sondern weist einfach einen anderen functions pointer zu... damit fällt dann auch das objtype weg.

falls du dich jetzt fragst wie du denn erkennen sollst welchs obj du vor dir hast, dann schau dir einfach die functions pointer von foo oder bar an.

damit schenkst dir dann auch das if(){}else{}...

lg lolo

[stefan-tiger]

noobLolo schrieb:

...

wenn die structs vom aufbau her identisch sind kannst es dir schenken die zweimal anzulegen sondern weist einfach einen anderen functions pointer zu... damit fällt dann auch das objtype weg.

falls du dich jetzt fragst wie du denn erkennen sollst welchs obj du vor dir hast, dann schau dir einfach die functions pointer von foo oder bar an.

damit schenkst dir dann auch das if(){}else{}...

lg lolo

Hallo,

du hast recht in diesem Beispiel ist das mit den Object-s überflüssig, da diese sich sehr ähneln.

Das ist für mich ja auch gerader der Knackpunkt. Wenn ich in die verkettete Liste nur Ojekte gleichen Typs speichern wollte hätte ich alles in "Entry_t" gepackt und wäre fertig.

Das hier soll aber allgemeingültig sein, für völlig verschiedene Objekte und in der "processList()" können dann unterschidlich viele "Member-Funktionen" der Objects aufgerufen werden.

Beispielsweise kann man Objekte haben die Berechnet werden müssen und welche die dann noch Ausgegeben werden müssen. D.h. in meinem Beispiel würde ich bei Objekt A vll. die Berechnungs und die Ausgage-Funktion aufrufen, für B aber nur eine Berechnungsfunktion, weil B garkeine Ausgabe hat.

[noobLolo]

nimm trotzdem die adressen als ClassID also dann die adresse in "void *obj;"

lg lolo

[stefan-tiger]

noobLolo schrieb:

nimm trotzdem die adressen als ClassID also dann die adresse in "void *obj;"

lg lolo

Das geht nicht, weil ich ja viele Instanzen eines Objekts in der Liste haben kann.
Sprich ich kann z.B. 10x ObjektA_t in der Liste habe und 20x ObjektB_t. Ich weiss nicht wie ich hier die Adressen der Instanzen als Objekt-Typ-Kennung verwenden, gescheige denn "auslesen" könnte.

Vll. hab ich auch nicht verstanden was du gemeint hast?

[pointercrash**]

stefan-tiger schrieb:

noobLolo schrieb:

nimm trotzdem die adressen als ClassID also dann die adresse in "void *obj;"

lg lolo

Das geht nicht, weil ich ja viele Instanzen eines Objekts in der Liste haben kann.
Sprich ich kann z.B. 10x ObjektA_t in der Liste habe und 20x ObjektB_t. Ich weiss nicht wie ich hier die Adressen der Instanzen als Objekt-Typ-Kennung verwenden, gescheige denn "auslesen" könnte.

Vll. hab ich auch nicht verstanden was du gemeint hast?

Natürlich geht's, Du stehst Dir nur gerade gedanklich selbst im Weg.

typedef struct
{  
  int somedata;
  void (*anyvoidofvoidfunction)(void);
} Object_t;

Ist jetzt mal nur ein Typ; erst wenn Du Elemente anlegst, weist Du anyvoidofvoidfunction entweder foo() oder bar() zu. Welche Funktion Du da reinschreibst, typisiert nicht nur das Listenelement, sondern die Funktion sollte ja auch wissen, was sie mit den anderen Daten in der Liste anfangen kann.
Wenn Du es weitertreiben magst, kannst Du auch Funktionen definieren, die ihre eigene Struct als Argument auswerten. Das müßte ziemlich dran hinkommen, was Du vorhast.

[stefan-tiger]

pointercrash() schrieb:

...Natürlich geht's, Du stehst Dir nur gerade gedanklich selbst im Weg. ...

Hallo,

ich glaube du versuchst was zusammenzufassen was ich getrennt haben will.

Beispielsweise soll ObjektA eine Memberfunktion foo() haben und ObjektB eine Memberfunktion bar().

Die Funktion foo() muss also niemals mit Typen von ObjektB umgehen können!

Vll. wird es deutlicher was ich will, wenn man statt ObjektA,B das Beispiel ganz anders aufzieht, z.B. mit einem Objekt "Pferd" und einem Objekt "Sofa".
Die haben miteinander nichts zu tun, also gibt es hier auch nichts zusammenzufassen. Einzig beispielsweise eine Draw() Funktion würden beiden gemeinsam sein, falls das z.B. Objekte eines Spiels wären.

Wenn ich jetzt alle (Instanzen aller) Objekte zeichnen lassen will dann brauch ich eine "zeichne-alle-Objekte-in-Liste" Funktion.

[noobLolo]

void hello(){
  printf("hello");
}
void world(){
  printf("world");
}
.-diese structs sind statisch daher kannst die adresse zu den structures verwenden um den typ abzufragen, wie in dem beispiel das ich dir gepostet hab.
v
struct{
  type_e objtype;
  void (*foo)(void); 
} ObjectA = {
  0x1
  ,hello
};

struct{
  type_e objtype;
  void (*foo)(void); 
} ObjectB = {
  0x2
  ,world
};

typedef struct 
{   
  type_e objtype;
  void (*bar)(void); 
} ObjectB_t;

typedef struct Entry_t
{
  struct Entry_t *next;
  int data;
  void *obj;
} Entry_t;

...

void processList(Entry_t* list)
{
  do 
  {
    if(list->obj==0)
      return;

    Entry_t *objtype = list->obj;

    if(objtype == &ObjectA)
    {
      printf("objtype=A\n");
      ((ObjectA_t*)(list->obj))->foo();
    }
    else if(objtype == &ObjectB)
    {
      printf("objtype=B\n");
      ((ObjectB_t*)(list->obj))->bar();
    }
    else   
    {
      printf("objtype unknown!\n");
    }

  list = list->next;
  } while(list != 0);

}
...

hoffe das wird jetzt klarer was ich mein;)

[noobLolo]

ups "void *objtype = list->obj;" und in dem bsp. war das nicht dabei

lg lolo

[stefan-tiger]

Hallo noobLolo,

danke für deine Antwort.

Ich denke jetzt verstehe ich was du mit "Adresse als ID" nehmen gemeint hast bzw. ich habe das schon geahnt.

Diese Lösung ist mir allerdings zu unflexibel und hat wenn ich es richtig sehe einige Nachteile:

1. Du legst hier global Speicher an und initialisierst ihn gleich noch
2. Es gibt nur eine Instanz ObjektA
3. Du frägst die Adresse dieser Instanz ab

Warum möchte ich das nicht haben:

zu 1.: Wenn jemand garkein ObjektA angelgen möchte bekommt er doch eins untergeschoben
zu 2.: Es soll möglich sein viele Instanzen von ObjektA zu erzeugen
zu 3.: Ich müsste für jede Instanz von ObjektA die Adresse abfragen; das geht nicht weil ich nicht weiss wieviele ObjektA-Instanzen zur Laufzeit angelegt werden; zudem wäre es umständlich

Vll liege ich auch falsch und hab dein Code doch nicht ganz verstanden? Kannst du dein Beispiel bitte mal mit zwei weiteren, zur Laufzeit angelegten, Instanzen von ObjektA erweitern? Dann wird es warscheinlich noch deutlicher...

Danke.

[noobLolo]

Du legst hier global Speicher an und initialisierst ihn gleich noch

na klar so wie man das eben macht.

Es gibt nur eine Instanz ObjektA

naja das ist nur zum teil richtig, denn es gibt nur eine "classe A" von dieser klasse werden dann die objecte abgeleitet.

Du frägst die Adresse dieser Instanz ab

ich frage nicht die adresse der instanz sondern die adresse der classe ab das ist ein unterschied.

ich denke wir haben einfach unterschiedliche ansichten wie oop aussehen muß.

lg lolo

[Big Brother]

stefan-tiger schrieb:

Warum möchte ich das nicht haben:

zu 1.: Wenn jemand garkein ObjektA angelgen möchte bekommt er doch eins untergeschoben
zu 2.: Es soll möglich sein viele Instanzen von ObjektA zu erzeugen
zu 3.: Ich müsste für jede Instanz von ObjektA die Adresse abfragen; das geht nicht weil ich nicht weiss wieviele ObjektA-Instanzen zur Laufzeit angelegt werden; zudem wäre es umständlich

Ein dynamisch erzeugtes ObjektX muss mit Werten initialisiert werden, sonst ist die Abfrage eines Objekt-Typs bzw. ein Zugriff auf einen Funktionszeiger nicht möglich. Bei der Initialisierung kannst du diesem Objekt einen Funktionszeiger verpassen.

Haben alle Objekte ( Objekt1, ... , ObjektN ) als erstes Element einen Fuktionszeiger z.B.
void (*func_ptr)(void* object), kannst du dir eine Art Schablone erstellen:

typedef struct objectX ObjectX; 
struct objectX
{
     void (*func_ptr)(void* object);
};

Der Zeiger auf diese Schablone ist dein 'Universalschlüssel' für den Zugang zu den Funktionen der Objekte Objekt1, ... , ObjektN. Damit hast du einen Direktzugriff auf die Funktionen der zugehörigen Objekte, ohne einen Objekttyp abragen zu müssen. Guckst du:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <errno.h>

typedef struct objectX ObjectX; 
typedef struct objectA ObjectA; 
typedef struct objectB ObjectB; 
typedef struct list List;

struct objectX
{
	void (*func_ptr)(void* object);
};

struct objectA
{
	void (*func_ptr)(void* object); 
	int value;
};

struct objectB
{
	void (*func_ptr)(void* object); 
	char buf[BUFSIZ];
};

struct list
{
	void* object;
	List* next;
};

void func_objectA ( void* object )
{
	ObjectA* p = object;
	printf ( "%d\n", p->value );
}

void func_objectB ( void* object )
{
	ObjectB* p = object;
	printf ( "%s\n", p->buf );
}

void init_objectA ( ObjectA* p )
{
	p->func_ptr = func_objectA, p->value = 707;
}

void init_objectB ( ObjectB* p )
{
	p->func_ptr = func_objectB, strncpy ( p->buf, "Hello World", sizeof(p->buf)-1 );
}

void process_list ( List* l )
{
	ObjectX* px;
	while ( l != NULL )
		px = l->object, px->func_ptr ( l->object ), l = l->next;
}

int main()
{
	List* L = calloc ( 2, sizeof ( *L ) );
	ObjectA* A = malloc ( sizeof( *A ) );
	ObjectB* B = malloc ( sizeof( *B ) );

	if ( errno ) { free ( A ), free ( B ), free ( L ); return 1; };

	init_objectA ( A ), init_objectB ( B );
	L[0].object = B, L[0].next = &L[1], L[1].object = A, L[1].next = NULL;
	process_list ( L );

	free ( A ), free ( B ), free ( L );
	return 0;
}

[noobLolo]

evtl. schaust dir mal in java script das prototype object und konzept an. wenn man verstanden hat was da passiert lässt sich oop auch easy in c umsetzen und man kommt nicht mit komischen vorstellungen daher die klassen structur und methoden in jede instanz mit reinzukopieren.

lg lolo

[stefan-tiger]

noobLolo schrieb:

...
naja das ist nur zum teil richtig, denn es gibt nur eine "classe A" von dieser klasse werden dann die objecte abgeleitet.
...
ich frage nicht die adresse der instanz sondern die adresse der classe ab das ist ein unterschied.

ich denke wir haben einfach unterschiedliche ansichten wie oop aussehen muß.

...

Korrigier mich wenn ich was falsches schreibe:
In deinem Code ist Klasse=Instanz und es gibt sie nur einmal. Und dieses eine mal ist auch noch zur Compile-Zeit und nicht zur Laufzeit angelegt.
Daher ist es in deinem Beispiel auch kein Problem die Adresse der "Klasse" abzufragen.

Ich möchte aber mehrere Instanzen zur Laufzeit anlegen.

Ich weiss nicht ob ich ein anderes Verständnis von OOP habe, aber in C ist für mich das was in C++ eine "class" ist ein "typedef struct".
Wichtig ist mir hierbei das "typedef", denn eine Klasse in C++ belegt an sich noch kein Speicher und kann nicht als "lebendes Objekt" vendendet werden, das wird erst mit einer Instanz möglich (oder nicht?).

[stefan-tiger]

Hallo Big Brother,

deinen ersten Satz verstehe ich nicht. Ist das ein Problem für Dich?
Für mich ist das kein Problem, da ich eine new-Funktion für meine Objekte schreibe in der das "malloc" gemacht wird und initialisiert wird.

Ansonsten kann ich dein Beispiel nachvollziehen, danke dafür.

Hierbei sind aber die Einschränkungen gegeben, dass

(a) alle Klassen diesen Funktionspointer haben müssen
(b) der Funktiinspointer im struct aller Klassen immer an der selben Stelle steht
(c) der Funktionspointer immer die selbe Signatur in allen Klassen haben muss

Der Vorteil dieser Lösung ist allerdings, dass es dem Basis-Klassen-Konzept von C++ näher kommt und dass die Implementierung zwischen der Liste und den Objekten besser getrennt ist.

[stefan-tiger]

Hallo Big Brother,

ich hab grad noch was gesehn was mit nicht gefällt bei der Lösung:

Die "Member"-Funktionen haben void-Pointer als Parameter.

[Big Brother]

stefan-tiger schrieb:

Hallo Big Brother,

deinen ersten Satz verstehe ich nicht. Ist das ein Problem für Dich?

Nein, kein Problem. Du hast ne new-Funktion, hast sich also erledigt.

stefan-tiger schrieb:

Hierbei sind aber die Einschränkungen gegeben, dass

(a) alle Klassen diesen Funktionspointer haben müssen

Oder eine Art Objekt ID, die ebenfalls alle Strukturen haben müssen, wobei der Zugriff auf die Funktionen umständlicher ist und länger dauert.

stefan-tiger schrieb:

(b) der Funktiinspointer im struct aller Klassen immer an der selben Stelle steht

Ja, die Reihenfolge der Strukturelemente ist eingeschränkt. Inwiefern ist das für Dich problematisch?

stefan-tiger schrieb:

(c) der Funktionspointer immer die selbe Signatur in allen Klassen haben muss

Dank der Zeigerübergabe aber flexibel ist.

stefan-tiger schrieb:

Der Vorteil dieser Lösung ist allerdings, dass es dem Basis-Klassen-Konzept von C++ näher kommt und dass die Implementierung zwischen der Liste und den Objekten besser getrennt ist.

Je näher an C++ ,desto besser?
Da drängt sich mir die Frage auf: Warum schreibst Du das nicht gleich in C++ ?

stefan-tiger schrieb:

Die "Member"-Funktionen haben void-Pointer als Parameter.

Was gefällt Dir daran nicht? Du kannst auch nen unsigned long nehmen oder sowas.

Gruß,
B.B.

[stefan-tiger]

Big Brother schrieb:

...

stefan-tiger schrieb:

(b) der Funktiinspointer im struct aller Klassen immer an der selben Stelle steht

Ja, die Reihenfolge der Strukturelemente ist eingeschränkt. Inwiefern ist das für Dich problematisch?
...

stefan-tiger schrieb:

Der Vorteil dieser Lösung ist allerdings, dass es dem Basis-Klassen-Konzept von C++ näher kommt und dass die Implementierung zwischen der Liste und den Objekten besser getrennt ist.

Je näher an C++ ,desto besser?
Da drängt sich mir die Frage auf: Warum schreibst Du das nicht gleich in C++ ?

stefan-tiger schrieb:

Die "Member"-Funktionen haben void-Pointer als Parameter.

Was gefällt Dir daran nicht? Du kannst auch nen unsigned long nehmen oder sowas.

Gruß,
B.B.

Problematisch ist es nicht direkt. Ich versuche nur eine so weit wie möglich allgemeingültige Lösung zu finden. Die Strukturen haben dann eben gewissen "organisatorischen" Regelen entsprechen und sind nichtmehr völlig unabhängig (wären sie mit der Typ-Kennung auch nicht 100%).

Warum ich nicht C++ verwende? Nun, ich denke ich kann mehr über die "internen" Dinge eines Programms lernen wenn ich in C Dinge selbst machen muss die in C++ inklusive sind bzw. durch Templates und umfangreiche Libraies gekapselt sind.
Natürlich kann man sich auch deren Implementierungen ansehen...

An den void-Parametern gefällt mir nicht, dass hier der Code an einer Stelle verändert wurde, weil an einer anderen Stelle eine bestimmte Implementierung gewählt wurde. Anders ausgedrückt: Ohne die verkettete Liste würde man den Member-Funktionen der Klassen einen Pointer des "richtigen" Klassen-Typs übergeben, statt einen void-Pointer.
Das ist eine Design-Regel die man z.B. anderen Programmierern die Klassen zuliefern möchten mitgeben muss. Das macht es jedenfall nicht einfacher.

[Big Brother]

stefan-tiger schrieb:

An den void-Parametern gefällt mir nicht, dass hier der Code an einer Stelle verändert wurde, weil an einer anderen Stelle eine bestimmte Implementierung gewählt wurde. Anders ausgedrückt: Ohne die verkettete Liste würde man den Member-Funktionen der Klassen einen Pointer des "richtigen" Klassen-Typs übergeben, statt einen void-Pointer.
Das ist eine Design-Regel die man z.B. anderen Programmierern die Klassen zuliefern möchten mitgeben muss. Das macht es jedenfall nicht einfacher.

Ok, ist hier auch machbar und es gefällt mir auch besser als die void*
Alternative:

void func_objectA ( ObjectA* object )
{
    printf ( "%d\n", object->value );
}

void func_objectB ( ObjectB* object )
{
	printf ( "%s\n", object->buf );
}