C Dynamische Datenstrukturen unter Linux: Struct-Padding, Linked Lists & Funktionszeiger
Erstellt: 07.11.2026 Aktualisiert: 07.11.2026
Management Summary: Im Gegensatz zu modernen Hochsprachen mit integrierten Standard-Collections (wie Javas
ArrayListoder Pythonsdict) liefert C ab Werk keinerlei dynamische Datenstrukturen mit. C-Systemprogrammierung auf Enterprise-Niveau bedeutet, Datenstrukturen maßgeschneidert auf die Hardware-Gegebenheiten des Prozessors zu konstruieren. Dieses Dokument bildet Teil 2.1 (Fortgeschritten) unseres C-Curriculums: Wir analysieren CPU-Speicher-Alignment und Struct-Padding (offsetof), entwickeln generische doppelt verkettete Listen mitvoid*, entkoppeln Programmlogik über Funktionszeiger und bauen einen praxiserprobten Circular Ring Buffer mit Watermark-Alarmen.
-
Alignment & Struct-Padding
Unsichtbare Padding-Bytes des Compilers mit
offsetof()aufdecken, Cache-Lines optimieren und 33 % RAM einsparen. -
Funktionszeiger & Callbacks
Funktionszeiger-Syntax entzaubern, Algorithmen von Datensätzen entkoppeln und schlanke Finite State Machines (FSM) bauen.
-
Generische Verkettete Listen
Typunabhängige Datenspeicherung mit
void*implementieren, Head/Tail-Referenzen verwalten und $O(n)$-Speicherfreigabe via Callback-Destruktor meistern. -
Circular Ring Buffer Lab
Einen fest allokierten FIFO-Ringpuffer für Streaming-I/O mit Watermark-Schwellenwert-Alarmen und null Reallocations konstruieren.
1. Speicher-Alignment, Hardware-Grenzen & Struct-Padding
Moderne 64-Bit-Prozessoren (x86_64 und aarch64) lesen physischen RAM nicht byteweise, sondern rufen Daten immer in 64-Bit (8-Byte) ausgerichteten Speicherwörtern über den Speicherbus ab.
Liegt eine Variable (beispielsweise ein 8-Byte großes uint64_t) quer über einer 8-Byte-Grenze, müsste die CPU zwei Buszyklen ausführen und das Ergebnis bitweise zusammenfügen – was massive Latenz verursacht. Um dies zu verhindern, fügt der C-Compiler automatisch unsichtbare Padding-Bytes zwischen den Mitgliedern einer Struktur ein.
%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
subgraph Bad ["❌ Unoptimiertes Struct (24 Bytes Gesamtgröße)"]
direction TB
B1["Slot 1: uint8_t a (1 Byte)<br/>⚠️ + 7 Bytes unsichtbares Padding!"]
B2["Slot 2: uint64_t b (8 Bytes)<br/>Auf 8-Byte-Grenze ausgerichtet"]
B3["Slot 3: uint8_t c (1 Byte)<br/>⚠️ + 7 Bytes Tail-Padding!"]
B1 --> B2 --> B3
end
subgraph Good ["✅ Optimiertes Struct (16 Bytes Gesamtgröße)"]
direction TB
G1["Slot 1: uint64_t b (8 Bytes)<br/>Auf 8-Byte-Grenze ausgerichtet"]
G2["Slot 2: uint8_t a (1 Byte) + uint8_t c (1 Byte)<br/>+ 6 Bytes Tail-Padding"]
G1 --> G2
endPadding mit offsetof() (<stddef.h>) sichtbar machen
Erstelle die Datei ~/c_struct_lab/padding_demo.c:
#include <stdio.h>
#include <stdint.h>
#include <stddef.h>
// 1. Ungünstig sortiertes Struct: Große und kleine Typen wechseln sich ab
typedef struct {
uint8_t flag_a; // 1 Byte (+ 7 Bytes Padding!)
uint64_t zaehler; // 8 Bytes (liegt bei Offset 8)
uint8_t flag_b; // 1 Byte (+ 7 Bytes Tail-Padding!)
} UnoptimiertesNode;
// 2. Optimiertes Struct: Absteigend nach Typgröße sortiert
typedef struct {
uint64_t zaehler; // 8 Bytes (Offset 0)
uint8_t flag_a; // 1 Byte (Offset 8)
uint8_t flag_b; // 1 Byte (Offset 9, + 6 Bytes Tail-Padding)
} OptimiertesNode;
int main(void) {
printf("=== STRUCT PADDING INSPECTOR (x86_64) ===\n\n");
printf("1. UnoptimiertesNode Größe: %zu Bytes\n", sizeof(UnoptimiertesNode));
printf(" - Offset von flag_a: %zu\n", offsetof(UnoptimiertesNode, flag_a));
printf(" - Offset von zaehler: %zu (7 Bytes davor verschwendet!)\n", offsetof(UnoptimiertesNode, zaehler));
printf(" - Offset von flag_b: %zu\n\n", offsetof(UnoptimiertesNode, flag_b));
printf("2. OptimiertesNode Größe: %zu Bytes\n", sizeof(OptimiertesNode));
printf(" - Offset von zaehler: %zu\n", offsetof(OptimiertesNode, zaehler));
printf(" - Offset von flag_a: %zu\n", offsetof(OptimiertesNode, flag_a));
printf(" - Offset von flag_b: %zu\n", offsetof(OptimiertesNode, flag_b));
return 0;
}
gcc -std=c17 -Wall -Wextra padding_demo.c -o padding_demo
./padding_demo
Erkenntnis: Durch schlichtes Umgruppieren der Strukturmitglieder schrumpft die Größe von 24 Bytes auf 16 Bytes. Bei Millionen von Datensätzen im RAM bedeutet das eine direkte Ersparnis von 33,3 % Arbeitsspeicher und eine spürbar bessere Ausnutzung der CPU-L1-Caches!
Wann Padding verboten ist: __attribute__((packed))
In Netzwerkprotokollen (wie IP- oder TCP-Headern) oder Dateiformaten dürfen keine Padding-Bytes existieren, weil die Bytes direkt so über die Leitung übertragen werden. Dies erzwingt man mit GCCs Attribut __attribute__((packed)):
typedef struct __attribute__((packed)) {
uint8_t version_ihl; // 1 Byte (IP-Version & Header-Länge)
uint8_t type_of_service;
uint16_t total_length; // 2 Bytes
uint16_t packet_id; // 2 Bytes
uint16_t flags_fragment; // 2 Bytes
uint8_t ttl; // 1 Byte
uint8_t protocol; // 1 Byte
uint16_t checksum; // 2 Bytes
uint32_t src_ip; // 4 Bytes
uint32_t dst_ip; // 4 Bytes
} IPv4HeaderWireFormat; // Exakt 20 Bytes im Netzwerkstream!
Performance-Verlust bei Packed Structs
Verwende __attribute__((packed)) niemals leichtfertig für normale In-Memory-Datenstrukturen! Auf Architekturen wie ARM können nicht-ausgerichtete Speicherzugriffe zu Hardware-Fehlern führen oder deutliche Performance-Einbrüche verursachen. Nutze es ausschließlich für Serialisierung und Wire-Protokolle.
2. Funktionszeiger: Speicherlayout, Syntax & Standardbibliotheks-Mechanik (qsort)
Um fortgeschrittenes C auf System-Ebene zu beherrschen, muss man die Vorstellung ablegen, Funktionen seien abstrakte Syntaxkonstrukte. In einer kompilierten ELF-Binärdatei liegen ausführbare Maschinencode-Befehle im .text-Codesegment des physikalischen Arbeitsspeichers.
Ein Funktionszeiger (Function Pointer) ist schlicht eine vorzeichenlose 64-Bit-Adressvariable, die auf das erste Byte dieses ausführbaren Maschinenbefehlsblocks verweist.
%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
subgraph VirtuellerSpeicher ["Virtueller Prozess-Adressraum"]
subgraph TextSegment [".text Codesegment (Ausführbar / Schreibgeschützt)"]
FN_ADD["0x00401120: addiere()<br/>push %rbp<br/>mov %rsp, %rbp<br/>add %esi, %edi<br/>ret"]
FN_MUL["0x00401140: multipliziere()<br/>push %rbp<br/>imul %esi, %edi<br/>ret"]
end
subgraph StackFrame ["Stack Frame (Lokale Variablen)"]
PTR["Variable: op_ptr<br/>Adresse: 0x7ffd08<br/>Wert: 0x00401120"]
end
end
PTR ==>|"Speichert Einstiegsadresse von"| FN_ADDRuft die CPU op_ptr(10, 20) auf, generiert der Compiler einen indirekten Sprungbefehl (call *%rax in x86_64-Assembler), wodurch der Hardware-Befehlszähler (RIP) direkt an die Speicheradresse 0x00401120 springt.
1. Die Operator-Präzedenzfalle: Die Syntax verstehen
In C bindet der Funktionsaufruf-Operator () stärker als der Dereferenzierungs-Operator *. Daraus entsteht eine klassische Verwechslungsgefahr:
int *berechne(int a, int b);
Deklariert eine normale Funktion, die einen Zeiger auf einintzurückgibt (int *).int (*berechne)(int a, int b);
Die Klammern erzwingen die Bindung: deklariert eine Zeigervariable namensberechne, die auf eine Funktion zeigt, welche zwei Ganzzahlen erwartet und einintliefert.
#include <stdio.h>
#include <stdint.h>
int32_t addiere(int32_t a, int32_t b) { return a + b; }
int32_t multipliziere(int32_t a, int32_t b) { return a * b; }
int main(void) {
// 1. Deklaration ohne typedef
int32_t (*operation)(int32_t, int32_t) = addiere;
printf("Direkter Aufruf via Zeiger: %d\n", operation(10, 5));
// Zeiger zur Laufzeit auf eine andere Funktion umbiegen!
operation = multipliziere;
printf("Umgebogener Aufruf via Zeiger: %d\n", operation(10, 5));
// 2. Professionelles C: Signaturen immer via typedef kapseln
typedef int32_t (*MatheBinaerOp)(int32_t, int32_t);
MatheBinaerOp op_tabelle[] = { addiere, multipliziere };
printf("Aufruf aus Sprungtabelle: %d\n", op_tabelle[0](20, 30));
return 0;
}
2. Der universitäre Standard: Generisches Sortieren mit qsort()
Das Paradebeispiel für Funktionszeiger in der C-Standardbibliothek ist qsort() (<stdlib.h>). Die Funktion implementiert den Quicksort-Algorithmus und kann jeden beliebigen Datentyp in-place sortieren:
Weil qsort nicht wissen kann, ob der Speicher Zahlen, Strings oder komplexe Server-Strukturen enthält, lagert es die Ordnungsrelation an eine Vergleichs-Callback-Funktion aus:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
typedef struct {
char hostname[32];
uint32_t ram_mb;
double cpu_last;
} NodeMetriken;
// Vergleichs-Callback: Sortierung nach RAM absteigend
int vergleiche_ram_absteigend(const void *a, const void *b) {
const NodeMetriken *node_a = (const NodeMetriken *)a;
const NodeMetriken *node_b = (const NodeMetriken *)b;
if (node_b->ram_mb > node_a->ram_mb) return 1;
if (node_b->ram_mb < node_a->ram_mb) return -1;
return 0;
}
// Vergleichs-Callback: Sortierung nach CPU-Last aufsteigend
int vergleiche_cpu_aufsteigend(const void *a, const void *b) {
const NodeMetriken *node_a = (const NodeMetriken *)a;
const NodeMetriken *node_b = (const NodeMetriken *)b;
if (node_a->cpu_last > node_b->cpu_last) return 1;
if (node_a->cpu_last < node_b->cpu_last) return -1;
return 0;
}
int main(void) {
NodeMetriken cluster[3] = {
{ "db01.lan", 32768, 1.85 },
{ "app01.lan", 16384, 0.42 },
{ "gw01.lan", 8192, 0.15 }
};
printf("=== Sortierung nach RAM (Absteigend) ===\n");
qsort(cluster, 3, sizeof(NodeMetriken), vergleiche_ram_absteigend);
for (int i = 0; i < 3; i++) {
printf(" %-12s | RAM: %5u MB | Last: %.2f\n", cluster[i].hostname, cluster[i].ram_mb, cluster[i].cpu_last);
}
printf("\n=== Sortierung nach CPU-Last (Aufsteigend) ===\n");
qsort(cluster, 3, sizeof(NodeMetriken), vergleiche_cpu_aufsteigend);
for (int i = 0; i < 3; i++) {
printf(" %-12s | RAM: %5u MB | Last: %.2f\n", cluster[i].hostname, cluster[i].ram_mb, cluster[i].cpu_last);
}
return 0;
}
3. Callbacks, Inversion of Control & Finite State Machines (FSM)
Warum entwerfen Systemarchitekten Software rund um Callbacks? Der theoretische Grundsatz lautet Inversion of Control (IoC), umgangssprachlich als Hollywood-Prinzip bekannt:
„Rufen Sie nicht uns an, wir rufen Sie an.“
In der traditionellen Programmierung steuert die aufrufende Stelle den Ablauf. In einer ereignisgesteuerten Architektur liefert ein Kernmodul den Mechanismus (z. B. Netzwerkpaket empfangen, Timer abgelaufen), während die Applikation die Geschäftslogik (Policy) über Funktionszeiger injiziert.
Das Zustandsautomaten-Problem: Warum switch-Blöcke kollabieren
In Netzwerkprotokollen (TCP, HTTP, TLS) wechselt ein System basierend auf eintreffenden Ereignissen zwischen diskreten Zuständen:
%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
IDLE["1. IDLE<br/>Wartet auf Verbindung"]
HANDSHAKE["2. HANDSHAKE<br/>Parst Header"]
STREAMING["3. STREAMING<br/>Überträgt Nutzdaten"]
CLOSED["4. CLOSED<br/>Gibt Ressourcen frei"]
IDLE ==>|"EV_CONNECT"| HANDSHAKE
HANDSHAKE ==>|"EV_HEADER_OK"| STREAMING
HANDSHAKE -.->|"EV_ERROR"| CLOSED
STREAMING ==>|"EV_EOF"| CLOSEDEin naiver Ansatz nutzt verschachtelte switch(state)- und switch(event)-Verzweigungen. Bei 15 Zuständen und 10 Events entstehen 150 Verzweigungen. Zur Laufzeit führt dies zu massiven Branch Mispredictions in der CPU-Pipeline, die die Befehlsausführung spürbar ausbremsen.
Tabellengesteuerte FSM: $O(1)$-Zustandsabarbeitung
Linux-Kernel-Treiber und Server wie Nginx ersetzen Verzweigungen durch eine Zustandsübergangs-Tabelle: eine zweidimensionale Matrix aus Funktionszeigern:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>
typedef enum {
ZUSTAND_IDLE = 0,
ZUSTAND_HANDSHAKE,
ZUSTAND_STREAMING,
ZUSTAND_CLOSED,
ZUSTAND_ANZAHL
} FsmZustand;
typedef enum {
EREIGNIS_VERBINDEN = 0,
EREIGNIS_DATEN_DA,
EREIGNIS_TRENNEN,
EREIGNIS_ANZAHL
} FsmEreignis;
struct SitzungsKontext;
// Signatur des Funktionszeigers für Zustandsübergänge
typedef FsmZustand (*FsmUebergangsHandler)(struct SitzungsKontext *ctx);
typedef struct SitzungsKontext {
int sitzungs_id;
FsmZustand aktueller_zustand;
uint32_t uebertragene_bytes;
} SitzungsKontext;
// Konkrete Übergangs-Handler
FsmZustand on_verbinden(SitzungsKontext *ctx) {
printf("[Sitzung %d] Verbindung hergestellt -> Wechsel zu HANDSHAKE\n", ctx->sitzungs_id);
return ZUSTAND_HANDSHAKE;
}
FsmZustand on_daten(SitzungsKontext *ctx) {
ctx->uebertragene_bytes += 4096;
printf("[Sitzung %d] 4096 Bytes empfangen (Gesamt: %u) -> STREAMING\n", ctx->sitzungs_id, ctx->uebertragene_bytes);
return ZUSTAND_STREAMING;
}
FsmZustand on_trennen(SitzungsKontext *ctx) {
printf("[Sitzung %d] Trennungssignal empfangen -> CLOSED\n", ctx->sitzungs_id);
return ZUSTAND_CLOSED;
}
FsmZustand on_ungueltig(SitzungsKontext *ctx) {
printf("[Sitzung %d] Ungültiges Ereignis in Zustand %d! Verworfen.\n", ctx->sitzungs_id, ctx->aktueller_zustand);
return ctx->aktueller_zustand;
}
// Zweidimensionale Übergangsmatrix: Zustand x Ereignis -> Handler
// Konstante O(1)-Tabellenabfrage OHNE CPU-Verzweigung!
static const FsmUebergangsHandler uebergangs_tabelle[ZUSTAND_ANZAHL][EREIGNIS_ANZAHL] = {
[ZUSTAND_IDLE] = { [EREIGNIS_VERBINDEN] = on_verbinden, [EREIGNIS_DATEN_DA] = on_ungueltig, [EREIGNIS_TRENNEN] = on_ungueltig },
[ZUSTAND_HANDSHAKE] = { [EREIGNIS_VERBINDEN] = on_ungueltig, [EREIGNIS_DATEN_DA] = on_daten, [EREIGNIS_TRENNEN] = on_trennen },
[ZUSTAND_STREAMING] = { [EREIGNIS_VERBINDEN] = on_ungueltig, [EREIGNIS_DATEN_DA] = on_daten, [EREIGNIS_TRENNEN] = on_trennen },
[ZUSTAND_CLOSED] = { [EREIGNIS_VERBINDEN] = on_ungueltig, [EREIGNIS_DATEN_DA] = on_ungueltig, [EREIGNIS_TRENNEN] = on_ungueltig }
};
// Event Dispatcher Engine
void fsm_ausloesen(SitzungsKontext *ctx, FsmEreignis ereignis) {
FsmUebergangsHandler aktion = uebergangs_tabelle[ctx->aktueller_zustand][ereignis];
if (aktion) {
ctx->aktueller_zustand = aktion(ctx);
}
}
int main(void) {
SitzungsKontext sitzung = { .sitzungs_id = 101, .aktueller_zustand = ZUSTAND_IDLE, .uebertragene_bytes = 0 };
printf("=== FINITE STATE MACHINE ENGINE INITIALISIERT ===\n\n");
fsm_ausloesen(&sitzung, EREIGNIS_VERBINDEN); // IDLE -> HANDSHAKE
fsm_ausloesen(&sitzung, EREIGNIS_DATEN_DA); // HANDSHAKE -> STREAMING
fsm_ausloesen(&sitzung, EREIGNIS_DATEN_DA); // STREAMING -> STREAMING
fsm_ausloesen(&sitzung, EREIGNIS_TRENNEN); // STREAMING -> CLOSED
printf("\nSitzung %d hat Endzustand (%d) erreicht. Gesamtbytes: %u\n",
sitzung.sitzungs_id, sitzung.aktueller_zustand, sitzung.uebertragene_bytes);
return 0;
}
gcc -std=c17 -Wall -Wextra fsm_protokoll_engine.c -o fsm_protokoll_engine
./fsm_protokoll_engine
4. Generische Doppelt Verkettete Listen (Doubly Linked Lists)
Arrays liegen in einem zusammenhängenden Speicherblock und lassen sich nicht ohne teures Umkopieren vergrößern. Eine Doppelt Verkettete Liste allokiert jedes Element einzeln auf dem Heap und verknüpft sie über next- und prev-Zeiger.
%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart LR
HEAD["Head-Pointer"] --> N1["Knoten A<br/>data: 0x10<br/>prev: NULL"]
N1 <==>|"next / prev"| N2["Knoten B<br/>data: 0x20"]
N2 <==>|"next / prev"| N3["Knoten C<br/>data: 0x30<br/>next: NULL"]
TAIL["Tail-Pointer"] --> N3Implementierung: Generische Liste (dlist.h & dlist.c)
Durch die Verwendung von void *data kann die Liste beliebige Datentypen (Zahlen, Strings oder komplexe Structs) aufnehmen, ohne Code duplizieren zu müssen. Beachte, wie die Destruktor-Funktion dlist_destroy das Callback-Muster via Funktionszeiger nutzt, das wir gerade in Abschnitt 2 und 3 kennengelernt haben, um die Daten der Knoten typunabhängig und sauber zu deallokieren!
#pragma once
#include <stddef.h>
#include <stdbool.h>
typedef struct DListNode {
void *data;
struct DListNode *prev;
struct DListNode *next;
} DListNode;
typedef struct {
DListNode *head;
DListNode *tail;
size_t anzahl;
} DList;
// Funktionsprototypen
DList *dlist_create(void);
bool dlist_push_back(DList *list, void *data);
bool dlist_push_front(DList *list, void *data);
void *dlist_pop_front(DList *list);
void dlist_destroy(DList *list, void (*free_data_fn)(void *));
#include <stdlib.h>
#include "dlist.h"
DList *dlist_create(void) {
DList *list = malloc(sizeof(DList));
if (!list) return NULL;
list->head = NULL;
list->tail = NULL;
list->anzahl = 0;
return list;
}
bool dlist_push_back(DList *list, void *data) {
if (!list) return false;
DListNode *node = malloc(sizeof(DListNode));
if (!node) return false;
node->data = data;
node->next = NULL;
node->prev = list->tail;
if (list->tail) {
list->tail->next = node;
} else {
list->head = node;
}
list->tail = node;
list->anzahl++;
return true;
}
bool dlist_push_front(DList *list, void *data) {
if (!list) return false;
DListNode *node = malloc(sizeof(DListNode));
if (!node) return false;
node->data = data;
node->prev = NULL;
node->next = list->head;
if (list->head) {
list->head->prev = node;
} else {
list->tail = node;
}
list->head = node;
list->anzahl++;
return true;
}
void *dlist_pop_front(DList *list) {
if (!list || !list->head) return NULL;
DListNode *node = list->head;
void *data = node->data;
list->head = node->next;
if (list->head) {
list->head->prev = NULL;
} else {
list->tail = NULL;
}
free(node);
list->anzahl--;
return data;
}
void dlist_destroy(DList *list, void (*free_data_fn)(void *)) {
if (!list) return;
DListNode *aktuell = list->head;
while (aktuell) {
DListNode *weiter = aktuell->next;
if (free_data_fn && aktuell->data) {
free_data_fn(aktuell->data);
}
free(aktuell);
aktuell = weiter;
}
free(list);
}
Vollständiges Anwendungsbeispiel: Die doppelt verkettete Liste in Aktion
Erstelle die Datei ~/c_struct_lab/dlist_demo.c, um alle Listenoperationen mit Server-Strukturen in einer ausführbaren main()-Funktion zu testen:
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include "dlist.h"
typedef struct {
int id;
char hostname[32];
uint32_t ram_mb;
} ServerNode;
// Callback zur Freigabe der Heap-Daten des Knotens
void free_server_node(void *daten) {
ServerNode *node = (ServerNode *)daten;
free(node);
}
ServerNode *create_server(int id, const char *hostname, uint32_t ram) {
ServerNode *srv = malloc(sizeof(ServerNode));
if (!srv) return NULL;
srv->id = id;
snprintf(srv->hostname, sizeof(srv->hostname), "%s", hostname);
srv->ram_mb = ram;
return srv;
}
int main(void) {
printf("=== GENERISCHE DOPPELT VERKETTETE LISTE DEMO ===\n\n");
// 1. Liste initialisieren
DList *cluster = dlist_create();
// 2. Elemente am Ende einhängen mit dlist_push_back
dlist_push_back(cluster, create_server(1, "srv01.prod.lan", 16384));
dlist_push_back(cluster, create_server(2, "srv02.prod.lan", 32768));
// 3. Wichtiges Element am Anfang einhängen mit dlist_push_front
dlist_push_front(cluster, create_server(0, "gateway.prod.lan", 8192));
printf("Liste enthält %zu Server-Knoten.\n", cluster->anzahl);
// 4. Vorwärtsdurchlauf (Head -> Tail über next-Zeiger)
printf("\nVorwärtsdurchlauf (Head -> Tail):\n");
DListNode *aktuell = cluster->head;
while (aktuell) {
ServerNode *s = (ServerNode *)aktuell->data;
printf(" [#%d] %-18s | RAM: %5u MB\n", s->id, s->hostname, s->ram_mb);
aktuell = aktuell->next;
}
// 5. Rückwärtsdurchlauf (Tail -> Head über prev-Zeiger)
printf("\nRückwärtsdurchlauf (Tail -> Head):\n");
aktuell = cluster->tail;
while (aktuell) {
ServerNode *s = (ServerNode *)aktuell->data;
printf(" [#%d] %-18s | RAM: %5u MB\n", s->id, s->hostname, s->ram_mb);
aktuell = aktuell->prev;
}
// 6. Erstes Element entnehmen mit dlist_pop_front
printf("\nKopf-Element entnehmen mit dlist_pop_front...\n");
ServerNode *entnommen = (ServerNode *)dlist_pop_front(cluster);
if (entnommen) {
printf(" Entnommen: [#%d] %s (Verbleibende Knoten: %zu)\n", entnommen->id, entnommen->hostname, cluster->anzahl);
free_server_node(entnommen);
}
// 7. Liste und alle verbleibenden Knoten sauber deallokieren
printf("\nListe zerstören und gesamten Speicher freigeben...\n");
dlist_destroy(cluster, free_server_node);
printf("Cluster-Liste sauber beendet – 0 Speicherlecks.\n");
return 0;
}
gcc -std=c17 -Wall -Wextra dlist.c dlist_demo.c -o dlist_demo
./dlist_demo
5. Hands-On Lab: Ein generischer High-Performance Circular Ring Buffer
Ein Ringpuffer (Circular Buffer) ist eine Queue fester Größe mit head- und tail-Indizes, die zyklisch umbrechen. Die Vorteile:
1. Keine dynamischen Allokationen während des laufenden Betriebs ($O(1)$ push und pop).
2. Optimale CPU-Cache-Lokalität (Elemente liegen zusammenhängend im RAM).
3. Perfekt für Streaming-I/O: Audio-Puffer, Netzwerk-Paketqueues und Ringpuffer in Gerätetreibern.
%%{init: {'flowchart': {'wrappingWidth': 600}}}%%
flowchart TB
subgraph Ring ["Fester Speicherbereich (Kapazität: 8 Slots)"]
direction LR
S0["[0]"] --- S1["[1]"] --- S2["[2]"] --- S3["[3]"] --- S4["[4]"] --- S5["[5]"] --- S6["[6]"] --- S7["[7]"]
end
TAIL["Tail-Zeiger (Lese-Index)<br/>Wandert bei Pop weiter"] -.-> S1
HEAD["Head-Zeiger (Schreib-Index)<br/>Wandert bei Push weiter"] ==> S5Implementierung von ring_buffer.c mit Watermark-Event
Erstelle die Datei ~/c_struct_lab/ring_buffer.c:
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <stdbool.h>
#include <string.h>
typedef struct {
uint8_t *puffer;
size_t kapazitaet;
size_t element_groesse;
size_t head;
size_t tail;
size_t anzahl;
// Callback bei Überschreiten von >= 80% Füllstand
void (*on_watermark_alert)(size_t anzahl, size_t kapazitaet);
} RingBuffer;
RingBuffer *rb_create(size_t kapazitaet, size_t element_groesse, void (*alarm_fn)(size_t, size_t)) {
RingBuffer *rb = malloc(sizeof(RingBuffer));
if (!rb) return NULL;
rb->puffer = malloc(kapazitaet * element_groesse);
if (!rb->puffer) {
free(rb);
return NULL;
}
rb->kapazitaet = kapazitaet;
rb->element_groesse = element_groesse;
rb->head = 0;
rb->tail = 0;
rb->anzahl = 0;
rb->on_watermark_alert = alarm_fn;
return rb;
}
bool rb_push(RingBuffer *rb, const void *element) {
if (rb->anzahl == rb->kapazitaet) {
return false; // Puffer ist voll!
}
void *ziel = rb->puffer + (rb->head * rb->element_groesse);
memcpy(ziel, element, rb->element_groesse);
rb->head = (rb->head + 1) % rb->kapazitaet; // Zyklischer Umbruch
rb->anzahl++;
// 80% Füllstandsschwelle prüfen
if (rb->on_watermark_alert && (rb->anzahl * 100 / rb->kapazitaet) >= 80) {
rb->on_watermark_alert(rb->anzahl, rb->kapazitaet);
}
return true;
}
bool rb_pop(RingBuffer *rb, void *ziel) {
if (rb->anzahl == 0) {
return false; // Puffer ist leer!
}
void *quelle = rb->puffer + (rb->tail * rb->element_groesse);
memcpy(ziel, quelle, rb->element_groesse);
rb->tail = (rb->tail + 1) % rb->kapazitaet; // Zyklischer Umbruch
rb->anzahl--;
return true;
}
void rb_destroy(RingBuffer *rb) {
if (!rb) return;
free(rb->puffer);
free(rb);
}
// Alarm-Funktion für Füllstand
void mein_puffer_alarm(size_t belegt, size_t gesamt) {
printf("⚠️ [WARNUNG: PUFFER-FÜLLSTAND] Auslastung bei %zu / %zu Slots (>= 80%%)!\n", belegt, gesamt);
}
int main(void) {
// Ringpuffer für 10 Integers anlegen
RingBuffer *rb = rb_create(10, sizeof(int), mein_puffer_alarm);
printf("=== CIRCULAR RING BUFFER DEMO ===\n");
// 9 Elemente einfügen -> löst bei Element 8 den 80% Alarm aus
for (int i = 1; i <= 9; i++) {
int wert = i * 10;
printf("Schreibe Element: %d\n", wert);
rb_push(rb, &wert);
}
printf("\nLese 4 Elemente aus dem Puffer:\n");
for (int i = 0; i < 4; i++) {
int gelesener_wert = 0;
if (rb_pop(rb, &gelesener_wert)) {
printf("Gelesen: %d\n", gelesener_wert);
}
}
printf("\nSchreibe 3 neue Elemente (nutzen zyklisch die frei gewordenen Slots):\n");
for (int i = 100; i <= 102; i++) {
printf("Schreibe Element: %d\n", i);
rb_push(rb, &i);
}
printf("\nAlle verbliebenen Elemente auslesen:\n");
int rest = 0;
while (rb_pop(rb, &rest)) {
printf("Restwert entnommen: %d\n", rest);
}
rb_destroy(rb);
printf("Puffer sauber freigegeben (0 Speicherlecks).\n");
return 0;
}
gcc -std=c17 -Wall -Wextra ring_buffer.c -o ring_buffer
./ring_buffer
6. Architektur-Vergleich: Linked List vs. Ring Buffer
| Metrik | Doppelt Verkettete Liste | Circular Ring Buffer |
|---|---|---|
| Speicherallokation | Dynamisch ($1 \times \text{malloc}$ pro Knoten) | Ein einzelner Block vorab allokiert |
| Einfügen / Löschen | $O(1)$ an Kopf und Ende | $O(1)$ an Kopf und Ende |
| Speicher-Overhead | Hoch ($16\text{ Bytes}$ Zeiger pro Knoten!) | Null Zeiger-Overhead pro Datenelement |
| CPU-Cache-Lokalität | Gering (Knoten im Heap verstreut) | Hervorragend (aufeinanderfolgende RAM-Zellen) |
| Maximale Kapazität | Nur durch gesamten Systemspeicher begrenzt | Feste, vorab definierte Kapazität |
| Optimaler Einsatz | Dynamische Sammlungen unbekannter Größe | Hochfrequente Queues, Audio, Paket-Streaming |
Nächste Schritte & Empfehlungen
Setze deinen Weg durch das C-Curriculum fort:
-
Teil 2.2: POSIX Dateisystem & Syscalls
Dateideskriptoren, ungepuffertes I/O, atomares Dateisperren mit flock und Unix-Daemonisierung meistern.
-
Teil 1.1: Kern-Syntax & Speichermodell
Pointers, Adressräume, Stack vs. Heap Allokation und feste Bitbreiten festigen.
-
Linux Prozessverwaltung & Syscalls
Laufende ELF-Prozesse, Signale (
SIGTERM/SIGKILL),strace-Syscall-Traces und/proc-Dateisysteme analysieren.