source: libcfa/src/bits/sequence.hfa @ 19de7864

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 19de7864 was 19de7864, checked in by Colby Alexander Parsons <caparsons@…>, 3 years ago

removed listed requirement for collections since it was redundant

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