Context Navigation

sequence.hfa @ 72713e5

Last change on this file since 72713e5 was d0502a3, checked in by Michael Brooks <mlbrooks@…>, 4 years ago

Fixing function bodies in bits/containers and bits/sequence so they can coexist with declarations in vector Fixes #237?

libcfa/src/bits/* the fixes
libcfa/src/fstream.hfa adding the desired include, which wasn't possible under #237
tests/includes/* adding tests for these problematic combinations

Property mode set to 100644

File size: 10.6 KB

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

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

Download in other formats:

Original Format