Context Navigation

sequence.hfa @ d46bdac

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

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

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

Download in other formats:

Original Format