source: libcfa/src/bits/sequence.hfa@ 6cdec7e

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 6cdec7e was a32cbac2, checked in by Peter A. Buhr <pabuhr@…>, 5 years ago

add comments to SeqIter
  • Property mode set to 100644
File size: 9.5 KB
RevLine 
[5e82d56]1#pragma once
2
3#include "collection.hfa"
4
5struct Seqable {
6 inline Colable;
7 Seqable * back; // pointer to previous node in the list
8};
9
10inline {
11 void ?{}( Seqable & sq ) with( sq ) {
[636d3715]12 ((Colable &) sq){};
[5e82d56]13 back = 0p;
14 } // post: ! listed()
15
[a78c3ff]16 Seqable & getBack( Seqable & sq ) with( sq ) {
17 return *back;
[5e82d56]18 }
19
20 Seqable *& Back( Seqable * sq ) {
21 return sq->back;
22 }
23} // distribution
24
25forall( dtype T ) {
26 struct Sequence {
27 inline Collection; // Plan 9 inheritance
28 };
29
30 inline {
31 // wrappers to make Collection have T
[a78c3ff]32 T & head( Sequence(T) & s ) with( s ) {
33 return *(T *)head( (Collection &)s );
[5e82d56]34 } // post: empty() & head() == 0 | !empty() & head() in *s
35
36 T *& Back( T * n ) {
37 return (T *)Back( (Seqable *)n );
38 }
39
40 void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy
41 Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment
42
43 void ?{}( Sequence(T) & s ) with( s ) {
44 ((Collection &) s){};
45 } // post: isEmpty().
46
47 // Return a pointer to the last sequence element, without removing it.
[b37515b]48 T & tail( Sequence(T) & s ) with( s ) {
[a78c3ff]49 return root ? (T &)*Back( &head( s ) ) : *0p;
[a5a67ab8]50 } // post: empty() & tail() == 0 | !empty() & tail() in *s
[5e82d56]51
52 // Return a pointer to the element after *n, or 0p if there isn't one.
[a5a67ab8]53 T * succ( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s
[5e82d56]54#ifdef __CFA_DEBUG__
[a5a67ab8]55 if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
[5e82d56]56#endif // __CFA_DEBUG__
[a5a67ab8]57 return Next( n ) == &head( s ) ? 0p : Next( n );
58 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
[5e82d56]59
60 // Return a pointer to the element before *n, or 0p if there isn't one.
[a5a67ab8]61 T * pred( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s
[5e82d56]62#ifdef __CFA_DEBUG__
[a5a67ab8]63 if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
[5e82d56]64#endif // __CFA_DEBUG__
[a5a67ab8]65 return n == &head( s ) ? 0p : Back( n );
[5e82d56]66 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s
67
68
69 // Insert *n into the sequence before *bef, or at the end if bef == 0.
[b37515b]70 void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
[5e82d56]71#ifdef __CFA_DEBUG__
[b37515b]72 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
[5e82d56]73#endif // __CFA_DEBUG__
[a78c3ff]74 if ( &bef == &head( s ) ) { // must change root
[5e82d56]75 if ( root ) {
[a78c3ff]76 Next( &n ) = &head( s );
77 Back( &n ) = Back( &head( s ) );
[5e82d56]78 // inserted node must be consistent before it is seen
79 asm( "" : : : "memory" ); // prevent code movement across barrier
[a78c3ff]80 Back( &head( s ) ) = &n;
[b37515b]81 Next( Back( &n ) ) = &n;
[5e82d56]82 } else {
[b37515b]83 Next( &n ) = &n;
84 Back( &n ) = &n;
[5e82d56]85 } // if
86 // inserted node must be consistent before it is seen
87 asm( "" : : : "memory" ); // prevent code movement across barrier
[b37515b]88 root = &n;
[5e82d56]89 } else {
[a78c3ff]90 if ( ! &bef ) &bef = &head( s );
[b37515b]91 Next( &n ) = &bef;
92 Back( &n ) = Back( &bef );
[5e82d56]93 // inserted node must be consistent before it is seen
94 asm( "" : : : "memory" ); // prevent code movement across barrier
[b37515b]95 Back( &bef ) = &n;
96 Next( Back( &n ) ) = &n;
[5e82d56]97 } // if
98 } // post: n->listed() & *n in *s & succ(n) == bef
99
100
101 // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
[b37515b]102 void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s
[5e82d56]103#ifdef __CFA_DEBUG__
[b37515b]104 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
[5e82d56]105#endif // __CFA_DEBUG__
[b37515b]106 if ( ! &aft ) { // must change root
[5e82d56]107 if ( root ) {
[a78c3ff]108 Next( &n ) = &head( s );
109 Back( &n ) = Back( &head( s ) );
[5e82d56]110 // inserted node must be consistent before it is seen
111 asm( "" : : : "memory" ); // prevent code movement across barrier
[a78c3ff]112 Back( &head( s ) ) = &n;
[b37515b]113 Next( Back( &n ) ) = &n;
[5e82d56]114 } else {
[b37515b]115 Next( &n ) = &n;
116 Back( &n ) = &n;
[5e82d56]117 } // if
118 asm( "" : : : "memory" ); // prevent code movement across barrier
[b37515b]119 root = &n;
[5e82d56]120 } else {
[b37515b]121 Next( &n ) = Next( &aft );
122 Back( &n ) = &aft;
[5e82d56]123 // inserted node must be consistent before it is seen
124 asm( "" : : : "memory" ); // prevent code movement across barrier
[b37515b]125 Back( Next( &n ) ) = &n;
126 Next( &aft ) = &n;
[5e82d56]127 } // if
128 } // post: n->listed() & *n in *s & succ(n) == bef
129
130 // pre: n->listed() & *n in *s
[b37515b]131 void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
[5e82d56]132#ifdef __CFA_DEBUG__
[b37515b]133 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
[5e82d56]134#endif // __CFA_DEBUG__
[a78c3ff]135 if ( &n == &head( s ) ) {
136 if ( Next( &head( s ) ) == &head( s ) ) root = 0p;
[a5a67ab8]137 else root = Next( &head( s ) );
[5e82d56]138 } // if
[b37515b]139 Back( Next( &n ) ) = Back( &n );
140 Next( Back( &n ) ) = Next( &n );
141 Next( &n ) = Back( &n ) = 0p;
[5e82d56]142 } // post: !n->listed().
143
144 // Add an element to the head of the sequence.
[b37515b]145 void addHead( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
146 insertAft( s, *0p, n );
[5e82d56]147 }
148 // Add an element to the tail of the sequence.
[b37515b]149 void addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
150 insertBef( s, n, *0p );
[5e82d56]151 }
152 // Add an element to the tail of the sequence.
[b37515b]153 void add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n
[5e82d56]154 addTail( s, n );
155 }
156 // Remove and return the head element in the sequence.
[b37515b]157 T & dropHead( Sequence(T) & s ) {
[a78c3ff]158 T & n = head( s );
159 return &n ? remove( s, n ), n : *0p;
[5e82d56]160 }
161 // Remove and return the head element in the sequence.
[b37515b]162 T & drop( Sequence(T) & s ) {
[5e82d56]163 return dropHead( s );
164 }
165 // Remove and return the tail element in the sequence.
[b37515b]166 T & dropTail( Sequence(T) & s ) {
167 T & n = tail( s );
168 return &n ? remove( s, n ), n : *0p;
[5e82d56]169 }
170
171 // Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
172 void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
173 if ( empty( from ) ) return; // "from" list empty ?
174 if ( empty( s ) ) { // "to" list empty ?
175 root = from.root;
176 } else { // "to" list not empty
[a78c3ff]177 T * toEnd = Back( &head( s ) );
178 T * fromEnd = Back( &head( from ) );
[5e82d56]179 Back( root ) = fromEnd;
[a78c3ff]180 Next( fromEnd ) = &head( s );
[5e82d56]181 Back( from.root ) = toEnd;
[a78c3ff]182 Next( toEnd ) = &head( from );
[5e82d56]183 } // if
184 from.root = 0p; // mark "from" list empty
185 }
186
187 // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
188 // Node "n" must be in the "from" list.
[a78c3ff]189 void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) {
[5e82d56]190#ifdef __CFA_DEBUG__
[a78c3ff]191 if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n );
[5e82d56]192#endif // __CFA_DEBUG__
193 Sequence(T) to;
194 to.root = from.root; // start of "to" list
[a78c3ff]195 from.root = Next( &n ); // start of "from" list
[5e82d56]196 if ( to.root == from.root ) { // last node in list ?
197 from.root = 0p; // mark "from" list empty
198 } else {
[a78c3ff]199 Back( &head( from ) ) = Back( &head( to ) ); // fix "from" list
200 Next( Back( &head( to ) ) ) = &head( from );
201 Next( &n ) = &head( to ); // fix "to" list
202 Back( &head( to ) ) = &n;
[5e82d56]203 } // if
204 transfer( s, to );
205 }
206 } // distribution
207} // distribution
208
209forall( dtype T ) {
210 // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
211 struct SeqIter {
212 inline ColIter;
[a32cbac2]213 // The Sequence must be passed to pred and succ to check for the end of the Sequence and return 0p. Without
214 // passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence
215 // to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular.
[5e82d56]216 Sequence(T) * seq;
217 };
218
219 inline {
[636d3715]220 void ?{}( SeqIter(T) & si ) with( si ) {
221 ((ColIter &)si){};
[5e82d56]222 seq = 0p;
223 } // post: elts = null.
224
225 void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
226 ((ColIter &) si){};
227 seq = &s;
[a78c3ff]228 curr = &head( s );
[5e82d56]229 } // post: elts = null.
[a5a67ab8]230
231 void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) {
232 ((ColIter &) si){};
233 seq = &s;
234 curr = &start;
235 } // post: elts = null.
236
[5e82d56]237 void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
238 seq = &s;
[a78c3ff]239 curr = &head( s );
[5e82d56]240 } // post: elts = {e in s}.
241
[3d0560d]242 bool ?>>?( SeqIter(T) & si, T && tp ) with( si ) {
[5e82d56]243 if ( curr ) {
[3d0560d]244 &tp = Curr( si );
[a5a67ab8]245 T * n = succ( *seq, Curr( si ) );
[a78c3ff]246 curr = n == &head( *seq ) ? 0p : n;
[3d0560d]247 } else &tp = 0p;
248 return &tp != 0p;
[5e82d56]249 }
250 } // distribution
251
252
253 // A SeqIterRev(T) is used to iterate over a Sequence(T) in tail-to-head order.
254 struct SeqIterRev {
255 inline ColIter;
[a32cbac2]256 // See above for explanation.
[5e82d56]257 Sequence(T) * seq;
258 };
259
260 inline {
261 void ?{}( SeqIterRev(T) & si ) with( si ) {
262 ((ColIter &) si){};
263 seq = 0p;
264 } // post: elts = null.
265
266 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
267 ((ColIter &) si){};
268 seq = &s;
[b37515b]269 curr = &tail( s );
[5e82d56]270 } // post: elts = null.
[a5a67ab8]271
272 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) {
273 ((ColIter &) si){};
274 seq = &s;
275 curr = &start;
276 } // post: elts = null.
277
[5e82d56]278 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
279 seq = &s;
[b37515b]280 curr = &tail( s );
[5e82d56]281 } // post: elts = {e in s}.
282
[3d0560d]283 bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
[5e82d56]284 if ( curr ) {
[3d0560d]285 &tp = Curr( si );
[a5a67ab8]286 T * n = pred( *seq, Curr( si ) );
[b37515b]287 curr = n == &tail( *seq ) ? 0p : n;
[3d0560d]288 } else &tp = 0p;
289 return &tp != 0p;
[5e82d56]290 }
291 } // distribution
292} // distribution
293
294// Local Variables: //
[a5a67ab8]295// compile-command: "cfa sequence.hfa" //
[5e82d56]296// End: //
Note: See TracBrowser for help on using the repository browser.