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

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since a3a76ea was a3a76ea, checked in by Peter A. Buhr <pabuhr@…>, 10 months ago

modify routines to return added/removed node to allow cascading calls

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