home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 5 / DATAFILE_PDCD5.iso / utilities / e / exthelp / !Ext / Heap < prev    next >
Text File  |  1993-04-12  |  12KB  |  402 lines
  1. Heap memory manager
  2. ===================
  3.  
  4. WimpExtension's heap manager is one of the module's most powerful, useful,
  5. and - unavoidably - complicated features. This document is provided to
  6. explain more about what a relocatable heap is, and how to use it.
  7.  
  8. Programming examples in this document are given in BASIC, because practically
  9. everyone knows how to use it.
  10.  
  11. This document assumes that you know how to program in the RISC OS Wimp, and
  12. that you understand terms such as "WimpSlot" (read the chapter "The Window
  13. Manager" in the PRMs if you don't).
  14.  
  15. Read the "SWIs" and "Manual" files for a brief description of the parameters
  16. for the SWI WimpExt_Heap.
  17.  
  18.  
  19.  
  20. Why do I need a heap?
  21. ---------------------
  22.  
  23. Any program which uses more than one block of memory which changes size needs
  24. a heap manager. For example, Edit and Paint need a heap manager, because they
  25. can have several files loaded at once, all of which can be changing size at
  26. any time. The files are loaded into memory "blocks", which are provided by
  27. the heap manager.
  28.  
  29.  
  30.  
  31. Why use a relocatable heap?
  32. ---------------------------
  33.  
  34. RISC OS provides a non-relocatable heap manager. This means that the memory
  35. blocks are fixed in memory, and don't move about. The problem with this is
  36. that it gets very wasteful on memory when you have finished using the block.
  37. Say you loaded three files into a text editor:
  38.  
  39.   /--------\ Highest memory address
  40.   | File 3 |
  41.   |        |
  42.   |--------|
  43.   | File 2 |
  44.   |        |
  45.   |        |
  46.   |--------|
  47.   | File 1 |
  48.   \--------/ Lowest memory address
  49.  
  50. This is fine, no problems so far. However, suppose the user decided the close
  51. the file "File 2":
  52.  
  53.   /--------\ Highest memory address
  54.   | File 3 |
  55.   |        |
  56.   |--------|
  57.   | unused |
  58.   |        |
  59.   |        |
  60.   |--------|
  61.   | File 1 |
  62.   \--------/ Lowest memory address
  63.  
  64. The block of memory in the middle is now unused, and is wasting space. A
  65. non-relocatable heap manager can't do anything about this. Another example is
  66. if the user adds something to File 2, making it longer. File 2 will no longer
  67. fit in its original block - if you extended it then it would overwrite
  68. File 3. Therefore the heap manager has to copy the whole file up in memory,
  69. as shown in the diagram:
  70.  
  71.   /--------\ Highest memory address
  72.   | File 2 |
  73.   |        |
  74.   |        |
  75.   |        |
  76.   |--------|
  77.   | File 3 |
  78.   |        |
  79.   |--------|
  80.   | unused |
  81.   |        |
  82.   |        |
  83.   |--------|
  84.   | File 1 |
  85.   \--------/ Lowest memory address
  86.  
  87. WimpExtension provides a relocatable heap manager, however. This means that
  88. the heap manager is allowed to move the blocks about, to try and reduce the
  89. amount of wasted memory. In the situation above, for example, WimpExtension
  90. would move File 2 and File 3 down in memory, like so:
  91.  
  92.   /--------\ Highest memory address
  93.   | File 2 |
  94.   |        |
  95.   |        |
  96.   |        |
  97.   |--------|
  98.   | File 3 |
  99.   |        |
  100.   |--------|
  101.   | File 1 |
  102.   \--------/ Lowest memory address
  103.  
  104. As you can see, this can save a lot of memory.
  105.  
  106.  
  107.  
  108. Anchors
  109. -------
  110.  
  111. The only disadvantage of a reloctable heap is due to the fact that it IS
  112. relocatable - the blocks of memory aren't fixed and may move about. A
  113. question which immediately arises is "How do I find my memory block?" - if
  114. the block may have moved, how do you find it?
  115.  
  116. The answer is by using an "anchor". An anchor is a word in memory. The
  117. contents of this word is always a pointer to the start of the block. ie:
  118.  
  119.                       /-------\
  120.                       |       |
  121.   /--------\          |       |
  122.   | anchor |--------->| block |
  123.   \--------/          \-------/
  124.  
  125. The anchor always stays fixed in the same place in memory, so you always know
  126. where to find it. So, to find the location of your block, you would use:
  127.  
  128.   block%=!anchor% : REM block% now points to the first byte in the block
  129.  
  130. The anchors are stored all together at the beginning of the heap.
  131.  
  132.  
  133.  
  134. Size of blocks
  135. --------------
  136.  
  137. The word before the start of any block contains the size of the block in
  138. bytes. So to find the size of a block, you would use:
  139.  
  140.   size%=!(block%-4)
  141.  
  142. or:
  143.  
  144.   size%=!( (!anchor%) -4)
  145.  
  146. (because block%=!anchor%).
  147.  
  148. Due to the way the heap manager works, the size of a block is always four
  149. plus a multiple of eight (ie. 12, 20, 28, etc.). If you ask WimpExtension to
  150. make a block with a size which isn't four plus a multiple of eight, then the
  151. size will be rounded up by between one and seven bytes, to take it to the
  152. next largest acceptable size.
  153.  
  154.  
  155.  
  156. Initialising the heap
  157. ---------------------
  158.  
  159. Before you can use any of the heap operations, you must initialise the heap.
  160. This requires two parameters - the number of anchors to create initially, and
  161. the address in memory of the base of the heap.
  162.  
  163. The anchors are stored all together at the beginning of the heap. Because you
  164. need one anchor for every block in use, the number of anchors is effectively
  165. the maximum number of blocks you can have in use at any one time. You can
  166. create more anchors later, but it is best to create enough now, and then you
  167. don't have to worry about it later. Remember that anchors do take memory
  168. though, so don't go wild.
  169.  
  170. For example:
  171.  
  172.   SYS "WimpExt_Heap",0,base%,anchors%
  173.  
  174. Note that a heap which is empty (ie. no blocks are in use) takes absolutely
  175. no memory at all.
  176.  
  177.  
  178.  
  179. Allocating blocks
  180. -----------------
  181.  
  182. Whenever you ask WimpExtension to make you a new block (called "allocating" a
  183. block), it gives you a pointer to the anchor for that block. You must store
  184. the pointer to the anchor, NOT the pointer to the block, because the anchor
  185. will never move, but the block may do. For example, to ask WimpExtension for
  186. a block "size%" bytes long, you would use:
  187.  
  188.   SYS "WimpExt_Heap",2,,size% TO ,anchor%
  189.  
  190. If WimpExtension cannot create the block, because there is not enough free
  191. memory, then the anchor returned will be zero. You need to check for this
  192. before writing anything into the block. eg:
  193.  
  194.   SYS "WimpExt_Heap",2,,size% TO ,anchor%
  195.   IF anchor%=0 THEN ERROR 1,"Not enough free memory"
  196.  
  197.  
  198.  
  199. Freeing blocks
  200. --------------
  201.  
  202. When you have finished using a block, you use the "Free block" call to tell
  203. WimpExtension that you don't need the block any more, and the memory it takes
  204. up can be re-used. eg:
  205.  
  206.   SYS "WimpExt_Heap",3,anchor%
  207.  
  208. or:
  209.  
  210.   SYS "WimpExt_Heap",3,block%
  211.  
  212. The block will be added to WimpExtension's list of free blocks.
  213.  
  214.  
  215.  
  216. Reallocating blocks
  217. -------------------
  218.  
  219. Sometimes you will want to re-size a block - this is called "reallocating"
  220. the block. WimpExtension allows you to increase or decrease the size of any
  221. block at any time. eg:
  222.  
  223.   SYS "WimpExt_Heap",4,block%,new_size% TO ,flag%
  224.  
  225. or:
  226.  
  227.   SYS "WimpExt_Heap",4,anchor%,new_size% TO ,flag%
  228.  
  229. If the flag is zero on exit then the re-size failed because there wasn't
  230. enough free memory.
  231.  
  232. Note that this call may cause the specified block to move in memory. Only the
  233. specific block that you are re-sizing can move, though - all the other blocks
  234. will stay where they are.
  235.  
  236.  
  237.  
  238. Garbarge collection
  239. -------------------
  240.  
  241. "Garbage collection" is the whole point of the relocatable heap. This is the
  242. process of shuffling the blocks about in memory, so that no memory is wasted.
  243. For example, if the heap was in the following state:
  244.  
  245.   /---------\ Highest memory address
  246.   | block 2 |
  247.   |         |
  248.   |---------|
  249.   |  free   |
  250.   |         |
  251.   |         |
  252.   |---------|
  253.   | block 1 |
  254.   \---------/ Lowest memory address
  255.  
  256. then performing garbage collection would shuffle the blocks as follows:
  257.  
  258.   /---------\ Highest memory address
  259.   | block 2 |
  260.   |         |
  261.   |---------|
  262.   | block 1 |
  263.   \---------/ Lowest memory address
  264.  
  265. This then allows WimpExtension to decrease your task's WimpSlot, thus making
  266. this memory available to any other programs which might need it.
  267.  
  268. Two garbage collection calls are provided; the Tidy call:
  269.  
  270.   SYS "WimpExt_Heap",5
  271.  
  272. and the Compact call:
  273.  
  274.   SYS "WimpExt_Heap",6
  275.  
  276. The Tidy call just tidies the heap a little bit - the heap won't necessarily
  277. immediately be shuffled into the ideal position, but the call is usually
  278. quite fast. This call is intended to be called just before you call
  279. Wimp_Poll. If you set bit 3 of R2 when you called WimpExt_Initialise, then
  280. the heap will be automatically Tidied once a second, in WimpExt_PrePoll. Most