Vor ~20 Jahren hatte Joel Spolsky (langjähriger Microsoft Entwickler und Mitbegründer von StackOverflow) auf seiner Seite einen interessanten Artikel gepostet.
www.joelonsoftware.com
Es geht im Grunde darum zu verstehen, was die Effizienz von Code beeinflusst und warum es auch mal interessant sein kann hinter die Kulissen der Implementierung zu schauen, um ein Verständnis dafür zu entwickeln.
In einem Abschnitt zieht er die Analogie zu einem ziemlich flachen Scherz an. In Kurzform:
Jeder der das liest fragt sich sofort, was für ein Idiot nimmt nicht einfach den Farbeimer mit? Tatsächlich haben wir aber noch heute Code in der Standardimplementierung, der nach diesem Algorithmus arbeitet. Verrückt
Spolsky beschreibt, was bei
Er hat einen null-initialiserten char-Puffer. Dort will er den String
Es ist ziemlich klar wohin das führt und man fragt sich unweigerlich, warum strcat nicht die Position der Nullterminierung an den Aufruf zurück liefert um zu vermeiden, dass sie immer wieder mit steigendem Aufwand neu gesucht werden muss? Tja, selbst nachdem diese Art der Implementierung seit 20 Jahren einen eigenen Name "Schlemiel the painter's algorithm" bekommen hat, ist das C Konsortium leider immer noch nicht auf die Idee gekommen zumindest eine Alternative anzubieten und strcat obsolet zu setzen. Also stricken wir uns was eigenes
Mehr Text für Kommentare als eigentlicher Funktionscode. Das Beispiel in der main() zeigt aber, dass es alles andere als kompliziert ist. Und Schlemiel lassen wir von nun ab seine Schildbürgerstreiche allein machen ...
Back to Basics
We spend a lot of time on this site talking about exciting Big Picture Stuff like .NET versus Java, XML strategy, Lock-In, competitive strategy, software design, architecture, and so forth. All thi…
www.joelonsoftware.com
In einem Abschnitt zieht er die Analogie zu einem ziemlich flachen Scherz an. In Kurzform:
Schlemiel wurde beauftragt, die gestrichelte Linie in der Straßenmitte neu zu ziehen. Er schafft am ersten Tag noch eine gute Strecke. Aber an jedem weiteren Tag wird die Strecke die hinzukommt kürzer und kürzer. Verärgert darüber, fragt sein Chef ihn nach dem Grund. Schlemiel erklärt, dass die Strecke, die er vom Farbtopf mit dem Pinsel laufen muss, jeden Tag länger wird.
Jeder der das liest fragt sich sofort, was für ein Idiot nimmt nicht einfach den Farbeimer mit? Tatsächlich haben wir aber noch heute Code in der Standardimplementierung, der nach diesem Algorithmus arbeitet. Verrückt
Spolsky beschreibt, was bei strcat() tatsächlich passiert:Er hat einen null-initialiserten char-Puffer. Dort will er den String
"John, " reinhängen. Kein Problem, strcat findet die Nullterminierung beim ersten Byte und kopiert "John " an diese Stelle. Jetzt will er dort noch "Paul, " anhängen. Nun muss strcat bereits einmal über den bereits vorhandenen String "John, " iterieren um die Nullterminierung zu finden, was die Position ist an die "Paul, " kopiert wird. Wenn noch ein "George, " angehängt werden soll, muss strcat über String "John, Paul, " iterieren, um die Nullterminierung zu finden, etc...Es ist ziemlich klar wohin das führt und man fragt sich unweigerlich, warum strcat nicht die Position der Nullterminierung an den Aufruf zurück liefert um zu vermeiden, dass sie immer wieder mit steigendem Aufwand neu gesucht werden muss? Tja, selbst nachdem diese Art der Implementierung seit 20 Jahren einen eigenen Name "Schlemiel the painter's algorithm" bekommen hat, ist das C Konsortium leider immer noch nicht auf die Idee gekommen zumindest eine Alternative anzubieten und strcat obsolet zu setzen. Also stricken wir uns was eigenes
C:
#include <stdio.h>
/** \brief Copy and/or concatenate strings.
*
* \param dest Pointer to the first element in a buffer array for the
* resulting string which has to have at least the length of
* the resulting string + 1 for the terminating null.
* In case that the function shall behave like strcat (see 3.
* below), dest must be null-terminated.
* \param pEndptr 1. If pEndptr is a NULL pointer, src will be copied to dest
* (like strcpy).
* 2. If pEndptr references a pointer to an element of dest
* (preferably the recent terminating null), src will be
* copied to this position.
* 3. If pEndptr references a NULL pointer, the end of the src
* string will be determined, and dest is appended
* (like strcat).
* In case of 1. the position of the terminating null can't be
* given back. Thus, the recommended use is 2., with pEndptr
* referncing a variable that holds the same pointer as dest.
* In case of 2. and 3. the referenced pointer holds the address
* of the terminating null after the function returned.
* \param src Incoming null-terminated string.
*
* \return char* Pointer dest is returned.
* In case of 2. and 3., (*pEndptr) - dest is the length of the
* resulting string (excluding the terminating null) */
char *CpyCat(char *dest, char **const pEndptr, const char *src)
{
if (dest != NULL && src != NULL) // Both dest and src must not be NULL.
{
// Iterator, initialized with either dest or the pointer which pEndptr
// references.
char *it = (pEndptr == NULL) ? dest : *pEndptr;
if (it == NULL) // If it is NULL ...
for (it = dest; *it != '\0'; ++it); // ... find the terminating null.
// Copy char by char until the terminating null is found.
for (; (*it = *src++) != '\0'; ++it);
if (pEndptr != NULL) // If a reference to a pointer was passed ...
*pEndptr = it; // ... give back the address of the terminating null.
}
return dest;
}
int main(void)
{
char buffer[256] = {0}; // Puffer ausreichender Größe für die resultierende Zeichenfolge incl. Nullterminierung
puts("~~~~~~~~~~~~ Kopieren ~~~~~~~~~~~~");
// Verhalten wie strcpy
printf("%s\n\n", CpyCat(buffer, NULL, "Hallo Welt!")); // pEndptr darf für einfaches Kopieren NULL sein
puts("~~~~~~~~~~~~ Verketten ~~~~~~~~~~~");
// neues Feature
char *endptr = buffer; // endptr hält initial die Adresse des Puffers
CpyCat(buffer, &endptr, "Das "); // nach Aufruf der Funktion zeigt endptr auf die Nullterminierung im Puffer
CpyCat(buffer, &endptr, "ist "); // bei jedem weiteren Aufruf wird endptr verwendet um dort die nächste Zeichenkette anzuhängen
CpyCat(buffer, &endptr, "ein ");
printf("%s\n\n", CpyCat(buffer, &endptr, "Test."));
// Verhalten wie strcat
endptr = NULL; // sollte sich im Puffer bereits ein nullterminierter String unbekannter Länge befinden, ist endptr NULL
printf("%s\n", CpyCat(buffer, &endptr, " Mit Anhang."));
printf("Resultierende Laenge: %u\n", (unsigned)(endptr - buffer));
return 0;
}Mehr Text für Kommentare als eigentlicher Funktionscode. Das Beispiel in der main() zeigt aber, dass es alles andere als kompliziert ist. Und Schlemiel lassen wir von nun ab seine Schildbürgerstreiche allein machen ...