-
Notifications
You must be signed in to change notification settings - Fork 1
/
collection.html
116 lines (68 loc) · 4.68 KB
/
collection.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
<html>
<head>
<meta charset='utf-8'>
<title>collection</title>
</head>
<body>
<h1>collection</h1>
<h2>Syntax</h2>
A <i>collectionDeclaration</i> is one of:<p>
</p>
<table>
<tr valign="top">
<td width="40"> </td>
<td width="40"><font size="+1">(a)</font></td>
<td colspan="7"><font size="+1"><b>var</b> <i>id </i>{ , <i>id </i>} : <b>collection</b> <b>of</b> <i>typeSpec</i></font></td>
</tr>
<tr valign="top">
<td width="40"> </td>
<td width="40"><font size="+1">(b)</font></td>
<td colspan="7"><font size="+1"><b>var</b> <i>id </i>{ , <i>id </i>} : <b>collection</b> <b>of</b> <b>forward</b> <i>typeId</i></font></td>
</tr>
</table>
<p></p>
<h2>Description</h2>
A collection declaration creates a new collection (or collections). A collection can be thought of as an array whose elements are dynamically created (by <b>new</b>) and deleted (by <b>free</b>). Elements of a collection are referred to by the collection's name subscripted by a pointer. See also <b>new</b>, <b>free</b> and <b>pointer</b>.<p>
</p>
<h2>Example</h2>
Create a collection that will represent a binary tree.<p>
</p>
<pre><code> var tree : collection of
record
name : string (10)
left, right : pointer to tree
end record
var root : pointer to tree
new tree, root
tree (root) . name := "Adam"</code></pre>
<h2>Details</h2>
The statement "<b>new</b> <i>C</i>,<i>p</i>" creates a new element in collection <i>C</i> and sets <i>p</i> to point at <i>i</i>. If there is no more memory space for the element, though, <i>p</i> is set to <i>nil</i> (<i>C</i>), which is the null pointer for collection <i>C</i>. The statement "<b>free</b> <i>C</i>,<i>p</i>" deletes the element of <i>C</i> pointed to by <i>p</i> and sets <i>p</i> to <i>nil</i> (<i>C</i>). In each case, <i>p</i> is passed as a <b>var</b> parameter and must be a variable of the pointer type of <i>C</i>.<p>
The keyword <b>forward</b> (form b above) is used to specify that the <i>typeId</i> of the collection elements will be given later in the collection's scope. The later declaration must appear at the same level (in the same list of declarations and statements) as the original declaration. This allows cyclic collections, for example, when a collection contains pointers to another collection, which in turn contains pointers to the first collection. In this case, the <i>typeId</i> is the name of the type that has not yet been declared; <i>typeId</i> cannot be used until its declaration appears. A collection whose element type is <b>forward</b> can be used only to declare pointers to it until the type's declaration is given.</p>
<p>
Suppose pointer <i>q</i> is equal to pointer <i>p</i> and the element they point to is deleted by "<b>free</b> <i>C</i>,<i>p</i>". We say <i>q</i> is a <i>dangling pointer</i> because it seems to locate an element, but the element no longer exists. A dangling pointer is considered to be an uninitialized value. It cannot be assigned, compared, used as a collection subscript, or passed to <b>free</b>.</p>
<p>
Collections cannot be assigned, compared, passed as parameters, bound to, or named by a <b>const</b> declaration. Collections must not be declared in procedures, functions, records or unions.</p>
<p>
The same short forms for classes can be also used for collections. These include omission of the collection name in <b>new</b>, <b>free</b> and <b>nil</b> together with the ^ and -> notations. Pointers to types (see <b>pointer</b>) can also be used, which are often more convenient to use than collections.</p>
<p>
The syntax of a <i>collectionDeclaration</i> presented above has been simplified by leaving out <b>unchecked</b> collections. With this feature, a <i>collectionDeclaration</i> is one of:</p>
<p>
</p>
<table>
<tr valign="top">
<td width="40"> </td>
<td>(a) <b>var</b> <i>id </i>{ , <i>id </i>} : [ <b>unchecked</b> ] <b>collection</b> <b>of</b> <i>typeSpec</i>
</td>
</tr>
<tr valign="top">
<td width="40"> </td>
<td>(b)<i> </i><b>var</b> <i>id </i>{ , <i>id </i>} : [ <b>unchecked</b> ] <b>collection</b> <b>of</b> <b>forward</b> <i>typeId</i>
</td>
</tr>
</table>
<p>
When <b>unchecked</b> is specified, the checking to verify that pointers actually locate elements is removed. This checking is done using a "time stamp" attached to each element and pointer, and making sure that these match with each other. When <b>unchecked</b> is specified, the execution is dangerous, but faster and smaller, and the pointers become simply machine addresses (as in C).</p>
<p>
</p>
</body>
</html>