Icon Ressource

Ressource [C] String- und Vector-Bibliotheken 1.5

german

Aktives Mitglied
devCommunity-Experte
german erstellte eine neue Ressource:

[C] String- und Vector-Bibliotheken - basierend auf der Idee von "length-prefixed" Strings

Diese Ressource besteht aus Bibliotheken, die ich ursprünglich auf 3 Ressourcen aufgeteilt hatte. Sie passen aber konzeptionell zusammen und bedingen sich teilweise gegenseitig, sodass ich mich dazu entschlossen habe, sie in einem Paket zusammen zu schnüren. Ein paar Änderungen sind auch gleich mit eingeflossen.





*** cstr - Stringbibliothek ***
voll kompatibel mit nullterminierten C-Strings

Historie

Es gibt mehrere...

Erfahre mehr über diese Ressource...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

cstr Initialisierung aus FILE* Streams, sowie cs_trim hinzu

BIN cstr cs_init_rdfile(FILE *stream, size_t cnt);
Liest den gesamten Dateiinhalt oder einen Teil davon in ein cstr.

cstr cs_init_rdline(FILE *stream);
Liest eine Zeile einer Datei in einen cstr.

cstr cs_trim(cstr cs, const char *char_set, unsigned mode);
Entfernt spezifizierte voran- oder nachgestellte Zeichen von einem cstr.

Lese den Rest der Aktualisierung...
 
Ich erwarte nicht, dass sich wirklich jemand durch den Code quält. Darum würde ich hier gern drei konzeptionelle Dinge für ein kleines RFC heraus picken. Ich erkläre auch ein bisschen drum herum, was meine Gedanken bei der Umsetzung waren. Würde mich aber über Meinungen dazu von euch freuen ...

1) Die meisten Funktionen beinhalten keine Prüfung auf NULL in Parametern.
Die cstr und cvec Typen sind Pointer. Normalerweise würde man in allen Funktionen prüfen, ob dort NULL Pointer übergeben wurden. Das erzeugt aber Overhead. Sollte man dort NULL übergeben, merkt man das aber üblicherweise bereits beim Debuggen. Außerdem ist die Gefahr größer einen mittlerweile ungültigen Pointer zu übergeben, als tatsächlich NULL. Das würde eine Prüfung gegen NULL natürlich nicht abfangen können.
Sollte ich eher den umgekehrten Weg gehen und jeden Pointerparameter prüfen?

2) Die Funktionen zum Allokieren von Speicher heißen nicht aus Spaß ...alloc_or_die
Bei Speicherallokationen bekommt man einen NULL Pointer zurückgegeben, wenn die Allokation fehlschlägt. Man könnte den NULL Pointer durchreichen und den User der Lib zwingen jeden Rückgabewert der Funktionen auf NULL zu prüfen um darauf zu reagieren. Mach ich aber nicht. Auch weil genau diese Prüfung Overhead erzeugt.
Ich hab erst vor ein paar Monate wieder Code mit einer "...OrDie" Implementierung zu tun gehabt, und zwar in der checked_math Lib von Chromium. Heißt, so ziemlich jeder von uns arbeitet mit einem Browser, der völlig absichtlich unter bestimmten Bedingungen einfach crasht.
Die Idee dahinter:
Wenn ein Prozess hirntot ist und es keine Chance auf Heilung gibt, dann ist aktive Sterbehilfe angesagt. (Hey, wir reden von Software, also können wir ethische Fragen ausblenden und völlig pragmatisch denken ;) ...). Natürlich könnte man jetzt künstlich beatmen und ernähren und darauf warten, dass alle anderen Organe und Zellen auch langsam absterben. Macht man hier aber nicht. Man gibt nicht mal eine humane Überdosis Narkotika, um den Prozess sanft wegschlummern zu lassen. Ganz im Gegenteil. Man gibt dem Ding mit der Panzerfaust den Gnadenschuss, damit auch wirklich niemand den Knall überhören kann.
So gehe ich auch vor, denn:
- Wenn mir das OS keinen Speicher mehr gibt, dann im Zweifelsfall weil der Arbeitsspeicher ausgereizt ist und einfach nichts mehr da ist was ich bekommen könnte.
- Wenn dieser Punkt erreicht ist, dann steht das komplette System kurz vorm BSOD.
- Was sollte der User nun mit der Information machen, einen NULL Pointer zurück bekommen zu haben?
Ich beende den Prozess "abnormal". Somit werfe ich dem OS sofort den wertvollen Speicherschrott vor die Füße, damit es sich wieder erholen kann. Nix mit peu à peu Speicher freigeben. Hier geht's möglicherweise um Sekundenbruchteile um einen BSOD abzuwenden. Und nix mit ordnungsgemäß mit Fehlercode beenden. Hier will ich höchstwahrscheinlich den Debugger reinhängen, was ich nicht mehr kann, wenn das Programm normal beendet wurde. Denn nur so kann ich sehen, wo das Problem gelegen hat. Und wahrscheinlich war der User der Lib selbst schuld, indem er vorher massiv Speicher allokiert hat, ohne ihn wieder freizugeben wenn er ihn nicht mehr braucht.
Was denkt ihr darüber? Ist das so sinnvoll oder haltet ihr das für zu aggressiv?

3) Die memmem Funktion gibt einen void* in einen const void* Speicherbereich zurück
Ach ja, C und const. Wenn selbst die Standardbibliotheken Mist enthalten, was soll man als Programmierer dann noch richtig machen?
Ich nutze da und dort ein paar Zeilen Code, die etwa so aussehen:

C:
static inline void *discard_const(const void *ptr) {
  const union {
    const void *ptr2const;
    void *ptr2mutable;
  } discardconst = {ptr};

  return discardconst.ptr2mutable;
}
Keine Angst, diese Funktion erzeugt kein Overhead und ist nur dazu da Analysetools zu beruhigen, die selbst bei einem cast (void*)ptr noch warnen. Sie gibt dieselbe Speicheradresse zurück, die sie bekommt. In Assembler gibt's kein const mehr, somit ist das sinnloser Code und fliegt beim Kompilieren komplett raus. Aber das nur nebenher ...

Benötigt wird diese Funktion für die Freigabe von Speicher. Der Parameter der free() Funktion ist void* statt const void* deklariert, was ein Bug ist, der so alt ist wie C selbst. Ich nutze sie aber auch noch für die memmem Funktion. Der erste Parameter ist const void* deklariert, der Rückgabewert ist aber void*. Das ist absichtlich falsch. Die Standardfunktionen memchr, strchr, strpbrk, strrchr, strstr sind genauso falsch implementiert. Normalerweise müsste es jeweils ein Funktionspaar geben. Eine mit Pointer auf const als ersten Parameter, die einen Pointer auf const zurückgibt. Eine weitere mit Pointer auf mutable als ersten Parameter, die auch einen Pointer auf mutable zurückgibt.
Wider besseren Wissens habe ich die memmem Funktion in der Tradition der Standardfunktionen aufgebaut, da ich sie als Erweiterung zu diesen betrachte. Okay so, oder sollte ich besser zwei Funktionen bereitstellen?




Nur aus Spaß und nicht mehr zu den Fragen gehörend, den Unsinn den man mit const in C anstellen kann/muss. Wenn ihr das selbst testen wollt, nehmt die in der main auskommentierten Funktionsaufrufe eine nach der anderen wieder rein und schaut euch an was passiert. Die Kommentare im Code erklären das ganze ein wenig.
C:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void PrintAndForget(const char *unmutable);
void FreeConst(const void *ptr);
void ProveTheStringLibWrong(const char *youwillneverbeabletochangeme);
void MutableCanBeConstAsConstCanBe(void);

int main(void) {
  char *str = malloc(128);
  strcpy(str, "Hello World!");
  printf(" - %s -\npointer: %p\nstring: %s\n\n", __func__, (void *)str, str);

  // ProveTheStringLibWrong(str);

  PrintAndForget(str);

  // MutableCanBeConstAsConstCanBe();

  return 0;
}

void PrintAndForget(const char *unmutable) {
  // Durch die const Deklaration des Parameters will ich vermeiden, dass ich Bugs in meinen Code baue. Die Funktion soll den String nur ausgeben,
  // aber auf keinen Fall verändern. Nun ist das bei den 2 Zeilen in dieser Funktion noch sehr Übersichtlich. Bei mehr Code würde man aber erst mal
  // eine Weile suchen. Das const sorgt dafür dass mir der Compiler versehentliche Änderungen sofort um die Ohren haut.
  // *unmutable = '\0'; // gcc: error: assignment of read-only location '*unmutable'

  printf(" - %s -\npointer: %p\nstring: %s\n\n", __func__, (const void *)unmutable, unmutable);

  // Und nun noch gleich freigeben, weil ich den Speicherbereich nicht mehr brauche. Aber ...
  // free(unmutable); // gcc: warning: passing argument 1 of 'free' discards 'const' qualifier from pointer target type [-Wdiscarded-qualifiers]
  // free((void*)unmutable); // clang: warning: cast from 'const char *' to 'void *' drops const qualifier [-Wcast-qual]
  FreeConst(unmutable);
}

void FreeConst(const void *ptr) {
  // Im zweiten Abschnitt auf dieser Seite erklärt Torvalds warum kfree() auf Linux einen `const void*` deklarierten Parameter hat:
  // https://yarchive.net/comp/const.html
  // Der C-Standard liegt verkehrt in der Annahme, dass nur weil malloc und Kollegen einen non-const Pointer zurückgeben, auch der
  // Parameter von free() non-const sein muss. Der Pointer zeigt immer auf veränderbaren Speicher. Eine const Deklaration der
  // empfangenden Variable ändert daran nichts, ebensowenig wie sich die Speicheradresse ändert, wie ich hier erneut zeige.
  const union {
    const void *ptr2const;
    void *ptr2mutable;
  } discardconst = {ptr};
  printf(" - %s -\nptr:         %p\nptr2const:   %p\nptr2mutable: %p\n\n", __func__, ptr, discardconst.ptr2const, discardconst.ptr2mutable);
  free(discardconst.ptr2mutable);
}

void ProveTheStringLibWrong(const char *youwillneverbeabletochangeme) {
  char *ptr = strstr(youwillneverbeabletochangeme, "W"); // Wahlweise memchr, strchr, strpbrk, strrchr
  strcpy(ptr, "weird!");

  // Surprise. War youwillneverbeabletochangeme nicht ein Pointer auf const char? Wie konnte das nur passieren ...
  printf(" - %s -\npointer: %p\nstring: %s\n\n", __func__, (const void *)youwillneverbeabletochangeme, youwillneverbeabletochangeme);

  // Fazit: Was der C-Standard bei free() ohne Nebenwirkungen hätte richtig machen können, hat man in der String Bibliothek nur
  // vermeintlich richtig gemacht, aber tatsächlich ist das so richtig falsch ;-)
  // Hier hätte es jeweils zwei Funktionen bedurft. Ist der Parameter ein Pointer auf const, dann muss auch der Rückgabewert ein
  // Pointer auf const sein. Ansonsten beide nicht const. Aber auch ich schreibe Funktionen in dieser Form bewusst falsch, um mir
  // doppelte Arbeit zu ersparen. Schuldig im Sinne der Anklage :-/
}

void MutableCanBeConstAsConstCanBe() {
  printf(" - %s -\n", __func__);

  // In den allermeisten Implementierungen verweist ein Pointer auf ein Stringliteral letztlich auf read-only Speicher im Stack.
  // C erlaubt (im Gegensatz zu C++) die Zuweisung an einen Pointer auf ein veränderbares char.
  // Hier wird der Unterschied zwischen einer const Deklaration (mit der ich den Compiler anweise mir einen Fehler entgegen
  // zu schmettern, falls ich eine Variable die ich nicht verändern wollte versehentlich doch ändere) und tatsächlich
  // konstantem read-only Speicher überdeutlich.
  char *pointertomutablecontent = "lie"; // Here you lie.
  pointertomutablecontent[0] = 'd';      // Thus, here you die.
  puts(pointertomutablecontent);
}
 
Zuletzt bearbeitet:
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

PTRTOCCSTR Macro hinzu

... da char** und const char** inkompatible Pointertypen. Ersterer wird nicht implizit zu letzterem gecastet.

Außerdem:
Fix für gcc Debug Build das static inline statt nur inline für discard_const_impl_detail sehen will (während das im Release Build nicht erforderlich war).
Kleinere Codeupdates und Korrektur von Rechtschreibfehlern.

Lese den Rest der Aktualisierung...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

memrmem Profiling

Die memrmem Funktion hatte eine ca. 10% schlechtere Performance als memmem. Durch Verschiebung des Iterators vom Ende auf den Anfang des vermuteten Suchbereiches ist offenbar eine bessere Optimierung möglich.
Ergebnis:
Code:
strstr
0000000001A74036
0000000001A74036
0.096818

memmem
0000000001A74036
0000000001A74036
0.045629

memrmem
0000000000A74040
0000000000A74040
0.045734
Gesucht wird ein 9 Byte langer Teilstring über einen nullterminierten String von 16MB Länge und zufällig...

Lese den Rest der Aktualisierung...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

Erstellen eines cstr aus formatierten Daten.

Die Funktionen
cstr cs_init_format(const char *format, ...);
und
cstrw csw_init_format(const wchar_t *formatw, ...);
stehen stellvertretend für die sprintf und swprintf Funktionen um Daten formatiert in einen String zu schreiben. Die Formatbezeichner sind gleich denen für sprintf, der benötigte Puffer wird aber automatisch allokiert.

Lese den Rest der Aktualisierung...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

Funktion cs_init_rdentirefile hinzu

Theoretisch könnte man das Einlesen einer kompletten Datei statt mit cs_init_rdentirefile auch mit cs_init_rdfile erledigen. Ich habe mich aber aus mehreren Gründen dazu entschlossen, diese Funktion zusätzlich zu implementieren:
cs_init_rdfile startet bei der derzeitigen Position des File Cursors im Stream. Das war noch nicht klar beschrieben, habe ich jetzt aber nachgeholt. Heißt, man kann vorab bspw. mittels fseek an eine...

Lese den Rest der Aktualisierung...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

Funktionen speziell für UTF-8 codierten Text

In v1.1 sind ein paar Funktionen hinzu gekommen, um Aufgaben abzudecken, die nur UTF-8 codierte Strings betreffen.

cs_utf8_count
Die strlen Funktion würde im Fall von UTF-8 die Anzahl der Code Units (Bytes) ermitteln. Alle nicht-ASCII Zeichen sind allerdings durch Sequenzen von 2-4 Bytes dargestellt. Die cs_utf8_count Funktion ermittelt die Anzahl der Zeichen (Code Points) im String und validiert gleichzeitig, ob das UTF-8 well-formed ist...

Lese den Rest der Aktualisierung...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

Speichermanagement und Codeformatierung

In v1.2 ist der maximal allokierte Speicher an PTRDIFF_MAX statt an SIZE_MAX angelehnt. Das ist insofern angemessen, als dass Längen in einigen Funktionen real durch die Differenz zweier Pointer berechnet werden. Selbst die Ermittlung von Dateigrößen mittels stat ergibt nur einen 32 bzw. 64 Bit breiten Signed Integer Typ, der in den verbreiteten Implementierungen sich letztlich mit der Definition eines ptrdiff_t matcht. CSDIE (zum...

Lese den Rest der Aktualisierung...
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

Checked Size

Version 1.3 schützt die Funktionen vor Überschreitungen der maximalen Längen der String- bzw. Vectortypen der Bibliotheken. Somit wird undefiniertes Verhalten abgewendet. Statt dessen crasht das Programm in solchen Fällen bevor eine Speicherverletzung auftritt. Um dem Benutzer die Möglichkeit zu geben, vorab zu prüfen, ob die maximalen Längen überschritten würden, sind weitere Funktionen implementiert, die diese zurückgeben:
size_t cs_max_size(void);
size_t...

Lese den Rest der Aktualisierung...
 
Ich vermute, dass die Nutzung von cs_utf8_idx_of_nth_codepoint und cs_utf8_idx_of_rnth_codepoint nicht ausreichend selbsterklärend ist. Grundsätzlich dienen sie einfach der Umrechnung von Codepoints in Bytes. Also poste ich noch mal ein ergänzendes Stückchen Code das zeigen soll, wie diese beiden Funktionen im Zusammenspiel mit anderen Stringfunktionen verwendet werden können. Die Kommentare im Code erklären, was jeweils passiert.
cstr_test.c:
#include "cstr.h"
#include <stdio.h>

int main(void) {
  cstr cs_u8 = cs_init("G\303\244rtner z\303\274chten gro\303\237e M\303\266hren."); // "Gärtner züchten große Möhren."

  const size_t pos = cs_utf8_idx_of_nth_codepoint(cs_u8, 16);          // "Gärtner züchten " incl. Leerzeichen sind 16 Code Points (18 Code Units aka Bytes aka char-Werte).
  const size_t length = cs_utf8_idx_of_nth_codepoint(cs_u8 + pos, 12); // "große Möhren" sind 12 Code Points (14 Code Units), bei Index 'pos' (18) beginnend.
  cstr cs_u8_sub = cs_substr(cs_u8, pos, length);                      // "Möhren" als Substring kopieren.

  printf("|%s|\n", cs_u8);
  cs_free(cs_u8);

  printf("|%s|\n", cs_u8_sub);
  cs_free(cs_u8_sub);

  puts("~~~~~~~~~~");

  cs_u8 = cs_init("\303\244"
                  "\342\202\254"
                  "\360\237\230\200"
                  "\321\216"); // "ä€😀ю"
  printf("|%s|\n", cs_u8);

  size_t idx = cs_utf8_idx_of_nth_codepoint(cs_u8, 3); // Index der ersten Code Unit von ю
  cs_erase(cs_u8, idx, cs_size(cs_u8) - idx);          // ю abschneiden
  printf("|%s|\n", cs_u8);

  idx = cs_utf8_idx_of_rnth_codepoint(cs_u8, idx, 1); // Index der ersten Code Unit von 😀
  cs_erase(cs_u8, 0, idx);                            // alles vor 😀 abschneiden
  printf("|%s|\n", cs_u8);

  cs_free(cs_u8);
  return 0;
}

Die Ausgabe könnte so aussehen (vorausgesetzt das Terminal unterstützt UTF-8 und die Darstellung von Glyphen wie Smileys):
1601725113635.png
 
german aktualisierte [C] String- und Vector-Bibliotheken mit einem neuen Updateeintrag:

const-cast und UTF-8 Partials Handling aktualisiert

Nach einem Jahr, hier die paar unwesentlichen Änderungen die eingeflossen sind, während ich die Lib genutzt habe.
- Der Umweg über eine Union scheint nicht notwendig zu sein um das const bei einem Pointer weg zu casten. Ein Zwischen-Cast zu intptr_t erfüllt denselben Zweck.
- cs_utf8_handle_partials nutzt das Lookup-Array von Christopher Wellons um die Länge eines UTF-8 Codepoints festzustellen (https://github.com/skeeto/branchless-utf8).

Lese den Rest der Aktualisierung...
 
Zurück
Oben Unten