Icon Ressource

[C] String- und Vector-Bibliotheken 1.2

[C] string and vector (dyn. array) libraries
based on the idea of length-prefixed strings
For an English description refer to the pdf file which is included in the download, too. Function references in the header files are in English anyway.





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 Möglichkeiten Strings zu definieren. C hat aus historischen Gründen einen Weg gewählt, der sich letztlich als unkomfortabel herausstellt. Wie kann man sich das vorstellen?
Nehmen wir an, Peter steht mit dem Fahrrad am Ortsausgang von Hundsdorf. Leonie steht am anderen Ende der Straße am Ortseingang von Katzleben. Peter möchte wissen wie weit der Weg nach Katzleben ist, setzt seinen Kilometerzähler zurück und fährt los. Nach fünfzehn Minuten abgehetzt in Katzdorf angekommen, fragt er Leonie, ob sie wüsste dass die Entfernung zwischen Hundsdorf und Katzleben 10km beträgt? Leonie dreht den Kopf zur Seite, zeigt auf das Ortsausgangsschild wo geschrieben steht: Hundsdorf 10km.
Ja, so ein Ortsschild ist keine schlechte Erfindung. Aber um den Bogen zurückzuschlagen, ein String in C hat diesen Luxus nicht. Um die Länge zu bestimmen, ist man gezwungen das Stringende mit der Nullterminierung zu suchen und muss somit, wie Peter mit seinem Fahrrad, einmal den kompletten Weg zurücklegen, um diese zu finden.
Schon die Pioniere in der Softwareentwicklung haben erkannt, dass so etwas suboptimal ist. Eine alternative Stringimplementierung ist als Pascal-String bekannt. Der für den String aufgewendete Speicher ist gleich. Statt dem String ein Byte als Nullterminierung nachzustellen, wird ein Byte vorangestellt, das die Länge des Strings beinhaltet. Das hat den Vorteil, dass das Stringende zu bestimmen eine Operation mit der Komplexität O(1) statt O(n) ist, sowie dass ein String auf diese Weise auch Null-Bytes enthalten darf. Somit kann ein String ebenso gut auch Binärdaten beinhalten. Durch die Typbreite eines Byte ist man allerdings auf eine Länge von 255 beschränkt. So ganz ausgereift war das also noch nicht, aber immerhin ein Anfang. Modernere Stringimplementierungen halten neben dem Pointer auf den Stringanfang, die Länge und die Kapazität des allokierten Speichers in ausreichend breiten Typen in Membern einer Struktur. Das macht solche Stringimplementationen flexibel und bietet die Möglichkeit erforderliche Reallokationen zu reduzieren um die Performance zu verbessern. Bei solchen Stringklassen kann man aber nicht direkt mit den Standardfunktionen der C Bibliothek interagieren. Um das zu erreichen, muss man sich wieder an die Implementierung des Pascal-Strings zurückerinnern. Dort sind alle Informationen in einem konsekutiven Speicherbereich hinterlegt. Das Offset zum eigentlichen Stringanfang ist dort 1 Byte. Aber wer sagt eigentlich, dass das immer nur ein Byte sein darf, solange das Offset konstant bleibt ...? ;)





cstr - Implementierung

Ziel ist es, die Vorteile einer Stringklasse, mit der Kompatibilität zu nullterminierten C-Strings zu verbinden.
Beispiel:
Wenn ein cstr erzeugt wurde ...
cstr cs = cs_init("ABC");
... dann soll ein ...
char ch = cs[1];
... ein 'B' der Variablen ch zuweisen, oder ein ...
char *ptr = strchr(cs, 'B');
... den Pointer auf das 'B' im cstr ermitteln, oder ein ...
puts(cs);
... den String ABC ausgeben.
Um das zu gewährleisten, werden Kapazität, Stringlänge und der eigentliche String in einem zusammenhängenden (konsekutiven) Speicherbereich abgelegt. Der Nutzer bekommt dabei aber immer nur den Pointer auf das erste Zeichen im eigentlichen String. Der vorangestellte Bereich mit Kapazität und Länge bleibt in der Implementierung verborgen. Diese beiden Daten haben jeweils die Breite eines size_t. Das Offset vom Beginn des allokierten Speichers bis zum ersten Zeichen des Strings ist somit immer konstant. Mit diesem Offset ist es also möglich vom Pointer auf das erste Zeichen, rückwärts auf den Beginn des gesamten Speicherbereichs zuzugreifen. Um den Zugriff auf die Daten zu vereinfachen, ist eine Hilfsstruktur cstr_base implementiert. Diese wird nie instanziiert. Lediglich Pointer auf diese Struktur werden verwendet, um mit Hilfe der Membernamen Zugriff auf Kapazität, Stringlänge und den char-Pointer zu bekommen.
Nachteil dieser Implementierung ist, dass es keine Möglichkeit gibt, ein Mutex direkt einzubauen, um thread-safe by design zu werden (so wie es @asc in seiner strbuf Umsetzung im coding-board gepostet hatte). Auf alle Daten wird hier über den cstr Pointer zugegriffen. Wird dieser in einem Thread durch Reallokation verändert, dann ist auch der Pointer auf das Mutex invalid, noch vor einem Lock im konkurierenden Zugriff. Weiterhin ist darauf zu achten, dass jeweils nur eine Variable pro cstr verwendet wird. Funktionen verändern ggf. die Adresse die die cstr Variable hält. Kopien des Pointers werden also potenziell invalid.

Die nachfolgende Illustration zeigt, wie die Daten im Speicher abgelegt sind. Der cstr Pointer ist das Interface, das in den Funktionen der Bibliothek verwendet wird. Die Darstellung der cstr_base Struktur zeigt wie und warum sie für den Zugriff auf die Daten verwendet werden kann, auch wenn das data Member nur ein Platzhalter für den eigentlichen String ist.

1591546653311.png





Die beiden definierten Typen der Bibliothek, um einen cstr zu repräsentieren, sind Pointer auf char.
Sie existieren grundsätzlich nur, um C-Strings von den speziell allokierten cstr Strings unterscheiden zu können.
typedef char *cstr;
typedef const char *ccstr;

Ein weiterer zusammengesetzter Typ ist implementiert, exklusiv um unvollständige Code Points von UTF-8 codierten Strings zu verarbeiten.
typedef struct tag_u8state u8state_t;



Das BIN Macro ist ohne Funktionalität. Es markiert lediglich die Funktionen der cstr Bibliothek, die mit binären Daten im String verwendbar sind.



Für das Erstellen und das Zerstören von cstr Strings stehen folgende Funktionen zur Verfügung:
cstr cs_init(const char *str);
cstr cs_init_format(const char *format, ...);
BIN cstr cs_init_n(const char *seq, size_t cnt);
BIN cstr cs_init_rdentirefile(FILE *stream);
BIN cstr cs_init_rdfile(FILE *stream, size_t cnt);
cstr cs_init_rdline(FILE *stream);
BIN cstr cs_init_zero(size_t size);
BIN void cs_free(ccstr cs);



Die Verarbeitung von cstr Strings erfolgt mit Funktionen, deren Namen und Funktionsweisen sich weitgehend an die C++ Stringbibliothek anlehnen:
cstr cs_append(cstr *pcs, const char *str);
BIN cstr cs_append_n(cstr *pcs, const char *seq, size_t cnt);
cstr cs_assign(cstr *pcs, const char *str);
BIN cstr cs_assign_n(cstr *pcs, const char *seq, size_t cnt);
BIN char cs_at(ccstr cs, size_t pos);
BIN size_t cs_capacity(ccstr cs);
BIN cstr cs_clear(cstr cs);
BIN bool cs_empty(ccstr cs);
BIN cstr cs_erase(cstr cs, size_t pos, size_t length);
cstr cs_fix(cstr *pcs, size_t length, const char *pad, unsigned mode);
cstr cs_insert(cstr *pcs, size_t pos, const char *str);
BIN cstr cs_insert_n(cstr *pcs, size_t pos, const char *seq, size_t cnt);
BIN size_t cs_length(ccstr cs);
BIN char cs_pop_back(cstr cs);
BIN cstr cs_push_back(cstr *pcs, const char ch);
cstr cs_replace(cstr *pcs, size_t pos, size_t length, const char *str);
BIN cstr cs_replace_n(cstr *pcs, size_t pos, size_t length, const char *seq, size_t cnt);
BIN cstr cs_reserve(cstr *pcs, size_t capa);
BIN cstr cs_resize(cstr *pcs, size_t size, char fill);
BIN cstr cs_reverse(cstr cs);
BIN cstr cs_shrink_to_fit(cstr *pcs);
BIN size_t cs_size(ccstr cs);
BIN cstr cs_substr(ccstr cs, size_t pos, size_t length);
cstr cs_trim(cstr cs, const char *char_set, unsigned mode);
BIN cstr cs_update_length(cstr cs, size_t length);
Darüber hinaus kann ein cstr String direkt mit den Stringfunktionen der C Stringbibliothek verwendet werden.

Für Strings basierend auf wchar_t sind die Typen cstrw und ccstrw implementiert. Die zugehörigen Funktionen beginnen mit csw_... statt cs_....


Funktionen speziell für UTF-8 codierten Text:
size_t cs_utf8_count(ccstr cs);
cstr cs_utf8_handle_partials(cstr *pcs, u8state_t *pstate);
bool cs_utf8_hasbom(ccstr cs);
size_t cs_utf8_idx_of_nth_codepoint(ccstr cs, size_t pos);
cstr cs_utf8_replace_invalids(cstr *pcs, const char *rep);

Beschreibungen der Funktionen mit deren Parametern und Rückgabewerten finden sich im cstr.h Header.





*** memmem - Suchen von Bytesequenzen in Binärdaten ***

Die memmem Funktion hat ein ähnliches Verhalten wie strstr und adressiert die Möglichkeit der cstr Implementierung, mit Binärdaten arbeiten zu können.
memmem sucht das erste, memrmem das letzte Vorkommen einer Bytesequenz in einem Datenbereich.
Sie passen nicht so recht in die cstr Bibliothek, da sie eigentlich Erweiterungen der Stringbibliothek im <string.h> Headers darstellen. Der gehört aber zum C Standard. Somit habe ich die Funktionen in ein eigenes Source-Header-Paar gepackt. Die Funktionen können völlig unabhängig von der cstr Bibliothek verwendet werden.

void *memmem(const void *buffer, size_t buffer_size, const void *target, size_t target_size);
void *memrmem(const void *buffer, size_t buffer_size, const void *target, size_t target_size);

Die Funktionen ...
char *strrstr(const char *str, const char *substr);
wchar_t *wcsrstr(const wchar_t *strw, const wchar_t *substrw);
... sind speziell für rückwärtige Suche in nullterminierten Strings implementiert.





*** cvec - Vector-Bibliothek ***
Arrays mit dynamischer Speicherverwaltung

Vorwort

In der Erklärung zur cstr Bibliothek hatte ich bereits ein wenig über das Konzept geschrieben. Auch die Basis für den cvec ist letztlich der Pascal-String, der ein String mit vorangestellter Längenangabe ist. Im cstr ist das bereits insofern verallgemeinert, dass nicht nur die Länge vorangestellt ist, sondern auch die Kapazität. Nun ist ein String letztlich nur ein Array von char-Werten. Die Idee, das Konzept weiter zu verallgemeinern, sodass man nicht auf den char-Typ beschränkt ist, liegt nahe. Theoretisch ist das auch kein Problem. Praktisch müsste man aber für jeden Elementtyp eine eigene Funktionsbibliothek schreiben, denn Funktionen für unterschiedliche Typen zu templatisieren, so wie das in C++ möglich ist, wird von C leider nicht unterstützt. Letztlich muss man also, wie immer in solchen Fällen, auf untypisierte Pointer void* zurückgreifen, mit allen zusätzlichen Risiken ...





cvec - Implementierung

Konzeptionelles Ziel ist auch hier, dass der User direkt einen Pointer auf das erste Element des Vectors erhält, während alle anderen Daten in der Implementierung verborgen bleiben. Durch ein Offset lässt sich auch hier wieder auf diese Daten zugreifen.
Durch das Arbeiten mit einem untypisierten Pointer, ist es allerdings notwendig, dass diese Daten auch die Typbreite eines Elements beinhalten. Ein cvec hält, neben den eigentlichen Daten, somit die Kapazität, die Länge, sowie die Typbreite. Zugriff erfolgt über einen Pointer auf eine Hilfsstruktur cvec_base.
Mehrdimensionale cvec Vectoren sind grundsätzlich auch umsetzbar (siehe main.c).

Die Illustration zeigt, wie die Daten im Speicher abgelegt sind. Der cvec Pointer ist das Interface, das in den Funktionen der Bibliothek verwendet wird. Die Darstellung der cvec_base Struktur dient dem zusätzlichen Verständnis.

1591546722962.png




Die beiden definierten Typen der Bibliothek sind Pointer auf void.
Sie existieren um andere Pointer von den speziell allokierten cvec Pointern abzugrenzen.
typedef void *cvec;
typedef const void *ccvec;

Des Weiteren ist der Pointertyp der Callbackfunktion zur Verwendung mit cv_for_each definiert.
typedef bool(*cv_for_each_proc_t)(void *element_data, void *user_param);



Das PTRTO Macro castet ein cvec zum Pointer auf den eigentlichen Typ der Elemente.
Das MAKEPTR Macro erzeugt einen Pointer auf einen Einzelwert oder eine Liste von Einzelwerten.



Für das Erstellen und das Zerstören von cvec Vektoren stehen folgende Funktionen zur Verfügung:
cvec cv_init(const void *seq, size_t cnt, size_t elementsize);
cvec cv_init_zero(size_t size, size_t elementsize);
void cv_free(ccvec cv);



Die Verarbeitung von cvec Vektoren erfolgt mit Funktionen, deren Namen und Funktionsweisen sich an die C++ Vektorbibliothek anlehnen:
cvec cv_append(cvec *pcv, const void *seq, size_t cnt);
cvec cv_assign(cvec *pcv, const void *seq, size_t cnt);
const void *cv_at(ccvec cv, size_t pos);
size_t cv_capacity(ccvec cv);
cvec cv_clear(cvec cv);
bool cv_empty(ccvec cv);
cvec cv_erase(cvec cv, size_t pos, size_t cnt);
bool cv_for_each(cvec cv, size_t pos, size_t cnt, cv_for_each_proc_t callback_func, void *user_param);
cvec cv_insert(cvec *pcv, size_t pos, const void *seq, size_t cnt);
const void *cv_pop_back(cvec cv);
cvec cv_push_back(cvec *pcv, const void *elem);
cvec cv_reserve(cvec *pcv, size_t capa);
cvec cv_resize(cvec *pcv, size_t size, const void *elem);
cvec cv_shrink_to_fit(cvec *pcv);
size_t cv_size(ccvec cv);
cvec cv_update_size(cvec cv, size_t size);

Beschreibungen der Funktionen mit deren Parametern und Rückgabewerten finden sich im cvec.h Header.






*** cstrvec - Zusammenspiel von cstr und cvec ***
abhängig von cstr und cvec

Nachdem ich begonnen hatte an @BAGZZlash 's Anregung zuarbeiten, ein Split und Join für die cstr Lib zu implementieren, ist mir sofort bewusst geworden, warum etwa C++ solche Funktionen nicht für dessen string Klasse vorgesehen hat. Sie passen einfach nicht ;) Der Grund ist einfach: Es wird beides benötigt, eine String- und eine Vektor-Implementation. Um die cstr und die cvec Libs nicht grundsätzlich voneinander abhängig zu machen, habe ich eine zusätzliche Mini-Bibliothek geschrieben. Diese ist allerdings von den beiden anderen Bibliotheken abhängig.



Die cstrvec Lib beinhaltet Funktionen um Strings aus einem Vector zu verketten oder einen String an Delimitern in einen Vector zu teilen ...
cstr cs_join(ccvec strvec, const char *delims); und
cvec cs_split(ccstr cs, const char *delims, size_t maxtok);

... und um eine Datei zeilenweise in einen Vector einzulesen.
cvec cstrvec_rdlines(FILE *stream, size_t maxlines);

Für die Spezialform "Vektor aus Strings"gibt es noch die zusätzliche Funktion
void cstrvec_free(ccvec strvec);
die die Freigabe der cstr Elemente und die Freigabe des cvec Containers vereint.

Aus demselben Grund gibt es drei weitere Macros.
PTRTOCSTR(_cvec)
MAKECSTRPTR(...)
MAKECCSTRPTR(...)
Diese sind Spezialisierungen für cstr der PTRTO und MAKEPTR Macros aus der cvec Bibliothek.

Für Strings basierend auf wchar_t sind analog die entsprechenden Funktionen und Macros implementiert:
cstrw csw_join(ccvec strwvec, const wchar_t *delimsw);
cvec csw_split(ccstrw csw, const wchar_t *delimsw, size_t maxtok);
cvec cstrwvec_rdlines(FILE *stream, size_t maxlines);
void cstrwvec_free(ccvec strwvec);
PTRTOCSTRW(_cvec)
PTRTOCCSTRW(_cvec)
MAKECSTRWPTR(...)

Um einen String aus einem Vector von Bytes zu erzeugen, bzw. umgekehrt, stehen folgende Funktionen zur Verfügung:
cstr cs_from_cvbyte(ccvec cv);
cvec cvbyte_from_cs(ccstr cs);

Detaillierte Beschreibungen finden sich im cstrvec.h Header.





Die main.c enthält Testcode und zeigt Beispiele, wie mit Funktionen und Macros zu arbeiten ist.
Natürlich könnt ihr jederzeit Fragen stellen, Fehler reporten, Verbesserungen vorschlagen oder allgemeines Feedback geben. Würde mich freuen.
  • Like
Reaktionen: Lowl3v3l
Autor
german
Downloads
272
Aufrufe
954
Erstellt am
Letzte Bearbeitung
Bewertung
5,00 Stern(e) 1 Bewertung(en)

Weitere Ressourcen von german

Letzte Aktualisierungen

  1. Speichermanagement und Codeformatierung

    In v1.2 ist der maximal allokierte Speicher an PTRDIFF_MAX statt an SIZE_MAX angelehnt. Das ist...
  2. 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...
  3. Funktion cs_init_rdentirefile hinzu

    Theoretisch könnte man das Einlesen einer kompletten Datei statt mit cs_init_rdentirefile auch...
Oben Unten