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

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since fd54fef was fd54fef, checked in by Michael Brooks <mlbrooks@…>, 9 months ago

Converting the project to use the new syntax for otype, dtype and ttytpe.

Changed prelude (gen), libcfa and test suite to use it. Added a simple deprecation rule of the old syntax to the parser; we might wish to support both syntaxes "officially," like with an extra CLI switch, but this measure should serve as a simple reminder for our team to try the new syntax.

  • 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( 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( 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( 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.