In einem Interview wurde ich gebeten, eine Implementierung von strcpy zu schreiben und sie dann so zu korrigieren, dass sie überlappende Zeichenfolgen richtig behandelt. Meine Implementierung ist unten und es ist sehr naiv..wie repariere ich es, damit a) es überlappende Strings erkennt und b) nach dem Erkennen..wie gehen wir mit der Überlappung um und fahren fort?
%Vor%BEARBEITEN:
Eine mögliche Implementierung, die auf der Antwort von @ Secure basiert, ist also:
%Vor%Wenn wir uns nicht auf memmove verlassen, dann
%Vor%Es gibt keine tragbare Möglichkeit, dies zu erkennen. Sie müssen Zeigervergleiche durchführen, und diese sind nur innerhalb desselben Objekts definiert. I.e. Wenn sich die beiden Strings nicht überschneiden und tatsächlich unterschiedliche Objekte sind, dann führen die Zeigervergleiche zu undefiniertem Verhalten.
Ich würde die Standardbibliothek damit umgehen lassen, indem ich memmove(a, b, strlen(b) + 1) verwende.
BEARBEITEN:
Wie Steve Jessop in den Kommentaren darauf hingewiesen hat, gibt es tatsächlich eine tragbare, aber langsame Möglichkeit, in diesem Fall eine Überschneidung zu erkennen. Vergleichen Sie jede Adresse innerhalb von b mit der ersten und letzten Adresse von a für Gleichheit. Der Gleichheitsvergleich mit == ist immer gut definiert.
Sie haben also so etwas:
%Vor%EDIT 2: Visualisierung von Fall 2
Sie haben so etwas wie das folgende Array und die folgenden Zeiger:
%Vor% Beachten Sie, dass b + strlen(b) einen Zeiger auf das abschließende \ 0 liefert. Beginnen Sie einen hinter, sonst benötigen Sie zusätzliche Handhabung von Rand Fällen. Es ist gültig, die Zeiger dort zu setzen, Sie können sie nur nicht dereferenzieren.
Nun die Kopierschleife, die auch das \ 0 kopiert.
%Vor%Der erste Schritt lautet:
%Vor% Und so weiter, bis src gleich b :
Wenn Sie es ein bisschen mehr häschen wollen, könnten Sie es weiter komprimieren, aber ich empfehle das nicht:
%Vor% Hinweis: b ist die Adresse der Quellzeichenfolge und a ist die Adresse des Ziels.
Mit a > b hätten Sie nicht unbedingt eine Überlappung. Wenn
dann haben Sie eine Überlappung.
Abgesehen von der Erkennung von Überlappungen für Interviews, sollte a > b auch für strcpy funktionieren. Die Idee ist dies:
Wenn b weiter im Speicher abgelegt wird ( b > a ), können Sie normalerweise b in a kopieren. Teile von b werden überschrieben, aber Sie sind bereits hinter diesem Teil.
Wenn a weiter im Speicher abgelegt wird ( a > b ), bedeutet dies, dass möglicherweise durch Schreiben auf die erste Stelle von a bereits eine Position in% co_de überschrieben hat % mit einem höheren Index. In diesem Fall sollten Sie in die entgegengesetzte Richtung kopieren. Anstatt also vom Index b nach 0 zu kopieren, sollten Sie von strlen(b)-1 nach strlen(b)-1 kopieren.
Wenn Sie verwirrt sind, wie das hilft, zeichnen Sie zwei überlappende Arrays auf Papier und versuchen Sie, einmal vom Anfang des Arrays und einmal vom Ende zu kopieren. Versuchen Sie dies mit den überlappenden Arrays in beiden Fällen 0 und a > b .
Beachten Sie, wenn Sie a < b brauchen, müssen Sie nichts kopieren und Sie können einfach zurückkehren.
Edit: Ich bin mir nicht sicher, aber wenn ich die anderen Lösungen lese, scheint es, als wäre diese Antwort nicht vollständig portabel. Vorsicht davor.
Sie können sich auf eine Implementierung beziehen von memmove , es ist ziemlich wie das, was ich gesagt habe.
(*) Sie sollten strlen (b) zwischenspeichern, um die Leistung zu verbessern
Was es tut:
prüft, ob die a+len [Adresse von a + extra len Bytes] innerhalb der Zeichenfolge oder a [Adresse von a] innerhalb der Zeichenfolge ist, dies sind die einzigen Möglichkeiten für eine Überlappung von Zeichenfolgen.
Wenn sich diese beiden Zeichenfolgen überschneiden, werden Sie beim Kopieren die ursprünglichen a - oder b -Zeiger durchlaufen.
Angenommen, dass strcpy (a, b) ungefähr ein & lt; - b bedeutet, dh der erste Parameter ist das Ziel der Kopie, dann prüft man nur, ob der Kopierzeiger b erreicht.
Sie müssen nur die ursprüngliche Position von b speichern und beim Kopieren überprüfen, ob Sie sie erreicht haben. Schreiben Sie auch nicht die abschließende Null, wenn Sie diese Position erreicht haben.
Dieser Algorithmus stoppt nur das Kopieren. Vielleicht möchtest du etwas anderes machen, wie zum Beispiel die Fehlerbedingung markieren oder ein Ende der Zeichenmarkierung an die vorherige Position hinzufügen (obwohl es stillschweigend fehlschlägt (wie es der Algorithmus im Moment tut), ist dies nicht die beste Option).
Hoffe, das hilft.
Das habe ich kürzlich in einem Interview gefragt. Wir müssen uns nicht überschneiden. Wir können strcpy so schreiben, dass überlappende Adressen berücksichtigt werden. Der Schlüssel besteht darin, vom Ende der Quellzeichenfolge anstelle vom Anfang zu kopieren.
Hier ist ein schneller Code.
%Vor%EDIT: Dies funktioniert nur, wenn ein & lt; b. Für ein & gt; b, kopiere von Anfang an.
Auch ohne Verwendung relationaler Zeigervergleiche, memmove , oder gleichwertig, ist es möglich, eine Version von strcpy zu codieren, die im nicht überlappenden Fall als strlen und memcpy ausgeführt wird, und als eine Top-Down-Kopie im überlappenden Fall. Der Schlüssel besteht darin, die Tatsache auszunutzen, dass, wenn das erste Byte des Ziels gelesen und dann durch Null ersetzt wird, strlen auf der Quelle aufgerufen wird und der zurückgegebene Wert zum Quellenzeiger einen legitimen Zeiger ergibt, der gleich dem ist Start des Ziels im Fall "problematische Überlappung". Wenn Quelle und Ziel unterschiedliche Objekte sind, kann der Zeiger "source plus strlen" sicher berechnet und als dem Ziel nicht gleichwertig betrachtet werden.
Für den Fall, dass das Hinzufügen des Quelltexts zum Zielzeiger den Zielzeiger ergibt, wird das Ersetzen des Nullbytes durch den früher gelesenen Wert und das Aufrufen von strlen auf dem Ziel dem Code erlauben, die Endadresse des Quell- und Zielzeichenketten zu bestimmen . Außerdem gibt die Länge der Quellzeichenfolge den Abstand zwischen den Zeigern an. Wenn dieser Wert groß ist (wahrscheinlich größer als 16 oder so), kann der Code die "move" -Operation effizient in eine top-down-Sequenz von memcpy-Operationen unterteilen. Andernfalls kann die Zeichenfolge mit einer Top-Down-Schleife von Ein-Byte-Kopieroperationen oder mit einer Sequenz von "memcpy to source to buffer" / "memcpy buffer to destination" -Operationen kopiert werden [wenn die pro-Byte-Kosten eines großen memcpy ist weniger als die Hälfte einer Einzelzeichenkopierschleife, die Verwendung eines ~ 256-Byte-Puffers kann eine nützliche Optimierung sein.