doppelt verkettete Liste - Listenelemente tauschen

[Darkstyle]

Nabend zusammen,

ich habe für ein Projekt eine Funktion geschrieben, die in einer doppelt verketteten Liste zwei Elemente miteinander austauscht. Wenn die Liste z.B. so aussieht:

[1] [2] [3]

und ich möchte Element 1 mit 2 tauschen, wird sie entsprechend umgestaltet:

[2] [1] [3]

Der Liste liegt folgende Struktur zu Grunde:

struct liste {
    // Daten
    struct liste *next;
    struct liste *prev;
};

Von diesen Strukturen habe ich mehrere, die sich in ihrem Datenanteil unterscheiden, und so unterschiedliche Listen ergeben. Die Zeiger next und prev sind jedoch stehts an der vorletzten und letzten Position. Da ich nicht für jede einzelne Liste eine extra Funktion bauen wollte, die dann jeweils nur mit dieser einen Liste umgehen kann, ansonsten aber alle die selbe Aufgabe erledigen, habe ich die Funktion universell aufgebaut.

void list_swap(void *list1, void *list2, int obj_size, int pnt_size)
{
    void **list1_next_prev, **list1_prev_next, **list2_next_prev, **list2_prev_next;
    void *cache_next, *cache_prev, **list1_next, **list1_prev, **list2_next, **list2_prev;

    // Adressen berechnen für list1->next, list1->prev, list2->next, list2->prev
    list1_next = list1 + obj_size - (pnt_size << 1);
    list1_prev = list1 + obj_size - pnt_size;
    list2_next = list2 + obj_size - (pnt_size << 1);
    list2_prev = list2 + obj_size - pnt_size;

    // Adressen berechnen für list1->prev->next, list1->next->prev, list2->prev->next, list2->next->prev
    list1_prev_next = (*list1_prev != NULL) ? (*list1_prev + obj_size - (pnt_size << 1)) : NULL;
    list1_next_prev = (*list1_next != NULL) ? (*list1_next + obj_size - pnt_size) : NULL;
    list2_prev_next = (*list2_prev != NULL) ? (*list2_prev + obj_size - (pnt_size << 1)) : NULL;
    list2_next_prev = (*list2_next != NULL) ? (*list2_next + obj_size - pnt_size) : NULL;

    // next und prev Zeiger der Nachbarelemente von list1 und list2 neu setzen
    if (*list1_prev != NULL)
        *list1_prev_next = list2;
    if (*list1_next != NULL)
        *list1_next_prev = list2;
    if (*list2_prev != NULL)
        *list2_prev_next = list1;
    if (*list2_next != NULL)
        *list2_next_prev = list1;

    // next und prev Zeiger von list1 und list2 neu setzen
    cache_next = *list1_next;
    cache_prev = *list1_prev;

    *list1_next = *list2_next;
    *list1_prev = *list2_prev;
    *list2_next = cache_next;
    *list2_prev = cache_prev;
}

Dies ist der Funktionsaufruf:

list_swap(list1, list2, sizeof(struct liste), sizeof(struct liste *));

// sizeof(struct liste) und sizeof(struct liste *) werden zur Berechnung der Zeiger-Adressen benötigt

Ganz oben werden zunächst die Speicheradressen der next und prev Zeiger berechnet, direkt darunter dann die next und prev Zeiger der entsprechenden Nachbarelemente.
Im nächsten Schritt werden die Zeiger der Nachbarn neu gesetzt (dass der Nachbar von list1 nun auf list2 zeigt und umgekehrt), und zuletzt noch die Zeiger von list1 und list2 selbst.

Diese Funktion habe ich soweit getestet, und scheinbar klappt alles, wie es soll. list1 und list2 können je am Anfang oder am Ende der Liste stehen, direkt miteinander benachbart sein oder beliebig weit voneinander entfernt mitten in der Liste stehen und werden in allen Konstellationen zuverlässig getauscht.
Mein Problem besteht jetzt mehr darin, diese Funktion nachzuvollziehen, denn eigentlich dürfte sie so nicht funktionieren (nach meinem Verständnis).
Um es besser verstehen zu können, habe ich sie noch einmal in veränderter Form implementiert:

void list_swap_new(struct liste *list1, struct liste *list2)
{
	struct liste *cache_next;
	struct liste *cache_prev;

	// next und prev Zeiger der Nachbarelemente von list1 und list2 neu setzen
	if (list1->prev != NULL)
		if (list1->prev != list2)
			list1->prev->next = list2;
	if (list1->next != NULL)
		if (list1->next != list2)
			list1->next->prev = list2;
	if (list2->prev != NULL)
		if (list2->prev != list1)
			list2->prev->next = list1;
	if (list2->next != NULL)
		if (list2->next != list1)
			list2->next->prev = list1;

	// next und prev Zeiger von list1 und list2 neu setzen
	cache_next = (list1->next != list2) ? list1->next : list1;
	cache_prev = (list1->prev != list2) ? list1->prev : list1;

	list1->next = (list2->next != list1) ? list2->next : list2;
	list1->prev = (list2->prev != list1) ? list2->prev : list2;
	list2->next = cache_next;
	list2->prev = cache_prev;
}

Hier kann jetzt zwar nur noch eine Liste vom Typ struct liste verarbeitet werden, aber die Berechnung der Adressen entfällt. Und hier ist mir auch aufgefallen, dass ich zusätzlich noch abfragen muss, ob list1 und list2 direkte Nachbarn sind, da sonst die Zeiger falsch gesetzt werden.
Wenn ich weiter oben z.B. die Abfrage

14    if (list2->prev != list1)

weglasse, und direkt

15        list2->prev->next = list1;

ausführe, list1 aber direkt neben list2 liegt (list2->prev == list1), dann würde im unteren Teil

25    list1->prev = list2->prev    // Abfrage (list2->prev != list1) auch hier entfernt

list1->prev auf sich selbst zeigen lassen. Der Aufbau wie in der ersten Funktion klappt hier also nicht.

Wenn man nun beide Funktionen vergleicht, fehlen ja oben diese ganzen Abfragen auf Nachbarn, lediglich auf NULL wird geprüft. Was ich nun aber nicht verstehe, warum funktioniert die erste Funktion trotzdem? Eigentlich müssten doch da die Zeiger falsch gesetzt werden, wenn list1 und list2 Nachbarn sind. Oder übersehe ich etwas?
Wie gesagt, beide Beispiele hier funktionieren bei mir, es geht mir lediglich um das Verständnis, warum die erste Funktion in dieser Form läuft.

Ich hoffe, ihr könnt mir helfen, denn vor lauter Zeigerwirrwarr blicke ich kaum noch durch.

mfg
Darkstyle

[DirkB]

Warum machst du die Verkettung nicht am Anfang der struct?

struct liste {
    struct liste *prev;
    struct liste *next;
    // Daten
};

Dann bist du die Sache mit der obj_size los und der Datenoffset ist immer 2 Zeiger groß.

[definator]

Andere Möglichkeit:

typedef struct navigation_pointer {
    struct liste *prev;
    struct liste *next;
} navigation_pointer;

#define NAVIGATION_POINTER(s) ((navigation_pointer *)(&s->prev))

void list_swap_ (navigation_pointer *list1, navigation_pointer *list2) { ... }
#define list_swap(list1, list2) do{list_swap_ (NAVIGATION_POINTER (list1), NAVIGATION_POINTER (list2));}while(0)

// aufruf
list_swap(list1, list2);