Queue Documentation

Anforderung:

Implementierung einer Datenstruktur zur Übertragung von Daten zwischen Threads. Threadsicherheit sollte gewährleistet werden.

Daten sollen nach FIFO-Prinzip übertragen werden.

Lösung:

Eine Warteschlange die Zugriffe auf Ressourcen von Zweiten durch Mutexe und Semaphoren schützt.

Umsetzung:

Umgesetzt wurde das Ganze mit einer selbst implementierten Warteschlange.

Deklaration und Definition in der queue.h und Implementierung in der queue.c

Deklaration und Definition

Die Warteschlange hat den Typ IG_Queue. Eine IG_Queue ist ein Struct und besitzt die folgende Felder:

typedef enum {IG_QUEUE_BLOCKING, IG_QUEUE_NONBLOCKING} IG_QueueType;

typedef struct{
	IG_UInt32 size;
	IG_QElement * front;
	IG_QElement * end;
	pthread_mutex_t mutex;
	sem_t size_sem;
	IG_QueueType type;
} IG_Queue;

• size: Anzahl der Elemente in der Warteschlange
• front: Verweist auf das vorderste Element
• end: Verweist auf das letzte Element
• mutex: Mutex um Zugriff von Ressourcen vor Zweiten zu schützen
• size_sem: Semaphore um Zweite bei Zugriff von nicht vorhanden Ressourcen zu blockieren.
• type: Typ der Warteschlange

Ein Element der Warteschlange hat den Typ IG_QElement. Ein IG_QElement ist ein Struct und besitzt die folgenden Felder:

typedef struct node IG_QElement;

struct node{
	IG_QElement * next;
	IG_Data * data;
};

• next: Verweis auf das nächste Element
• data: Verweis auf die eigentlichen Daten

Funktionen

Für das Arbeiten mit der IG_Queue stehen folgende Funktionen zu Verfügung.

Erzeugen einer IG_Queue

Zur Erzeugung einer IG_Queue.

IG_Queue * IG_Queue_new( IG_QueueType type)

Die Funktion allokiert Speicher für ein IG_Queue Struct auf dem Heap und initialisiert diese mit NULL- und 0 Werten. Der Mutex und die Semaphore werden jedoch entsprechend wie vorgesehen initialisiert.

Parameter:

• type: Beschreibt welchen Typ die Warteschlange annehmen soll

Rückgabewert: Gibt einen Pointer auf ein IG_Queue Struct zurück welches auf dem Heap angelegt wird.

3.2.2 Löschen einer IG_Queue Zum Löschen einer IG_Queue.

void IG_Queue_delete( IG_Queue * queue);

Die Funktion legt den Speicher aller übrigen Element frei und zerstört sein Mutex und seine Semaphore, welche jedoch jeweils wieder freigegeben werden um einen Deadlock zu vermeiden. Der Pointer wird zum Schluss auf NULL gesetzt.

Parameter:

• queue: Pointer auf zu löschende IG_Queue

Rückgabewert: Keiner.

Einfügen von Daten in einer IG_Queue

Zum Einfügen bzw. anhängen von Daten ans Ende einer IG_Queue.

void IG_Queue_put( IG_Queue * queue, IG_Data * new_data);
void IG_Queue_put_copy( IG_Queue * queue, IG_Data new_data);

Die Funktion allokiert Speicher für ein IG_QElement und hängt diese am Ende der IG_Queue an. Um zu verhindern, dass Zweite in die selbe IG_Queue zeitgleich Daten einfügen wird der Mutex gesperrt. Nach dem Einfügen wird dieser wieder entsperrt. Die Semaphore wird beim Typ IG_QUEUE_BLOCKING inkrementiert. Bei Daten die auf dem Stack liegen kann man bequem die IG_Queue_put_copy Funktion verwenden. Diese erzeugt entsprechend die Daten auf dem Heap und hängt diese an die IG_Queue an.

Parameter:

• queue: Pointer auf die zu verwendende IG_Queue
• new_data: Pointer auf neuen Datensatz der angehängt wird / Struct für die Daten

Rückgabewert: Keiner.

Entnehmen von Daten aus einer IG_Queue

Zum Entnehmen des vordersten Elements einer IG_Queue.

IG_Data * IG_Queue_take( IG_Queue * queue);

Die Funktion entnimmt das vorderste Element der Warteschlange und gibt den Pointer auf diese zurück. Genau wie die IG_Queue_put Funktion versucht diese ebenso die IG_Queue vor dem Zugriff Zweiter zu schützen. Das neue vorderste Element wird das Folgeelement des entnommenen Elementes.

Parameter:

• queue: Pointer auf die zu verwendende IG_Queue

Rückgabewert: Pointer auf das entnommene Element. Bei leere Warteschlange wird ein NULL Pointer zurückgegeben.

Überprüfen ob eine IG_Queue leer ist

Zum Überprüfen ob eine IG_Queue keinerlei Elemente mehr beinhaltet.

IG_Bool IG_Queue_isEmpty( IG_Queue * queue);

Überprüft ob eine IG_Queue leer ist.

Parameter:

• queue: Pointer auf die zu verwendende IG_Queue

Rückgabewert: Boolean der ausdrückt ob die Queue leer ist oder nicht.