String beliebiger Länge einlesen / Problem mit Funktion

was passiert wenn die rückgabe != NULL und p != orig dann wird doch der speicher von orig nie wieder freigegeben oder

ISO/IEC 9899:1999 7.20.3.4 (2) schrieb:

The realloc function deallocates the old object pointed to by ptr and returns a pointer to a new object that has the size specified by size. The contents of the new object shall be the same as that of the old object prior to deallocation, up to the lesser of the new and old sizes. Any bytes in the new object beyond the size of the old object have indeterminate values.

danke, wieder was dazu gelernt *kiss*

chmbw

Hallo,

erstmal vielen Dank für die tollen Antworten!

Um das nochmal klarzustellen: Der Ansatz bzw. mein Gedankengang war vollkommen in Ordnung (von der vergessenen Stringterminierung mal abgesehen), ich habe nur das Problem einer ziemlich schlechten Laufzeit weil ich realloc einfach viel zu oft aufrufe und somit Rechenzeit verballer?!

Da ich mir aber nicht ganz sicher bin, ob ich den Code von seldon wirklich verstanden habe (trotzdem herzlichen Dank!!!), hab ich ihn einfach mal mit einigen Kommentaren / Fragen versehen:

char *get_line(FILE *stream) {
  size_t const CHUNKSIZE = 128;  // CHUNKSIZE ist mein Puffer und wird in 
                                 // size_t deklariert, weil er die Größe
  size_t n = 0;                  // meines Speicherbereichs (Puffer) beschreibt
  char *buf = NULL, *pos = NULL; 

  if(feof(stream)) return NULL;  //Wenn mein Stream/datei keine Zeichen enthält 
                                 //wird beendet
  do {
    char *p;               //*p wird eingeführt, weil wenn realloc NULL
                           //zurückgeben würde reserviert es Speicher wie 
    n += CHUNKSIZE;        //malloc, wobei allerdings eine komplett neue
                           //Adresse zugeteilt wird und der Speicher auf den 
    p = realloc(buf, n + 1); //ich vorher zeigte nicht mehr "ansprechbar" ist
    if(p == NULL) {          //Warum nochmal n+1?
      free(buf);
      return NULL;
    }
    buf = p; //buf ist mein Speicherbereich in den ich den String einlese?!
    pos = buf + n - CHUNKSIZE;  //Wieso rechne ich das so? Für was ist pos gut?

    if(fgets(pos, CHUNKSIZE + 1, stream) == NULL) {
      /* Für den Fall, dass die letzte Zeile im Stream nicht mit \n endet */
      if(feof(stream)) {
        return buf;
      } else {
        free(buf);
        return NULL;
      }
    }
  } while(pos[strlen(pos) - 1] != '\n');

  return buf;
}

Genau verstanden habe ich auch das Zusammenspiel von *buf und *pos noch nicht so ganz...

chmbw schrieb:

Um das nochmal klarzustellen: Der Ansatz bzw. mein Gedankengang war vollkommen in Ordnung (von der vergessenen Stringterminierung mal abgesehen), ich habe nur das Problem einer ziemlich schlechten Laufzeit weil ich realloc einfach viel zu oft aufrufe und somit Rechenzeit verballer?!

Ja.

Was den Code angeht,

char *get_line(FILE *stream) {
  size_t const CHUNKSIZE = 128;

  size_t n = 0;
  char *buf = NULL, *pos = NULL;

  if(feof(stream)) return NULL;

  do {
    char *p;

    /* buf wird oben anfänglich auf NULL gesetzt, also fordert realloc im ersten
     * Schleifendurchlauf einen Buffer der Länge CHUNKSIZE + 1 an, in den
     * darauffolgenden Durchläufen wird der Buffer immer um CHUNKSIZE
vergrößert.
     */
    n += CHUNKSIZE;
    p = realloc(buf, n + 1);
    if(p == NULL) {
      free(buf);
      return NULL;
    }
    buf = p;
    pos = buf + n - CHUNKSIZE;

    if(fgets(pos, CHUNKSIZE + 1, stream) == NULL) {
      /* Für den Fall, dass die letzte Zeile im Stream nicht mit \n endet */
      if(feof(stream)) {
        return buf;
      } else {
        free(buf);
        return NULL;
      }
    }
  } while(pos[strlen(pos) - 1] != '\n');

  return buf;
}

Bah, da ist was danebengegangen. Tschuldigung.

Also weiter:

n += CHUNKSIZE;
    p = realloc(buf, n + 1);
    if(p == NULL) {
      /* Das ist Fehlerbehandlung, wenn kein Speicher mehr angefordert werden
       * konnte. */
      free(buf);
      return NULL;
    }
    buf = p;
    pos = buf + n - CHUNKSIZE;

    /* Hier ist buf ein Buffer von s * CHUNKSIZE + 1 Zeichen Länge, wobei
     * s die Anzahl der Schleifendurchläufe ist. pos zeigt auf den Sentinel
     * des bisher eingelesenen Strings bzw. beim ersten mal auf den Anfang
     * des Buffers - die Stelle, wo weitergeschrieben werden soll. */

    if(fgets(pos, CHUNKSIZE + 1, stream) == NULL) {
      /* Für den Fall, dass die letzte Zeile im Stream nicht mit \n endet */
      if(feof(stream)) {
        return buf;
      } else {
        free(buf);
        return NULL;
      }
    }
  /* Und im Grunde merke ich mir pos hauptsächlich, um hier strlen nicht
   * jedes mal auf den ganzen Buffer anwenden zu müssen. */
  } while(pos[strlen(pos) - 1] != '\n');

  return buf;
}

Ich fordere immer s * CHUNKSIZE + 1 Byte als Buffer an, weil das die Adressierung vereinfacht.

supertux

chmbw schrieb:

Genau verstanden habe ich auch das Zusammenspiel von *buf und *pos noch nicht so ganz...

buf ist der Puffer (engl buffer), der dynamisch angelegt und vergrößert wird. Darin wird die eingelesene Zeichnektte gespeichert.

pos ein ein Zeiger auf buf , der zeigt stets auf die aktuelle Position in buf , wo Zeichen weiter hinzugefügt werden müssen.

Stell dir vor, CHUNKSIZE ist 4 und du liest "a b c d e f g\n"

für buf wird zunächst CHUNKSIZE Bytes reserviert. pos wird auf die Stelle positioniert, wo man weiter Zeichen hinzufügen soll. n zählt, wie viele Bytes bereits gelesen wurden. Da n stets um CHUNKSIZE erhört wird, bevor das Lesen stattfindet, muss man das bei der Berechnung von pos berücksichtigen und eben CHUNKSIZE davon abziehen. Da n die Anazahl von gelesenen Zeichen hat, entspricht buf + n die Stelle, wo Zeichen wieterhin hinzugefügt werden müssen.

Das macht man solange, wie EOF erreicht wird oder \n gelesen wird.

Es gibt da einen kleinen Fehler, es sollte

if(fgets(pos, CHUNKSIZE, stream) == NULL) {

heißen, da fgets \0-terminierte Strings garantiert.

Nein, nein, es muss schon CHUNKSIZE + 1 sein, sonst ist der Sentinel nicht an der richtigen Stelle, wenn keine ganze Zeile eingelesen werden konnte.

Der Trick dabei ist, dass pos in Relation zu buf in jedem Durchlauf um genau CHUNKSIZE versetzt werden kann. Wenn du das Extrabyte am Ende nicht mitbenutzt, fliegt das auseinander, und wenn du es ohne da Extrabyte am Ende machst, hast du im ersten Schleifendurchlauf einen Sonderfall, der etwas haarig zu bedienen ist.

Etwa so, mit CHUNKSIZE = 3:

1. Durchlauf, Buffer = | | | | |
                   pos -^
2. Durchlauf, Buffer = |T|e|x|\0|
                         pos -^ (um 3 erhöht)
3. Durchlauf, Buffer = |T|e|x|t|d|a|\0|
                               pos -^ (um 3 erhöht)
4. Durchlauf, Buffer = |T|e|x|t|d|a|t|e|n|\0|
                                     pos -^ (um 3 erhöht)
Ende        , Buffer = |T|e|x|t|d|a|t|e|n|\n|\0| | |

chmbw

in jedem Durchlauf vergrößer ich also meinen Speicherbereich um CHUNKSIZE (Zeile 18) und weise diesen Speicherbereich erstmal p zu um zu prüfen ob alles in Ordnung ist.
Ist dies der Fall, wird der Speicherbereich meinem buf übergeben, ich habe meinen Puffer vergrößert.

Zeile 24 dient jetzt dazu die Position anzugeben an welcher weitergeschrieben werden soll. Dazu übergebe ich die Anfangsadresse von meinem Speicherbereich (hier: buf), gehe um (n - CHUNKSIZE)-Stellen weiter, sprich zu meiner ERSTEN Stelle vom neu hinzugekommenen Speicher (Sprich "alte" letzte Speicherstelle von buf im vorherigen Durchlauf +1).

In Zeile 26 lese ich jetzt von meinem Stream eine Anzahl von CHUNKSIZE Werten ein, und speicher sie an der entsprechend neuen Stelle. Dabei teste ich gleich ob NULL zurückgeben wird (also ein Fehler passiert ist). Wenn ja, prüfe ich ob dieser Aufgrund eines EOF passiert, dann gebe ich den Speicherbereich zurück und bin fertig, oder es ist irgendetwas anderes geschehen und ich gebe den ganzen Buffer wieder frei.

Einlesen tu ich bis an der vorletzten Stelle im String ein '\n' steht (letzte Stelle steht ja immer \0)

Hab ich das so richtig verstanden?!

Du gehst an die letzte Stelle des alten Buffers, wo der Sentinel steht, damit dieser von fgets überschrieben wird. Der neu dazugekommene Speicher (auf technische Details wie die Verlegung des ganzen Blocks verzichten wir mal) liegt direkt dahinter.

Ansonsten ist das so richtig, ja.

chmbw

top, habt vielen vielen Dank! Eine geniale Funktion wie ich finde

Naja, mehr oder weniger. Es ist zu Anschauungszwecken ganz gut, aber in der Realität ist die GNU-Funktion, die ich erwähnte, meistens besser. Wenn man eine Zeile einlesen will, will man in aller Regel auch noch mehr einlesen, und dafür nicht jedes mal neuen Speicher anfordern zu müssen, ist schon eine gute Sache.

chmbw

Function: ssize_t getline (char **lineptr, size_t *n, FILE *stream)
This function reads an entire line from stream, storing the text (including the newline and a terminating null character) in a buffer and storing the buffer address in *lineptr.

Before calling getline, you should place in *lineptr the address of a buffer *n bytes long, allocated with malloc. If this buffer is long enough to hold the line, getline stores the line in this buffer. Otherwise, getline makes the buffer bigger using realloc, storing the new buffer address back in *lineptr and the increased size back in *n. See section 3.2.2 Unconstrained Allocation.

If you set *lineptr to a null pointer, and *n to zero, before the call, then getline allocates the initial buffer for you by calling malloc.

In either case, when getline returns, *lineptr is a char * which points to the text of the line.

When getline is successful, it returns the number of characters read (including the newline, but not including the terminating null). This value enables you to distinguish null characters that are part of the line from the null character inserted as a terminator.

This function is a GNU extension, but it is the recommended way to read lines from a stream. The alternative standard functions are unreliable.

If an error occurs or end of file is reached without any bytes read, getline returns -1.

http://www.delorie.com/gnu/docs/glibc/libc_185.html

Stimmt, das ist ja anscheinend eine mehr als starke Funktion (bzw. allg. Bibliothek). Ich werde mich dann mal eingehender damit befassen! Danke für den Hinweis!

So allgemein ist die gar nicht. Wenn du eine Bibliothek schreibst, die getline benutzt, muss der Benutzer den GNU Compiler haben.
Das ist keine gute Idee. Diese Funktion kannst du auch selbst mit Standardmitteln erstellen.

supertux

seldon schrieb:

Nein, nein, es muss schon CHUNKSIZE + 1 sein, sonst ist der Sentinel nicht an der richtigen Stelle, wenn keine ganze Zeile eingelesen werden konnte.

ich weiß nicht. Laut code:

n += CHUNKSIZE;
p = realloc(buf, n + 1);
...
if(fgets(pos, CHUNKSIZE + 1, stream) == NULL) {

oBdA: wir reden vom ersten Durchlauf. Du reserierst n+1 Bytes. Du sagst fgets, es soll ebenfalls n+1 bytes lesen. Da fgets ein \0-terminiertes String garantiert, schreibt es n+2 Bytes.

//edit:

wer lesen kann, ist klar im Vorteil. Ich muss zugeben, dass ich nicht mehr sicher war, was fgets genau mit dem 'size' Parameter macht und hab die man-Page dazu gelesen. Da steht ja

char *fgets(char *s, int size, FILE *stream);
...
fgets() reads in at most one less than size characters

Also, ich nehm's zurück, was ich davor gesagt habe, da ich von einer falschen Annahme ausging.