Ist dies eine korrekte und tragbare Methode, um zu überprüfen, ob sich 2 C-Strings im Speicher überschneiden?

Vielleicht nicht der effizienteste Weg, aber ist er richtig und portabel?

int are_overlapping(const char *a, const char *b) {
  return (a + strlen(a) == b + strlen(b));
}

Zur Verdeutlichung: Was ich suche, ist Überschneidung Erinnerung, nicht im eigentlichen Inhalt. Zum Beispiel:

const char a[] = "string";
const char b[] = "another string";
are_overlapping(a, b); // should return 0
are_overlapping(a, a + 3); // should return 1

Ja, dein Code ist richtig. Wenn zwei Zeichenfolgen an der Abtaststelle enden, überlappen sie sich definitionsgemäß – sie teilen sich denselben Null-Terminator. Entweder sind beide Strings identisch, oder einer ist ein Teilstring des anderen.

Alles an Ihrem Programm ist perfekt definiertes Verhalten, also sollte es, vorausgesetzt, dass es sich um standardkonforme Compiler handelt, perfekt portierbar sein.

Das relevante Bit im Standard ist von 6.5.9 Gleichheitsoperatoren (Hervorhebung von mir):

Zwei Zeiger sind genau dann gleich, wenn beide sind Nullzeiger, beide sind Zeiger auf dasselbe Objekt (einschließlich eines Zeigers auf ein Objekt und ein Unterobjekt am Anfang) oder Funktion, beide sind Zeiger auf eins nach dem letzten Element desselben Array-Objektsoder einer ist ein Zeiger auf einen hinter dem Ende eines Array-Objekts und der andere ist ein Zeiger auf den Anfang eines anderen Array-Objekts, das zufällig unmittelbar auf das erste Array-Objekt im Adressraum folgt.

Wenn ich an zdans Kommentare zu meinem vorherigen Post denke (der wahrscheinlich in Kürze gelöscht wird), bin ich zu dem Schluss gekommen, dass das Überprüfen von Endpunkten ausreicht.

Wenn es Überschneidungen gibt, sorgt der Null-Terminator dafür, dass die beiden Strings nicht verschieden sind. Sehen wir uns einige Möglichkeiten an.

Wenn Sie mit beginnen

a 0x10000000 "Hello" and somehow add
b 0x10000004 "World",

Sie haben ein einziges Wort: HellWorld, da das W das \0 überschreiben würde. Sie würden am selben Endpunkt enden.

Wenn Sie irgendwie zum gleichen Ausgangspunkt schreiben:

a 0x10000000 "Hello" and
b 0x10000000 "Jupiter"

Sie haben das Wort Jupiter und denselben Endpunkt.

Gibt es einen Fall, in dem Sie denselben Endpunkt haben können, ohne dass es zu Überschneidungen kommt? So’ne Art.

a = 0x1000000 "Four" and
b = 0x1000004 "".

Das wird auch eine Überlappung geben.

Ich kann mir keine Zeit vorstellen, in der Sie Überschneidungen haben, bei denen Sie keine übereinstimmenden Endpunkte haben – Angenommen, Sie schreiben nullterminierte Zeichenfolgen in den Speicher.

Daher die kurze Antwort: Ja, Ihr Scheck ist ausreichend.

Es ist wahrscheinlich nicht relevant für Ihren Anwendungsfall, da sich Ihre Frage speziell auf C-Strings bezieht, aber der Code funktioniert nicht, wenn die Daten NUL-Bytes in die Strings eingebettet haben.

char a[] = "abcd\0ABCD";
char *b = a + 5;

Abgesehen davon ist Ihre Lösung einfach und richtig. Es funktioniert, da Sie nur verwenden == für den Zeigervergleich und nach Standard (ab C11 6.5.9/6)

Zwei Zeiger sind genau dann gleich, wenn beide Nullzeiger sind, beide Zeiger auf dasselbe Objekt (einschließlich eines Zeigers auf ein Objekt und ein Unterobjekt an seinem Anfang) oder Funktion sind, beide Zeiger auf eins nach dem letzten Element desselben Arrays sind Objekt, oder einer ist ein Zeiger auf einen hinter dem Ende eines Array-Objekts und der andere ist ein Zeiger auf den Anfang eines anderen Array-Objekts, das zufällig unmittelbar auf das erste Array-Objekt im Adressraum folgt.

Allerdings sind die Vergleichsoperatoren strenger (ab C11 6.5.8/5):

Wenn zwei Zeiger verglichen werden, hängt das Ergebnis von den relativen Orten im Adressraum der Objekte ab, auf die gezeigt wird. Wenn zwei Zeiger auf Objekttypen beide auf dasselbe Objekt zeigen oder beide um eins nach dem letzten Element desselben Array-Objekts zeigen, sind sie im Vergleich gleich. Wenn die Objekte, auf die gezeigt wird, Mitglieder desselben Aggregatobjekts sind, sind Zeiger auf später deklarierte Strukturmitglieder größer als Zeiger auf früher in der Struktur deklarierte Mitglieder, und Zeiger auf Array-Elemente mit größeren tiefgestellten Werten sind größer als Zeiger auf Elemente desselben Arrays mit niedrigeren tiefgestellten Werten. Alle Zeiger auf Mitglieder desselben Vereinigungsobjekts sind gleich. Wenn der Ausdruck P auf ein Element eines Array-Objekts und der Ausdruck Q auf das letzte Element desselben Array-Objekts zeigt, ist der Zeigerausdruck Q+1 größer als P. In allen anderen Fällen ist das Verhalten undefiniert.

Der letzte Satz ist der Kicker.

Einige haben Anstoß an der Tatsache genommen, dass Ihr Code die Länge der Überlappung möglicherweise zweimal berechnet, und haben versucht, Vorkehrungen zu treffen, um dies zu vermeiden. Der Effizienz der Reduzierung dieser Berechnung wird jedoch mit einem zusätzlichen Zeigervergleich pro Iteration entgegengewirkt oder beinhaltet undefiniertes oder implementierungsdefiniertes Verhalten. Angenommen, Sie möchten eine tragbare und konforme Lösung, ist der tatsächliche durchschnittliche Gewinn wahrscheinlich gleich Null und die Mühe nicht wert.

Diese Lösung bietet immer noch die gleiche Worst-Case-Leistung, ist aber für Treffer optimiert – Sie müssen nicht beide Strings parsen.

char * temp_a = a;
char * temp_b = b;

while (*temp_a != '\0') {

    if (temp_a++ == b) 
        return 1;

}

// check for b being an empty string
if (temp_a == b) return 1;

/* but if b was larger, we aren't done, so you have to try from b now */
while (*temp_b != '\0') {
    if (temp_b++ == a)
        return 1;
}

/* don't need the a==b check again here

return 0;

Anscheinend ist nur die Zeigergleichheit (nicht die Ungleichheit) in C portierbar, also sind die folgenden Lösungen nicht portierbar – alles unten ist von, bevor ich das wusste.

Ihre Lösung ist gültig, aber warum strlen auf der zweiten Zeichenfolge berechnen? Sie kennen den Start- und Endpunkt einer Zeichenfolge, sehen Sie nur, ob die andere dazwischen liegt (einschließlich). erspart Ihnen das Durchlaufen der zweiten Zeichenfolge — O (M + N) bis O (M)

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
length = strlen(lower_addr_string)
return higher_addr_string >= lower_addr_string && higher_addr_string <= lower_addr_string + length;

Alternativ können Sie das String-Parsing selbst durchführen.

char * lower_addr_string = a < b ? a : b
char * higher_addr_string = a > b ? a : b
while(*lower_addr_string != '\0') {
    if (lower_addr_string == higher_addr_string)
        return 1;
    ++lower_addr_string;
}
/* check the last character */
if (lower_addr_string == higher_addr_string)
    return 1;
return 0;

Ja, Ihre Überprüfung ist korrekt, aber sicherlich nicht die effizienteste (wenn Sie mit “Effizienz” die Recheneffizienz meinen). Die offensichtliche intuitive Ineffizienz in Ihrer Implementierung basiert auf der Tatsache, dass, wenn sich die Zeichenfolgen tatsächlich überlappen, die strlen Aufrufe werden über ihren gemeinsamen Teil iterieren zweimal.

Aus Gründen der formalen Effizienz könnte man einen etwas anderen Ansatz verwenden

int are_overlapping(const char *a, const char *b) 
{
  if (a > b) /* or `(uintptr_t) a > (uintptr_t) b`, see note below! */
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  while (a != b && *a != '\0')
    ++a;

  return a == b;
}

Ein wichtiger Hinweis zu dieser Version ist, dass sie einen relationalen Vergleich von zwei Zeigern durchführt, die nicht garantiert auf dasselbe Array zeigen, was formal zu undefiniertem Verhalten führt. Es wird in der Praxis auf einem System mit flachem Speichermodell funktionieren, könnte aber von einem pedantischen Code-Reviewer kritisiert werden. Um dieses Problem formal zu umgehen, könnte man die Zeiger in umwandeln uintptr_t bevor relationale Vergleiche durchgeführt werden. Auf diese Weise wird das undefinierte Verhalten in den meisten (wenn nicht allen) traditionellen Implementierungen mit flachem Speichermodell in implementierungsdefiniertes Verhalten mit der richtigen Semantik für unsere Zwecke konvertiert.

Dieser Ansatz ist frei von dem Problem des “Doppelzählens”: Er analysiert nur den nicht überlappenden Teil der Zeichenfolge, der sich “früher” im Speicher befindet. In der Praxis könnten sich die Vorteile dieses Ansatzes natürlich als nicht existent erweisen. Es hängt sowohl von der Qualität Ihres ab strlen Implementierung und eine der Eigenschaften der eigentlichen Eingabe.

Zum Beispiel in dieser Situation

const char *str = "Very very very long string, say 64K characters long......";

are_overlapped(str, str + 1);

Meine Version erkennt die Überlappung viel schneller als Ihre. Meine Version erledigt dies in 1 Iteration des Zyklus, während Ihre Version 2 * 64K-Iterationen ausgibt (unter der Annahme einer naiven Implementierung von strlen).

Wenn Sie sich entscheiden, in das Reich der fragwürdigen Zeigervergleiche einzutauchen, kann die obige Idee auch als neu implementiert werden

int are_overlapping(const char *a, const char *b) 
{
  if (a > b)
  {
    const char *t = a; 
    a = b; 
    b = t;
  }

  return b <= a + strlen(a);
}

Diese Implementierung führt keinen zusätzlichen Zeigervergleich bei jeder Iteration durch. Der Preis dafür ist, dass es immer bis zum Ende einer der Zeichenfolgen iteriert, anstatt vorzeitig zu enden. Dennoch ist es immer noch effizienter als Ihre Implementierung, da es aufruft strlen nur einmal.