home *** CD-ROM | disk | FTP | other *** search
/ Turbo Toolbox / Turbo_Toolbox.iso / cebit_91 / tricks / realloc.doc < prev    next >
Encoding:
Text File  |  1991-03-07  |  5.0 KB  |  165 lines
  1. "realloc"-Implementation  (toolbox-Praxis 4'91)
  2.  
  3. Mehr Dynamik für Turbo Pascal
  4.  
  5. von Gerd Cebulla
  6.  
  7.  
  8. Die Verwaltung größerer Datenmengen
  9. läßt sich in der Regel nur mit Hilfe
  10. von dynamischen Variablen bewerkstelli-
  11. gen.
  12. Was Turbo Pascal fehlt, ist ein Befehl,
  13. der die Größe des für eine dynamische
  14. Variable belegten Speicherbereichs
  15. nachträglich verändert -- sozusagen
  16. eine "Dynamisierung der dynamischen
  17. Speicherverwaltung". Eine solche Funk-
  18. tion hat übrigens jeder x-beliebige C-
  19. Compiler unter dem Namen "realloc" im-
  20. plementiert. Die Unit "Realloc"
  21. implementiert die dynamische Freigabe
  22. von Speicher für Turbo Pascal.
  23.  
  24. Zur Verwaltung von dynamischem
  25. Speicher stellt Turbo Pascal dem Pro-
  26. grammierer mit den Standardprozeduren
  27. New/Dispose und GetMem/FreeMem sowie
  28. Mark/Release auch alle nötigen Hilfs-
  29. mittel zur Verfügung.
  30.  
  31. Wirklich alle? Nehmen wir einmal an,
  32. Sie schreiben eine Textverarbeitung.
  33. Normalerweise wird das in Form einer
  34. doppelt verketteten Liste von Zeigern
  35. auf Strings (respektive Char-Arrays)
  36. realisiert. Nun werden vom Anwender
  37. hemmungslos Zeichen eingefügt oder ge-
  38. löscht sowie Zeilen umgebrochen -- die
  39. Länge einer Zeile ist also laufenden
  40. Änderungen unterworfen.
  41.  
  42. Diesem Problem könnte man dadurch be-
  43. gegnen, daß man für jede Zeile von
  44. vornherein die maximal mögliche Anzahl
  45. Zeichen (z. B. 80) reserviert. Diese
  46. Methode stellt jedoch nicht nur eine
  47. gigantische Speicherplatzverschwendung
  48. dar, sondern hat auch noch den Nachteil
  49. mangelnder Flexibilität -- nach Murphys
  50. Gesetzen hat garantiert der übernächste
  51. Anwender einen DIN-A3-Drucker und benö-
  52. tigt mindestens 120 Zeichen pro Zei-
  53. le...
  54.  
  55. Es hilft alles nichts -- wir müssen den
  56. Speicherplatz dynamisch verwalten. Un-
  57. ter Turbo Pascal muß dazu zunächst ein
  58. Speicherbereich mit der neuen Größe
  59. belegt, sodann der Inhalt der alten
  60. dynamischen Variable umkopiert und
  61. schließlich der alte Speicherplatz
  62. freigegeben werden. Das sieht dann un-
  63. gefähr so aus:
  64.  
  65.   GetMem(PNeu, NeueGroesse);
  66.   IF NeueGroesse < AlteGroesse THEN
  67.     Groesse := NeueGroesse
  68.   ELSE
  69.     Groesse := AlteGroesse;
  70.   Move(P^, PNeu^, Groesse);
  71.   FreeMem(P, AlteGroesse);
  72.   P := PNeu;
  73.  
  74. Das ist erstens recht umständlich,
  75. zweitens wird temporär für ein und die-
  76. selbe Variable gleich zweimal Speicher-
  77. platz belegt, was bei größeren Arrays
  78. durchaus zu Problemen führen kann; vor
  79. allem aber ist diese Methode extrem
  80. rechenaufwendig -- schließlich müssen
  81. bei jeder Größenänderung soundso viele
  82. Byte in einen anderen Speicherbereich
  83. kopiert werden.
  84.  
  85. Bei einem Turbo-Pascal-Programm liegt
  86. der Heap oberhalb aller Code- und Da-
  87. tensegmente. Bei jedem Aufruf von "New"
  88. bzw. "GetMem" wird an der niedrigsten
  89. verfügbaren Adresse Speicherplatz re-
  90. serviert; der Heap wächst also von un-
  91. ten nach oben. Wenn bei der Freigabe
  92. einer dynamischen Variable ein "Loch"
  93. im Heap entsteht, trägt Turbo die
  94. Start- und Endadresse des Lochs in die
  95. sogenannte Fragmentliste ein. Die Frag-
  96. mentliste befindet sich am oberen Ende
  97. des Programmspeichers und wächst von
  98. oben nach unten.
  99.  
  100. Zur Verwaltung des Heap deklariert die
  101. Laufzeitbibliothek von Turbo-Pascal
  102. einige globale Variable: "HeapOrg" ist
  103. ein Zeiger auf den Heapanfang,
  104. "HeapPtr" zeigt auf den Beginn des
  105. freien Heap, und "FreePtr" enthält die
  106. Startadresse der Fragmentliste. Mit
  107. diesem Rüstzeug ausgestattet, können
  108. wir uns daran machen, eine Funktion zur
  109. nachträglichen Veränderung der Größe
  110. einer dynamischen Variablen zu schrei-
  111. ben.
  112.  
  113.  
  114. Diese Funktion -- nennen wir sie "Chan-
  115. geMem" -- benötigt drei Argumente: ei-
  116. nen Zeiger auf die dynamische Variable,
  117. die derzeitige Größe der Variable und
  118. die gewünschte neue Größe. Wenn die
  119. neue Größe kleiner als die alte ist,
  120. ist die Sache einfach: Wir brauchen
  121. lediglich den nicht mehr benötigten
  122. Speicherplatz freizugeben, das heißt,
  123. in die Fragmentliste einzutragen.
  124.  
  125. Soll der belegte Speicherplatz dagegen
  126. vergrößert werden, schaut "ChangeMem"
  127. zunächst in der Fragmentliste nach, ob
  128. oberhalb der dynamischen Variable genug
  129. Platz verfügbar ist. Ist das der Fall,
  130. wird dieser Bereich belegt; andernfalls
  131. ermittelt "ChangeMem" den freien Be-
  132. reich unterhalb der dynamischen Varia-
  133. ble. Reicht dieser aus, wird er belegt
  134. und der Inhalt der Variable auf eine
  135. entsprechend niedrigere Adresse ko-
  136. piert.
  137.  
  138. Schlägt auch dieser Versuch fehl,
  139. bleibt nur noch die übliche Methode:
  140. Reservierung eines Speicherbereichs mit
  141. der neuen Größe, Kopieren der Variable
  142. und anschließende Freigabe des alten
  143. Bereichs.
  144.  
  145. Die Funktion "ChangeMem" ist in der
  146. Unit "ReAlloc" implementiert. Der Auf-
  147. ruf geschieht wie folgt:
  148.  
  149.   PNeu := ChangeMem(P, AlteGroesse,
  150.                     NeueGroesse);
  151.  
  152. Als Funktionsergebnis wird ein Zeiger
  153. auf die neue Adresse der dynamischen
  154. Variable zurückgeliefert. Falls auf dem
  155. Heap nicht mehr genug Platz verfügbar
  156. ist, wird der Wert "NIL" zurückgegeben,
  157. vorausgesetzt daß Sie eine eigene Heap-
  158. Fehlerbehandlung installiert haben;
  159. siehe dazu das Kapitel "Interne De-
  160. tails" im Referenzhandbuch.
  161.  
  162.                    (wr)
  163.  
  164.  
  165.