In-place Trimming/Stripping in C

Eine Erklärung von In-Place-Algorithmen findest du in meinem vorherigen Beitrag über Zero-Copy-In-Place-Splitting

Das Problem

Du hast einen C-String, der möglicherweise Leerzeichen am Anfang und/oder am Ende enthält.

char* s = " abc   \n\r";

Mit einem In-Place-Algorithmus möchtest du die Leerzeichen aus diesem String entfernen.

Dies ist auch mit boost::algorithm::trim möglich, hat jedoch die gleichen Einschränkungen wie boost::algorithm::split, wie in meinem vorherigen Beitrag über C-Splitting diskutiert.

Was sind Leerzeichen

Für den Rahmen dieses Beitrags definieren wir Leerzeichen als Zeichen, für die

isspace(char c)

aus ctype.h true zurückgibt. Dies kann an benutzerspezifische Bedürfnisse angepasst werden.

Leerzeichen am Anfang entfernen

Leerzeichen am Anfang des Strings zu entfernen ist recht einfach, aber es gibt eine wichtige Einschränkung.

#include <ctype.h>

char* trimLeft(char* s) {
    while(isspace(*s)) {
        s++;
    }
    return s;
}

Die Idee ist, einen neuen Zeiger zu erstellen, der bis zum ersten Nicht-Leerzeichen vorgerückt ist. Nun zur Einschränkung.

Nehmen wir an, dein Code-Block sieht so aus:

char* s = strdup(/*...*/);
char* sLeftTrimmed = trimLeft(s);
// ... do sth with sLeftTrimmed
free(s);

Dieser Code funktioniert einwandfrei. Aber denk daran, dass du immer s freigeben musst, nicht sLeftTrimmed. Der folgende Code führt zu undefiniertem Verhalten:

char* s = strdup(/*...*/);
char* s = trimLeft(s);
// ... do sth with sLeftTrimmed
free(s);

Diese Einschränkung ist gefährlich, weil im Fall, dass s keine Leerzeichen am Anfang enthält, alles einwandfrei funktioniert. Wenn jedoch Leerzeichen entfernt werden, kann free alles Mögliche tun, z.B. gar nichts (wodurch s nicht freigegeben wird), andere Teile deines Programms korrumpieren (was es fast unmöglich macht zu debuggen) oder einfach zufällig abstürzen. Du solltest What Every C Programmer Should Know About Undefined Behavior lesen, um diese Art von Problem kennenzulernen.

Leerzeichen am Ende entfernen

Dieser Teil des Algorithmus ist etwas komplexer, leidet aber nicht unter der falschen free()-Verwendung wie trimLeft().

#include <ctype.h>

char* trimRight(char* s) {
    //Schutz gegen leere Strings
    int len = strlen(s);
    if(len == 0) {
        return s;
    }
    //Eigentlicher Algorithmus
    char* pos = s + len - 1;
    while(pos >= s && isspace(*pos)) {
        *pos = '\0';
        pos--;
    }
    return s;
}

Die Idee ist, jedes Leerzeichen am Ende in-place durch \0 zu ersetzen. Alle Funktionen

Beachte, dass die Rückwärts-Strategie gut für ASCII-Kodierungen funktioniert und mit kleiner Modifikation auch für UTF-16- und UTF-32-Kodierungen, aber für UTF8 ist ausgedehnteres Backtracking erforderlich, bis man das erste Byte des Codepoints findet.

Beidseitiges Trimming

Gegeben die Funktionen zum Trimmen jeder Seite ist das Trimmen beider Seiten trivial:

char* trim(char* s) {
    return trimRight(trimLeft(s));
}

Der Grund, zuerst links zu trimmen, ist, dass die Suche nach dem Ende des Strings in trimRight() über strlen() aufgrund des kürzeren Strings möglicherweise etwas schneller ist. Für reale Anwendungsfälle sollte dies jedoch kaum einen Unterschied machen.

Beachte, dass die free()-Einschränkung, wie im Abschnitt trimLeft() diskutiert, auch für trim() gilt.

Siehe auch das vollständige Trim-Beispiel