String beliebiger Länge einlesen / Problem mit Funktion

chmbw

Hallo,

ich versuche mir grade eine Funktion zu basteln, die mir einen String von beliebiger Länge einliest. Ich habe mir überlegt, dass ich erstmal einen kleinen Speicherbereich mit calloc anfordere und dann in einer Endlosschleife immer weiter und weiter Zeichen einlese, bis ein '\n' eingegeben wird. Nach Jedem neu eingegebenen Zeichen wird das Char-Array mit realloc vergrößert.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main()
{
    char *str = NULL;
    int i=1;

    str = calloc(2,sizeof(char));

    if( NULL == str)
    {
    printf("\nFehler, nicht genug Speicher\n");
    free(str);
    }

    printf("Bitte String beliebiger Laenge eingeben:\n\n");

    while(1)
    {
        fgets(str,2,stdin);
        if(NULL != strchr(str,(int)'\n'))
        {
            printf("\nStringausgabe: ");
            puts(str);
            break;
        }
        i++;
        str = realloc(str,i+1);
        if(NULL == str)
        {
            printf("\n Nicht genug Speicher\n");
            free(str);
            break;
        }

    }
    return 0;
}

Irgendwie will er mir nur nicht meinen String wieder ausgeben, wenn ich ein \n eingegeben habe. Woran kann das liegen? Ist es überhaupt sinnvoll so eine Funktion so auf diese Art zu programmieren? Bin über jede Meinung / jeden Hinweis etc. sehr dankbar!

Vielen Dank im Voraus!

Viele Grüße

edit: Rechtschreibung

chmbw schrieb:

str = realloc(str,i+1);
        if(NULL == str)
        {
            free(str);
        }

    }
    return 0;
}

Wenn str NULL ist, dann gibst du den Speicher von str frei?
Richtig wäre:

char *newPtr = realloc(str, i+1);
if (newPtr == NULL)
  free(ptr);
else
  ptr = newPtr;

chmbw schrieb:

Irgendwie will er mir nur nicht meinen String wieder ausgeben, wenn ich ein \n eingegeben habe. Woran kann das liegen?

Zeichenketten in C müssen \0-Terminiert sein. Deine Zeichenkette ist das nicht. Du musst selbst die \0 ans Ende schreiben (realloc ist kein calloc!).

chmbw schrieb:

Ist es überhaupt sinnvoll so eine Funktion so auf diese Art zu programmieren? Bin über jede Meinung / jeden Hinweis etc. sehr dankbar!

Ist schon richtig so. Allerdings solltest du statt "i+1" lieber sowas haben wie "i*2" oder zumindest "i+16". Denn ein Aufruf von malloc kostet einiges an Zeit, und das für jedes Zeichen ist einfach pure Verschwendung von Rechenleistung.

mngbd

Janjan schrieb:

Denn ein Aufruf von malloc kostet einiges an Zeit, und das für jedes Zeichen ist einfach pure Verschwendung von Rechenleistung.

Und realloc() kostet zusätzlich (könnte auch NULL sein, dann verlierst du alles). Lies mal hier weiter:
http://www.c-plusplus.net/forum/viewtopic-var-t-is-206606.html
Einen vernüftigen Faktor für die Vergrösserung des Bereichs zu setzen, ist nicht leicht. Ich würde 1.41 nehmen.

Ein in diesem Zusammenhang schönes Feature von realloc ist, dass, wenn der erste Parameter NULL ist, es genau wie malloc funktioniert. Das erlaubt einem, das ganze schön einfach in einer Schleife als "Speicher anfordern, Speicher füllen, bis Kram da ist" abzuhandeln und auf das Springen aus der Mitte einer Endlosschleife zu verzichten.

Beispielsweise so:

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;

    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;
}

Natürlich kann man den Buffer auch immer um einen bestimmten Faktor vergrößern, aber Zeilen in einer Datei bzw. vom Benutzer eingegebene werden selten so lang, dass das einen Unterschied macht.

Übrigens: in der GNU-C-Bibliothek gibt es eine Funktion

ssize_t getline(char **lineptr, size_t *n, FILE *stream);

die bereits angeforderten Speicher wiederverwendet. Etwa so:

char *line = NULL;
size_t n = 0;
FILE *fd = fopen("datei.txt", "r");

while(getline(&line, &n, fd) != -1) {
  printf("%s", line);
}

free(line);

...was einem natürlich einen großen Teil der mallocerei erspart, wenn man viele Zeilen einlesen will. Das umzusetzen sei aber eine Aufgabe für den Leser.

sollte man es nicht mal so versuchen

void *safe_realloc(void *ptr, size_t size){
  void *newPtr = realloc(ptr, size);
  if(newPtr != ptr){
    free(ptr);
    ptr = newPtr;
  }
  return ptr;
}

lg lolo

Ich nehme an, du meinst

void *safe_realloc(void *orig, size_t n) {
  void *p = realloc(orig, n);

  if(p == NULL) {
    free(orig);
    return NULL;
  }

  return p;
}

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.