source: libcfa/src/bits/sequence.hfa@ d9b7b66

Last change on this file since d9b7b66 was d0502a3, checked in by Michael Brooks <mlbrooks@…>, 5 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
22struct Seqable {
23 __cfa_anonymous_object(Colable);
24 // pointer to previous node in the list
25 struct Seqable * back;
26};
27
28#ifdef __cforall
29static 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
55forall( 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
246forall( 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.