Context Navigation

sequence.hfa @ 867fca3

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

Last change on this file since 867fca3 was 7d4ce2a, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago
make collections publicly accessible in include directory
Property mode set to `100644`
File size: 9.6 KB

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

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

Download in other formats:

Original Format