Inhalt

• Speicher
  • Wo liegt was?
  • Stack versus Heap
  • Manuelle Speicherverwaltung des Heaps
• Zeiger ("pointer")
  • Typsicherer Zugriff auf Speicheradressen

Beispiel zu Laufzeit Stack (Run-Time Stack oder kurz einfach Stack)

In C kann die Fibonacci Funktion wie folgt ausgedrückt werden.

int fib(int n){
 int f1, f2;
 if (n<=1) return 1;
 f1=fib(n-1);
 f2=fib(n-2);
 return f1+f2;
}

Was ergibt der Aufruf fib(3)? Wie geschieht der Zugriff auf lokale Variablen wie f1. Wo liegen diese Variablen im Speicher?

Die Funktionsaufrufabfolge kann durch einen Stack simuliert werden. Das Laufzeitsystem benutzt einen Run-Time Stack (Laufzeitstack oder einfach Stack) zur Verwaltung von Funktionsaufrufen Dieser Run-Time Stack kann mittels Debugger beobachtet werden

Aufgabe: Setzen Sie geignete break points und verfolgen Sie die Berechung von fib(3).

Eine weitere Möglichkeit zur Verfolgung des Stacks ist in dem einfach nachfolgende Funktionsaufrufe eingerückt auf der Konsole ausgegben werden.

Betrachte Variante fibLevel(int n, int level) (Details siehe unten). Parameter level zählt mit wieviele geschachtelte Aufrufe stattfanden.

    call fibLevel(4)

       call fibLevel(3)

          call fibLevel(2)

             call fibLevel(1)

             call fibLevel(0)

          call fibLevel(1)

       call fibLevel(2)

          call fibLevel(1)

          call fibLevel(0)

    call fibLevel(3)

       call fibLevel(2)

          call fibLevel(1)

          call fibLevel(0)

       call fibLevel(1)

Jeder Aufruf (call) von fibLevel legt einen neuen Speicherbereich auf dem Stack an.

In diesem Speicherbereich von fib werden die lokalen Variable verwaltet (die Parameter n und level als auch f1 und f2). Zusätzliche Informationen sind Rücksprungadresse (des Aufrufers).

Fall innerhalb von fib weitere Funktionsaufrufe stattfinden, wird weiterer Speicher auf dem Stack angelegt.

Der Speicherbereich belegt durch einen fib Aufruf wird "deaktiviert" (freigegben) bei Rücksprung (return).

Jetzt ist klar, wieso der gesamte Bereich zur Verwaltung von Funktionen ein Stack ist. Die Funktionsaktivierung und -deaktivierung entspricht genau den Zugriffen auf einen Stack.

Funktionsaufruf = push.

Funktionsrücksprung = pop.

Run-Time Stack und Heap

Der Speicherbereich bei der Ausführung des Programmes ist wie folgt aufgeteilt.

 CODE
 STATIC DATA
 STACK
 ...
 HEAP

• CODE enthält den übersetzten und gelinkten Source Code
• STATIC DATA enthält alle statischen Datenanteile
• STACK ist der Speicherbereich für lokale Daten (Variablen definiert in Funktionen, Funktionsparameter und Rückgabewerte)
• HEAP ist der Speicherbereich für dynamische Daten, die explizt vom Programm allokiert werden
• STACK und HEAP befinden sich in der Regel an gegenseitigen Enden des Speicherbereichs (wo genau hängt von Compiler/Platform ab). Beide Bereiche wachsen und schrumpfen zur Laufzeit.

Der STACK Speicherbereich wird automatisch verwaltet (durch das Laufzeit/Run-Time System):

• Solange die Funktion aktiv ist, ist der von der Funktion belegte Stackbereich aktiv.

• Sobald die Funktion verlassen wird, wird der von der Funktion belegte Stackbereich "deaktiviert". Dies bedeutet, der Speicherbereich kann anderweitig verwendet werden.

In C unterliegt der HEAP Speicherbereich der Kontrolle des Programmieres (manuelle Verwaltung). Heapspeicher muss explizit angefordert werden via malloc (new in C++) und explizit freigegeben werden via free (delete in C++).

Im Vergleich. In Java gilt:

• Alle Objekte die mit new angelegt werden liegen auf dem Heap.

• Alle weiteren (primitiven) Datentypen liegen auf dem Stack.

Beachte: Der Bereich belegt durch einen Stack ist in der Regel limitiert. Extrem geschachtelte Funktionsaufrufe wie auch rekursive Funktionen können zu einem "Stack overflow" führen.

Speicheradressen und Run-Time Stack

Folgende Variante der Fibonacci Implementierung, erlaubt es uns zu beobachten an welchem Ende des Speichers sich der Stack befindet.

int fib2(int n) {
 int f1, f2;
 int* nPtr;
 printf("fib2(%d)\n",n);
 nPtr = &n;
 printf("&n = %ld \n",(long int)nPtr);
 if (n<=1) return 1;
 f1=fib2(n-1);
 f2=fib2(n-2);
 return f1+f2;
}

• &n liefert Adresse der Variable n
• Dargestellt durch Pointer auf einen int Wert.
• Zur Ausgabe wird der Pointer in einen long int Wert gecastet

Komplettes fib Beispiel

#include <stdio.h>

// Macros
// Debugausgaben koennen so einfach an-/ausgeschaltet werden.
// Abschalten: Macro undefiniert lassen.
// Anschalten: Macro definieren.

// #define FIBRET(l,n,x)  printFibRet(l,n,x)
#define FIBRET(l,n,x)

// Weitere Variante.
// Macro fuer die konditionale Kompilierung, siehe unten.
#define FIBCALL

int fib(int n){
 int f1, f2;
 if (n<=1) return 1;
 f1=fib(n-1);
 f2=fib(n-2);
 return f1+f2;
}


// Ausgaben zur Illustration/Debuggen

// Annahme (Invariante): level >= 0
void printLevel(int level) {
  int i;
  printf("\n");
  for (i = 3*level; i >= 0; i--)
     printf(" ");
}

void printFibCall(int level, int n) {
  printLevel(level);
  printf("call fibLevel(%d)", n);
}

void printFibRet(int level, int n, int f) {
  printLevel(level);
  printf("%d = fibLevel(%d)", f, n);
}

int fibLevel(int n, int level){
 int f1, f2;

 printf("\n");
 if (n<=1) return 1;

 #ifdef FIBCALL
 printFibCall(level, n-1);
 #endif
 f1=fibLevel(n-1, level+1);
 FIBRET(level, n-1, f1);

 #ifdef FIBCALL
 printFibCall(level, n-2);
 #endif
 f2=fibLevel(n-2, level+1);
 FIBRET(level, n-2, f2);
 return f1+f2;
}

// Variante um zu verfolgen in welche (Speicher)Richtung der Stack waechst.
int fib2(int n) {
 int f1, f2;
 int* nPtr;
 printf("fib2(%d)\n",n);
 nPtr = &n;
 printf("&n = %ld \n",(long int)nPtr);
 if (n<=1) return 1;
 f1=fib2(n-1);
 f2=fib2(n-2);
 return f1+f2;
}

int main() {
  int x;

  x = fibLevel(5,1);
  

}

Zeiger/Pointer

Programmiersprachen verwalten Variablen im Speicher. Z.B. eine short int Variable liegt an einer bestimmten Speicheradresse, z.B. X, und belegt 2 Bytes Speicher (so definiert im Fall von short int).

Der Speicher wird in der Regel Byte-weise adressiert. Deshalb sind die Speicheradressen X und X+1 belegt durch das short int.

C/C++ erlaubt Zugriff auf Variablen via Speicheradressen. Wir bezeichnen eine Speicheradresse auch als Referenz.

C/C++ unterstützt deshalb Zeiger Variablen in den Speicheradressen verwaltet werden können. Im Englischen auch Pointer genannt.

Im folgenden betrachten wir.

• Zeigerdeklaration

• Zeigeroperationen

  • Dereferenzierung

  • Adressoperator

  • Zeigerarithmetik

Zeigerdeklaration

Betrachte folgende Variablendeklaration.

unsigned short int x = 2;

• Variable vom Typ unsigned short int gefüllt mit Wert 2

• Wo findet sich der Wert?

• Irgendwo im Speicher, z.B. an der Adresse 1200

      -------------------
1200  |00000000|00000010|
      __________________  

• In C/C++ Zugriff auf Speicherbereich via Zeiger (Pointer)

Wir wiederholen die Deklaration von i und deklarieren einen Zeiger (Zeiger Variable).

  unsigned short int i;
  unsigned short int* iPtr;

• i ist eine Variable vom Typ unsigned short int
  • i speichert unsigned short int Werte
  • i benötigt 2 Bytes Speicher
• iPtr ist eine Variable vom Type unsigned short int*
  • iPtr speichert Adressen von unsigned short int Variablen
  • iPtr benötigt 4 Bytes Speicher (32Bit Architektur)
• Umgangssprachlich
  • iPtr ist ein unsigned short int Pointer

So könnte der Speicher belegt sein. An Adresse 1200 liegt i. An Adresse 2000 liegt iPtr. Der Inhalt beider Variablen ist 0 (unsere Annahme).

      -------------------
1200  |00000000|00000000|
      __________________


      -------------------------------------
2000  |00000000|00000000|00000000|00000000|
      _____________________________________

Wertebereich und Speicherplatz

Der Wertebereich von unsigned short int ist 0..2$^16$-1. Soviele verschiedene positive Werte passen in 2 Bytes.

Wertebereich von Speicher? Architektur abhängig.

32-Bit Architektur. Die Hardware verwendet 4 Bytes zur Adressierung von Speicher. 64-Bit Architektur. Die Hardware verwendet 8 Bytes zur Adressierung von Speicher.

Z.B. auf 32-Bit Architektur können ca. 4GB Speicher verwaltet werden. Wertebereich von 0..2$^32$-1.

Wieviel Speicherplatz benötigt ein Zeiger? Abhängig von Architektur. 32-Bit Architektur werden 4 Bytes verwendent.

Wir nehmen in der Regel 32-Bit Architektur an. Auf heutiger moderner Hardware gilt 64-Bit Architektur.

Weitere Beispiele

  unsigned short int i;
  unsigned short int* iPtr;
  int j;
  int* jPtr;
  float f;
  float* fPtr;

• iPtr, jPtr und fPtr sind Zeiger
• Werte von Zeigern sind Adressen (4 Bytes gross auf 32Bit Architektur)
• Durch Typdeklaration int* wissen wir welche Werte an dieser Adresse stehen

Schreibweisen

  unsigned short int* iPtr;
  int *jPtr;
  float * fPtr;

Adressoperator/Zeiger Initialisierung

  int i = 0;
  int* iPtr = &i;

• i initialisiert mit 0
• Werte von iPtr sind Adressen
• & Adressoperator
• &i liefert die Adresse von i

Wichtig. Folgende Variante wird vom Compiler nicht akzeptiert.

  float f = 1.0;
  int* iPtr = &f;

&f liefert eine Adresse.

f ist eine Fliesskommazahl. Deshalb verweist/referenziert &f auf eine Fliesskommzahl.

Eine Zuweisung an einen Zeiger vom Typ int* ist nicht erlaubt.

Dereferenzierung/Zeiger Zugriff

  unsigned short int i;
  unsigned short int* iPtr;

  i = 0;
  iPtr = &i;

  i = *iPtr;

  *iPtr = i + 3;

• * Verweisoperator (Derefenzierung)
• *iPtr liefert Variable auf die iPtr verweist
• Kann links oder rechts von Zuweisung verwendet werden

Wichtig. Die semantische Ausführung von *iPtr ist wie folgt.

1. Hole Adresse gespeichert in iPtr.

2. Interpretiere diese Adresse mit Hilfe von unsigned short int* iPtr.

3. In unserem Fall, interpretiere 2 Bytes beginnend mit Adresse iPtr als unsigned short int.

Zeiger Arithmetik

Motivation

Betrachte

int i;

i = 2;

i++;

i--;

i = i + 5;

• i++ berechnet den Nachfolger.

• i-- den Vorgänger.

• i + 5 den 5-ten Nachfolger.

Das ganze bezogen auf den jeweils akutellen Wert in.

Nachfolger von 2 ist 3. Vorgänger von 3 ist 2.

Betrachte arithmetische Operationen im Kontext von Zeigern.

int* p;

p = &i;

p++;

p--;

p = p + 5;

Vorgänger, Nachfolger von p?

p verwaltet Speicheradressen. Falls in p der Wert (Speicheradresse) 2000 ist, dann sollte nach p++ in p der Wert 2001 sein?

NEIN. So, ist nicht die Semantik für Zeiger.

Beachte: Jeder Zeiger ist mit Typinformation versehen. Z.B. int* p;.

Bedeutet p referenziert eine Speicheradresse an der sich ein int Wert befindet. Annahme: int belegt 2 Bytes und in p ist der Wert 2000.

Nach Ausführung von p++ befindet sich in p der Wert 2002. Wieso 2002? Dies ist die Speicheradresse an der sich der nachfolgende Integerwert befindet.

Beispiel

  int i = 0;
  int* iPtr = &i;

  i++;
  iPtr++;
  i = i + 5;
  iPtr = iPtr + 5;

• iPtr++ inkrementiere Zeiger
  • iPtr = Adresse X
  • Nach Ausführung iPtr++
    
  • iPtr = Adresse X + sizeof(int)
• iPtr = iPtr + 5
  • iPtr = Adresse Y
  • Nach Ausführung
  • iPtr = Adresse Y + 5 * sizeof(int)

sizeof liefert die Grösse eines Datentyps in Bytes.

Weiteres Beispiel

  int i = 0;         // 1.
  int* iPtr = &i;    // 2.

  i++;               // 3.
  iPtr++;            // 4.
  i = i + 5;         // 5.
  iPtr = iPtr + 5;   // 6.

Byte-weise Adressierung, int der Größe 2 Bytes

1. Variable i hat den Wert 0
   • Annahme: Speicher der Variable i an Adresse 1602
2. Variable iPtr hat den Wert 1602
3. Variable i hat den Wert 1
4. Variable iPtr hat den Wert 1604
   • Zähle um ein int Element hoch, also zwei Bytes
5. Variable i hat den Wert 6
6. Variable iPtr hat den Wert 1614
   • Zähle um fünf int Element hoch, also 10 Bytes

Zeiger Arithmetik Allgemein

• T* ptr
• ptr = Adresse Z
• ptr + 7
• Adresse Z + 7 * sizeof(T)

Zeiger und Arrays

In C/C++ gilt.

Array Deklaration legt Speicher an.

int a[5] = { 0, 1, 2, 3, 4 };

5 Integerwerte. Diese Integerwerte liegen hintereinander im Speicher, so dass ein konstanter Zugriff auf die einzelnen Elemente möglich ist.

D.h. a[0] ist vor a[1] usw.

Dann ist folgendes möglich.

int* ptr;

ptr = &a[0];

p++;

*ptr = 2;

Zugriff auf Arrayelemente via Zeiger!

Konvention:

Arrayname a ist konstanter Zeiger auf erstes Element an der Adresse &a[0].

Weiteres Beispiel

  int i;
  int a[5] = {0, 1, 2, 3, 4}; 
  int* ptr;

  // Array Name bezeichnet Adresse des ersten Elements
  ptr = a;
  for(i=1; i<5; i++) {
    printf("%d ",*ptr); 
    ptr++; 
  }

• Ausgabe?

• Aufgabe: Umformulierung als while Schleife ohne Laufvariable i

• Beachte: a äquivalent zu &a[0]

Mehrdimensionale Arrays

  int i;
  int a[3][2] = { {0,1},{2,3},{4,5}}; 
  int* ptr;
  int (*p)[2];

  p = a;
  ptr = &a[0][0];
  for(i=1; i<7; i++) {
    printf("%d ",*ptr); 
    ptr++; 
  }

Beachte:

• int a[3][2] legt jeweils 3 hintereinander befindliche 1-dimensionale Arrays der Grösse 2 an.

• ptr = a geht nicht.

• a referenziert das erste Element. Dies ist ein 1-dimensionales Array!

• p ist ein Zeiger auf ein 1-dimensionale Arrays der Grösse 2.

Zeiger Programmcode zusammengefasst (bis hierher)

#include <stdio.h>


void schreibweisen() {
  unsigned short int* iPtr;
  int *jPtr;
  float * fPtr;
}

void testAusgabe () {
  int i = 1;
  int* iPtr;

  printf("i=%d \n", i);  

  printf("Adresse von i = %ld \n", (long int)&i); 
  
  iPtr = &i; 

  printf("i=%d \n",*iPtr);

}

// Zeiger sind typsicher. Man kann aber das Typsystem aushebeln.
void testEvil() {
  int i = 1;
  int* iPtr;
  float f = 1.0;
  float* fPtr;

  fPtr = (float*)(&i);

  i = 100000;
  iPtr = (int*)(i);
  // iPtr = &i;

  printf("\n *iPtr = %d, *fPtr = %f", *iPtr, *fPtr);
}


void testZeigerArithemtik() {
  int* p;
  int i;

  i = 2;

  i++;

  i--;

  i = i + 5;

  p = &i;

  p++;

  p--;

  p = p + 5;

}


void testAusgabeZeigerArithemtik() {
  int i = 0;
  int* iPtr = &i;

  printf(" %d %ld \n", i, (long int)iPtr);
  i++;
  iPtr++;
  printf(" %d %ld \n", i, (long int)iPtr);  
  i = i + 5;
  iPtr = iPtr + 5;
  printf(" %d %ld \n", i, (long int)iPtr);  
}


void testZeigerArray() {
  int a[5] = { 0, 1, 2, 3, 4 };
  int* ptr;
  ptr = &a[0];
  ptr++;
  printf("%d \n",*ptr);
}


// Arrayname a ist konstanter Zeiger auf erstes Element an der Adresse &a[0].
void testZeigerArray2() {
  int a[5] = { 0, 1, 2, 3, 4 };
  int* ptr;
  ptr = a;
  ptr++;
  printf("%d \n",*ptr);
}


void testZeigerArray3() {
  int i;
  int a[5] = {0, 1, 2, 3, 4}; 
  int* ptr;

  // Array Name bezeichnet Adresse des ersten Elements
  ptr = a;
  for(i=1; i<5; i++) {
    printf("%d ",*ptr); 
    ptr++; 
  }
}

void testMultiDimArray() {
  int i;
  int a[3][2] = { {0,1},{2,3},{4,5}}; 
  int* ptr;
  int (*p)[2];

  p = a;
  ptr = &a[0][0];
  for(i=1; i<7; i++) {
    printf("%d ",*ptr); 
    ptr++; 
  }
}


int main() {

  testEvil();
  // testAusgabe();

}

Zeiger - Am Beispiel der Referenzübergabe

Zeiger - Referenzübergabe

• Parameterübergabe in C/C++ ist "call-by value"
• Effizienzproblem im Fall von "grossen" Datentypen

struct big {
  int a[100];
  int x;
};

struct big incX(struct big b2) {
  b2.x = b2.x + 1;
  return b2;
}

int main() {
  struct big b;
  b = incX(b);
}

• Lösung 1: Entpacke "x", inkrementiere einzeln, Aufwendig und Fehleranfällig
• Lösung 2: Benutze "call-by reference" mit Hilfe von Zeigern

Zeiger - Referenzübergabe (2)

Referenzübergabe = call-by reference

struct big {
  int a[100];
  int x;
};

void incXByReference(struct big* bPtr) {
  *bPtr.x = *bPtr.x + 1;
}

int main() {
  struct big b;
  incXByReference(&b);
}

• Übergabe von Referenz (Adresse im Speicher)
• "in-place update": Originalwert wird direkt verändert
• Kein Kopieren notwendig

Zeiger - Rückgabe via Referenz

int inc(int x) { return x+1; }

void inc2(int x, int* r) { *r = x+1; }

int main() {
  int x = 1;
  int result;

  x = inc(x);
  inc2(x, &result);
}

• Übergebe Speicherbereich für Resultat
• Konvention
  • (Pointer)Parameter die Rückgabewerte repräsentieren kommen zuletzt

Zeigernotation durch Macros versteckt

#include <stdio.h>

#define CallByRef(t,x) t* x

#define DeRef(x) *x

#define PassByRef(x) &x



int inc(int x) {
     x++;
     return x;
}

void incByRef(int x, CallByRef(int,y)) {
  x++;
  DeRef(y) = x;
}

int main() {

  int n = 1;
  int r;

  incByRef(n,PassByRef(r));

  printf("n = %d \n r = %d \n",n, r);

}

Die Magie erklärt

#define PassByRef(x) &x

// incByRef(n, &r);
incByRef(n,PassByRef(r));

Übergabe der Adresse von r.

Der Operator & liefert die Adresse (im Speicher).

#define CallByRef(t,x) t* x

// void incByRef(int x, int* y)
void incByRef(int x, CallByRef(int,y))

Zweiter Parameter y ist ein "Zeiger". Notation int*.

Wertebereich sind Adressen.

Genauer Adressen welche auf Integerwerte verweisen.

#define DeRef(x) *x

// *y = x;
DeRef(y) = x;

Zugriff auf Wert via Adresse.

Operator * verweist auf Wert der an dieser Adresse liegt.

Auf linker Seite der Zuweisung = wird der Wert dann durch rechte Seite überschrieben.

Strings in C

In C wird ein String durch eine Sequenz von alphanumerischen Zeichen repräsentiert. Ein String kann daher durch ein Array von Zeichen repräsentiert werden. Arrays in C haben keine Längeninformation (wieviele Elemente befinden sich im Array).

Im Fall von Strings würde das bedeuteten der User müsste die Längeninfo selbst verwalten. Deshalb gilt folgende Konvention in C.

Das Ende des Strings wird gekennzeichnet durch das Nullterminator Zeichen (Ascii code 0):

'\0'

Es gibt zwei prinzipielle Möglichkeiten einen String mit fester Länge zu initialisieren.

char s1[] = "Hallo";
char s2[] = { 'H', 'a', 'l', 'l', 'o' };

Im ersten Fall wird die "String" Notation verwendet. Der Compiler erkennt dies als String und fügt automatisch den Nullterminator hinzu. Das Array s1 hat deshalb die Länge 6.

Im zweiten Fall wird ein Array s2 von Zeichen initialisiert. Der Nullterminator fehlt. Dies muss der User selber explizit hinzufügen. Falls also s2 als String verwendet werden soll, muss die Deklaration wie folgt geändert werden.

char s2[] = { 'H', 'a', 'l', 'l', 'o', `\0` };

Deshalb am besten die "String" notation zur Initialiserung verwenden. Folgende Variante sollen sie nicht verwenden.

char* s3 = "Hallo";

Es wird nur ein Zeichen allokiert.

Da Arrays durch Zeiger dargestellt werden, ist ein String nichts anderes als ein Zeiger auf das erste Zeichen. Das Ende ist markiert durch den Nullterminator.

Folgende Funktion berechnet die Länge eines Strings.

int len(char* s) {
  int i = 0;
  while(*s != '\0') {
    s++;
    i++;
  }
  return i;
}

Mehr zu Strings folgt in Labor- und Scheinaufgaben.

Generischer Zeiger

Bisher

int i,j;
int* p;      // p Zeiger auf Speicherbereich welcher as int interpretiert wird

p = &i;
j = *p;

Generischer Zeiger

void* anyPtr;

• Zeiger auf Wert eines nicht genau definierten Typs
• Vor Zugriff muss Typ genau spezifiziert werden

Hinweis: Vergleich zu Object in Java.

int i,j;
anyPtr = &i;
j = * ((int*) anyPtr);

*anyPtr nicht möglich, weil Typ nicht bekannt.

* ((float*) anyPtr) erlaubt aber gefährlich, weil Speicherlayout von int und float verschieden.

Anwendungsbeispiel: scanf

Betrachte

int i;
float f;

int* p = &i;
float* q = &f;

scanf("%d", p);

scanf("%f", q);

Welchen Funktionsprototypen hat scanf?

void scanf(char*, int*);

void scanf(char*, float*):

C unterstützt kein Overloading! Obiges deshalb nicht möglich. Deshalb wird folgendes verwendet.

void scanf(char*, void*);

Jeder Zeiger kann in einen generischen Zeiger umgewandelt werden. Mit Hilfe der im Formatstring kodierten Typinformation, wird der generische Zeiger Typ-spezifisch angepasst.

Manuelle Speicherverwaltung

• In bisherigen Beispielen, aller Speicher wurde statisch allokiert.
• Dynamische Datenstrukturen (Array flexibler Größe, verkettete Liste etc) benötigen dynamische Speicherallokation.
• In C ist die Speicherverwaltung unter Kontrolle des Programmierers (keine garbage collection):
• Manuelle Speicherverwaltung
  • Hole Speicher: malloc
  • Gebe Speicher frei: free

// Teil der standard library
// Falls verwendet, folgender include notwendig
// #include <stdlib.h>

  void *malloc(size_t number_of_bytes)

  void free(void *memblock);

Vergleich zu Java:

• new in Java berechnet automatisch wieviele Bytes benötigt werden.

• free wird automatisch vom Java Laufzeitsystem durchgeführt.

Manuelle Speicherverwaltung Beispiel

char* initString(int n) {
  char* p = malloc((n+1) * sizeof(char));
  // Generischer Zeiger automatisch gecastet auf char*
  char* q = p;
  int i;
  for(i = 0; i < n; i++, q++) {
    *q = ' ';
  }
  *q = '\0';

  return p;
}

• String variabler Länge n
• Allokation von n+1 Bytes
• Initialiserung mit Leerzeichen

Was alles schief gehen kann

• NULL Dereferenzierung
• Fehlende Speicherfreigabe
• Zu häufige Speicherfreigabe
• ...

NULL Dereferenzierung

  char c;
  char* s;
  c = *s;

• Annahme s mit NULL (0) initialisiert

• Zugriff *s schlägt fehl

Segmentation fault: 11

• Aber Initwert oft zufällig!

NULL Dereferenzierung Beispiele

• Falsche Reihenfolge

  char c;
  char* s;
  c = *s;
  s = initString(5);

Regel: Dereferenzierung nur falls Zeiger auf allokierten Speicher verweist.

• Speicher voll, initString liefert NULL

  char c;
  char* s;
  s = initString(5);
  c = *s;

• Aufgabe: Wie kann man initString sicher machen?

Speicherfreigabe

• Vergessen $\Rightarrow$ Speicherleck
  • Bleibt oft unbemerkt

int main() {
  char* s;
  s = initString(5);
}

Regel: Zu jedem "alloc" ein "free".

• Mehrfache Freigabe des gleichen Speicherbereichs $\Rightarrow$ Ausnahme zur Laufzeit

int main() {
  char* s1;
  char* s2;
  s1 = initString(5);
  s2 = s1;
  free(s1);
  free(s2);
}

Zeiger auf Zeiger

#include <stdio.h>
int main() {
  int i = 0;
  int* p = &i;
  int** pp = &p;
  int*** ppp = &pp;
 
  *(*(*ppp)) = 1; 
  printf(" %d \n", i);
}

• ***ppp Kurzform von *(*(*ppp))

Zeiger und Strukturen

#include <stdio.h>

struct position {
  int x;
  float y;
};

int main() {
    struct position p = {1,3.0}; 
    struct position* ptr = &p;
    (*ptr).x = 3;
    ptr->y = 1.0;  
    return 0;
}

• Zugriff auf Struktur via (*ptr)
• Zugriff auf Strukturelement via .x
• Notationelle Abkürzung ptr->
• (*ptr) und ptr-> sind gleichwertig

Zeiger und Verschachtelte Strukturen

struct position {
  int x;
  float y;
};

struct node {
   struct position pos;
   struct node* next; // Pointer auf Struktur
   // verschachtelte Struktur
};

typedef struct node* NodePtr; // Abkuerzung

• NULL (0) spezieller Wert (Adresse)
• In unserem Fall, beschreibt Ende der Liste von Strukturen

+=======+           +=======+  
| node1 | --next--> | node2 |  --next--> ... --next--> NULLL  
+=======+           +=======+ 

Notation am Beispiel

Betrachte das Fibonacci Beispiel.

enum  Status {
  Full=0,
  Empty=1
};
struct Fib {
  int fib;
  enum Status status;
};

typedef struct Fib* FibPtr;

struct FibArray {
  FibPtr f;
  int len;
};

Folgende Deklarationen sind gegeben.

int n;
FibPtr f1;
struct Fib* f2;
structFibArry* fa;

• f1 und f2 sind Zeiger vom gleichen Typ.

• Folgende Schreibweisen sind äquivalent

fa->f[n].status

(*fa).f[n].status

fa->(*(f+n)).status

fa->(f+n)->status

Funktionspointer

  int (*pf)(int);

• Zeiger auf Funktion mit Parameter int und Rückgabe int
• Adress-/Verweisoperator wie gehabt
• Beispiel:

int f(int x) { return x+1; }
int main () {
  int (*pf)(int); 
  pf = &f;
  printf("f(1) = %d \n",f(1));
  printf("(*pf)(1) = %d \n",(*pf)(1));  
}

Anwendungen von Funktionspointer

• Call-backs
• Generische Funktionen
• Beispiel generische Sortierfunktion
  • Aus stdlib.h
  • size_t ist ein unsiged Typ, gross genug um die Größen von Datentypen zu berechen (Plattformabhängig)
  • Hier notwendig, weil wir die Größe des Typs des zu sortierenden Arrays benötigen

void qsort(void *base, 
           size_t num_elements , 
           size_t element_size, 
           int (*compare)(void const *, 
                          void  const *));

Weitere Beispiele

#include <stdio.h>

typedef int (*intFunc)(int);

void mapInt(int* p, int len, intFunc f) {
 int i;
 for(i=0; i<len; i++)
   p[i] = (*f)(p[i]);
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };
   mapInt(x,5,&inc);
   mapInt(x,5,&square);

   printf("%d", x[1]);
   
   return 0;
}

Implizite Konversion (in neustem Standard).

#include <stdio.h>


void mapInt(int* p, int len, int f(int)) {
 int i;
 for(i=0; i<len; i++)
   p[i] = f(p[i]);
}


int inc(int x) { return x+1; }
int square(int x) { return x*x; }


int main() {
   int x[5] = { 1,2,3,4,5 };
   mapInt(x,5,inc);
   mapInt(x,5,square);

   printf("%d",x[0]);
   return 0;
}

Zusammenfassung

Teil 1:

• IO printf/scanf
• Einfache Datentypen
• Kontrollstrukturen
• Komplexe Datenstrukturen

Teil 2:

• Funktionen
• Header und Source Files
• Präprozessor und Makros

Teil 3:

• Zeiger und Speicher

Die wichtigsten Punkte von C wurden damit behandelt.