void* array an qsort übergeben

SeppJ

Du kannst übrigens auch Pointer vergleichen (also direkt über <, >, ==, usw.). Diese Aktion ist aber streng genommen nur definiert, falls die Pointer alle auf Werte im gleichen Array zeigen, was auch der einzige Fall ist, wo Pointervergleiche irgendwie Sinn machen. Praktisch kannst du jedoch davon ausgehen, dass diese Aktion für einen i386 im protected mode auch für beliebige Pointer funktioniert. Wenn man dies tut, muss man sich jedoch wirklich die Frage

mgaeckler schrieb:

Welchen Sinn es macht, die Variablen nach Ihren Adressen im Speicher zu sortieren, mußt Du allerdings schon erklären.

gefallen lassen und sollte eine gute Antwort darauf haben.

CJosef

void* n00b schrieb:

Was mache ich falsch?

Ich gehe davon aus, dass du das Array nach den Integerwerten sortieren willst.
Ansonsten bräuchtest du nicht die Integer-Zeiger im Array zu speichern
Deine Funktion compare nimmt nicht wie du vllt. vermutet hast die int* Zeiger entgegen sondern die Adressen der void* Zeiger, die in deinem void** pv gespeichert sind.
Die Parameter a, b deiner Vergleichsfunktion nehmen also die Werte &pv[0], &pv[1], &pv[2] an.
Vielleicht klingelt es jetzt schon ein wenig(?) - die Funktion compare hat zwar als Parameter void* Zeiger, es kommen aber void** Zeiger rein.
Wie wärs also mit folgender Lösung(ich hoffe du willst nach den Werten sortieren, sonst ist das alles heir fürn Popo :D):
a und b nach void** casten und dereferenzieren ergibt void* (das sind die pv[0], pv[1], pv[2], in denen deine Integer-Zeiger stecken).

void* pa = *((void**)a);
void* pb = *((void**)b);

Das Ganze dann nochmal nach int* casten und dereferenzieren, damit kommst du dann an deine Integerwerte ran, die du für die Vergleichsfunktion brauchst.

return *(int*)pa - *(int*)pb;

Ohne die Hilfsvariablen sieht die Vergleichsfunktion dann so aus:

int compare ( const void* a, const void* b )
{
    return *(int*)(*((void**)a)) - *(int*)(*((void**)b));
}

CJosef schrieb:

Ich gehe davon aus, dass du das Array nach den Integerwerten sortieren willst.

Ja, genau.

CJosef schrieb:

Deine Funktion compare nimmt nicht wie du vllt. vermutet hast die int* Zeiger entgegen sondern die Adressen der void* Zeiger, die in deinem void** pv gespeichert sind.

Oops achso!
Daher der 'Murks'!

CJosef schrieb:

int compare ( const void* a, const void* b )
{
return (int)(((void**)a)) - (int)(((void**)b));
}

Das sieht schon recht kompliziert aus, das ist zuverlässig, im Gegensatz zur Wutzs 'Lösung' ?

CJosef

Da habe ich keine Bedenken, du?

mgaeckler

void* n00b schrieb:

warum nicht zuverlässig?

Der Standard garantiert m.W. nicht, daß alle Zeiger gleich groß sind. Es wird nur garantiert, daß void* alle anderen aufnehmen kann. Dieses Konstrukt:

**(int**)a

macht aber aus einem void-zeiger einen int-zeiger.

Allerdings, ich kenne kein System, bei dem die Zeiger unterschiedliche Größen haben können. In der 16-Bit Welt gab es das mal, da hing die Größe aber nicht vom Typ ab, sondern vom Speicherbereich, der benutzt wurde. Mit den Schlüsselworten far und near konnte die Größe und damit Reichweite eines Zeigers festgelegt werden. Ich denke, die letzten funktionsfähigen Computer, die nur sowas ausführen konnten, findet man nur noch in Museen. Windows 7 (zumindest die 64-Bit version) führt sowas überhaupt nicht mehr aus.

mfg Martin

Wutz

Meine Lösung

int compare ( const void* a, const void* b )
{
    return **(int**)a - **(int**)b; /* <-- funktioniert nicht zuverlässig */
}

ist für den genannten Anwendungsfall vollkommen korrekt im Sinne des Standards,
und mit "nicht zuverlässig" war natürlich das potentielle UB für signed int Unterläufe gemeint und nicht das Zeigergeraffel.
Probiere mal

a=1,b=2,c=INT_MIN

aus, dann merkst du schon, dass da irgendwas nicht stimmt, hier übrigens der relativ seltene Fall, wo UB relativ zuverlässig zu sichtbaren Falschergebnissen führt und deshalb hier besser auf irgendwelche eigene "Optimierungen" verzichten und einfach

int compare ( const void* a, const void* b )
{
if ( **(int**)a < **(int**)b ) return -1;
if ( **(int**)a > **(int**)b ) return 1;
return 0;
}

verwenden, das ist auch noch besser lesbar.
Glaube mir, solchgelagerte Fehler sind sehr schwer zu finden, wenn man nicht üppige Testfälle besitzt, welche oftmals selbst in "professionellen" Projekten selten zu finden sind.
P.S. Ja ja ich weiß, K&R2 machen das auch so (falsch), aber lass die mal in Ruhe, die sind schon OK.

mgaeckler

Wutz schrieb:

Probiere mal
a=1,b=2,c=INT_MIN
aus, dann merkst du schon, dass da irgendwas nicht stimmt, hier übrigens der relativ seltene Fall, wo UB relativ zuverlässig zu sichtbaren Falschergebnissen führt und deshalb hier besser auf irgendwelche eigene "Optimierungen" verzichten und einfach
int compare ( const void* a, const void* b )
{
if ( **(int**)a < **(int**)b ) return -1;
if ( **(int**)a > **(int**)b ) return 1;
return 0;
}

Gut gesehen, nicht schlecht. Allerdings kommt es in der Praxis wohl eher selten vor, daß man so haarscharf an den Grenzen des zulässigen Wertebereichs eines ints hantiert.

Aber Du hast natürlich vollkommen recht, wenn man das tut, sollte man seinen Code schon auch daraufhin abklopfen.

mfg Martin

Wutz schrieb:

mit "nicht zuverlässig" war natürlich das potentielle UB für signed int Unterläufe gemeint und nicht das Zeigergeraffel.

um welches geraffel geht es hier? um dieses geraffel oder um das andere ?!

mgaeckler schrieb:

void* n00b schrieb:

warum nicht zuverlässig?

Der Standard garantiert m.W. nicht, daß alle Zeiger gleich groß sind. Es wird nur garantiert, daß void* alle anderen aufnehmen kann. Dieses Konstrukt:
**(int**)a
macht aber aus einem void-zeiger einen int-zeiger.

Was aber kein Problem ist, wenn das ganze denn tatsächlich auf einen int zeigt, der Void-Pointer also aus einem Int-Pointer entstanden ist.

Allerdings, ich kenne kein System, bei dem die Zeiger unterschiedliche Größen haben können.

Manche C-Implementierungen für die PDP-10. Pointer auf Char wurden hier als Zeiger auf ein 36-Bit-Wort plus einen wortinternen Offset auf den 9-bittigen Char dargestellt. Ist aber heute wohl ähnlich irrelevant wie das x86-far/near-Gedöns.

Nachtrag: wobei es mich nicht wundern würde, wenn Unisys heute noch Mainframes mit in dieser Hinsicht vergleichbaren CPUs verkauft.