Ich habe kürzlich eine Frage zum undefinierten Verhalten des Tuns beantwortet p < q in C wann p und q sind Zeiger auf verschiedene Objekte/Arrays. Das brachte mich zum Nachdenken: C++ hat das gleiche (undefinierte) Verhalten von < bietet in diesem Fall aber auch die Standard-Bibliotheksvorlage an std::less was garantiert dasselbe zurückgibt wie < wenn die Zeiger verglichen werden können, und eine konsistente Reihenfolge zurückgeben, wenn dies nicht möglich ist.
Bietet C etwas mit ähnlicher Funktionalität, mit dem beliebige Zeiger (auf denselben Typ) sicher verglichen werden können? Ich habe versucht, den C11-Standard zu durchsuchen und nichts gefunden, aber meine Erfahrung in C ist um Größenordnungen geringer als in C++, daher hätte ich leicht etwas übersehen können.
Kommentare sind nicht für längere Diskussionen gedacht; diese Konversation wurde in den Chat verschoben.
– Samuel Liew ♦
11. Oktober 2019 um 13:30 Uhr
Verwandte: Wie funktioniert der Zeigervergleich in C? Ist es in Ordnung, Zeiger zu vergleichen, die nicht auf dasselbe Array zeigen? für den Hintergrund an p<q in C UB sein, wenn sie nicht auf dasselbe Objekt zeigen.
– Peter Cordes
21. November 2021 um 20:57 Uhr
Peter Kordes
Bei Implementierungen mit einem flachen Speichermodell (im Grunde alles) wird gecastet uintptr_t wird einfach funktionieren.
(Aber siehe Sollten Zeigervergleiche in 64-Bit x86 vorzeichenbehaftet oder nicht vorzeichenbehaftet sein? für eine Diskussion darüber, ob Sie Zeiger als vorzeichenbehaftet behandeln sollten oder nicht, einschließlich Fragen zum Bilden von Zeigern außerhalb von Objekten, was UB in C ist.)
Es gibt jedoch Systeme mit nicht flachen Speichermodellen, und wenn Sie darüber nachdenken, kann dies die aktuelle Situation erklären, z. B. für C++ mit unterschiedlichen Spezifikationen < vs. std::less.
Ein Teil des Punktes < bei Zeigern auf separate Objekte, die in C UB sind (oder zumindest in einigen C++-Revisionen nicht spezifiziert sind), um seltsame Maschinen zu ermöglichen, einschließlich nicht flacher Speichermodelle.
Ein bekanntes Beispiel ist der reale x86-16-Modus, bei dem Zeiger segment:offset sind und eine lineare 20-Bit-Adresse via bilden (segment << 4) + offset. Dieselbe lineare Adresse kann durch mehrere unterschiedliche seg:off-Kombinationen dargestellt werden.
C++ std::less auf Zeiger auf seltsame ISAs müssen möglicherweise teuer seinz. B. “normalisieren” Sie ein segment:offset auf x86-16, um offset <= 15 zu haben. Es gibt jedoch keine tragbar Weg, dies umzusetzen. Die zur Normalisierung von a erforderliche Manipulation uintptr_t (oder die Objektdarstellung eines Zeigerobjekts) ist implementierungsspezifisch.
Aber auch auf Systemen, auf denen C++ std::less muss teuer sein, < muss nicht sein. Unter der Annahme eines “großen” Speichermodells, bei dem ein Objekt in ein Segment passt, < kann nur den versetzten Teil vergleichen und sich nicht einmal mit dem Segmentteil beschäftigen. (Zeiger innerhalb desselben Objekts haben dasselbe Segment, und ansonsten ist es UB in C. C ++ 17 wurde in lediglich “nicht angegeben” geändert, was möglicherweise immer noch das Überspringen der Normalisierung und das bloße Vergleichen von Offsets ermöglicht.) Dies setzt voraus, dass alle Zeiger auf einen beliebigen Teil verweisen eines Objekts immer gleich verwenden seg Wert, normalisiert sich nie. Dies ist, was Sie von einem ABI für ein “großes” im Gegensatz zu einem “riesigen” Speichermodell erwarten würden. (Siehe Diskussion in den Kommentaren).
(Ein solches Speichermodell könnte beispielsweise eine maximale Objektgröße von 64 KB haben, aber einen viel größeren maximalen Gesamtadressraum, der Platz für viele solche Objekte mit maximaler Größe bietet. ISO C ermöglicht Implementierungen eine Begrenzung der Objektgröße, die niedriger ist als die Maximalwert (ohne Vorzeichen) size_t darstellen kann, SIZE_MAX. Selbst auf Systemen mit flachem Speichermodell begrenzt GNU C beispielsweise die maximale Objektgröße auf PTRDIFF_MAX Daher kann die Größenberechnung den vorzeichenbehafteten Überlauf ignorieren.) Siehe diese Antwort und Diskussion in den Kommentaren.
Wenn Sie Objekte zulassen möchten, die größer als ein Segment sind, benötigen Sie ein “riesiges” Speichermodell, das sich darum kümmern muss, dass der Offset-Teil eines Zeigers dabei überläuft p++ um ein Array zu durchlaufen, oder bei der Indexierung / Zeigerarithmetik. Dies führt überall zu langsamerem Code, würde aber wahrscheinlich das bedeuten p < q würde zufällig für Zeiger auf verschiedene Objekte funktionieren, da eine Implementierung, die auf ein “riesiges” Speichermodell abzielt, normalerweise alle Zeiger die ganze Zeit über normal halten würde. Siehe Was sind nahe, ferne und große Zeiger? – Einige echte C-Compiler für den realen x86-Modus hatten eine Option zum Kompilieren für das “riesige” Modell, bei dem alle Zeiger standardmäßig auf “riesig” eingestellt waren, sofern nicht anders angegeben.
Die x86-Real-Mode-Segmentierung ist nicht das einzig mögliche nicht-flache Speichermodell, ist es lediglich ein nützliches konkretes Beispiel, um zu veranschaulichen, wie es von C/C++-Implementierungen gehandhabt wurde. Im wirklichen Leben erweiterten Implementierungen ISO C um das Konzept von far vs. near Zeiger, sodass Programmierer wählen können, wann sie nur den 16-Bit-Offset-Teil relativ zu einem gemeinsamen Datensegment speichern / weitergeben können.
Aber eine reine ISO C-Implementierung müsste zwischen einem kleinen Speichermodell (alles außer Code in denselben 64 KB mit 16-Bit-Zeigern) oder groß oder riesig mit allen Zeigern mit 32-Bit wählen. Einige Schleifen könnten optimiert werden, indem nur der Offset-Teil erhöht wird, aber Zeigerobjekte könnten nicht optimiert werden, um kleiner zu sein.
Wenn Sie wüssten, was die magische Manipulation für eine bestimmte Implementierung ist, könnten Sie sie in reinem C implementieren. Das Problem ist, dass verschiedene Systeme unterschiedliche Adressierungen verwenden und die Details nicht durch portable Makros parametrisiert werden.
Oder vielleicht auch nicht: Es könnte etwas aus einer speziellen Segmenttabelle oder etwas nachschlagen, zB wie x86 Protected Mode statt Real Mode, wo der Segmentteil der Adresse ein Index ist, kein Wert, der nach links verschoben werden muss. Sie könnten teilweise überlappende Segmente im geschützten Modus einrichten, und die Segmentselektorteile von Adressen würden nicht unbedingt in derselben Reihenfolge wie die entsprechenden Segmentbasisadressen angeordnet werden. Das Abrufen einer linearen Adresse von einem seg:off-Zeiger im geschützten x86-Modus kann einen Systemaufruf beinhalten, wenn die GDT und/oder LDT in Ihrem Prozess nicht lesbaren Seiten zugeordnet sind.
(Natürlich verwenden Mainstream-Betriebssysteme für x86 ein flaches Speichermodell, sodass die Segmentbasis immer 0 ist (außer für Thread-lokalen Speicher mit fs oder gs Segmente), und nur der 32-Bit- oder 64-Bit-„Offset“-Teil wird als Zeiger verwendet.)
Sie könnten manuell Code für verschiedene spezifische Plattformen hinzufügen, z. B. standardmäßig flach annehmen oder #ifdef etwas, um den x86-Realmodus zu erkennen und aufzuteilen uintptr_t in 16-Bit-Hälften für seg -= off>>4; off &= 0xf; Kombinieren Sie diese Teile dann wieder zu einer 32-Bit-Zahl.
Warum sollte es UB sein, wenn das Segment nicht gleich ist?
– Eichel
11. Oktober 2019 um 13:18 Uhr
@Acorn: Soll das andersherum sagen; Fest. Zeiger auf dasselbe Objekt haben dasselbe Segment, sonst UB.
– Peter Cordes
11. Oktober 2019 um 14:05 Uhr
Aber warum glaubst du, dass es überhaupt UB ist? (umgekehrte Logik oder nicht, eigentlich ist es mir auch nicht aufgefallen)
– Eichel
11. Oktober 2019 um 17:53 Uhr
p < q ist UB in C, wenn sie auf verschiedene Objekte zeigen, oder? Ich weiss p - q ist.
– Peter Cordes
11. Oktober 2019 um 17:55 Uhr
@Acorn: Wie auch immer, ich sehe keinen Mechanismus, der in einem Programm ohne UB Aliase (unterschiedliche seg:off, gleiche lineare Adresse) generieren würde. Es ist also nicht so, dass der Compiler große Anstrengungen unternehmen muss, um dies zu vermeiden; Jeder Zugriff auf ein Objekt verwendet dieses Objekt seg -Wert und einen Offset, der >= der Offset innerhalb des Segments ist, in dem dieses Objekt beginnt. C macht es UB, viel von allem zwischen Zeigern auf verschiedene Objekte zu tun, einschließlich solcher Dinge tmp = a-b und dann b[tmp] zugreifen a[0]. Diese Diskussion über segmentiertes Zeiger-Aliasing ist ein gutes Beispiel dafür, warum diese Design-Wahl sinnvoll ist.
– Peter Cordes
11. Oktober 2019 um 20:04 Uhr
SS Anne
Ich habe einmal versucht, dies zu umgehen, und ich habe eine Lösung gefunden, die für überlappende Objekte funktioniert und in den meisten anderen Fällen davon ausgeht, dass der Compiler das “übliche” macht.
Sie können zunächst den Vorschlag in How to implement memmove in standard C without an intermediate copy implementieren? und dann, wenn das nicht funktioniert, cast to uintptr (ein Wrapper-Typ für beides uintptr_t oder unsigned long long je nachdem ob uintptr_t verfügbar ist) und ein höchstwahrscheinlich genaues Ergebnis erhalten (obwohl es wahrscheinlich sowieso keine Rolle spielen würde):
#include <stdint.h>
#ifndef UINTPTR_MAX
typedef unsigned long long uintptr;
#else
typedef uintptr_t uintptr;
#endif
int pcmp(const void *p1, const void *p2, size_t len)
{
const unsigned char *s1 = p1;
const unsigned char *s2 = p2;
size_t l;
/* Check for overlap */
for( l = 0; l < len; l++ )
{
if( s1 + l == s2 || s1 + l == s2 + len - 1 )
{
/* The two objects overlap, so we're allowed to
use comparison operators. */
if(s1 > s2)
return 1;
else if (s1 < s2)
return -1;
else
return 0;
}
}
/* No overlap so the result probably won't really matter.
Cast the result to `uintptr` and hope the compiler
does the "usual" thing */
if((uintptr)s1 > (uintptr)s2)
return 1;
else if ((uintptr)s1 < (uintptr)s2)
return -1;
else
return 0;
}
Chux – Wiedereinsetzung von Monica
Bietet C etwas mit ähnlicher Funktionalität, das es ermöglichen würde, beliebige Zeiger sicher zu vergleichen?
Nein
Betrachten wir zunächst nur Objektzeiger. Funktionszeiger eine ganze Reihe anderer Bedenken einbringen.
2 Zeiger p1, p2 können unterschiedliche Kodierungen haben und so auf die gleiche Adresse zeigen p1 == p2 wenngleich memcmp(&p1, &p2, sizeof p1) nicht 0 ist. Solche Architekturen sind selten.
Dennoch Konvertierung dieser Zeiger auf uintptr_t erfordert nicht das gleiche ganzzahlige Ergebnis, das zu führt (uintptr_t)p1 != (uinptr_t)p2.
(uintptr_t)p1 < (uinptr_t)p2 selbst ist wohl legaler Code, der unter Umständen nicht die erhoffte Funktionalität bietet.
Wenn der Code wirklich nicht verwandte Zeiger vergleichen muss, bilden Sie eine Hilfsfunktion less(const void *p1, const void *p2) und dort plattformspezifischen Code ausführen.
Vielleicht:
// return -1,0,1 for <,==,>
int ptrcmp(const void *c1, const void *c1) {
// Equivalence test works on all platforms
if (c1 == c2) {
return 0;
}
// At this point, we know pointers are not equivalent.
#ifdef UINTPTR_MAX
uintptr_t u1 = (uintptr_t)c1;
uintptr_t u2 = (uintptr_t)c2;
// Below code "works" in that the computation is legal,
// but does it function as desired?
// Likely, but strange systems lurk out in the wild.
// Check implementation before using
#if tbd
return (u1 > u2) - (u1 < u2);
#else
#error TBD code
#endif
#else
#error TBD code
#endif
}
Der C-Standard erlaubt Implementierungen ausdrücklich, sich „in einer dokumentierten Weise zu verhalten, die für die Umgebung charakteristisch ist“, wenn eine Aktion „undefiniertes Verhalten“ aufruft. Als der Standard geschrieben wurde, wäre es für jeden offensichtlich gewesen, dass Implementierungen, die für die Low-Level-Programmierung auf Plattformen mit einem flachen Speichermodell vorgesehen sind, genau dies tun sollten, wenn sie relationale Operatoren zwischen beliebigen Zeigern verarbeiten. Es wäre auch offensichtlich gewesen, dass Implementierungen, die auf Plattformen abzielen, deren natürliche Mittel zum Vergleichen von Zeigern niemals Nebenwirkungen haben würden, Vergleiche zwischen beliebigen Zeigern auf eine Weise durchführen sollten, die keine Nebenwirkungen hat.
Es gibt drei allgemeine Umstände, unter denen Programmierer relationale Operatoren zwischen Zeigern ausführen können:
Zeiger auf nicht verwandte Objekte werden niemals verglichen.
Code kann Zeiger innerhalb eines Objekts vergleichen, wenn die Ergebnisse wichtig wären, oder zwischen nicht verwandten Objekten in Fällen, in denen die Ergebnisse keine Rolle spielen würden. Ein einfaches Beispiel hierfür wäre eine Operation, die auf möglicherweise überlappende Feldsegmente in entweder aufsteigender oder absteigender Reihenfolge einwirken kann. Die Wahl der aufsteigenden oder absteigenden Reihenfolge wäre in Fällen wichtig, in denen sich die Objekte überlappen, aber jede Reihenfolge wäre gleichermaßen gültig, wenn auf Array-Segmente in nicht verwandten Objekten eingewirkt wird.
Code stützt sich auf Vergleiche, die eine transitive Ordnung ergeben, die mit der Zeigergleichheit konsistent ist.
Die dritte Art der Verwendung würde selten außerhalb von plattformspezifischem Code auftreten, der entweder wüsste, dass Vergleichsoperatoren einfach funktionieren würden, oder eine plattformspezifische Alternative kennen würde. Die zweite Verwendungsart könnte in Code auftreten, der hauptsächlich portierbar sein sollte, aber fast alle Implementierungen könnten die zweite Verwendungsart genauso billig unterstützen wie die erste, und es gäbe keinen Grund, etwas anderes zu tun. Die einzigen Leute, die sich darum kümmern sollten, ob die zweite Verwendung definiert wurde, wären Leute, die Compiler für Plattformen schreiben, auf denen solche Vergleiche teuer wären, oder diejenigen, die sicherstellen möchten, dass ihre Programme mit solchen Plattformen kompatibel sind. Solche Personen wären besser als der Ausschuss in der Lage, die Vor- und Nachteile der Aufrechterhaltung einer „Nebenwirkungsfreiheit“-Garantie zu beurteilen, und daher lässt der Ausschuss diese Frage offen.
Die Tatsache, dass es für einen Compiler keinen Grund gäbe, ein Konstrukt nicht sinnvoll zu verarbeiten, ist freilich keine Garantie dafür, dass ein „Gratuitously Clever Compiler“ den Standard nicht als Entschuldigung dafür nimmt, etwas anderes zu tun, sondern der Grund dafür ist der C-Standard einen “weniger”-Operator nicht definiert, ist, dass das Komitee erwartet hat, dass “<" für fast alle Programme auf fast allen Plattformen angemessen wäre.
13645300cookie-checkHat C ein Äquivalent zu std::less von C++?yes
Kommentare sind nicht für längere Diskussionen gedacht; diese Konversation wurde in den Chat verschoben.
– Samuel Liew
♦
11. Oktober 2019 um 13:30 Uhr
Verwandte: Wie funktioniert der Zeigervergleich in C? Ist es in Ordnung, Zeiger zu vergleichen, die nicht auf dasselbe Array zeigen? für den Hintergrund an
p<q
in C UB sein, wenn sie nicht auf dasselbe Objekt zeigen.– Peter Cordes
21. November 2021 um 20:57 Uhr