Zweidimensionales Array (Strings) - Speicherallokation



  • Malcom schrieb:

    Ich habe versucht, das Beispiel für Strings anzupassen, aber irgendwie haut das was ich mache einfach nicht hin und ich verstehs auch nicht ganz.
    Hat jemand eine gute Seite auf Lager, die das gut erklärt (auf Strings bezogen)? Oder kann mir jemand ein Beispiel liefern?

    es ist 1:1 identisch, bloß anstatt int schreibst du char . Wenn du weitere Probleme hast, musst du sie beschreiben, wir können nämlich nicht hellsehen.



  • seldon schrieb:

    char **realloc_string_array(char **old_array, size_t anzahl_strings, size_t neue_groesse) {
      char **new_array = realloc(old_array, (anzahl_strings + 1) * sizeof(char*) + neue_groesse);
    
      if(new_array) {
        size_t i;
    
        /* Index neu aufbauen */
        for(i = 0; i < anzahl_strings; ++i) {
          new_array[i] = (char*) new_array + (old_array[i] - (char*) old_array);
        }
      }
    
      return new_array;
    }
    

    Ich hoffe, mir ist dabei kein Fehler unterlaufen. Das ist ein ziemliches Gefrickel.

    was soll eigentlich dieses Index neu aufbauen? Ich verstehe überhaupt nicht den Sinn dafür. Hast du dir schon Geadnken gemacht, dass old_array[i] - (char*) old_array komplett sinnlos ist? Ich jedenfalls verstehe ich gar nicht, was du damit erreichen willst.

    1. realloc sorgt für die Einhalt der "Reihenfolge"

    2. wenn nach realloc new_array und old_array nicht gleich sind, dann darfst du nicht auf old_array zugreifen, denn der Speicher ist bereits freigegeben oder wird schon von jemanden anders benutzt. Nur weil man C Code schreibt, muss man nicht gleich alles verkomplizieren.



  • Ok, ich bin deinem Rat gefolgt, supertux, und habe das Beispiel angepasst.
    Funktioniert auch wunderbar.

    Nur habe ich nun ein Problem, wenn ich später eine zeile anhängen will.
    Also zuerst habe ich:

    [code
    values = malloc(zeilen * sizeof(char * ));

    for(i = 0; i < zeilen; i++) {
    values[i] = malloc(spalten * sizeof(char));
    }
    [/code]
    Nun habe ich Speicher reserviert und füge fleißig ein. Das klappt wunderbar.
    Später gibt es dann in einer anderen Funktion die Möglichkeit, genau eine neue Zeile anzufügen, mit der gleichen Anzahl von Spalten. Aber mein realloc knallt immer weg. Wenn ich ein realloc() mache, muss ich das dann genau wie beim malloc() machen, also sprich genau der Aufbau wie oben, nur dann halt mit realloc?



  • Zeig doch mal deinen realloc-Code.



  • ++zeilen;
    values = realloc(values, zeilen * sizeof(char *));
    
    for(i=0; i < zeilen; i++) {
      values[i]=realloc(values[i], spalten * sizeof(char)); 
    }
    

    Irgendwie knallt er wohl bei der for-Schleife weg,
    "realloc(): Invalid next size". Irgendwie zweifel ich auch daran,
    das das so richtig ist.



  • Malcom schrieb:

    ++zeilen;
    values = realloc(values, zeilen * sizeof(char *));
     
    for(i=0; i < zeilen; i++) {
      values[i]=realloc(values[i], spalten * sizeof(char)); 
    }
    

    Irgendwie knallt er wohl bei der for-Schleife weg,
    "realloc(): Invalid next size". Irgendwie zweifel ich auch daran,
    das das so richtig ist.

    Was genau hast du vor? Der obige Code ist (fast) richtig [1], ob er der richtige für deine Aufgabe ist eine andere Frage.

    [1] Wenn realloc NULL zurückliefert, dann verlierst du auf die Weise (wie du geschrieben hast) den original Pointer und hast dann ein mögliches Memory-Leak.

    void *x = malloc(SOME_SIZE);
    
    ...
    
    void *new_x = realloc(x, SOME_NEW_SIZE);
    
    if(new_x)
      x = new_x;
    else
       FEHLER BEHANDELN
    


  • Wie gesagt, später gibt es dann in einer anderen Funktion die Möglichkeit, genau eine neue Zeile anzufügen, mit der gleichen Anzahl von Spalten.

    Steh allerdings bei deinem Codeschnipsel gerade etwas auf den Schlauch, wie das gemeint ist 😕



  • supertux schrieb:

    was soll eigentlich dieses Index neu aufbauen? Ich verstehe überhaupt nicht den Sinn dafür. Hast du dir schon Geadnken gemacht, dass old_array[i] - (char*) old_array komplett sinnlos ist? Ich jedenfalls verstehe ich gar nicht, was du damit erreichen willst.

    1. realloc sorgt für die Einhalt der "Reihenfolge"

    2. wenn nach realloc new_array und old_array nicht gleich sind, dann darfst du nicht auf old_array zugreifen, denn der Speicher ist bereits freigegeben oder wird schon von jemanden anders benutzt. Nur weil man C Code schreibt, muss man nicht gleich alles verkomplizieren.

    Na, wenn das Ganze in einem großen Speicherblock verwaltet werden soll, reicht das Einhalten der Reihenfolge nicht aus, weil die Zeiger im vorderen Teil noch in den alten Block zeigen. Ich hatte die Anforderung zunächst so verstanden:

    Malcom schrieb:

    Da ich weiss, wieviel Speicher ich benötigen könnte, möchte und soll ich direkt alles auf einmal mit malloc reservieren. Am Ende würde ich dann den Speicherbereich auf seine tatsächliche Größe beschränken.

    Es ist allerdings richtig, dass ich mir den ersten Offset vorher merken muss. Berichtiger Code wie folgt:

    char **realloc_string_array(char **old_array, size_t anzahl_strings, size_t neue_groesse) {
      ptrdiff_t offset = old_array[0] - (char*) old_array;
      char **new_array = realloc(old_array, (anzahl_strings + 1) * sizeof(char*) + neue_groesse);
    
      if(new_array) {
        size_t i;
    
        /* Index neu aufbauen */
        for(i = 0; i < anzahl_strings; ++i) {
          ptrdiff_t offset_next = new_array[i + 1] - new_array[i];
          new_array[i] = (char*) new_array + offset;
          offset += offset_next;
        }
      }
    
      return new_array;
    }
    

    Wenn das mehrfache Gehen an den Heap allerdings doch kein Problem darstellt, ist es mit mehrfachem malloc einfacher.



  • Mit dem gewünschten realloc z.B.

    typedef char STR100[100];
    
    void addString(STR100 **p, const char *new)
    {
        int i=*p?*(int*)(*p):1;
        *p=realloc(*p,++i*sizeof**p);
        *(int*)(*p)=i;
        strcpy((*p)[i-1],new);
    }
    int main()
    {
        int i=1;
        STR100 *a=0;
        addString(&a,"bla");
        addString(&a,"fasel");
        for( ;*a && i<*(int*)a;++i )
          puts(a[i]);
        free(a);
        return 0;
    }
    


  • seldon schrieb:

    Es ist allerdings richtig, dass ich mir den ersten Offset vorher merken muss. Berichtiger Code wie folgt:

    Ich verstehe nach wie vor nicht was du wirklich meinst. Mein Problem liegt es bei beiden Zeilen:

    ptrdiff_t offset_next = new_array[i + 1] - new_array[i];
          new_array[i] = (char*) new_array + offset;
    

    insbesondere die zweite macht für mich keinen Sinn, weil es keine Relation ziwschen new_array und new_array[ i ] existiert.

    Wenn ich erstmal Speicher für 100 Einträge habe, aber nur 80 benötige, dann rufe ich realloc mit der Speichergröße für 80 Einträge und fertig. Aber du verschiebst den Zeieger für new_array[ i ] im Zusammenhang mit new_array. Zahlenbeispiel:

    new_array zeigt auf 0x1000 und wurde Platz für 10 Zeiger (40 Bytes) reserviert.
    
    new_array[0] zeigt auf 0xa00001000
    new_array[1] zeigt auf 0xa00001004
    new_array[2] zeigt auf 0xa00001008
    ...
    new_array[9] zeigt auf 0xa00001028
    

    dann mache ich ein realloc für mehr Platz, sagen wir mal 15 Zeiger (54 Bytes) und die Adresse ändert sich auf 0x2000

    new_array zeigt auf 0x2000 und wurde Platz für 15 Zeiger (54 Bytes) reserviert.
    
    new_array[0] zeigt auf 0xa00001000
    new_array[1] zeigt auf 0xa00001004
    new_array[2] zeigt auf 0xa00001008
    ...
    new_array[9] zeigt auf 0xa00001028
    new_array[10] zeigt auf undefiniert
    ....
    new_array[14] zeigt auf undefiniert
    

    Mit

    ptrdiff_t offset_next = new_array[i + 1] - new_array[i];
          new_array[i] = (char*) new_array + offset;
    

    für die erste Iteration:
    offset_next ist 4, new_array[0] weist du dann 0x2004 zu. 0x2004 ist zwar zufällig in einem von dir allozierten Block, aber der Verweis auf 0xa00001000 geht dadurch verloren. Sagen wir mal new_array[1] würde auf 0x10001024 zeigen, dann hast du in nächsten Iterationsschritt: offset_next = 0x9EFFFFFE4, du weist array[1] 0x9F0001FE4 zu und landest völlig im Nirvana. Aus diesem Grund verstehe ich gar nicht, was du machen willst oder was du mit "Index neu aufbauen" willst.

    @wutz: finde deinen Code oberhäßlich, die Größe des Arrays im ersten Element reinzukodieren ist für mich häßliches Frickeln, ich hoffe, ich schreibt normalerweise nicht solchen C-Code. Wenn ich warum auch immer typedef char STR100[2]; mache, haut das nicht mehr hin. Man kann auch so machen, dass der letzte Eintrag der Liste NULL ist und ich die Länge so errechnen kann oder addString bekommt zusätzlich die Länge, was weiß ich. Solche Hacks sollte man jedenfalls Anfängern nicht beibringen. 👎

    Malcom schrieb:

    Wie gesagt, später gibt es dann in einer anderen Funktion die Möglichkeit, genau eine neue Zeile anzufügen, mit der gleichen Anzahl von Spalten.

    Steh allerdings bei deinem Codeschnipsel gerade etwas auf den Schlauch, wie das gemeint ist 😕

    wieso beschreibst du nicht, was du tatsächlich willst? Willst du nur ein Array von Strings (also array[ i ] zeigt auf String) oder 2-dim-Matrix von Strings (array[ i ] zeigt auf ein Array von Strings bzw. array [ i ][ j ] zeigt auf String)? 😕



  • Aber natürlich besteht eine Korrelation zwischen new_array und new_array[i]. Das ist doch der ganze Witz!

    Die Idee ist Folgende: Du forderst einen großen Speicherbereich an. Den vorderen Teil interpretierst du als Array von Zeigern in den hinteren Teil, wo die eigentlichen Daten liegen. Etwa so:

    |    |    |    |    |    |Hallo\0Welt\0foo\0bar\0|
    +----+----+----+----+----+-----------------------+
       |    |    |    |_______^______^_____^____^
       |    |    |____________|______|_____|
       |    |_________________|______|
       |______________________|
    

    Wenn dann der Speicherbereich umgelegt wird, müssen die Zeiger im vorderen Teil (der Index) auf den neuen Speicherbereich ausgerichtet werden, weil sie natürlich noch in den alten zeigen.

    Wenn die Anforderung ist, und so hatte ich das ursprünglich verstanden, dass alles mit einmal malloc abgehandelt werden soll, ist das die einfachste Möglichkeit, die mir einfällt. Wenn man zur Laufzeit vorher weiß, wie viele Strings man bekommt und wie viel Platz man etwa dafür braucht, kann man sich auf die Art eine Menge Heap-Arbeit sparen, und in stark nebenläufigen Anwendungen ist Heap-Contention immer ein Problem. Bevor du mir jetzt an den Kopf wirfst, das sei eine völlig weltfremde Spielerei.



  • seldon schrieb:

    Aber natürlich besteht eine Korrelation zwischen new_array und new_array[i]. Das ist doch der ganze Witz!

    Die Idee ist Folgende: Du forderst einen großen Speicherbereich an. Den vorderen Teil interpretierst du als Array von Zeigern in den hinteren Teil, wo die eigentlichen Daten liegen.

    Aha, jetzt verstehe ich, was du da meinst. Aber ehrlich gesagt, an welcher Stelle hat der Threadstarter so etwas gemeint? Ich hab es mir nochmal gelesen und konnte es nicht herausfinden.

    seldon schrieb:

    Wenn die Anforderung ist, und so hatte ich das ursprünglich verstanden, dass alles mit einmal malloc abgehandelt werden soll, ist das die einfachste Möglichkeit, die mir einfällt. Wenn man zur Laufzeit vorher weiß, wie viele Strings man bekommt und wie viel Platz man etwa dafür braucht, kann man sich auf die Art eine Menge Heap-Arbeit sparen, und in stark nebenläufigen Anwendungen ist Heap-Contention immer ein Problem. Bevor du mir jetzt an den Kopf wirfst, das sei eine völlig weltfremde Spielerei.

    mag sein, dass es keine weltfremde Spielerei ist, ich halte es dennoch für unschönes Gefrickel, was sehr fehleranfällig sein kann. Meine Meinung lautet nach wie vor, dass man einem Anfänger nicht solche Sachen beibringen sollte, denn viele Anfänger verstehen immer noch nicht, was ein zeiger überhaupt ist.



  • Wie ich oben schon erwähnte, ich hatte das hier:

    Malcom schrieb:

    Da ich weiss, wieviel Speicher ich benötigen könnte, möchte und soll ich direkt alles auf einmal mit malloc reservieren. Am Ende würde ich dann den Speicherbereich auf seine tatsächliche Größe beschränken.

    so verstanden.



  • seldon schrieb:

    Wie ich oben schon erwähnte, ich hatte das hier:

    Malcom schrieb:

    Da ich weiss, wieviel Speicher ich benötigen könnte, möchte und soll ich direkt alles auf einmal mit malloc reservieren. Am Ende würde ich dann den Speicherbereich auf seine tatsächliche Größe beschränken.

    so verstanden.

    Ich wage zu bezweifeln, dass der Threadersteller das gemeint hat, was du da erklärt hast sondern eher:

    malloc(anzahl von Zeilen)
    for each Zeile
      malloc(anzahl von Spalten)
    

    und erst dann mit Werten füllen.


Anmelden zum Antworten