c - true - std::map example




Hat C ein Äquivalent von std:: less aus C++? (2)

Bietet C eine ähnliche Funktionalität, mit der beliebige Zeiger sicher verglichen werden können?

Nein

Betrachten wir zunächst nur Objektzeiger . Funktionszeiger bringen eine ganze Reihe anderer Bedenken mit sich.

2 Zeiger p1, p2 können unterschiedliche Codierungen haben und auf dieselbe Adresse zeigen, so dass p1 == p2 , obwohl memcmp(&p1, &p2, sizeof p1) nicht 0 ist. Solche Architekturen sind selten.

Die Konvertierung dieser Zeiger nach uintptr_t erfordert jedoch nicht dasselbe ganzzahlige Ergebnis, das zu (uintptr_t)p1 != (uinptr_t)p2 .

(uintptr_t)p1 < (uinptr_t)p2 selbst ist ein rechtlicher Code, der möglicherweise nicht die erhoffte Funktionalität bietet.

Wenn Code wirklich nicht verwandte Zeiger vergleichen muss, bilden Sie eine Hilfsfunktion less(const void *p1, const void *p2) und führen Sie dort plattformspezifischen Code aus.

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 
}

Kürzlich beantwortete ich eine Frage zum undefinierten Verhalten von p < q in C, wenn p und q Zeiger auf verschiedene Objekte / Arrays sind. Das brachte mich zum Nachdenken: C ++ hat in diesem Fall das gleiche (undefinierte) Verhalten von < , bietet aber auch die Standard-Bibliotheksvorlage std::less die garantiert das Gleiche zurückgibt wie < wenn die Zeiger verglichen werden können, und einige zurückgibt konsistente Reihenfolge, wenn sie nicht können.

Bietet C eine ähnliche Funktionalität, mit der beliebige Zeiger (mit demselben Typ) sicher verglichen werden können? Ich habe versucht, den C11-Standard durchzublättern und nichts gefunden, aber meine Erfahrung in C ist um Größenordnungen kleiner als in C ++, sodass ich leicht etwas übersehen hätte können.


Bei Implementierungen mit einem flachen Speichermodus (im Grunde genommen alles) uintptr_t das uintptr_t in uintptr_t .

Es gibt jedoch Systeme mit nichtflachen Speichermodellen, und wenn Sie darüber nachdenken, kann dies die aktuelle Situation erklären, z. B. wenn C ++ andere Spezifikationen für < vs. std::less .

Ein Teil des Punktes < on Zeiger auf separate Objekte, die UB in C sind (oder zumindest in einigen C ++ - Versionen nicht spezifiziert sind), besteht darin, seltsame Maschinen, einschließlich nicht flacher Speichermodelle, zuzulassen.

Ein bekanntes Beispiel ist der Real-Modus x86-16, in dem Zeiger segment: offset sind und eine lineare 20-Bit-Adresse über (segment << 4) + offset . Dieselbe lineare Adresse kann durch mehrere verschiedene Seg: Off-Kombinationen dargestellt werden.

C ++ std::less auf Zeigern auf seltsamen ISAs müssen möglicherweise teuer sein , z. B. "normalisieren" Sie ein Segment: Offset auf x86-16, um Offset <= 15 zu haben. Es gibt jedoch keine portable Möglichkeit, dies zu implementieren. Die zum Normalisieren eines uintptr_t (oder der Objektdarstellung eines uintptr_t erforderliche Manipulation ist implementierungsspezifisch.

Aber auch auf Systemen, auf denen C ++ std::less teuer sein muss, muss es nicht sein. Angenommen, ein "großes" Speichermodell, bei dem ein Objekt in ein Segment passt, kann < nur den Versatzteil vergleichen und sich nicht einmal mit dem Segmentteil beschäftigen. (Zeiger innerhalb desselben Objekts haben dasselbe Segment, andernfalls ist es in C UB. C ++ 17 wurde in "unspecified" geändert, was möglicherweise weiterhin das Überspringen von Normalisierung und nur das Vergleichen von Offsets ermöglicht.) Dies setzt voraus, dass alle Zeiger auf einen beliebigen Teil verweisen eines Objekts immer den gleichen seg Wert verwenden, niemals normalisieren. Dies ist, was ein ABI für ein "großes" im Gegensatz zu einem "großen" Speichermodell erfordern würde. (Siehe Diskussion in Kommentaren ).

(Ein solches Speichermodell hat möglicherweise eine maximale Objektgröße von beispielsweise 64 KB, aber einen viel größeren maximalen Adressraum, der Platz für viele Objekte mit maximaler Größe bietet. ISO C ermöglicht Implementierungen, die Objektgröße auf einen Wert zu begrenzen, der unter dem Grenzwert liegt Der Maximalwert (ohne Vorzeichen) size_t kann SIZE_MAX . GNU C begrenzt beispielsweise die maximale Objektgröße auf PTRDIFF_MAX sodass die Größenberechnung den vorzeichenbehafteten Überlauf ignorieren kann.) Siehe diese Antwort und Diskussion in Kommentaren.

Wenn Sie Objekte zulassen möchten, die größer als ein Segment sind, benötigen Sie ein "großes" Speichermodell, das sich Gedanken über das Überlaufen des Versatzteils eines Zeigers machen muss, wenn Sie mit p++ eine Schleife durch ein Array ausführen oder wenn Sie eine Indizierungs- / Zeigerarithmetik ausführen. Dies führt überall zu langsamerem Code, würde aber wahrscheinlich bedeuten, dass p < q für Zeiger auf verschiedene Objekte funktioniert, da eine Implementierung, die auf ein "großes" Speichermodell abzielt, normalerweise alle Zeiger ständig normalisiert. Siehe Was sind nahe, ferne und riesige Zeiger? - Einige echte C-Compiler für den x86-Real-Modus hatten die Option, für das "riesige" Modell zu kompilieren, bei dem alle Zeiger standardmäßig "riesig" waren, sofern nicht anders angegeben.

Die x86-Real-Mode-Segmentierung ist nicht das einzige mögliche nicht-flache Speichermodell , sondern lediglich ein nützliches konkretes Beispiel, um zu veranschaulichen, wie es von C / C ++ - Implementierungen gehandhabt wurde. In der Praxis wurde ISO C durch Implementierungen um das Konzept der Fern- / Nahzeiger erweitert, sodass Programmierer wählen können, wann sie den 16-Bit-Offset-Teil im Verhältnis zu einem bestimmten gemeinsamen Datensegment nur speichern / durchlaufen können.

Bei einer reinen ISO-C-Implementierung müsste man sich zwischen einem kleinen Speichermodell (alles außer Code in demselben 64-kB-Format mit 16-Bit-Zeigern) oder einem großen oder großen Format mit 32-Bit-Zeigern entscheiden. Einige Schleifen könnten durch Inkrementieren nur des versetzten Teils optimiert werden, Zeigerobjekte könnten jedoch nicht so optimiert werden, dass sie kleiner sind.

Wenn Sie wissen, was die magische Manipulation für eine Implementierung ist, können Sie sie in reinem C implementieren . Das Problem ist, dass unterschiedliche Systeme unterschiedliche Adressierungen verwenden und die Details nicht durch tragbare Makros parametrisiert werden.

Oder vielleicht auch nicht: Möglicherweise müssen Sie etwas aus einer speziellen Segmenttabelle nachschlagen oder so etwas, z. B. x86-geschützter Modus anstelle von Real-Modus, bei dem der Segmentteil der Adresse ein Index ist und kein Wert, der verschoben werden soll. Sie könnten teilweise überlappende Segmente im geschützten Modus einrichten, und die Segmentauswahlteile von Adressen müssten nicht unbedingt in derselben Reihenfolge wie die entsprechenden Segmentbasisadressen angeordnet sein. Das Abrufen einer linearen Adresse von einem seg: off-Zeiger im geschützten x86-Modus kann einen Systemaufruf beinhalten, wenn der GDT und / oder der LDT nicht in lesbaren Seiten in Ihrem Prozess zugeordnet sind.

(Natürlich verwenden Mainstream-Betriebssysteme für x86 ein flaches Speichermodell, sodass die Segmentbasis immer 0 ist (mit Ausnahme des thread-lokalen Speichers mit fs oder gs Segmenten), und nur der 32-Bit- oder 64-Bit- "Offset" -Teil wird als verwendet ein Zeiger.)

Sie können Code für verschiedene Plattformen manuell hinzufügen, z. B. standardmäßig flat oder #ifdef , um den x86-Real-Modus zu erkennen, und uintptr_t für seg -= off>>4; off &= 0xf; in 16-Bit-Hälften uintptr_t seg -= off>>4; off &= 0xf; seg -= off>>4; off &= 0xf; Kombinieren Sie diese Teile dann wieder zu einer 32-Bit-Zahl.







memory-segmentation