Context Navigation

sequence.hfa @ 7c1144b

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum

Last change on this file since 7c1144b was 7c1144b, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago
formatting, more switch from pointer to reference
Property mode set to `100644`
File size: 9.5 KB

Line
1	#pragma once
2
3	#include "collection.hfa"
4
5	struct Seqable {
6	inline Colable;
7	Seqable * back; // pointer to previous node in the list
8	};
9
10	inline {
11	// PUBLIC
12
13	void ?{}( Seqable & sq ) with( sq ) {
14	((Colable &) sq){};
15	back = 0p;
16	} // post: ! listed()
17
18	Seqable & getBack( Seqable & sq ) with( sq ) {
19	return *back;
20	}
21
22	// PRIVATE
23
24	Seqable & Back( Seqable sq ) {
25	return sq->back;
26	}
27
28	// wrappers to make Collection have T
29	forall( dtype T ) {
30	T *& Back( T & n ) {
31	return (T )Back( (Seqable )&n );
32	}
33
34	T & head( Sequence(T) & s ) with( s ) {
35	return (T )head( (Collection &)s );
36	} // post: empty() & head() == 0 \| !empty() & head() in *s
37	} // distribution
38	} // distribution
39
40	forall( dtype T ) {
41	struct Sequence {
42	inline Collection; // Plan 9 inheritance
43	};
44
45	inline {
46	void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
47	Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
48
49	void ?{}( Sequence(T) & s ) with( s ) {
50	((Collection &) s){};
51	} // post: isEmpty().
52
53	// Return a pointer to the last sequence element, without removing it.
54	T & tail( Sequence(T) & s ) with( s ) {
55	return root ? (T &)Back( head( s ) ) : 0p;
56	} // post: empty() & tail() == 0 \| !empty() & tail() in *s
57
58	// Return a pointer to the element after *n, or 0p if list empty.
59	T * succ( Sequence(T) & s, T * n ) with( s ) { // pre: n in s
60	#ifdef __CFA_DEBUG__
61	if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
62	#endif // __CFA_DEBUG__
63	return Next( n ) == &head( s ) ? 0p : Next( n );
64	} // post: n == tail() & succ(n) == 0 \| n != tail() & succ(n) in s
65
66	// Return a pointer to the element before *n, or 0p if there isn't one.
67	T * pred( Sequence(T) & s, T * n ) with( s ) { // pre: n in s
68	#ifdef __CFA_DEBUG__
69	if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
70	#endif // __CFA_DEBUG__
71	return n == &head( s ) ? 0p : Back( *n );
72	} // post: n == head() & head(n) == 0 \| n != head() & pred(n) in s
73
74
75	// Insert n into the sequence before bef, or at the end if bef == 0.
76	void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & bef in s
77	#ifdef __CFA_DEBUG__
78	if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
79	#endif // __CFA_DEBUG__
80	if ( &bef == &head( s ) ) { // must change root
81	if ( root ) {
82	Next( n ) = &head( s );
83	Back( n ) = Back( head( s ) );
84	// inserted node must be consistent before it is seen
85	asm( "" : : : "memory" ); // prevent code movement across barrier
86	Back( head( s ) ) = &n;
87	Next( *Back( n ) ) = &n;
88	} else {
89	Next( n ) = &n;
90	Back( n ) = &n;
91	} // if
92	// inserted node must be consistent before it is seen
93	asm( "" : : : "memory" ); // prevent code movement across barrier
94	root = &n;
95	} else {
96	if ( ! &bef ) &bef = &head( s );
97	Next( n ) = &bef;
98	Back( n ) = Back( bef );
99	// inserted node must be consistent before it is seen
100	asm( "" : : : "memory" ); // prevent code movement across barrier
101	Back( bef ) = &n;
102	Next( *Back( n ) ) = &n;
103	} // if
104	} // post: n->listed() & n in s & succ(n) == bef
105
106
107	// Insert n into the sequence after aft, or at the beginning if aft == 0.
108	void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & aft in s
109	#ifdef __CFA_DEBUG__
110	if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
111	#endif // __CFA_DEBUG__
112	if ( ! &aft ) { // must change root
113	if ( root ) {
114	Next( n ) = &head( s );
115	Back( n ) = Back( head( s ) );
116	// inserted node must be consistent before it is seen
117	asm( "" : : : "memory" ); // prevent code movement across barrier
118	Back( head( s ) ) = &n;
119	Next( *Back( n ) ) = &n;
120	} else {
121	Next( n ) = &n;
122	Back( n ) = &n;
123	} // if
124	asm( "" : : : "memory" ); // prevent code movement across barrier
125	root = &n;
126	} else {
127	Next( n ) = Next( aft );
128	Back( n ) = &aft;
129	// inserted node must be consistent before it is seen
130	asm( "" : : : "memory" ); // prevent code movement across barrier
131	Back( *Next( n ) ) = &n;
132	Next( aft ) = &n;
133	} // if
134	} // post: n->listed() & n in s & succ(n) == bef
135
136	// pre: n->listed() & n in s
137	void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
138	#ifdef __CFA_DEBUG__
139	if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
140	#endif // __CFA_DEBUG__
141	if ( &n == &head( s ) ) {
142	if ( Next( head( s ) ) == &head( s ) ) root = 0p;
143	else root = Next( head( s ) );
144	} // if
145	Back( *Next( n ) ) = Back( n );
146	Next( *Back( n ) ) = Next( n );
147	Next( n ) = Back( n ) = 0p;
148	} // post: !n->listed().
149
150	// Add an element to the head of the sequence.
151	void addHead( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
152	insertAft( s, *0p, n );
153	}
154	// Add an element to the tail of the sequence.
155	void addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
156	insertBef( s, n, *0p );
157	}
158	// Add an element to the tail of the sequence.
159	void add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
160	addTail( s, n );
161	}
162	// Remove and return the head element in the sequence.
163	T & dropHead( Sequence(T) & s ) {
164	T & n = head( s );
165	return &n ? remove( s, n ), n : *0p;
166	}
167	// Remove and return the head element in the sequence.
168	T & drop( Sequence(T) & s ) {
169	return dropHead( s );
170	}
171	// Remove and return the tail element in the sequence.
172	T & dropTail( Sequence(T) & s ) {
173	T & n = tail( s );
174	return &n ? remove( s, n ), n : *0p;
175	}
176
177	// Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
178	void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
179	if ( empty( from ) ) return; // "from" list empty ?
180	if ( empty( s ) ) { // "to" list empty ?
181	root = from.root;
182	} else { // "to" list not empty
183	T * toEnd = Back( head( s ) );
184	T * fromEnd = Back( head( from ) );
185	Back( *root ) = fromEnd;
186	Next( *fromEnd ) = &head( s );
187	Back( *from.root ) = toEnd;
188	Next( *toEnd ) = &head( from );
189	} // if
190	from.root = 0p; // mark "from" list empty
191	}
192
193	// Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
194	// Node "n" must be in the "from" list.
195	void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) {
196	#ifdef __CFA_DEBUG__
197	if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n );
198	#endif // __CFA_DEBUG__
199	Sequence(T) to;
200	to.root = from.root; // start of "to" list
201	from.root = Next( n ); // start of "from" list
202	if ( to.root == from.root ) { // last node in list ?
203	from.root = 0p; // mark "from" list empty
204	} else {
205	Back( head( from ) ) = Back( head( to ) ); // fix "from" list
206	Next( *Back( head( to ) ) ) = &head( from );
207	Next( n ) = &head( to ); // fix "to" list
208	Back( head( to ) ) = &n;
209	} // if
210	transfer( s, to );
211	}
212	} // distribution
213	} // distribution
214
215	forall( dtype T ) {
216	// SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
217	struct SeqIter {
218	inline ColIter;
219	// The Sequence must be passed to pred and succ to check for the end of the Sequence and return 0p. Without
220	// passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence
221	// to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular.
222	Sequence(T) * seq; // FIX ME: cannot be reference
223	};
224
225	inline {
226	void ?{}( SeqIter(T) & si ) with( si ) {
227	((ColIter &)si){};
228	seq = 0p;
229	} // post: elts = null.
230
231	void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
232	((ColIter &) si){};
233	seq = &s;
234	curr = &head( s );
235	} // post: elts = null.
236
237	void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) {
238	((ColIter &) si){};
239	seq = &s;
240	curr = &start;
241	} // post: elts = null.
242
243	void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
244	seq = &s;
245	curr = &head( s );
246	} // post: elts = {e in s}.
247
248	bool ?>>?( SeqIter(T) & si, T && tp ) with( si ) {
249	if ( curr ) {
250	&tp = Curr( si );
251	T * n = succ( *seq, Curr( si ) );
252	curr = n == &head( *seq ) ? 0p : n;
253	} else &tp = 0p;
254	return &tp != 0p;
255	}
256	} // distribution
257
258
259	// A SeqIterRev(T) is used to iterate over a Sequence(T) in tail-to-head order.
260	struct SeqIterRev {
261	inline ColIter;
262	// See above for explanation.
263	Sequence(T) * seq; // FIX ME: cannot be reference
264	};
265
266	inline {
267	void ?{}( SeqIterRev(T) & si ) with( si ) {
268	((ColIter &) si){};
269	seq = 0p;
270	} // post: elts = null.
271
272	void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
273	((ColIter &) si){};
274	seq = &s;
275	curr = &tail( s );
276	} // post: elts = null.
277
278	void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) {
279	((ColIter &) si){};
280	seq = &s;
281	curr = &start;
282	} // post: elts = null.
283
284	void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
285	seq = &s;
286	curr = &tail( s );
287	} // post: elts = {e in s}.
288
289	bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
290	if ( curr ) {
291	&tp = Curr( si );
292	T * n = pred( *seq, Curr( si ) );
293	curr = n == &tail( *seq ) ? 0p : n;
294	} else &tp = 0p;
295	return &tp != 0p;
296	}
297	} // distribution
298	} // distribution

Note: See TracBrowser for help on using the repository browser.

Download in other formats:

Original Format