Aufbau eines variablen Records

[3_of_8]

Morgen.

Der Aufbau eines statischen Records ändert sich ja nie.

Ich frage mich jetzt, wie es aussieht mit Arrays, dessen Felder eine variable Größe haben, beispielsweise dynamische Arrays oder nicht-statische Strings.

Die einfachste Möglichkeit, die mir einfallen würde, wäre die, dass vor dem String ein Integer/Cardinal liegt, der die Größe des Strings angibt und alle Daten hinter dem String sich verschieben, wenn er wächst oder schrumpft, analog dann beim Array.

Ist es so einfach?

[Dax]

Nein. Dynamische Arrays und Strings sind Pointer auf Records, die ihrerseits die Länge der Struktur und einen Pointer auf die Daten enthalten. Recordgrößen ändern sich, per Defionition, nie.

[Khabarakh]

Ein sich ausdehnender/zusammenziehender Stack wäre doch mal was Lustiges .

[St.Pauli]

String ist nur ein Zeiger der auf einen Speicherblock zeigt. Vor dem Speicherblock steht die Länge. Bin mir nicht sicher ob es cardinal oder sogar int64 ist. Auf jeden fall verhält es sich mit dynamischen Arrays gleich.

[3_of_8]

"Vor dem Speicherblock"...

Das heißt, ich habe z.B. einen String 'wuppdi' in meinem record stehen.

Der ist ein Pointer auf die Speicheradresse x.

Dann finde ich bei Position x-4 die Länge des Strings, richtig? (Int64 glaube ich nicht, so viel Speicher gibts bei 32 Bit Systemen ja IMHO gar nicht.)

Ein statischer String hingegen steht immer direkt im Record, oder?

EDIT: Wie sieht das bei dynamischen Arrays of arrays aus? Ein Pointer auf ein dyn. Array mit Pointern auf dynamische Arrays?

[Muetze1]

Zitat von 3_of_8:

Das heißt, ich habe z.B. einen String 'wuppdi' in meinem record stehen.

Der ist ein Pointer auf die Speicheradresse x.

Dann finde ich bei Position x-4 die Länge des Strings, richtig? (Int64 glaube ich nicht, so viel Speicher gibts bei 32 Bit Systemen ja IMHO gar nicht.)

Ja, siehe hier: Daten vor dem String auslesen

Zitat von 3_of_8:

Ein statischer String hingegen steht immer direkt im Record, oder?

Ja, richtig.

Zitat von 3_of_8:

EDIT: Wie sieht das bei dynamischen Arrays of arrays aus? Ein Pointer auf ein dyn. Array mit Pointern auf dynamische Arrays?

Ja, auch genau richtig.

[3_of_8]

Angenommen ich habe folgende zwei Records:

Delphi-Quellcode:

type
  TR1=record
    s1, s2, s3: String;
  end;

  TR2=record
    a, b, c: Integer;
    r: TR1;
    d, e, f: Char;
  end;

Steht dann das TR1 direkt im TR2 drin mit jeweils drei Pointern auf Strings oder steht im TR2 ein Pointer auf das TR1 drin, in welchem wiederum die drei Pointer sind?

[yankee]

Erstmal vorweg:
Ein string IST ein array. Ein array of char.

Wenn du dir den RAM vorstellst... Wie eine lange Tabelle:

Code:

Nummer: 1   2   3   4   5   6   7   8   9   ...
Inhalt: 0   0   0   5   H   A   L   L   O   ...

Jede Nummer kann 1 Byte speichern. Bei 32 Bit-Systemen sind die Nummern 32 Bit zahlen. Daher ist bei 32 Bit-Systemen auch bei 4GB RAM Schluss und du brauchst 64 Bit.

In meinem Beispiel hast du im RAM den string 'hallo' gespeichert. Dabei sind byte 1-4 zusammen ein Cardinal Wert, die die länge des Strings darstellen. Zumindest meine ich mich zu erinner, dass Delphi einen Cardinal verwendet... Ist fürs Verständnis aber egal:

Ein Buchstabe ist nur 1 Byte gross (zumindest im ASCII-Zeichensatz). Wenn du jetzt eine Variable
var s:string; hast, dann ist s eigentlich erstmal nur ein Pointer, also ein Cardinal mit dem Wert 1. Der zeigt einfach nur auf die Stelle im RAM, wo der String anfängt.
Da an der ersten Stelle des Strings die Länge des selbigen abgespeichert ist, weisst du genau, welche Felder der String belegt und kannst so mit dem String arbeiten.
Nachteil an dieser Konstruktion: Der String muss so, wie in meinem Beispiel hinternander weg im RAM sein. Wenn dein string dann 50 MB gross ist, dann brauchst du 50*10^20 Adressen, die hintereinander liegen. Wenn du dann bei so einem grossen array setlength() benutzt um den Array zu vergrössern, dann ist im RAM wahrscheinlich garnicht genug Platz hinter dem Array um einfach mal was anzuhängen, weil dort andere Daten liegen.
Du musst dir also einen neuen Array erstellen und alle bisherigen Daten in den neuen vergösserten Array kopieren. In C und Java ist der vorgang deutlicher, denn da gibt es kein setlength. Ein einmal initialisierter String ist eben einfach da und die einzige Möglichkeit ihn zu ändern ist eine geänderte Kopie zu erstellen.
Dieser Vorgang ist natürlich äusserst langsam.

Ein Lösungsansatz dafür sind verkettete Listen. Bei denen hast du am Ende jedes Elementes deines Arrays wieder einen Pointer auf das nächste Element. Daher müssen die Elemente im RAM nicht hintereinander sein. Die beschleunigt das löschen und anfügen von Elementen stark. Hat aber den Nachteil, dass du für den next-Pointer immer weitere 32 bit (bzw mehr, je nach CPU und OS) verschwendest. Ausserdem ist der Zugriff sehr langsam, wenn du jedes mal von Anfang 50000 mal dem Folgepointer folgen musst, bis du die richtige Datenposition hast.
Bei einem Array, der alle Elemente hinternander liegen hat, kannst du dir die Datenposition ganz einfach errechnen. Ausserdem kannst du auch mit einem Pointer über einen String iterieren.

Delphi-Quellcode:

var p: ^char;
    s:string;
begin
  s :='HALLO';
  p :=@s[1];
  showmessage(p^); //H
  inc(p);
  showmessage(p^); //A
  ...
end;

in diesem Beispiel setzen wir p als Pointer auf das erste Zeichen des strings. Also auf das 'H'. Dann erhöhen wir den Pointer (also die Adresse, auf die der Pointer zeigt) und schwupp finden wir an der stelle im RAM das A. So kann man immer wieder an die nächste stelle im RAM gehen, bis der string zu Ende ist (eigentlich noch weit darüber hinaus, bis es eine AV gibt, weil dein RAM zu Ende ist ^^).

Ein Array of Array ist demnach einfach, wie du bereits sagtest, ein ganz normaler eindemensionaler Array. Mit einem Pointer auf einen zweidemensionalen Array in jedem Element des ersten Arrays.


Ich hoffe das war verständlich .

[Muetze1]

Zitat von yankee:

Ein Buchstabe ist nur 1 Byte gross (zumindest im ASCII-Zeichensatz). Wenn du jetzt eine Variable
var s:string; hast, dann ist s eigentlich erstmal nur ein Pointer, also ein Cardinal mit dem Wert 1.

Cardinal? 1? Ich weiss nicht was du meinst. Wie kommst du auf 1 Byte? Meinst du den Variablennamen? Der ist egal, da der Compiler diese schliesslich nicht übernimmt bzw. nutzt. Es ist an der Stelle von S einfach nur ein Pointer. Diese zeigt auf ein Nullbyte und vor dem liegen 2 Cardinals - Reference Counter und Länge des Strings. (siehe Link in meinem Beitrag)

Zitat von yankee:

Da an der ersten Stelle des Strings die Länge des selbigen abgespeichert ist, ...

Nein, 4 Bytes vor dem Speicher auf den der String-Pointer zeigt.

Zitat von yankee:

(eigentlich noch weit darüber hinaus, bis es eine AV gibt, weil dein RAM zu Ende ist ^^).

Nicht der RAM, sondern der dem Prozess zugewiesene und alloziierte Speicher...

Zitat von 3_of_8:

Steht dann das TR1 direkt im TR2 drin mit jeweils drei Pointern auf Strings oder steht im TR2 ein Pointer auf das TR1 drin, in welchem wiederum die drei Pointer sind?

TR1 steht direkt in TR2 an der Position, da der Record direkt dort definiert wurde. Ein Record hat keine solche Automatismen mit Pointern etc. Du müsstest extra einen Zeiger auf TR1 defineren und in TR2 angeben um deine zweite Möglichkeit zu erhalten.

Deine erste Aussage war somit richtig. Du kannst auch einfach die Grösse rausfinden mit SizeOf(). Beispiel:

Delphi-Quellcode:

  ShowMessage(IntToStr(SizeOf(TR1)));
  ShowMessage(IntToStr(SizeOf(TR2))); 
  ShowMessage(IntToStr(SizeOf(TR2.r)));

[3_of_8]

@yankee: Danke, ich hatte ein Semester lang Rechnerarchitektur. Ich weiß, wie Prozessverwaltung funktioniert, wie ein RAM aufgebaut ist und wie einfache Datentypen aufgebaut sind. Ich wollte nur wissen, wie Delphi variable Records speichert.

Code:

Nummer: 1   2   3   4   5   6   7   8   9   ...
Inhalt: 0   0   0   5   H   A   L   L   O   ...

Das glaube ich nicht. Der Cardinal '5' steht garantiert NICHT als 4 Bytes (0, 0, 0, 5) im Speicher, sondern als (5, 0, 0, 0). Das nennt sich "Little Endian-Format".

Dass 's' in deinem Beispiel den Wert 1 hat, halte ich in Delphi für sehr, sehr unwahrscheinlich. Ein leerer String ist ein Pointer mit dem Wert 0, aber 1? Glaube ich nicht.

@Muetze: Danke, das wollte ich hören.