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

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since b66d14a was 9536761, checked in by Peter A. Buhr <pabuhr@…>, 5 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
6struct Seqable {
7 __cfa_anonymous_object(Colable);
8 struct Seqable * back; // pointer to previous node in the list
9};
10
11#ifdef __cforall
12static 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
45forall( 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
233forall( 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.