Context Navigation

sequence.hfa @ a3a76ea

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

Last change on this file since a3a76ea was a3a76ea, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago
modify routines to return added/removed node to allow cascading calls
Property mode set to `100644`
File size: 9.8 KB

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

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

Download in other formats:

Original Format