Icon Ressource

[C] String- und Vector-Bibliotheken 1.4

Neben ein paar kleineren Änderungen im Code, ist es mit Version 1.4 möglich rückwärts über eine definierte Anzahl von UTF-8 Codepoints zu iterieren, um den Byteindex dieser Position im String zu bestimmen.

size_t cs_utf8_idx_of_rnth_codepoint(ccstr cs, size_t rbeginidx, size_t rsteps);
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 csw_max_size(void);
size_t cv_max_size(size_t elementsize);

Diese technischen Maximallängen sagen natürlich nichts darüber aus, ob ausreichend Arbeitsspeicher vorhanden ist, um erfolgreiche Allokationen in dieser Größenordnung ausführen zu können. Die Wahrscheinlichkeit ist hoch, dass dies nicht der Fall sein würde.
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 abnormalen Beenden des Programms) wird prinzipiell nur noch bei fehlgeschlagener Speicherallokation oder (und das ist neu) vor einer unabwendbaren Speicherverletzung ausgeführt. Für andere Fälle habe ich die entsprechenden Funktionen insofern verändert, dass sie im Fehlerfall NULL zurückgeben, sodass es dem Benutzer durch Prüfung des Rückgabewertes frei steht zu recovern. Ich habe somit vorerst meine Erwägung verworfen, einen Parameter für eine Handlerroutine einem Großteil der Funktionen hinzuzufügen. (ref. https://dev-community.de/threads/do-or-die.205/)

Ferner ist der Code nun mittels clang-format formatiert. Allerdings mit nach meinem Geschmack angepassten Regeln. Das ist mal mehr und mal weniger sinnvoll, aber immerhin konsistent.
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.

cs_utf8_handle_partials
Es kann nötig sein, UTF-8 codierte Streams zu puffern. Dabei besteht eine große Gefahr, dass Multibyte Sequenzen an den Puffergrenzen zerschnitten werden. Die gepufferten Inhalte können somit nicht sinnvoll weiterverarbeitet werden.
Die cs_utf8_handle_partials Funktion nutzt ein Cache um unvollständige Codepoints zwischenzuspeichern. Diese werden bei einem folgenden Aufruf der Funktion vervollständigt. Der zurückgegebene String enthält also immer vollständige Code Points.

cs_utf8_hasbom
Es ist legal, dass UTF-8 codierten Streams ein Byte Order Mark (BOM) vorangestellt wird. Dieses BOM soll aber textual nicht verarbeitet werden.
Die cs_utf8_hasbom stellt fest, ob ein String mit einem UTF-8 BOM beginnt, damit der User darauf reagieren kann (bspw. um bei der Verarbeitung des Textes die 3 Bytes des BOM zu überspringen).

cs_utf8_idx_of_nth_codepoint
Wie bereits geschrieben, kann ein Zeichen in UTF-8 durch Sequenzen von bis zu 4 Bytes repräsentiert werden.
Die cs_utf8_idx_of_nth_codepoint Funktion ermittelt das Offset in Bytes vom Stringanfang zum n-ten Zeichen (Code Point) im String.

cs_utf8_replace_invalids
Malformed UTF-8 kann nicht sinnvoll weiterverarbeitet werden, da Anzahl und Grenzen der Code Units nicht eindeutig sind.
Die cs_utf8_replace_invalids Funktion ersetzt ungültige Code Units durch valide UTF-8 Sequenzen. Standardmäßig passiert das durch den Unicode Replacement Character (U+FFFD). Es ist aber auch möglich eine andere Sequenz zu spezifizieren oder ungültige Code Units zu entfernen.


Ein paar kleinere Änderungen, die nicht die Funktionalität des bestehenden Codes tangieren (lediglich die Robustheit des Codes), sind additional eingeflossen.
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 bestimmte Position in der Datei springen und dort eine definierte Anzahl Bytes einlesen. Es ist also nicht sinnvoll vorab die komplette Größe der Datei für den cstr zu allokieren. Ein ftell gibt allerdings nicht zuverlässig die Position des File Cursors zurück. Insbesondere nicht im Textmodus. Somit hatte ich mich dazu entschlossen den Dateiinhalt byte-weise einzulesen.
Mit cs_init_rdentirefile konnte ich einen anderen Weg gehen. Hier ist klar, dass immer der komplette Dateiinhalt gelesen werden soll. Mit Conditional Compilation lassen sich ggf. auch Funktionen wie fstat heranziehen, um schnell und zuverlässig die Dateigröße zu bestimmen. Somit kann einmalig Speicher allokiert werden und mit einem einzigen Aufruf von fread gelesen und in den Puffer geschrieben werden. Das kann bei großen Dateien um den Faktor 50 schneller werden, als das char-weise Lesen und Schreiben in der Implementierung von cs_init_rdfile.


Das war aktuell der letzte Punkt auf meiner TODO Liste. Ich traue mir also mal eine Version 1.0 davor zu schreiben ... ;)
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.
Since the libraries seem to attract more attention than expected I decided to attach an English description to the zip file.

Furthermore some minor updates have been made, such like explicite type casts which avoid warnings related to the signedness of values.
... der in wchar_t Stepps iteriert, was die Performance verbessert.
Weiterhin ist feof nicht mehr (alleiniges) Abbruchkriterium einiger Loops, da das zu unsicher ist.
Die cstr und cstrvec Bibliotheken sind um die entsprechenden Funktionen für Strings basierend auf wchar_t erweitert.
Die memmem Bibliothek enthält zwei zusätzliche Funktionen für die rückwärtige Suche in nullterminierten Strings.
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 generiertem Inhalt im Bereich Leerzeichen bis Tilde. Die beiden Adressen in den Blöcken sind die erwartete und die gefundene Adresse. Danach die Zeit in Sekunden. Der erste Block zeigt die Performance der strstr Standardfunktion zum Vergleich. MinGW x64 Release Build, -O3 Optimierung.
Oben Unten