Datenspeicherung und Datenstrukturen

Trees

'Baume' stellen eine Datenstruktur dar. Hier ist der Zugriff auf einzelne Daten meist hierarchisch gegliedert. Man fängt bei der 'Wurzel' (root) an und kann sich dann über mehrere Stufen zum gewünschten Datum hinbewegen. Auf jeder Stufe 'veraestelt' sich der Baum, man hat dann mehrere Möglichkeiten, sich für den Pfad zu entscheiden, der zum gewünschten Datum führt.

Sub-Directories

Eine sehr sinnvolle Anwendung für solche Hierarchien sind Trees: Sub-DirectoriesSub-Directories, die man bei manchen Disketten-Betriebssystemen auf einer Diskette anlegen kann. Beim Atari ST werden sie beispielsweise 'Ordner' genannt, dahinter verbirgt sich aber genau dieses Konzept. Bei den geringen Speicher-Kapazitäten der 3-Zoll-Floppies sind derartige Spielereien noch nicht unbedingt nötig, immerhin kann man seine Diskette aber auch hier in mehrere USER-Bereiche einteilen.

Sinnvoll sind soche Unter-Inhaltsverzeichnisse vor allem dann, wenn ein Speicher mit mehreren Megabytes zur Verfügung steht, also eine Hard-Disc etwa.

Der Zugriff auf eine bestimmte Datei unter Die Abteilungen des Betriebssystems: AmsdosAmsdos könnte immerhin auch schon Baum-foermig dargestellt werden:

                     Die Abteilungen des Betriebssystems: AmsdosAMSDOS
                      / \
                     /   \
                    /     \
             Laufwerk Operationen: BD5B / 349A / 349A:  FLO SUBA   Laufwerk LOW KERNEL JUMPBLOCK: 000B:  LOW KL LOW PCHL
LOW KERNEL JUMPBLOCK: 001B:  LOW KL FAR PCHL
LOW KERNEL JUMPBLOCK: 003B:  LOW EXT INTERRUPTB
              / | \        /  |  \
             /  |  \      /   |   \
            /   |        /    |    User 2
           /            /    User 1
         User 0       User 0
                      / | \
                     /  |  \
                    /   |  "wordstar.com"
                   /   "bestellg.002"
           "brief.001"

Um den Brief einzuladen, muss man Die Abteilungen des Betriebssystems: AmsdosAMSDOS bewegen, auf Laufwerk LOW KERNEL JUMPBLOCK: 000B: LOW KL LOW PCHL
LOW KERNEL JUMPBLOCK: 001B: LOW KL FAR PCHL
LOW KERNEL JUMPBLOCK: 003B: LOW EXT INTERRUPTB im User-Bereich 0 nachzuschauen und dort die Datei "brief.001" zu laden. Die Abteilungen des Betriebssystems: AmsdosAmsdos ist die Wurzel und der Baum wächst typischerweise nach unten.

Listen

Auch die Trees: ListenListen von Einleitung: LOGO
Übergabe von Argumenten und Ergebnissen: LOGO:LOGO lassen sich leicht mit einer baumartig verzweigten Kette realisieren. Jedem Datenelement muss man dsabei (mindestens) zwei Pointer zuordnen: Einen, mit dem man ein Element innerhalb einer übergeordneten Trees: ListenListe einreiht und einen, der eventuell auf eine eigene Trees: ListenListe zeigt, die durch dieses Element 'benannt' ist:

Trees: ListenListe in Einleitung: LOGO
Übergabe von Argumenten und Ergebnissen: LOGO:LOGO: [ 100 200 [30 40 50] [1 2 3] ]

Diese Trees: ListenListe enthält zwei Unterlisten: [30 40 50] und [1 2 3]. Das folgende Beispiel zeigt, wie man diese verschachtelten Trees: ListenListen im Speicher darstellen kann:

Startpointer --+      +---> POINTER4-----> POINTER5-----> POINTER6--->O
               |      |     pointer4->O    pointer5->O    pointer6->O
               |      |        1              2              3
               |      |
 +-------------+      +-------------------------------------------+
 |                                                                |
 +--> POINTER0-----> POINTER1-----> POINTER2-----> POINTER3-->O   |
      pointer0->O    pointer1->0    pointer2--+    pointer3-------+
       100            200            Trees: ListenLISTE    |     Trees: ListenLISTE
                                              |
                      +-----------------------+
                      |
+-----------+         +---> POINTER7-----> POINTER8-----> POINTER9----->O
|Anm.: O=NIL|               pointer7->O    pointer8->O    pointer9->O
+-----------+                 30             40             50

Es gibt aber noch viele andere, mögliche Form für verkettete Trees: ListenListen. Man kann auch Ringspeicher realisieren, indem man in den letzten Pointer nicht NIL sondern wieder ein Zeiger auf das erste Element der Trees: ListenListe einträgt. Man kann aber auch die Datenspeicherung und Datenstrukturen: RecordsRecords in einer verketteten Trees: ListenListe über je einen Vor- und Rückwärtszeiger verknuepfen, um sich innerhalb der Trees: ListenListe in beiden Richtungen bewegen zu können. Nicht nur baumartige Iterationen - Schleifen: StrukturStrukturen sondern auch mehrdimensionale Felder sind realisierbar. Unter praktischen Gesichtspunkten sind die aber fast ausschließlich den Datenspeicherung und Datenstrukturen: ArraysArrays vorbehalten.

verkettete Listen im CPC

Das Betriebssystem des Schneider CPCDas Betriebssystem des Schneider CPC verwendet verkettete Trees: ListenListen hauptsächlich im MAIN FIRMWARE JUMPBLOCK: KERNEL
Die Firmware des Schneider CPC: KERNELKernel: Die Interrupt-verursachenden Trees: ListenListen sind allesamt Datenspeicherung und Datenstrukturen: ChainsChains:

li Die Ticker Datenspeicherung und Datenstrukturen: ChainsChain, li die Fast Ticker Datenspeicherung und Datenstrukturen: ChainsChain und li die Frame Flyback Datenspeicherung und Datenstrukturen: ChainsChain.

Auch die Trees: ListenListen, in die die gekickten Ereignisse bis zu ihrer Bearbeitung eingereiht werden, sind Datenspeicherung und Datenstrukturen: ChainsChains:

li Die asynchronous pending queue und li die synchronous pending queue.

Bei der letzteren kommt als eine Variante noch hinzu, dass hier die einzelnen Einträge eine Priorität haben und vom MAIN FIRMWARE JUMPBLOCK: KERNEL
Die Firmware des Schneider CPC: KERNELKernel entsprechend eingereiht werden.

Außerdem sind auch noch die Tabellen für die externen Kommandos (Maschinencode über HIMEM: RSXRSX'es) über verkettete Trees: ListenListen verknuepft, wofür man bei jedem Aufruf von KERNEL: BCD1: KL LOG EXTKL LOG EXT vier Datentypen: Bytes
Datenbreite: BytesBytes des freien Speichers zur Verfügung stellen muss.