String-Heap

Aus C64-Wiki
(Weitergeleitet von Stringheap)
Zur Navigation springenZur Suche springen

Der String-Heap (engl. heap = dt. Haufen) ist der Speicherbereich für dynamische Zeichenketten des BASIC-Interpreters. Er liegt beim C64, wie bei allen 8-Bit Microsoft BASICs, am Ende des Basic-Speichers, die Standardadresse (MEMTOP) ist 40960/$A000. Andere CBM-BASIC-Varianten mit mehr als 64 KByte Speicherausstattung verlagern den String-Heap mitunter sogar in eine andere Speicher-Bank (gemeinsam mit anderen Variablen oder sogar separat).
Als weitere Bezeichnung sind auch String Storage Area[1], String Space, String-Bereich, String-Speicher in verschiedenen Quellen bekannt und mehr oder weniger geläufig.

Aufbau[Bearbeiten | Quelltext bearbeiten]

Die Elemente des Heaps bestehen aus Zeichenketten, die eine Länge von 1 bis 255 Zeichen aufweisen. Diese werden von einem String-Descriptor (z.B. in einer String-Variablen oder vom String-Descriptor-Stack) referenziert, wenn eine Zeichenkette noch in Verwendung ist. Ausgehend von den am Heap befindlichen Zeichenketten lassen sich eventuell dazugehörige String-Descriptoren und die nicht mehr verwendeten Zeichenketten (engl. garbage, also der Zeichenkettenmüll, auch als unbenutzte "Lücken" bezeichnet) nicht direkt ermitteln, was eine Reorganisation und Kompaktierung des Heaps aufwendig macht.
Ab BASIC 3.5 (hervorgegangen aus dem älteren Vorfahren BASIC 4.0 der PET-Ära, wo eine neue Art der Organisation erstmalig zu finden ist) und in späteren BASIC-Versionen wird dieser Nachteil mit folgenden Strukturmaßnahmen am Heap beseitigt:

  1. Ein zusätzlicher Rückwärtsverweis zum String-Descriptor (Back-Link) bei jeder Zeichenkette erlaubt das Lokalisieren eines Descriptors und dessen Korrektur, sollte sich die Zeichenkette verschieben.
  2. Einer Längenangabe einer zurückgelassenen Lücke, wodurch der Heap eine einzige Struktur wird, wo aktive Zeichenketten und unbenutzte Teile identifiziert werden können.

Neu angelegte Zeichenketten lassen den Heap "abwärts" wachsen, in Richtung niedrigerer Adressen, dem Ende des Speicherbereichs für indizierte Variablen (STREND) entgegen. Die aktuelle "Spitze" des Haufens markiert der Zeiger FRETOP.
Ist der String-Heap ausgeschöpft (wenn also FRETOP bei STREND angelangt ist), wird mit Hilfe der Garbage Collection versucht, diesen so zu kompaktieren, dass nicht mehr verwendete Zeichenketten (also nicht von einem String-Descriptor referenzierte "Lücken") wieder zu einem zusammenhängenden freien Bereich zusammengefasst werden.

Nach dem Aufruf folgender Befehle im Direktmodus:

A$="ABC"
B$(2)=A$+"XYZ"

sieht der String-Heap im Speicher wie folgt aus:

          ├─             ─┤
MEMSIZ    │               │◄─────┐           BASIC-Speicherende, üblicherweise $A000
          └───────────────┘      
          ┌───────────────┐      
$9FFF     │      'C'      ─             ─      'B'      ─             ─      'A'      │◄───┐            String "ABC" von A$
          ├───────────────┤    │        ─┐
          │      'Z'      │    │         │ 
          ├─             ─┤    │         │
          │      'Y'      │    │         │  ungenützter Speicherblock ("Lücke"), der nach der String-Addition übrig geblieben ist
          ├─             ─┤    │         │  (nicht mehr von einem Descriptor referenziert)
          │      'X'      │    │         │
          ├───────────────┤    │        ─┘
          │      'Z'      │    │ ─             ─┤    │       'Y'      │    │ ─             ─┤    │       'X'      │    │ ─             ─┤    │       'C'      │    │ ─             ─┤    │       'B'      │    │ ─             ─┤    │       'A'      │◄─┐ │ ◄┐         Zusammengesetzter String "ABCXYZ" von B$(2)
          ├───────────────┤  │ │       ─┐
          │               │  │ │        │
          ├─             ─┤  │ │        │
          │               │  │ │         .          │ │         .          │ │        │  Freier, noch zuweisbarer Platz des String-Heaps
                  .          │ │        │
          │               │  │ │        │
          ├─             ─┤  │ │        │
STREND    │               │  │ │  ◄┐    │
          └───────────────┘  │ │      ─┘
                  .          │ │   
                  .          │ │   
                  .          │ │   
          ├───────────────┤  │ │   
          │   High-Byte   ││ │ │   
          ├─             ─┤├─┘ │   
          │   Low-Byte    ││   │   
          ├─             ─┤    │    
          │   Länge (6)   │    │          String-Descriptor im Array B$(), Element B$(2)
          ├───────────────┤    │   
                  .            │   
                  .            │   
                  .            │   
          ├───────────────┤    │   
          │   High-Byte   ││   │   
          ├─             ─┤├───┘   
          │   Low-Byte    ││       
          ├─             ─┤         
          │   Länge (3)   │               String-Descriptor der Variable A$
          ├───────────────┤         
                  .                
                  .                
                  .                
          ┌───────────────┐         
$0038     │   High-Byte   ││     │  
          ├─             ─┤├─────┘         MEMSIZ - Ende des BASIC-Speichers: höchstmögliche Adresse des String-Heaps
$0037     │   Low-Byte    │        
          └───────────────┘         
                  .                 
                  .                 
                  .                 
          ┌───────────────┐         
$0034     │  High-Byte    ││       │ 
          ├─             ─┤├───────┘        FRETOP - Zeigt auf den zuletzt angeforderten String (auf des 1. belegte Byte)
$0033     │   Low-Byte    │         
          ├───────────────┤          
$0032     │  High-Byte    ││         │
          ├─             ─┤├─────────┘       STREND - Ende des Array-Bereichs: niedrigstmögliche Adresse des String-Heaps
$0031     │   Low-Byte    │                          (das erste Byte nach den Arrays)
          └───────────────┘


Legende:
   belegt
   unbelegt (Lücke)
   frei


Quellen[Bearbeiten | Quelltext bearbeiten]