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

26

Ich habe kürzlich eine Frage zum undefinierten Verhalten p < qin C beantwortet, wenn pund qZeiger auf verschiedene Objekte / Arrays sind. Das brachte mich zum Nachdenken: C ++ hat <in diesem Fall das gleiche (undefinierte) Verhalten , bietet aber auch die Standardbibliotheksvorlage, std::lessdie garantiert dasselbe zurückgibt, wie <wenn die Zeiger verglichen werden können, und eine konsistente Reihenfolge zurückgibt, wenn sie nicht können.

Bietet C etwas mit ähnlicher Funktionalität, mit dem beliebige Zeiger (mit demselben Typ) sicher verglichen werden können? Ich habe versucht, den C11-Standard durchzusehen, 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.

Angew ist nicht mehr stolz auf SO
quelle
1
Kommentare sind nicht für eine ausführliche Diskussion gedacht. Dieses Gespräch wurde in den Chat verschoben .
Samuel Liew

Antworten:

20

Bei Implementierungen mit einem Flat-Memory-Modell (im Grunde alles) funktioniert das Casting uintptr_tnur.

( Weitere Informationen dazu, ob Sie Zeiger als signiert behandeln sollten oder nicht, finden Sie unter Sollten Zeigervergleiche in 64-Bit-x86 signiert oder nicht signiert sein.

Aber Systeme mit nicht flachen Speichermodelle existieren, und über sie denken kann die aktuelle Situation helfen zu erklären, wie C ++ mit unterschiedlichen Spezifikationen für <vs. std::less.


Ein Teil des Punktes von Ein- <Zeigern auf separate Objekte, die UB in C sind (oder zumindest in einigen C ++ - Revisionen nicht angegeben sind), besteht darin, seltsame Maschinen zu berücksichtigen, einschließlich nicht flacher Speichermodelle.

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

C ++ std::lessfür Zeiger auf seltsamen ISAs muss möglicherweise teuer sein , z. B. ein Segment "normalisieren": Offset auf x86-16, um Offset <= 15 zu haben. Es gibt jedoch keine tragbare Möglichkeit, dies zu implementieren. Die zur Normalisierung eines uintptr_t(oder der Objektdarstellung eines Zeigerobjekts) erforderliche Manipulation ist implementierungsspezifisch.

Aber auch auf Systemen, auf denen C ++ std::lessteuer sein muss, <muss es nicht sein. Wenn Sie beispielsweise ein "großes" Speichermodell annehmen, bei dem ein Objekt in ein Segment passt, <können Sie 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 lediglich in "nicht angegeben" geändert, wodurch möglicherweise noch die Normalisierung übersprungen und nur Offsets verglichen werden können.) Dies setzt alle Zeiger auf einen beliebigen Teil voraus eines Objekts verwenden immer den gleichen segWert, niemals normalisierend. Dies ist, was Sie von einem ABI für ein "großes" im Gegensatz zu einem "großen" Speichermodell erwarten würden. (Siehe Diskussion in Kommentaren ).

(Ein solches Speichermodell kann beispielsweise eine maximale Objektgröße von 64 KB haben, aber einen viel größeren maximalen Gesamtadressraum, der Platz für viele solcher Objekte mit maximaler Größe bietet. ISO C ermöglicht Implementierungen eine Begrenzung der Objektgröße, die niedriger als die ist Maximaler Wert (ohne Vorzeichen) size_tkann darstellen SIZE_MAX. Beispielsweise begrenzt GNU C selbst auf Flachspeichermodellsystemen die maximale Objektgröße auf, PTRDIFF_MAXsodass 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 "riesiges" Speichermodell, das sich Sorgen machen muss, dass der versetzte Teil eines Zeigers beim p++Durchlaufen eines Arrays oder bei der Indizierung / Zeigerarithmetik überläuft. Dies führt überall zu langsamerem Code, würde aber wahrscheinlich bedeuten, dass p < qdies für Zeiger auf verschiedene Objekte funktioniert, da eine Implementierung, die auf ein "riesiges" Speichermodell abzielt, normalerweise dafür sorgt, dass alle Zeiger die ganze Zeit normalisiert bleiben. Siehe Was sind nahe, ferne und große 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 wird. Im wirklichen Leben erweiterten Implementierungen ISO C um das Konzept von farvs. nearZeigern, sodass Programmierer wählen können, wann sie davonkommen können, indem sie nur den 16-Bit-Offset-Teil relativ zu einem gängigen Datensegment speichern / weitergeben.

Eine reine ISO C-Implementierung müsste jedoch zwischen einem kleinen Speichermodell (alles außer Code in denselben 64 KB mit 16-Bit-Zeigern) oder groß oder groß wählen, wobei alle Zeiger 32-Bit sind. Einige Schleifen könnten durch Inkrementieren nur des Versatzteils optimiert werden, aber Zeigerobjekte könnten nicht so optimiert werden, dass sie kleiner sind.


Wenn Sie wüssten, was die magische Manipulation für eine bestimmte Implementierung ist, können Sie sie in reinem C implementieren . Das Problem ist, dass verschiedene Systeme unterschiedliche Adressierungen verwenden und die Details von keinem tragbaren Makro parametrisiert werden.

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

(Natürlich verwenden Mainstream-Betriebssysteme für x86 ein Flat-Memory-Modell, sodass die Segmentbasis immer 0 ist (mit Ausnahme von Thread-lokalem Speicher mit fsoder gsSegmenten) und nur der 32-Bit- oder 64-Bit-Teil "Offset" als Zeiger verwendet wird .)

Sie können manuell Code für verschiedene spezifische Plattformen hinzufügen, z. B. standardmäßig flach annehmen oder #ifdefetwas, um den x86-Realmodus zu erkennen und uintptr_tin 16-Bit-Hälften aufzuteilen, seg -= off>>4; off &= 0xf;um diese Teile dann wieder zu einer 32-Bit-Zahl zu kombinieren.

Peter Cordes
quelle
Warum sollte es UB sein, wenn das Segment nicht gleich ist?
Eichel
@Acorn: Soll das anders herum sagen; Fest. Zeiger auf dasselbe Objekt haben dasselbe Segment, ansonsten UB.
Peter Cordes
Aber warum denkst du, ist es auf jeden Fall UB? (umgekehrte Logik oder nicht, eigentlich habe ich es auch nicht bemerkt)
Acorn
p < qist UB in C, wenn sie auf verschiedene Objekte zeigen, nicht wahr? Ich weiß p - qist.
Peter Cordes
1
@Acorn: Wie auch immer, ich sehe keinen Mechanismus, der in einem Programm ohne UB Aliase (unterschiedliche Segmente: Aus, gleiche lineare Adresse) erzeugen würde. Es ist also nicht so, dass der Compiler alles daran setzen muss, um dies zu vermeiden. Jeder Zugriff auf ein Objekt verwendet den segWert dieses Objekts und einen Versatz, der> = der Versatz innerhalb des Segments ist, in dem das Objekt beginnt. C macht es UB, viel zwischen Zeigern auf verschiedene Objekte zu tun, einschließlich Sachen wie tmp = a-bund dann b[tmp]darauf zuzugreifen a[0]. Diese Diskussion über segmentiertes Zeiger-Aliasing ist ein gutes Beispiel dafür, warum diese Entwurfsauswahl sinnvoll ist.
Peter Cordes
17

Ich habe einmal versucht, einen Weg zu finden, 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" tut.

Sie können den Vorschlag zunächst unter Wie implementiere ich memmove in Standard C ohne Zwischenkopie? und dann, wenn das nicht funktioniert, in uintptr(ein Wrapper-Typ für entweder uintptr_toder unsigned long longabhängig davon, ob uintptr_tverfügbar) umwandeln und ein höchstwahrscheinlich genaues Ergebnis erhalten (obwohl es wahrscheinlich sowieso keine Rolle spielt):

#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;
}
SS Anne
quelle
5

Bietet C etwas mit ähnlicher Funktionalität, mit dem 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, p2können unterschiedliche Codierungen haben und auf dieselbe Adresse verweisen, p1 == p2obwohl dies memcmp(&p1, &p2, sizeof p1)nicht 0 ist. Solche Architekturen sind selten.

Die Konvertierung dieses Zeigers in uintptr_terfordert jedoch nicht dasselbe ganzzahlige Ergebnis, das zu führt (uintptr_t)p1 != (uinptr_t)p2.

(uintptr_t)p1 < (uinptr_t)p2 selbst ist wohl 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 
}
chux - Monica wieder einsetzen
quelle