Queue in C

Hallo an alle C-Profis,

1. vorneweg: Ich bin Neuling in C und starte meine ersten Gehversuche.
2. vorneweg: Es gibt bereits Lösungen von Forenmitgliedern und fertige Sachen, die mein Problem lösen. Ich möchte aber zur Bestätigung meiner selbst das auch hinkriegen
Es gibt die Möglichkeit, die Queue aus glib.h zu verwenden. Das funktioniert und wird über die Präprozessor-Direktive hiergesteuert. Um von der Abhängigkeit los zu kommen, möchte habe ich meine eigene kleine Queue geschrieben.

Ausgangssituation:
Das libvdpau-sunxi Backend benötigt zur Darstellung einen fifo-Buffer etc. Ich nenne das hier Queue.
Softhddevice erstellt ein Surface. Das Backend reserviert Speicher für ein Strukt (task) mit den Angaben zum Surface, erstellt einen Zeiger darauf und stellt diesen ans Ende einer Queue (vdp_presentation_queue_display).
Ein eigenständiger Thread arbeitet diese Queue vom Kopf her ab (*presentation_thread) und reicht den Zeiger an die Darstellungsfunktion (do_presentation_queue_display) weiter. Dort wird das Surface angezeigt und danach wird der Speicher auf den der Zeiger zeigt wieder freigegeben.

Dabei möchte ich die Größe der Queue im Vorneherein erstmal nicht festlegen. Eine Bremse kann man immer noch einbauen. Das sollte möglich sein, wenn nur mit den Zeigern (oder -adressen) hantiert wird.
Im Prinzip müsste der ja momentan dynamisch sein und von der Anzahl der offenen Tasks bestimmt werden. Um einen Überlauf zu verhindern, müsste man den natürlich später begrenzen.

Problem:
Irgendwo habe ich hier aber einen Denkfehler. Ich glaube nämlich, dass ich da mit Zeiger auf Zeigern bzw. den Adressen arbeiten müsste?!

Quellcode:
Die reine Queue liegt mit Beispielprogramm hier und funktioniert eigentlich (augenscheinlich mit einem billigem int).
Das habe ich jetzt versucht zu übernehmen und der Code schaut dann so aus. Relevant sind nur queue.c, queue.h und presentation_queue.c
Einige Funktionen im Queue-Code sind dabei ungenutzt. Genutzt werden hier nur q_push_tail, q_extract_head, q_pop_head und q_queue_free, q_queue_init.
Das "pushen" in die Queue funktioniert. Ich kann direkt danach den letzten Eintrag auslesen und der stimmt. Nur im presentation_thread habe ich keinen Zugriff mehr darauf. Hier unterscheiden sich auch die Speicheradressen von diesem &task und diesem hier, wenn ich sie mit

printf("task_addr: %x", &task);

anzeigen lasse.

-> Und ich glaube hier liegt mein Fehler.

Ich weiß, es ist anstrengend, sich in fremden Code reinzudenken, aber vielleicht weiß ja jemand nicht, was er gerade tun soll und kann sich das mal ansehen. Ich jedenfalls bin gerade etwas überfordert damit

Vielen Dank und Gruß
Andreas

Zitat von johns

Für sowas kannst z.b. doppelt verkettete Listen verwenden.

http://perlgeek.de/de/artikel/doppelt-verkettete-listen

Damit du ein Element herausnehmen kannst, enthält das Element Zeiger auf das vorherige und das nächste.

Du musst aufpassen, daß das Ganze Thread sicher ist. Da ja verschiedene Threads auf die Liste zugreifen.
...
Johns

Alles anzeigen

Im Prinzip habe ich es ja so gemacht. Eine Liste mit ->head und ->tail als Zeiger auf Anfang und Ende und die Listeneinträge selbst als struct mit Zeigern auf ->prev und ->next und einem Zeiger auf die Datenstruktur.
In der Beispiel Queue funktioniert das auch wunderbar, nur nicht mehr, wenn ich versuche, diese Queue in libvdpau_sunxi einzusetzen.

Danke und Gruß
Andreas

Hi LordJaxom,
danke für deine Antwort.

Zitat von LordJaxom

Dass sich die Adressen von dem gepushten task und dem "extrahierten" unterscheiden, ist doch klar: Du allokierst vor dem extrahieren neuen Speicher mit calloc und übergibst diesen an die Funktion q_extract_head.

Zunächst mal kann das so nicht funktionieren, da in der Funktion q_extract_head sizeof(void) genommen wird. Mich wundert, dass der Compiler das überhaupt zulässt. Jedenfalls wird dieser sizeof nicht das zurückgeben, was Du haben möchtest, und somit nicht den kompletten Task aus der Queue nach data kopieren. Warum hier überhaupt neuen Speicher allokieren?

Ok. Eigentlich brauch ich die Funktion nicht. q_peek würde ausreichen, um den Zeiger zu bekommen und damit was anzustellen. Spar ich mir Speicher und kann ein free() nicht vergessen.

Zitat

....

Wenn wirklich eine Kopie nötig ist, musst Du die Größe an q_extract_head mit übergeben. Dann wunder Dich aber auch nicht, dass die Adresse des neu allokierten und kopierten Tasks anders ist

Wie würde ich das machen müssen?

q_extract_head(queue, task_p, sizeof(task_t *task_p));

und

void q_extract_head(QUEUE *queue, void *data, int size)
{
...
memcpy(data, queue->head->data, size);
...
}

?
...

Zitat

Zum Schluss noch ein kleiner Hinweis auf etwas, was ich als schlechten Stil bezeichnen würde: Den Speicher für data allokiert bei dieser Queue der Aufrufer, freigeben tut aber die Queue (in q_node_free). Eigentlich sollte sich um die Freigabe immer derjenige kümmern, der den Speicher auch angefordert hat. So nimmst Du Dir die Möglichkeit, jemals etwas in die Queue zu packen, was nicht mit malloc/calloc allokiert wurde.

Am besten wäre es dann wohl, wenn sich die Queue komplett um die Speicherzuweisung kümmert? q_queue_free(queue) sollte dann im Endeffekt schon dafür sorgen müssen, dass auch alle Speicherbereiche der Zeiger in der Queue und der Daten freigegeben werden...
Dh. ich müsste das hier besser so machen:

task_t task; // zuerst ein struct erstellen 
task->clip_width = clip_width; // und befüllen
task->clip_height = clip_height;
...
q_push_tail(queue, &task); // nur die Adresse übergeben

Oder reicht das nicht aus, und ich muss die Speichergröße wie oben übergeben und Speicher zuweisen?

q_push_tail(queue, &task, sizeof(task_t *task);

void q_push_tail(QUEUE *queue, void *data, int size)
{
...
NODE *node = allocate_node(data, size);
...
}

NODE *allocate_node(void *data, int size)
{
void *data = (void *)calloc(1, size);
NODE *node = (NODE *)calloc(1, sizeof(NODE));
...
}

?

Danke für deine Hilfe, wahrscheinlich sind meine Fragen teilweise großer Schmarrn und alles bissl DAU mäßig. Aber dauert es noch, bis ich als Fachfremder das Zeigerzeug einigermaßen verstanden habe.

Mich wundert nur, warum die Beispiel Queue ohne Meckern kompiliert und mit dem jetzigen Code-Stand funktioniert, und das gleiche Prinzip in libvdpau-sunxi nicht. Kann das einfach an den kleinen Speichergrößen wg. des "int value" liegen?

Gruß
Andreas

Mit "long double value" klappts schon nicht mehr :p.

Gruß
Andreas

PS: Ein bißchen Google, und man sieht wie klein die Welt ist

So klappt das mit dem q_extract jetzt. Fehlerbehandlung mit Rückgabewert muss ich noch einbauen.
Gruß Andreas

Ich hab jetzt alles noch ein bißchen umgestellt und hoffentlich verbessert.
Alle Funktionen sollten vom Prinzip her so passen.
-> aktueller Stand

Jetzt wäre noch zu klären, ob die Queue den Speicher für *data zuweist und wieder freigibt, oder das Hauptpogramm oder gemischt ...

Gruß
Andreas

Zitat von LordJaxom

Aktuell ist es so, dass der Aufrufer allokiert und den Zeiger an die Queue übergibt. Die Queue gibt in q_free_node auch den übergebenen Bereich frei, die q_pop-Funktionen geben diesen Bereich aber nach dem free zurück. In diesem Fall müssten die pop-Funktionen in jedem Fall void (oder einen Status) zurückgeben, da mit einem Zeiger nach dem free nichts mehr anzufangen ist.

Wenn der Aufrufer den Speicher verwaltet, könnte man sich bei push/pop noch darauf einigen, dass pop die Daten zurückgibt (ungefreed) und diese freigegeben werden müssen, für das Löschen der gesamten Queue könnte man aber keine Funktion mehr anbieten.

Code

void* data = malloc(...);
q_push(queue, data);
...
void* data = q_pop(queue);
free(data);

Habs jetzt erst mal im Prinzip so gemacht wie du beschrieben hast.
Der Aufrufer allokiert und übergibt den Zeiger. q_pop löscht die Referenzen innerhalb der Queue auf die Daten, d.h. den NODE* und gibt dann die Daten als Zeiger wieder zurück. Danach muss sich der Aufrufer wieder darum kümmern, dass der Speicherbereich der Daten gefree'd wird. Je nachdem, was er damit vorhat.
Das geht mit dem Schalter "data_reset = 0" in q_node_free.

Um nichts vergessen zu können, räumt ein q_queue_free die komplette Queue inkl. Daten auf - sofern vorhanden. Nach dem freigeben der Queue gibts halt keine Daten mehr, ausser sie wurden vorher mit q_pop oder q_extract geholt.
Ich denke, das ist ein passender Kompromiss. Die Queue aus glib.h macht das genauso.

Zitat

Wenn die Queue den Speicher allein verwaltet (Übergabe von Zeiger und Größe) handelt man sich immer eine potentiell unnötige Kopie ein, der Aufrufer würde eine gefüllte Struktur übergeben und die Queue neuen Speicher allokieren und den Inhalt kopieren.

Aus Gründe der Resourcenschonung denke ich, dass ein weiteres malloc und memcpy vermieden werden sollte...

Zitat

Ein Kompromiss wäre, der Queue die Möglichkeit zu spendieren, eine Deallokationsfunktion zu übergeben, die dann in der Node gespeichert wird. Damit könnte die Queue auch komplexe Strukturen verwalten, der Aufrufer hat die Kontrolle und würde auch den Speicher freigeben (indirekt zwar, weil durch die Queue angestoßen, aber unter eigener Kontrolle). Die Deallokationsfunktion könnte man mit einem Default versehen. Beispiel:

Code

void q_push(QUEUE* queue, void* data, void (*free_func)(void*))
{
	...
	node->free_func = free_func;
}


void q_push_default(QUEUE* queue, void* data)
{
	q_push(queue, data, free); // Hier ist die Funktion free aus stdlib.h gemeint
}


void q_pop(QUEUE* queue)
{
    ...
	node->free_func(node->data);
	free(node);
}

Alles anzeigen

Wenn das allerdings zu kompliziert wird, ist auch nichts gewonnen. Dann sollte man im Zweifel einfach vertraglich vereinbaren, dass der an q_push übergebene Speicher mit malloc oder calloc allokiert sein muss. Dann gib aber wenigstens den Zeiger nicht nach dem free aus q_pop zurück

Das wäre eine umfassende Lösung, wird aber momentan für einfache Strukturen nicht benötigt. Entweder wird alles gelöscht oder gar nichts. Und das kann man auch so wie oben machen. Evtl. erweitere ich den Code später mal in diese Richtung bei Bedarf.

Das einzige Problem, das ich gestern hatte war, dass ich die q_pop Funktionen so definieren wollte, weils m.E. konsequenter wäre:

qStatus *q_pop_tail(QUEUE *queue, void **data)

Ich wollte das dann in der Funktion so wie bei q_peek handhaben (nur mit zusätzlichen dereferenzieren des NODE in der Queue) und einfach

*data = queue->head->data;

machen.
Ich glaube aber, dass das Problem dabei war, dass ich data nicht halten kann, wenn sich der Head ändert. Ich würde also die ursprüngliche Adresse von *data und nicht queue->head->data zurückliefern müssen.
Liege ich da richtig in der Analyse und wie müsste ich das richtig machen?

Danke für die Hilfe, du hast mir bisher sehr geholfen und mir das C wieder etwas näher gebracht. Der Tip mit dem sizeof war der ausschlaggebende

Gruß Andreas