Zweidimensionales Array (Strings) - Speicherallokation

[Malcom]

Hallo,

ich habe da ein leichtes Problem bei der Speicherreservierung
für ein zweidimensionales, dynamisches Arrays von Strings - das Array besteht
aus Zeilen und Spalten, die Anzahl der Zeilen und Spalten ist bekannt, sowie die Länge einer Zeile und die Gesamtgröße.

Anhand eines Beispiels eines Openbooks soll für int-Werte erst Speicher für die int-Zeiger (=zeile) reserviert werden:

int ** matrix;

matrix = malloc(zeile * sizeof(int *));

und dann noch Speicher reservieren für die einzelnen Spalten der i-ten Zeile

for(i = 0; i < zeile; i++) {
      matrix[i] = malloc(spalte * sizeof(int));
}

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?

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.

Wäre über eine Antwort echt dankbar.

Gruß,
Malcom

[seldon]

Mir schwant Böses. Wer ist der Autor dieses Openbooks?

Wie dem auch sei, wenn du alles in einem großen Speicherblock haben willst, ist das unter Umständen etwas Gefummel. Wenn du weißt, wie groß die einzelnen Strings werden können (d.h. zur Compilezeit eine Obergrenze kennst) und unbenutzter Speicher zwischen unterschiedlich langen Strings dich nicht stört, ist es ziemlich simpel - nur die Syntax ist etwas gewöhnungsbedürftig:

char (*string_array)[100] = malloc(100 * anzahl_strings);

Ist das nicht der Fall, wirst du eine Art einfachen Heap selbst verwalten müssen, was ein bisschen anspruchsvoller ist. Denkbar wäre etwas in dieser Form:

size_t i;
/* Kommentar unten */
char **array = malloc((anzahl_strings + 1) * sizeof(char*) + vorgehaltener_speicher_fuer_strings);

array[0] = (char*) (array + anzahl_strings + 1);

for(i = 0; i < anzahl_strings; ++i) {
  /* Hier muss eigentlich natürlich geprüft werden, ob noch genug Speicher da ist */
  array[i + 1] = stpcpy(array[i], hole_string()) + 1; 
}

stpcpy ist eine POSIX-Funktion, die sich verhält wie strcpy, aber einen Zeiger auf das Ende des Strings (d.h. den Sentinel) zurückgibt. Ich bin nicht sicher, ob es diese Funktion unter Windows gibt, ggf. ist sie aber leicht nachbaubar. Der Code verschwendet sizeof(char*) Byte Speicher, indem Platz für anzahl_strings + 1 Zeiger angefordert wird, aber es vereinfacht den Zuweisungsalgorithmus, weil in der Schleife nicht geprüft werden muss, ob es noch einen nächsten String gibt.

Ein großer Nachteil dieses Ansatzes ist, dass die Umlegung relativ kompliziert wird, wenn der zunächst angeforderte Speicher nicht reicht. Realloc alleine ist nicht genug, weil die Zeiger im vorderen Teil des Arrays nicht mehr stimmen - man könnte hier entweder mit Indices arbeiten, was die Adressierung zu einem Krampf machen dürfte, oder die Umlegung etwa so gestalten:

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.

Wenn du ein zweidimensionales String-Array unbekannter Dimension oder gar nicht-rechteckiger Struktur brauchst, d.h. char***, lässt sich der Ansatz prinzipiell in ähnlicher Weise erweitern, wobei dann natürlich zusätzlich Platz für Zeiger auf die eigentlichen Strings angefordert und verwaltet werden muss. Der Aufwand steigt exponentiell mit der Anzahl der Dimensionen, ganz besonders bei der Umlegung; in einem solchen Fall würde ich wohl darauf verzichten, das alles mit einem einzelnen malloc abhandeln zu wollen.

[supertux]

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.

[supertux]

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.

[Malcom]

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?

[It0101]

Zeig doch mal deinen realloc-Code.

[Malcom]

++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.

[supertux]

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

[Malcom]

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

[seldon]

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.

[Wutz]

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

[supertux]

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)?

[seldon]

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.

[supertux]

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.

[seldon]

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.

[supertux]

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.