Wie zu beheben strcpy so, dass es erkennt überlappende strings

In einem interview wurde ich gebeten, zu schreiben, der eine Implementierung von strcpy und dann fixieren Sie es so, dass es richtig behandelt überlappende strings. Meine Implementierung ist unten und es ist sehr naiv. Wie kann ich es beheben, so dass:

  1. Es erkennt überlappende strings und
  2. nach erkennen, wie gehen wir mit der überlappung und gehen?
char* my_strcpy(char *a, char *b) {

     if (a == NULL || b == NULL) {
         return NULL;
     }
     if (a > b) {
         //we have an overlap?
         return NULL;
     }
     char *n = a;

     while (*b != '\0') {
         *a = *b;
         a++;
         b++;
     }
     *a = '\0';
     return n;
}

int main(int argc, char *argv[])
{
    char str1[] = "wazzupdude";
    char *after_cpy = my_strcpy(str1 + 2, str1);
    return 0;
}

EDIT:

Also eine mögliche Umsetzung auf der Grundlage @Secure Antwort ist:

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    memmove(a, b, strlen(b) + 1);
    return a;
}

Wenn wir verlassen uns nicht auf memmove, dann 

char* my_strcpy(char *a, char *b) {

    if (a == NULL || b == NULL) {
        return NULL;
    }

    if (a == b) {
        return a;
    }

    //case1: b is placed further in the memory
    if ( a <= b && a + strlen(a) > b ) {
        char *n = a;

        while(*b != '\0') {
            *a = *b;
            a++; b++;
        }
        *a = '\0';
        return n;
    }

    //case 2: a is further in memory
    else if ( b <= a && b + strlen(b) > a ) { 
        char *src = b + strlen(b) - 1; //src points to end of b
        char *dest = a;

        while(src != b) {
            *dest = *src;
            dest--; src--;  //not sure about this..
        }
        *a = '\0';
        return a;
    }
}
  • Wie ist a > b sollen "erkennen, ein überlappen"? Es werden lediglich tests der beiden Adressen.
  • Kann man zwei Kopien: kopieren Sie zuerst zu einem lokalen Puffer, keine chance zu überlappen, dann aus dem lokalen Puffer auf das Ziel zu.
  • könnte man, aber dann my_strcpy müsste erlaubt sein, zu scheitern ENOMEM.
  • stimmt - "Es gibt kein solches Ding wie ein freies Mittagessen gibt"; obwohl dabei zwei Kopien ist sehr weit von einem kostenlosen Mittagessen in den ersten Platz 🙂
  • In Bezug auf Ihre Bearbeitung, wie ein interviewer meine nächste Frage wäre: Warum sollte man sich nicht darauf verlassen, memmove, und stattdessen den Handel one-liner gegen einen wartbaren Zeiger Umgang mit Chaos?
  • eigentlich...möchte ich Erstens verlassen sich auf memmove und wenn der interviewer fragt nach der blutigen details oder besteht kann ich nicht verwenden Sie memmove ich würde geben eine detaillierte Umsetzung...btw..ist die Umsetzung oben korrigieren?
  • Richtig? Ich Bezug auf die Portabilität, wie gesagt, Sie sind Berufung auf Undefiniertes Verhalten, wenn die zwei Zeiger sind aus verschiedenen arrays. Es gibt einen offensichtlichen Fehler, bist du mit strlen(a), aber das ist einfach zu lösen. *dest = '\0'; legt das erste byte des a, nicht auf das Letzte byte. Aber am wichtigsten ist, Sie ' ve verpasst den Fall, dass die strings sich nicht überlappen...
  • Für den Fall, wo Sie sich nicht überlappen würden, werden umgesetzt in der gleichen Weise, wie case1. Allerdings bin ich nicht in der Lage zu visualisieren, der zweite Fall(eine ist weiter im Speicher)..daher der Fehler codieren.Ich machte einige änderungen, aber ich werde es zu schätzen wissen wenn Sie mir helfen können visualisieren, Fall 2
  • Ich habe bearbeitet Sie meine Antwort mit einer Visualisierung der Fall ist 2.
  • Hinweis: if(a == NULL || b == NULL){ return NULL; } ist nicht erforderlich, wenn a, b Punkt-zu-C-strings.
  • Sollte nicht die "char *dest = a;" am Ende der entsprechenden Ziel-und count-down von dort aus, wenn Sie den Countdown von der aktuellen position, bist du nicht Puffer-unter-fließt?

InformationsquelleAutor user7 | 2011-09-15
  1. 9

    Gibt es keinen portablen Weg, dies zu erkennen. Sie haben zu tun, Zeiger-Vergleiche, und diese sind nur definiert innerhalb des gleichen Objekts. I. e. wenn die beiden strings nicht überschneiden und sind in der Tat verschiedene Objekte, dann die Zeiger-Vergleiche geben Ihnen Undefiniertes Verhalten.

    Ich würde das standard-Bibliothek behandelt diese, durch die Verwendung memmove(a, b, strlen(b) + 1).

    EDIT:

    Als Steve Jessop wies darauf hin, in den Kommentaren, es ist eigentlich eine portable, aber langsam Möglichkeit zu erkennen, überschneiden sich in diesem Fall. Vergleichen Sie jede Adresse innerhalb von b mit der ersten und letzten Adresse eines für die Gleichstellung. Der Geschlechter-Vergleich mit == ist immer gut definiert.

    So, Sie haben so etwas wie dieses:

    l = strlen(b);
isoverlap = 0;
for (i = 0; i <= l; i++)
{
    if ((b + i == a) || (b + i == a + l))        
    {
        isoverlap = 1;
        break;
    }
}

    EDIT 2: Visualisierung von Fall 2

    Haben Sie etwas wie das folgende array und Zeiger:

    S t r i n g 0 _ _ _ _ _ _ _
^       ^
|       |
b       a

    Beachten Sie, dass b + strlen(b) Ergebnisse in einen Zeiger auf das abschließende \0. Start hinter sich, was Sie brauchen zusätzliche Behandlung der Grenzfälle. Es ist gültig bis legen Sie den Zeiger dort, nur können Sie nicht dereferenzieren Sie.

    src = b + strlen(b) + 1;
dst = a + strlen(b) + 1;

S t r i n g 0 _ _ _ _ _ _ _
^       ^     ^       ^  
|       |     |       |
b       a     src     dst

    Nun die copy loop, die Kopien der \0, zu. 

    while (src > b)
{
    src--; dst--;
    *dst = *src;
}

    Den ersten Schritt bietet dieser:

    src--; dst--;

S t r i n g 0 _ _ _ _ _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

*dst = *src;

S t r i n g 0 _ _ _ 0 _ _ _
^       ^   ^       ^  
|       |   |       |
b       a   src     dst

    Und so weiter, bis src landet gleich b:

    S t r i S t r i n g 0 _ _ _
^       ^              
|       |            
b       a          
src     dst

    Wenn Sie wollen, dass es ein bisschen mehr hackish, könnte man komprimiert es weiter, aber ich weiß nicht empfehlen diese:

    while (src > b)
    *(--dst) = *(--src);
    • Es ist nicht wahr, die sich überschneiden, kann nicht festgestellt werden, tragbar. Es ist eine erschreckend inefficent Weg. Dies ist für memmove, aber ich glaube, es kann angepasst werden für strcpy: stackoverflow.com/questions/4023320/...
    • "Sie haben zu tun, Zeiger-Vergleiche, und diese sind nur definiert innerhalb des gleichen Objekts." -Wie kann ich überprüfen, ob die beiden Zeiger zeigen auf das gleiche Objekt (ein array in diesem Fall)
    • Jessop: Richtig, aber in diesem Fall kann nicht festgestellt werden, tragbar, denn Sie nur haben zwei Zeiger, nicht aber die array-Grenzen (Startadresse und Größe) Sie zeigen in.
    • Es muss gegeben werden, als bekannt Voraus. Sonst können Sie nicht prüfen, für die es ohne Berufung auf ein Undefiniertes Verhalten, wenn Sie es nicht sind, außer wenn die array-Grenzen sind bekannt als Steve hingewiesen. Dann können Sie jede mögliche Adresse in einem der arrays gleich sein wie die anderen Zeiger. OTOH, wenn Sie wissen, die Grenzen für beide arrays, können Sie einfach überprüfen Sie für Gleichberechtigung sind. Eine überprüfung auf Gleichheit von Zeigern mit == ist immer gut definiert, das gleiche-Objekt-Regel gilt nur für die kleiner-als-oder größer-als-überprüft.
    • Aber wie haben Sie selbst gesagt, strlen(b)+1 gibt Sie, die Größe. Es geht nur schief, wenn der Anrufer hat sich etwas getan ungültig ersten, z.B. wenn a nicht auf ein ausreichend großer Puffer, aber das ist nicht unsere Schuld.
    • Jessop: Aber der string kann in der Mitte eines viel größeren array. Wenn a Punkte um eine position vor b innerhalb dieses Arrays können Sie nicht prüfen, ob diese.
    • ja, Sie können. Mein code auf, dass memmove Frage stellt. Wenn a ist vor b, und die Regionen, die wir über Pflege für strcpy überschneiden, dann für einige l < strlen(b)+1 Sie Treffer a + l == b.
    • Vergiss meinen letzten Kommentar, ich verstehe, was du meinst. Du hast Recht, wenn die überprüfung a und a + strlen(b) für die Gleichstellung innerhalb b. Dies wird funktionieren, aber langsam. 😉
    • Sie für deine ausführliche Erklärung.
    • Die Saiten überlappen, wenn a + strlen(a) == b + strlen(b).
    • "Zeiger-Vergleiche sind nur innerhalb des gleichen Objektes" - also was? wenn string-Pointer nicht zum selben Objekt gehören, können Sie sich nicht überlappen irgendwie so undefiniert Verhalten wird nicht Schaden. das bedeutet, einfacher Vergleich ist in der Tat tragbar!
    • Vergleiche von unabhängigen Zeigern nicht nur die Rendite einer unbestimmten Ergebnis. Einige Compiler können daraus schließen, dass, da die Norm enthält keine Anforderungen an das, was passieren soll, wenn Unbeteiligte Zeiger verglichen werden, die Standard erlegt keine Bedingungen, was ein Programm tun sollten, wenn gegeben Eingänge, das würde dazu führen, dass diese Zeiger verglichen wird. Solche Compiler könnte dann weiter folgern, dass, wenn eine Bedingung kann nur wahr sein, wenn Sie angesichts Eingänge, die aufrufen würde zu Undefiniertem Verhalten, ein compiler kann davon ausgehen, der Zustand ist immer falsch. Folglich ist es nicht sicher zu Undefiniertem Verhalten.
    • 1)src = b + strlen(b) + 1; dst = a + strlen(b) + 1; sollte src = b + strlen(b);dst = a + strlen(b) ;2)es ist falsch, während b>a und a+strlen(b) > b.
    • Ich weiß, es ist eine late-Kommentar (fast 5 Jahren auf den Tag!) aber (wie ich es verstehe), können Sie nicht sicher verwenden strlen(a) weil Sie nicht wissen, wie die Erinnerung an a angeordnet ist.
    • wenn Sie nicht der übergabe von strings, ist das Spiel vorbei, ja. Das ist nicht wirklich ein Teil des Problems, aber. Mein Punkt war nur diese: wenn sich die Saiten überlappen, Sie unbedingt teilen die gleichen null-terminator. So haben Sie, um nur ein Vergleich, nicht viele.
    • Technisch ist der memory konnten sich überschneiden, aber das - strings nicht. a (Ziel) könnte so etwas wie abc\0def\0ghijklmnop\0 mit b dem Hinweis auf die ghijklmnop (könnte man so etwas von strtok()). Die - strings an a (abc) und bei b (ghijklmnop) nicht überlappen, aber die Erinnerung, dass Sie möchten strcpy( a, b ) zu kopieren (wenn dies erlaubt ist) würde überlappen.
    • ok, sicher, aber naive-string kopieren funktioniert in diesem Fall....
    • Nicht unbedingt... was hat mich hierher geführt, war eine der letzten kompiliert unter gcc (von einigen sehr alten code) Herstellung der "falschen" Ergebnis für eine "shift-Links" kopieren. (Technisch gesehen, kann das Ergebnis nicht "falsch" sein, weil-wie wir waren [mis]mit strcpy, ist das Ergebnis undefiniert, aber falsch im Sinne von "nicht das, was wir erwartet und passiert seit Jahren").

    InformationsquelleAutor Secure
  2. 4

    Könnten Sie wahrscheinlich verwenden Sie memmove (), wenn Sie erwarten, dass die Saiten zu überschneiden.

    char* my_strcpy(char *a, char *b)
{
    memmove(a, b, strlen(b) + 1);
    return a;
}
    • Das ist unter Berücksichtigung, dass ein char == byte für byte. Ich würde ändern, strlen(b) + 1 durch ( strlen(b) + 1 ) * sizeof( char )
    • sizeof(char) ist immer genau ein byte.
    • Yep, aber memmove erwartet bytes, keine chars, auch wenn Sie übrigens die selbe Größe haben. Wie auch immer, ich sagte nur "ich würde".
    • rechnet bytes, chars nicht" ist irreführend. memmove() erwartet Sie eine Größe in Zeichen und in C, "bytes" und Zeichen haben die gleiche Größe. "Der memmove-Funktion kopiert n Zeichen aus dem Objekt verweist s2 in das Objekt wies auf die von s1. C11 "7.24.2.2"
    InformationsquelleAutor brain
  3. 4

    Hinweis: Hier b ist die Adresse des Quell-string und a ist die Adresse des Ziels.

    Mit a > b Sie würde nicht unbedingt überschneiden. Wenn

    (a <= b && a+strlen(a) >= b) || (b <= a && b+strlen(b) >= a)

    dann hast du eine überschneidung.

    Jedoch, neben der Erkennung von überschneidungen zum Wohle interview a > b tun sollte, feinen für strcpy. Die Idee ist diese:

    Wenn b platziert, weitere in den Speicher (b > a), dann kannst du normal kopieren b in a. Teile b überschrieben werden, aber Sie sind schon Vergangenheit, Teil.

    Wenn a platziert, weitere in den Speicher (a > b), es bedeutet, dass möglicherweise durch das schreiben auf die erste Lage des a Sie haben bereits überschrieben einem Standort in b mit einem höheren index. In einem solchen Fall, sollten Sie kopieren Sie in die entgegengesetzte Richtung. Also statt der Kopie von index 0 zu strlen(b)-1 Sie sollten kopieren von strlen(b)-1 zu 0.

    Wenn Sie verwirrt sind, wie das hilft, zeichnen Sie zwei sich überlappende arrays auf Papier und versuchen, Sie zu kopieren, sobald aus dem Beginn des Arrays und einmal am Ende. Versuchen Sie, diese mit den überlappenden arrays sowohl in den Fällen, in a > b und a < b.

    Beachten, wenn a == b Sie müssen nicht wirklich alles kopieren, und Sie können einfach zurückgeben.

    Edit: ich bin mir nicht sicher, aber das Lesen der anderen Lösungen, wie es scheint, diese Antwort kann nicht vollständig portabel. Hüten Sie sich vor, dass.

    • wenn a==b Sie könnte auch einfach zurück 🙂 strcpy nimmt Zeiger auf nicht-volatile, also es gibt keine Voraussetzung, um wirklich berühren Sie den Speicher. Das heißt, es ist nicht Wert das hinzufügen von code zu optimieren, der absurde Fall.
    • Ja, wie konnte ich das übersehen! Ich bearbeitet meine Antwort
    • Sie haben die abschließenden NUL berücksichtigt?
    • Recht. Danke für den Kommentar.
    InformationsquelleAutor Shahbaz
  4. 3
    if a > b; then
    copy a from the beginning
else if a < b; then
    copy a from the ending
else //a == b
    do nothing

    Können Sie beziehen sich auf eine Umsetzung von memmove ist, ist es ziemlich wie das, was ich sagte.

    InformationsquelleAutor Mu Qiao
  5. 1
    if (a>= b && a <= b+strlen(b))) || (b+strlen(b) >= a && b+strlen(b) <= a + strlen(b))

    (*) sollten Sie die cache-strlen(b) um die Leistung zu verbessern

    Was es tut:

    prüft, ob der a+len [Adresse a + extra-len bytes] ist innerhalb der Zeichenfolge, oder a [Adresse a] ist, innerhalb der Zeichenfolge, diese sind die einzigen Möglichkeiten für eine Zeichenfolge überschneiden.

    InformationsquelleAutor amit
  6. 1

    Wenn diese zwei strings überschneiden, dann, beim kopieren ist, dass man über die ursprüngliche a oder b Zeiger.

    Unter der Annahme, dass strcpy( a, b ) etwa bedeutet, dass a <- b, d.h. der erste parameter ist das Ziel der Kopie, dann hast du nur überprüfen ob die Kopie Zeiger erreicht b's position.

    Brauchen Sie nur zu speichern die b ursprüngliche position, und beim kopieren, prüfen Sie noch nicht erreicht. Auch schreiben Sie nicht die nachgestellte null, wenn Sie erreicht haben, die position.

     char* my_strcpy(char *a, const char *b)
 {

    if ( a == NULL
      || b == NULL )
    {
        return NULL;
    }

    char *n = a;
    const char * oldB = b;

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

    if ( a != oldB ) {
        *a = '\0';
    }

    return n;
 }

    Dieser Algorithmus hört einfach auf zu kopieren. Vielleicht möchten Sie etwas anderes tun, wie z.B. die Markierung der Fehler, oder fügen Sie ein Ende der Zeichenfolge markieren, um die Vorherige position (obwohl stillschweigendes fehlschlagen (wie der Algorithmus funktioniert im moment) nicht die beste option).

    Hoffe, das hilft.

    InformationsquelleAutor Baltasarq
  7. 1

    Wurde ich gebeten, dies in einem aktuellen interview. Wir don ' T haben, um 'erkennen' überlappen. Wir können schreiben strcpy in der Weise, dass sich überlagernde Adressen gesorgt. Der Schlüssel ist, um die Kopie aus dem Ende des Quell-Zeichenfolge anstelle von Anfang an.

    Hier ist ein quick-code. 

    void str_copy(const char *src, char *dst) 
{
    /* error checks */

    int i = strlen(a); /* may have to account for null character */

    while(i >= 0) 
    {
        dst[i] = src[i];  
        i--; 
    }
}

    EDIT: Dies funktioniert nur, wenn a < b. Für a > b, kopieren von Beginn an.

    • Das problem besteht bei überlappenden strings. Wie memcpy Sie kopieren sollten von Anfang oder am Ende, basierend darauf, ob das Ziel, zu kopieren, hat niedrigere oder höhere Adresse als die Quelle beziehungsweise.
    • +1, guter Punkt. Wie konnte ich es verpassen?
    • 1) der Code nicht kompilieren. 2) Schlagen Nachbesserung Antwort/code src dest im gesamten eher als a b. 3) strlen() zurück geben size_t, aber dann size_t i verursacht Probleme mit while(i>=0) test, die ist immer wahr.
    InformationsquelleAutor Bhaskar
  8. 1

    Sogar ohne die Verwendung der relationalen Zeiger-Vergleiche memmove, oder äquivalent, ist es möglich, code eine version von strcpy die durchgeführt als eine strlen und memcpy im nicht überlappenden Fall und als top-down-Kopie, die sich im überlappenden Fall. Der Schlüssel ist, zu nutzen, die Tatsache, dass, wenn das erste byte der Ziel gelesen wird, und dann durch null ersetzt, aufrufen strlen auf die Quelle und mit der Quelle Zeiger den Wert, der zurückgegeben wurde, wird der Ertrag einer legitimen Zeiger, die gleich zu Jahresbeginn das Ziel in der "lästige überschneidungen" der Fall. Wenn Quelle und Ziel verschiedene Objekte, die "Quelle plus strlen" - Zeiger kann sicher berechnet und beobachtet zu werden, ungleich der Ziel.

    Im Falle, dass das hinzufügen der string-Länge des Quell-pointer ergibt sich die Ziel-Zeiger, ersetzen die null-byte mit den früheren-Wert Lesen und aufrufen von strlen auf die Ziel-erlauben-code, um zu bestimmen, die Endung-Adresse des Quell-und Ziel-strings. Weiter ist die Länge der Quell-Zeichenkette gibt den Abstand zwischen den Zeigern. Wenn dieser Wert groß (vermutlich größer als 16 oder so), kann code effizient unterteilen Sie die "move" - Vorgang in einem top-down-Reihenfolge der memcpy-Operationen. Sonst wird der string kopiert werden kann mit einer top-down-Schleife von single-byte-Kopie-Operationen, oder mit einer Folge von "memcpy an der Quelle zu Puffern"/"Puffer memcpy zum Ziel" Operationen [wenn die pro-byte-Kosten für einen großen memcpy ist weniger als die Hälfte, dass von einer individuellen Charakter-Kopie-Schleife, mit einem ~256-byte-Puffer kann eine sinnvolle Optimierung].

    InformationsquelleAutor supercat
Schreibe einen Kommentar