38. Dynamische Strings

Dynamische Speicherverwaltung erlaubt uns z.B., eine etwas großzügigere Art von String zu implementieren. Der folgende Code stellt sozusagen Konstruktor und Destruktor für eine Art Klasse dar:

typedef struct estr_s {
  int length, cCompatible;
  char *content;
} eStr;

eStr *eStr_new(int len)
{
  eStr *eString = malloc(sizeof(eStr));

  if (eString) {
    eString->length = len;
    if (!(eString->content =
      malloc((len+1)*sizeof(char)))) {
      free(eString); return NULL;
    }
    memset(eString->content, 0, len+1);
    eString->cCompatible = 0;
  }
  return eString;
}

void eStr_free(eStr *eString)
{
  free(eString->content);
  free(eString);
}

eStr *eStr_fromString(char *cString)
{
  eStr *eString=eStr_new(strlen(cString));
  if (eString) {
    strcpy(eString->content, cString);
    eString->cCompatible = 1;
  }
  return eString;
}

Anmerkungen:

1. Wir definieren uns zunächst einen struct, der die zum Datentyp gehörenden Daten versammelt. Das ist hier nicht schwer: Zunächst wollen wir uns die Länge des Strings merken, dann brauchen wir einen Zeiger auf die Zeichen, aus denen der String besteht, und schließlich richten wir uns noch ein Flag ein, in dem wir notieren, ob der String Nullzeichen enthält oder nicht (wenn nicht, ist cCompatible wahr, und einige Standard-Stringoperationen könnten auf die Zeichenfolgen in content funktionieren).
2. Wir schreiben vor alle Namen, die wir hier verwenden, ein eStr_. Sinn davon ist, name space clashes zu verhindern, dass also unser “Modul” (noch ist es das nicht) Namen überschreibt, die die Programmiererin, die das Modul benutzt, selbst verwendet.
3. Wir haben zunächst einen ganz schlichten Konstruktor eStr_new, der einen leeren (mit Nullen gefüllten) String einer bestimmten Länge erzeugt. memset ist dabei eine in string.h deklarierte Funktion, die ein Stück Speicher (memory – der Zeiger darauf steht im ersten Argument, seine Länge in chars im letzten) mit dem zweiten Argument füllt. Wir legen im content-Feld ein char mehr als nötig an, weil wir “gute Strings” C-kompatibel speichern wollen. Dieser Konstruktor ist so noch nicht zu viel gut.
4. Die Funktion prüft den Rückkehrwert von malloc sorgfältig. Das ist bei so recht bescheidenen Anforderungen vielleicht overkill, da moderne Maschinen mit virtuellem Speicher praktisch immer ein paar Byte übrig haben; man sollte sich das dennoch angewöhnen, weil am Ende des Tages eben doch schief geht, was schief gehen kann, und wenigstens unsere Basisfunktionen solide arbeiten sollten. Die dauernden Tests werden einem früher oder später auf die Nerven gehen – Pythons Exceptions sind kein überflüssiges Sprachelement.
5. Wenn das Allozieren des Speichers für die Zeichen (eString->content) nicht geklappt hat, wird auch der für den eString selbst reservierte Speicher freigegeben. Wird sowas vergessen, entsteht ein memory leak, ein Leck, durch das auf Dauer immer mehr Speicher verschwindet. Memory leaks gehören zu den häufigsten Fehlern in C-Programmen.
6. Der Konstruktor eStr_FromString erzeugt einen eStr aus einem normalen C-String. Dabei folgen wir der C-Konvention, das String-Ende durch ein Null zu markieren, um “normale” Strings C-kompatibel zu halten. Eine Eigenschaft dieser Art sollte natürlich – am besten direkt beim typedef – dokumentiert werden. Wir haben also jetzt schon zwei Konstruktoren für unsere “Klasse” – das ist auch in wirklichen statisch typisierten objektorientierten Sprachen so: Wenn man polymorphes Verhalten haben will (Funktionen verhalten sich unterschiedlich je nach den Typen ihrer Argumente), muss für jeden Typ, den man behandeln will, eine eigene Methode her. C++ und Java erlauben aber, dass verschiedene Funktionen gleiche Namen haben, solange sie verschiedene Prototypen haben.
7. eStr_Free gibt den von einem eStr belegten Speicher frei. Dazu muss man in zwei Schritten vorgehen, und die Reihenfolge dieser Schritte ist wichtig, weil man Speicher, den man freigegeben hat, nicht mehr anfassen darf, auch nicht lesend.
8. Wir haben es hier mit einem wenigstens konzeptionell objektorientierten Design zu tun: Es gibt Konstruktoren, die neue Objekte zurückgeben, und einen Destruktor, der Objekte wieder zerstört. In Python muss man sich in der Regel um das Freigeben der Objekte keine Sorgen machen. Für Fälle, in denen die Freigabe eines Objekts spezielle Operationen braucht (für ein Datei-Objekt könnte das etwa das Schließen der Datei sein), kann man aber die __del__-Methode eines Objekts definieren, die dann die Funktion eines Destruktors übernimmt. Man muss allerdings etwas vorsichtig sein, was man in der __del__-Methode treibt, weil der Interpreter bei ihrer Ausführung in einem etwas prekären Zustand sein kann. Mehr dazu in der Python Language Reference.

Ein paar Funktionen, die mit diesen eStrs arbeiten:

eStr *eStr_add(eStr *op1, eStr *op2)
{
  eStr *dest=eStr_new(op1->length+op2->length);
  if (dest) {
    memcpy(dest->content, op1->content, op1->length);
    memcpy(dest->content+op1->length, op2->content,
      op2->length);
  }
  return dest;
}

int eStr_findChar(eStr *eString, char c, int count)
{
  int i;
  for (i=0; i<eString->length; i++) {
    if (eString->content[i]==c) {
      if (!--count) { return i; }
    }
  }
  return -1;
}

Anmerkungen:

1. Wir haben zunächst eine Funktion, die zwei eStrs verkettet, ganz ähnlich dem +-Operator für Strings in Python. Auch hier ist der Code so gemacht, dass die Funktion NULL zurückgibt, wenn etwas schief geht. memcpy funktioniert ähnlich wie memset, nur wird eben eine Anzahl Bytes (im letzten Argument) vom Speicher, auf den das zweite Argument zeigt, in den Speicher, auf den das erste Argument zeigt kopiert.
2. eStr_findChar ist eine Primitivvariante von Pythons find-Methode für Strings (sie kann nur einzelne Chars finden). Bemerkenswert ist allenfalls, wie implementiert ist, dass man nach dem count-ten Auftreten des chars fragen kann.
3. Um den Code auf die Folie zu kriegen, musste ich etwas von meinem üblichen Indentation Style abweichen. Das ist nicht zur Nachahmung empfohlen.

Um daraus ein Programm zu machen, müssen noch die nötigen Header eingebunden (das sind in dem Fall string.h und stdlib.h sowie stdio.h für das folgende main) und z.B. eine Main-Funktion dieser Art dazugeschrieben werden:

int main(void)
{
  eStr *kuck=eStr_fromString("Kuckuck, ");
  eStr *ruft=eStr_fromString("rufts aus dem Wald");
  eStr *dest1, *dest2;

  dest1 = eStr_add(kuck, kuck);
  dest2 = eStr_add(dest1, ruft);
  eStr_free(dest1);
  printf("%s %d\n", dest2->content, eStr_findChar(dest2, 'u', 3));
  return 0;
}

Dieses Main lässt auch schon ähnen, dass wir ohne weiteres nicht den Komfort von Python werden erreichen können. Einerseits muss für die Stringverkettung natürlich extra eine Funktion aufgerufen werden – der +-Operator lässt sich nicht für eStrs umdefinieren (in C++ und übrigens auch in Python geht dieses so genannte operator overloading – vgl. den Exkurs unten). Andererseits, und das wiegt deutlich schwerer, müssen wir uns selbst drum kümmern, Strings, die wir nicht mehr brauchen, freizugeben.

Man kann sich durchaus Systeme überlegen, die nicht mehr benutzte Daten eigenständig freigeben (Garbage Collectors) – aber das ist relativ kompliziert. Eine Möglichkeit wäre, regelmäßig über alle allozierten Blöcke zu laufen und nachzusehen, ob das Programm noch irgendwelche Pointer auf diese Blöcke hält und sie, wenn nicht, freizugeben. Problematisch dabei ist, dass man einen Überlick sowohl über die allozierten Blöcke als auch die Pointer des Programms haben muss, und dass die Garbage Collection eine ganze Weile dauern kann. Dennoch funktionieren die meisten Garbarge Collectors nach diesem Prinzip, so etwa die von üblichen Java- oder Lisp-Systemen.

Python hat traditionell ein etwas anderes Verfahren verwendet, nämlich Refcounting. Die Idee dabei ist, dass man, wenn man sich einen Pointer auf ein Objekt besorgt, eine dem Objekt zugeordnete Variable, nämlich den Reference Count, inkrementiert, und sie wieder dekrementiert, wenn man den Pointer wieder wegnimmt. Wenn der Refcount eines Objekts auf Null sinkt, wird es freigegeben. Problematisch dabei ist vor allem, dass es einige Disziplin braucht, um die Buchhaltung nicht zu vergessen – in Python selbst merkt man davon natürlich nichts, das Python-System und seine Erweiterungen in C werden davon aber sehr wohl belastet.

Ein anderes Problem des Refcounting sind zirkuläre Referenzen. Das ist in folgenem Python-Code zu sehen:

class Circ:

  def __init__(self):
    self.myself = self

Wenn man nun c=Circ() sagt, so ist c.myself eine zweite Referenz das so erzeugte Objekt, dessen Refcount jetzt also zwei ist. Wenn wir später c=None sagen, sollte das Objekt eigentlich freigegeben werden, weil wir damit jede Möglichkeit verloren haben, es nochmal zu benutzen (das Programm hält keine Referenz mehr darauf). Leider ist sein Refcount aber danach immer noch 1, es wird also nicht freigegeben, weil es eben eine Referenz auf sich selbst hat.

Solche Fälle treten nicht sehr häufig auf, und wenn, lassen sie sich meist mit weak references entschärfen (Modul weakref) – so man denn merkt, dass etwas nicht stimmt und wo es nicht stimmt.

Weil sich in komplexere Programme dann aber doch gerne mal (vor allem indirekte) zirkuläre Referenzen einschleichen, haben neuere Python-Fassungen auch einen “richtigen” Garbage Collector; wer darüber mehr wissen will, sei auf die Dokumentation zum gc-Modul verwiesen.