Context Navigation

sequence.hfa @ 63ec5fa

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

Last change on this file since 63ec5fa was b37515b, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago
start converting from pointer to reference parameters/returns across the containers
Property mode set to `100644`
File size: 9.3 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	void ?{}( Seqable & sq ) with( sq ) {
12	((Colable & ) sq){};
13	back = 0p;
14	} // post: ! listed()
15
16	Seqable * getBack( Seqable & sq ) with( sq ) {
17	return back;
18	}
19
20	Seqable & Back( Seqable sq ) {
21	return sq->back;
22	}
23	} // distribution
24
25	forall( dtype T ) {
26	struct Sequence {
27	inline Collection; // Plan 9 inheritance
28	};
29
30	inline {
31	// wrappers to make Collection have T
32	T * head( Sequence(T) & s ) with( s ) {
33	return (T *)head( (Collection &)s );
34	} // post: empty() & head() == 0 \| !empty() & head() in *s
35
36	bool empty( Sequence(T) & s ) with( s ) { // 0 <=> *s contains no elements
37	return empty( (Collection &)s );
38	}
39
40	bool listed( T * n ) {
41	return Next( (Colable *)n ) != 0;
42	}
43
44	T & Next( T n ) {
45	return (T )Next( (Colable )n );
46	}
47
48	T & Back( T n ) {
49	return (T )Back( (Seqable )n );
50	}
51
52	T * Root( Sequence(T) & s ) with( s ) {
53	return (T *)root;
54	}
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( Root( s ) ) : *0p; // needs cast?
66	} // post: empty() & tail() == 0 \| !empty() & tail() in *s
67
68	// Return a pointer to the element after *n, or 0p if there isn't one.
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 ) == Root( 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 there isn't one.
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 == Root( 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 == 0.
86	void 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 == Root( s ) ) { // must change root
91	if ( root ) {
92	Next( &n ) = Root( s );
93	Back( &n ) = Back( Root( s ) );
94	// inserted node must be consistent before it is seen
95	asm( "" : : : "memory" ); // prevent code movement across barrier
96	Back( Root( 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 = Root( 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	} // post: n->listed() & n in s & succ(n) == bef
115
116
117	// Insert n into the sequence after aft, or at the beginning if aft == 0.
118	void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & aft in s
119	#ifdef __CFA_DEBUG__
120	if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
121	#endif // __CFA_DEBUG__
122	if ( ! &aft ) { // must change root
123	if ( root ) {
124	Next( &n ) = Root( s );
125	Back( &n ) = Back( Root( s ) );
126	// inserted node must be consistent before it is seen
127	asm( "" : : : "memory" ); // prevent code movement across barrier
128	Back( Root( s ) ) = &n;
129	Next( Back( &n ) ) = &n;
130	} else {
131	Next( &n ) = &n;
132	Back( &n ) = &n;
133	} // if
134	asm( "" : : : "memory" ); // prevent code movement across barrier
135	root = &n;
136	} else {
137	Next( &n ) = Next( &aft );
138	Back( &n ) = &aft;
139	// inserted node must be consistent before it is seen
140	asm( "" : : : "memory" ); // prevent code movement across barrier
141	Back( Next( &n ) ) = &n;
142	Next( &aft ) = &n;
143	} // if
144	} // post: n->listed() & n in s & succ(n) == bef
145
146	// pre: n->listed() & n in s
147	void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
148	#ifdef __CFA_DEBUG__
149	if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
150	#endif // __CFA_DEBUG__
151	if ( &n == Root( s ) ) {
152	if ( Next( Root( s ) ) == Root( s ) ) root = 0p;
153	else root = Next( Root(s ) );
154	} // if
155	Back( Next( &n ) ) = Back( &n );
156	Next( Back( &n ) ) = Next( &n );
157	Next( &n ) = Back( &n ) = 0p;
158	} // post: !n->listed().
159
160	// Add an element to the head of the sequence.
161	void addHead( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
162	insertAft( s, *0p, n );
163	}
164	// Add an element to the tail of the sequence.
165	void addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
166	insertBef( s, n, *0p );
167	}
168	// Add an element to the tail of the sequence.
169	void add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
170	addTail( s, n );
171	}
172	// Remove and return the head element in the sequence.
173	T & dropHead( Sequence(T) & s ) {
174	T * n = head( s );
175	return n ? remove( s, n ), n : *0p;
176	}
177	// Remove and return the head element in the sequence.
178	T & drop( Sequence(T) & s ) {
179	return dropHead( s );
180	}
181	// Remove and return the tail element in the sequence.
182	T & dropTail( Sequence(T) & s ) {
183	T & n = tail( s );
184	return &n ? remove( s, n ), n : *0p;
185	}
186
187	// Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
188	void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
189	if ( empty( from ) ) return; // "from" list empty ?
190	if ( empty( s ) ) { // "to" list empty ?
191	root = from.root;
192	} else { // "to" list not empty
193	T * toEnd = Back( Root( s ) );
194	T * fromEnd = Back( Root( from ) );
195	Back( root ) = fromEnd;
196	Next( fromEnd ) = Root( s );
197	Back( from.root ) = toEnd;
198	Next( toEnd ) = Root( from );
199	} // if
200	from.root = 0p; // mark "from" list empty
201	}
202
203	// Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
204	// Node "n" must be in the "from" list.
205	void split( Sequence(T) & s, Sequence(T) & from, T * n ) with( s ) {
206	#ifdef __CFA_DEBUG__
207	if ( ! listed( n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, n );
208	#endif // __CFA_DEBUG__
209	Sequence(T) to;
210	to.root = from.root; // start of "to" list
211	from.root = Next( n ); // start of "from" list
212	if ( to.root == from.root ) { // last node in list ?
213	from.root = 0p; // mark "from" list empty
214	} else {
215	Back( Root( from ) ) = Back( Root( to ) ); // fix "from" list
216	Next( Back( Root( to ) ) ) = Root( from );
217	Next( n ) = Root( to ); // fix "to" list
218	Back( Root( to ) ) = n;
219	} // if
220	transfer( s, to );
221	}
222	} // distribution
223	} // distribution
224
225	forall( dtype T ) {
226	// SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
227	struct SeqIter {
228	inline ColIter;
229	Sequence(T) * seq;
230	};
231
232	inline {
233	// wrappers to make ColIter have T
234	T * Curr( SeqIter(T) & si ) with( si ) {
235	return (T *)curr;
236	}
237
238	void ?{}( SeqIter(T) & si ) with( si ) {
239	((ColIter &) si){};
240	seq = 0p;
241	} // post: elts = null.
242
243	void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
244	((ColIter &) si){};
245	seq = &s;
246	curr = head( s );
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	Sequence(T) * seq;
269	};
270
271	inline {
272	// wrappers to make ColIter have T
273	T * Curr( SeqIterRev(T) & si ) with( si ) {
274	return (T *)curr;
275	}
276
277	void ?{}( SeqIterRev(T) & si ) with( si ) {
278	((ColIter &) si){};
279	seq = 0p;
280	} // post: elts = null.
281
282	void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
283	((ColIter &) si){};
284	seq = &s;
285	curr = &tail( s );
286	} // post: elts = null.
287
288	void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
289	seq = &s;
290	curr = &tail( s );
291	} // post: elts = {e in s}.
292
293	bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
294	if ( curr ) {
295	&tp = Curr( si );
296	T * n = pred( *seq, Curr( si ) );
297	curr = n == &tail( *seq ) ? 0p : n;
298	} else &tp = 0p;
299	return &tp != 0p;
300	}
301	} // distribution
302	} // distribution
303
304	// Local Variables: //
305	// compile-command: "make install" //
306	// End: //

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

Download in other formats:

Original Format