Indirection.html 13 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230
  1. <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html401/loose.dtd">
  2. <html>
  3. <!-- Created on December 10, 2012 by texi2html 1.82
  4. texi2html was written by:
  5. Lionel Cons <[email protected]> (original author)
  6. Karl Berry <[email protected]>
  7. Olaf Bachmann <[email protected]>
  8. and many others.
  9. Maintained by: Many creative people.
  10. Send bugs and suggestions to <[email protected]>
  11. -->
  12. <head>
  13. <title>avram - a virtual machine code interpreter: 3.1.7 Indirection</title>
  14. <meta name="description" content="avram - a virtual machine code interpreter: 3.1.7 Indirection">
  15. <meta name="keywords" content="avram - a virtual machine code interpreter: 3.1.7 Indirection">
  16. <meta name="resource-type" content="document">
  17. <meta name="distribution" content="global">
  18. <meta name="Generator" content="texi2html 1.82">
  19. <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
  20. <style type="text/css">
  21. <!--
  22. a.summary-letter {text-decoration: none}
  23. blockquote.smallquotation {font-size: smaller}
  24. pre.display {font-family: serif}
  25. pre.format {font-family: serif}
  26. pre.menu-comment {font-family: serif}
  27. pre.menu-preformatted {font-family: serif}
  28. pre.smalldisplay {font-family: serif; font-size: smaller}
  29. pre.smallexample {font-size: smaller}
  30. pre.smallformat {font-family: serif; font-size: smaller}
  31. pre.smalllisp {font-size: smaller}
  32. span.roman {font-family:serif; font-weight:normal;}
  33. span.sansserif {font-family:sans-serif; font-weight:normal;}
  34. ul.toc {list-style: none}
  35. -->
  36. </style>
  37. </head>
  38. <body lang="en" bgcolor="#FFFFFF" text="#000000" link="#0000FF" vlink="#800080" alink="#FF0000">
  39. <a name="Indirection"></a>
  40. <table cellpadding="1" cellspacing="1" border="0">
  41. <tr><td valign="middle" align="left">[<a href="Deconstruction-Functions.html#Deconstruction-Functions" title="Previous section in reading order"> &lt; </a>]</td>
  42. <td valign="middle" align="left">[<a href="The-Universal-Function.html#The-Universal-Function" title="Next section in reading order"> &gt; </a>]</td>
  43. <td valign="middle" align="left"> &nbsp; </td>
  44. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  45. <td valign="middle" align="left">[<a href="Lists.html#Lists" title="Up section"> Up </a>]</td>
  46. <td valign="middle" align="left">[<a href="Character-Table.html#Character-Table" title="Next chapter"> &gt;&gt; </a>]</td>
  47. <td valign="middle" align="left"> &nbsp; </td>
  48. <td valign="middle" align="left"> &nbsp; </td>
  49. <td valign="middle" align="left"> &nbsp; </td>
  50. <td valign="middle" align="left"> &nbsp; </td>
  51. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  52. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  53. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  54. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  55. </tr></table>
  56. <hr size="1">
  57. <a name="Indirection-1"></a>
  58. <h3 class="subsection">3.1.7 Indirection</h3>
  59. <p>In some cases it is necessary to build a tree from the top down rather
  60. <a name="index-pointers-4"></a>
  61. than from the bottom up, when it is not known in advance what&rsquo;s on the
  62. bottom. Although the <code>list</code> type is a pointer itself, these
  63. situations call for a type of pointers to lists, which are declared as
  64. the <code>branch</code> type in &lsquo;<tt>branches.h</tt>&rsquo;. For example, if <code>b</code> is
  65. declared as a <code>branch</code> and <code>l</code> is declared as a <code>list</code>,
  66. it would be possible to write <code>b = &amp;l</code>.
  67. </p>
  68. <p>Facilities are also provided for maintaining queues of branches, which
  69. <a name="index-queues-2"></a>
  70. are declared as the <code>branch_queue</code> type. This type is a pointer to
  71. a structure with two fields, <code>above</code> and <code>following</code>, where
  72. <code>above</code> is a <code>branch</code> and <code>following</code> is a
  73. <code>branch_queue</code>.
  74. </p>
  75. <p>These functions are used internally elsewhere in the library and might
  76. not be necessary for most client programs to use directly.
  77. </p>
  78. <dl>
  79. <dt><a name="index-avm_005finitialize_005fbranches"></a><u>Function:</u> void <b>avm_initialize_branches</b><i> ()</i></dt>
  80. <dd><p>This must be done once before any of the other branch related functions is
  81. used, and creates some internal data structures. Results of the other
  82. functions are undefined if this one isn&rsquo;t called first.
  83. </p></dd></dl>
  84. <dl>
  85. <dt><a name="index-avm_005fcount_005fbranches"></a><u>Function:</u> void <b>avm_count_branches</b><i> ()</i></dt>
  86. <dd><p>This function can be used at the end of a run to detect unreclaimed
  87. storage used for branches or branch queues. If any storage remains
  88. unreclaimed, a message about unreclaimed branches is written to standard
  89. error.
  90. </p></dd></dl>
  91. <dl>
  92. <dt><a name="index-avm_005fanticipate"></a><u>Function:</u> void <b>avm_anticipate</b><i> (branch_queue *<var>front</var>, branch_queue *<var>back</var>, branch <var>operand</var>)</i></dt>
  93. <dd><p>This function provides a simple queueing facility for
  94. branches. Similarly to the case with <code>avm_enqueue</code>, <code>front</code>
  95. and <code>back</code> should be initialized to <code>NULL</code> before the first
  96. call. Each call to this function will enqueue one item to the back,
  97. assuming enough memory is available, as the following example shows.
  98. </p>
  99. <table><tr><td>&nbsp;</td><td><pre class="example">front = NULL;
  100. back = NULL;
  101. l = avm_join(NULL,NULL);
  102. anticipate(&amp;front,&amp;back,&amp;(l-&gt;head));
  103. anticipate(&amp;front,&amp;back,&amp;(l-&gt;tail));
  104. </pre></td></tr></table>
  105. <p>After the above code is executed, these postconditions will hold.
  106. </p>
  107. <table><tr><td>&nbsp;</td><td><pre class="example">front-&gt;above == &amp;(l-&gt;head)
  108. front-&gt;following-&gt;above == &amp;(l-&gt;tail)
  109. front-&gt;following == back
  110. back-&gt;following == NULL
  111. </pre></td></tr></table>
  112. <p>The name &ldquo;anticipate&rdquo; is used because ordinarily the queue contains
  113. positions in a tree to be filled in later. As usual, only unshared trees should be
  114. modified in place.
  115. </p></dd></dl>
  116. <dl>
  117. <dt><a name="index-avm_005frecoverable_005fanticipate"></a><u>Function:</u> void <b>avm_recoverable_anticipate</b><i> (branch_queue *<var>front</var>, branch_queue *<var>back</var>, branch <var>operand</var>, int *<var>fault</var>)</i></dt>
  118. <dd><p>This function is similar to <code>avm_anticipate</code>, except that it will
  119. not exit with an error message in the event of an overflow error, but
  120. will simply set <code>*<var>fault</var></code> to a non-zero value and return to the
  121. caller. If an overflow occurs, nothing about the queue is changed.
  122. </p></dd></dl>
  123. <dl>
  124. <dt><a name="index-avm_005fenqueue_005fbranch"></a><u>Function:</u> void <b>avm_enqueue_branch</b><i> (branch_queue *<var>front</var>, branch_queue *<var>back</var>, int <var>received_bit</var>)</i></dt>
  125. <dd><p>A slightly higher level interface to the <code>avm_anticipate</code> function
  126. is provided by this function, which is useful for building a tree from
  127. <a name="index-trees-5"></a>
  128. a string of input bits in a format similar to the one described in
  129. <a href="Concrete-Syntax.html#Concrete-Syntax">Concrete Syntax</a>.
  130. </p>
  131. <p>This function should be called the first time with <code>front</code> and
  132. <code>back</code> having been initialized to represent a queue containing a
  133. <a name="index-queues-3"></a>
  134. single branch pointing to a list known to the caller. The list itself
  135. need not be allocated or initialized. An easy way of doing so would be
  136. the following.
  137. </p>
  138. <table><tr><td>&nbsp;</td><td><pre class="example">front = NULL;
  139. back = NULL;
  140. avm_anticipate(&amp;front,&amp;back,&amp;my_list);
  141. </pre></td></tr></table>
  142. <p>On each call to <code>avm_enqueue_branch</code>, the <code><var>received_bit</var></code>
  143. parameter is examined. If it is zero, nothing will be added to the
  144. queue, the list referenced by the front branch will be assigned
  145. <code>NULL</code>, and the front branch will be removed from the queue. If
  146. <code><var>received_bit</var></code> is a non-zero value, the list referenced by
  147. the front branch will be assigned to point to a newly created unshared
  148. list node, and two more branches will be appended to the queue. The
  149. first branch to be appended will point to the head of the newly created
  150. list node, and the second branch to be appended will point to the tail.
  151. </p>
  152. <p>If the sequence of bits conforms to the required concrete syntax, this
  153. function can be called for each of them in turn, and at the end of the
  154. sequence, the queue will be empty and the list referenced by the initial
  155. branch (i.e., <code>my_list</code>) will be the one specified by the bit
  156. string. If the sequence of bits does not conform to the required
  157. concrete syntax, the error can be detected insofar as the emptying of
  158. the queue will not coincide exactly with the last bit.
  159. </p>
  160. <p>The caller should check for the queue becoming prematurely empty due to
  161. syntax errors, because no message is reported by
  162. <code>avm_enqueue_branch</code> in that event, and subsequent attempts to
  163. enqueue anything are ignored. However, in the event of a memory overflow,
  164. an error message is reported and the process is terminated.
  165. </p></dd></dl>
  166. <dl>
  167. <dt><a name="index-avm_005frecoverable_005fenqueue_005fbranch"></a><u>Function:</u> void <b>avm_recoverable_enqueue_branch</b><i> (branch_queue *<var>front</var>, branch_queue *<var>back</var>, int <var>received_bit</var>, int *<var>fault</var>)</i></dt>
  168. <dd><p>This function is similar to <code>avm_enqueue_branch</code> but will leave
  169. error handling to the caller in the event of insufficient memory to
  170. enqueue another branch. Instead of printing an error message and
  171. exiting, it will dispose of the queue, set the <code><var>fault</var></code> flag
  172. to a non-zero value, and return. Although the queue will be reclaimed,
  173. the lists referenced by the branches in it will persist. The list nodes
  174. themselves can be reclaimed by disposing of the list whose address was
  175. stored originally in the front branch.
  176. </p></dd></dl>
  177. <dl>
  178. <dt><a name="index-avm_005fdispose_005fbranch_005fqueue"></a><u>Function:</u> void <b>avm_dispose_branch_queue</b><i> (branch_queue <var>front</var>)</i></dt>
  179. <dd><p>This function deallocates a branch queue by chasing the <code>following</code>
  180. fields in each one. It does nothing to the lists referenced by the
  181. branches in the queue.
  182. </p>
  183. <p>Rather than using <code>free</code> directly, client programs should use this
  184. function for deallocating branch queues, because it allows better
  185. performance by interacting with a local internal cache of free memory,
  186. and because it performs necessary bookkeeping for
  187. <code>avm_count_branches</code>.
  188. </p></dd></dl>
  189. <dl>
  190. <dt><a name="index-avm_005fdispose_005fbranch"></a><u>Function:</u> void <b>avm_dispose_branch</b><i> (branch_queue <var>old</var>)</i></dt>
  191. <dd><p>This disposes of a single branch queue node rather than a whole queue.
  192. Otherwise, the same comments as those above apply.
  193. </p></dd></dl>
  194. <hr size="1">
  195. <table cellpadding="1" cellspacing="1" border="0">
  196. <tr><td valign="middle" align="left">[<a href="Deconstruction-Functions.html#Deconstruction-Functions" title="Previous section in reading order"> &lt; </a>]</td>
  197. <td valign="middle" align="left">[<a href="The-Universal-Function.html#The-Universal-Function" title="Next section in reading order"> &gt; </a>]</td>
  198. <td valign="middle" align="left"> &nbsp; </td>
  199. <td valign="middle" align="left">[<a href="Library-Reference.html#Library-Reference" title="Beginning of this chapter or previous chapter"> &lt;&lt; </a>]</td>
  200. <td valign="middle" align="left">[<a href="Lists.html#Lists" title="Up section"> Up </a>]</td>
  201. <td valign="middle" align="left">[<a href="Character-Table.html#Character-Table" title="Next chapter"> &gt;&gt; </a>]</td>
  202. <td valign="middle" align="left"> &nbsp; </td>
  203. <td valign="middle" align="left"> &nbsp; </td>
  204. <td valign="middle" align="left"> &nbsp; </td>
  205. <td valign="middle" align="left"> &nbsp; </td>
  206. <td valign="middle" align="left">[<a href="avram.html#Top" title="Cover (top) of document">Top</a>]</td>
  207. <td valign="middle" align="left">[<a href="avram_toc.html#SEC_Contents" title="Table of contents">Contents</a>]</td>
  208. <td valign="middle" align="left">[<a href="Function-Index.html#Function-Index" title="Index">Index</a>]</td>
  209. <td valign="middle" align="left">[<a href="avram_abt.html#SEC_About" title="About (help)"> ? </a>]</td>
  210. </tr></table>
  211. <p>
  212. <font size="-1">
  213. This document was generated on <i>December 10, 2012</i> using <a href="http://www.nongnu.org/texi2html/"><i>texi2html 1.82</i></a>.
  214. </font>
  215. <br>
  216. </p>
  217. </body>
  218. </html>