Was bedeutet dieser Code in C qsort?

Question

void qsort (void *a, size_t n, size_t es, int (*compare)(const void *, const void *) 

Dabei steht a für einen Start der Array-Adresse, n für die Größe des Arrays, es für die Größe des Array-Elements.

Ich habe den Quellcode von qsort in C gelesen, den ich nicht verstehen kann. Der Code ist wie folgt.

#define SWAPINT(a,es) swaptype = ((char*)a- (char*)0 % sizeof(long) || \ 
     es % sizeof(long) ? 2: es == sizeof(long)? 0 : 1 

Ich interpretiere dieses Makro durch,

if(((char*)a- (char*)0)% sizeof(long))==1 || es % sizeof(long)==1) 
    swaptype = 2; 
else if(es== sizeof(long)) 
    swaptype = 0; 
else 
    swaptype = 1; 

Aber ich verstehe nicht, warum Typumwandlung implementiert ist, (char *) ein.

Und was bedeutet diese Linie?

(char*)a- (char*)0)% sizeof(long)==1 

Answer 1

Wo immer Sie diesen Code gefunden haben, haben Sie ihn wahrscheinlich falsch kopiert. Ich fand einige sehr ähnlichen Code in libutil from Canu:

c.swaptype = ((char *)a - (char *)0) % sizeof(long) || \ 
    es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1; 

Dieser Code wahrscheinlich illegitimally war (weil die Bedingungen der Copyright-Lizenz verletzt werden) von FreeBSD libc kopiert:

//__FBSDID("$FreeBSD: src/lib/libc/stdlib/qsort.c,v 1.12 2002/09/10 02:04:49 wollman Exp $"); 

So du, ich bin zu raten, habe es von einer * BSD libc-Implementierung bekommen. Indeedd FreeBSD quicksort Implementierung enthält the SWAPINIT macro (nicht SWAPINT):

#define SWAPINIT(TYPE, a, es) swaptype_ ## TYPE =  \ 
     ((char *)a - (char *)0) % sizeof(TYPE) ||  \ 
     es % sizeof(TYPE) ? 2 : es == sizeof(TYPE) ? 0 : 1; 

---

Nach Parsen, sollten Sie feststellen, dass der obige Code ist in etwa die gleiche wie

condition_one = ((char *)a - (char *)0) % sizeof(long); 
condition_two = es % sizeof(long); 
condition_three = es == sizeof(long); 
c.swaptype = (condition_one || condition_two) ? 2 : condition_three ? 0 : 1; 

Beachten Sie, dass condition_two als Bedingung ist nicht das gleiche wie es % sizeof(long) == 1, sondern es % sizeof(long) != 0. Abgesehen davon war deine Übersetzung korrekt.

---

Die Absicht dieser Bedingungen scheint wie folgt zu sein:

• condition_one ist true wenn a nicht long -ausgerichtete ist.
• condition_two ist true wenn es kein Vielfaches von long ist.
• condition_three ist true wenn es genau long ist.

Als Ergebnis

• swaptype == 2 ist, wenn Sie tauschen klug nicht genügend Garantien über die Elemente sein müssen,
• swaptype == 1 für Arrays mit Elementen vorgesehen, die entlang long ausgerichtet sind, Grenzen (Anmerkung: aber nicht notwendigerweise ausgerichtet als longs!) und
• swaptype == 0 ist für Arrays vorgesehen, die der vorherigen Beschreibung entsprechen, die auch Elemente haben, die ebenfalls long -sized sind.

Es gibt eine explizite Typumwandlung in diesem Fall, da avoid* hat geben, for which type arithmetic is undefined. Beachten Sie jedoch, daß auch ((char *)a - (char *)0) undefiniert zu:

Wenn zwei Zeiger subtrahiert werden, die beide zu den Elementen des gleichen Array Objekt zeigen soll, oder eine hinter dem letzten Element des Arrays Objekts; Das Ergebnis ist die Differenz der Indizes der beiden Array-Elemente.

(C11 Entwurf N1570, Abschnitt 6.5.6, Abschnitt 9 auf den Seiten 93 und 94)

ist es nicht gerade in C11 Dinkel, aber der Nullzeiger ist nicht Teil der gleichen Anordnung wie die Objekt wies auf a, so dass die Grundregeln für Zeigerarithmetik verletzt werden, so ist das Verhalten undefiniert.

Answer 2

Die Makros versuchen, die Ausrichtung in einer Sprache C portabel zu prüfen, was einen solchen Test nicht wirklich zulässt. Also subtrahieren wir den Null-Zeiger von unserem Zeiger, um eine ganze Zahl zu erhalten, und nehmen dann das Modulus der Länge. Wenn das Ergebnis Null ist, sind die Daten lang ausgerichtet und wir können so lange zugreifen. Wenn nicht, können wir ein anderes Schema ausprobieren.

Answer 3

Wie bemerkt in den Kommentaren, die Makrodefinition Sie präsentieren sich nicht ausdehnt, um gültige C-Code, weil es Computing beinhaltet (char*)0 % sizeof(long), wo der linke Operand des % Typ char * hat. Das ist kein Integer-Typ, aber beide Operanden von % müssen einen Integer-Typ haben.

Außerdem hat die Makroerweiterung unsymmetrische Klammern. Das ist nicht inhärent falsch, aber es macht das Makro schwierig zu bedienen. Selbst wenn die Vorrangstellung des Operators ein vernünftiges Ergebnis ergibt, kann die Verwendung von Klammern und zusätzlichen Leerzeichen die menschliche Interpretation des Codes unterstützen, ohne die Ausführungsgeschwindigkeit zu beeinträchtigen und die zusätzlichen Kompilierungskosten vernachlässigen.

Also, ich glaube, das gewünschte Makro eher wie dieses wäre:

#define SWAPINT(a,es) swaptype = (         \ 
    ((((char*)a - (char*)0) % sizeof(long)) || (es % sizeof(long))) \ 
     ? 2               \ 
     : ((es == sizeof(long)) ? 0 : 1))       \ 
) 

ich stattdessen betrachten würde die vorletzte Zeile als

 : (es != sizeof(long)) 

Schreiben der Komplexität des Ausdrucks auf eine reduzieren leichte Kosten für seine Verständlichkeit.In jedem Fall scheint die Absicht swaptype zu setzen zu sein: auf einer n -Byte Grenze

• 2 wenn a ist nicht ausgerichtet sind, wobei n die Anzahl der Bytes in einem long ist oder wenn es ist kein ganzzahliges Vielfaches der Größe eines long; ansonsten
• 1 wenn es ungleich der Größe eines long ist; sonst
• 0

Das ist ähnlich, aber nicht identisch sind, auf Ihre Interpretation. Beachten Sie jedoch, dass auch dieser Code aufgrund von (char*)a - (char*)0 ein undefiniertes Verhalten aufweist. Die Auswertung dieses Unterschieds hat das Verhalten nur dann definiert, wenn beide Zeiger auf dasselbe Objekt oder kurz nach dem Ende desselben Objekts zeigen, und (char *)0 nicht auf das Ende eines Objekts zeigt.

Sie ausdrücklich gefragt:

Aber ich verstehe nicht, warum Typumwandlung implementiert ist, (char *) ein.

, die durchgeführt wird, weil die Zeigerarithmetik in Bezug auf dem spitzen-geben, so definiert ist, (1) kann ein konformes Programm nicht Arithmetik durchführt mit einem void *, und (2) möge der Code das Ergebnis der Subtraktion in den gleichen Einheiten wie das Ergebnis des Operators sizeof (Bytes) sein.

Und was bedeutet diese Linie?

(char*)a- (char*)0)% sizeof(long)==1 

Diese Zeile erscheint nicht in dem Makro Sie präsentiert, und es ist kein vollständiger Ausdruck wegen der unausgeglichenen Klammern. Es scheint zu versuchen, zu bestimmen, ob a Punkte hinter einer n-Byte-Grenze zeigt, wobei n wie oben definiert ist, aber wiederum hat die Auswertung der Zeigerdifferenz ein undefiniertes Verhalten. Beachten Sie auch, dass für eine ganze Zahl x, x % sizeof(long) == 1 im booleschen Kontext ausgewertet hat eine andere Bedeutung als x % sizeof(long) im gleichen Kontext ausgewertet. Letzteres macht in dem von Ihnen beschriebenen Kontext mehr Sinn.