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

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

start converting from pointer to reference parameters/returns across the containers

  • Property mode set to 100644
File size: 9.3 KB
Line 
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 ) {
12                ((Colable & ) sq){};
13                back = 0p;
14        } // post: ! listed()
15
16        Seqable * getBack( Seqable & sq ) with( sq ) {
17                return back;
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
32                T * head( Sequence(T) & s ) with( s ) {
33                        return (T *)head( (Collection &)s );
34                } // post: empty() & head() == 0 | !empty() & head() in *s
35
36                bool empty( Sequence(T) & s ) with( s ) {               // 0 <=> *s contains no elements
37                        return empty( (Collection &)s );
38                }
39
40                bool listed( T * n ) {
41                        return Next( (Colable *)n ) != 0;
42                }
43
44                T *& Next( T * n ) {
45                        return (T *)Next( (Colable *)n );
46                }
47
48                T *& Back( T * n ) {
49                        return (T *)Back( (Seqable *)n );
50                }
51
52                T * Root( Sequence(T) & s ) with( s ) {
53                        return (T *)root;
54                }
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( Root( s ) ) : *0p;     // needs cast?
66                }       // post: empty() & tail() == 0 | !empty() & tail() in *s
67
68                // Return a pointer to the element after *n, or 0p if there isn't one.
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 ) == Root( 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 there isn't one.
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 == Root( 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 == 0.
86                void 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 == Root( s ) ) {                                      // must change root
91                                if ( root ) {
92                                        Next( &n ) = Root( s );
93                                        Back( &n ) = Back( Root( s ) );
94                                        // inserted node must be consistent before it is seen
95                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
96                                        Back( Root( 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 = Root( 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                }       // post: n->listed() & *n in *s & succ(n) == bef
115
116
117                // Insert *n into the sequence after *aft, or at the beginning if aft == 0.
118                void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {   // pre: !n->listed() & *aft in *s
119#ifdef __CFA_DEBUG__
120                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
121#endif // __CFA_DEBUG__
122                        if ( ! &aft ) {                                                         // must change root
123                                if ( root ) {
124                                        Next( &n ) = Root( s );
125                                        Back( &n ) = Back( Root( s ) );
126                                        // inserted node must be consistent before it is seen
127                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
128                                        Back( Root( s ) ) = &n;
129                                        Next( Back( &n ) ) = &n;
130                                } else {
131                                        Next( &n ) = &n;
132                                        Back( &n ) = &n;
133                                } // if
134                                asm( "" : : : "memory" );                               // prevent code movement across barrier
135                                root = &n;
136                        } else {
137                                Next( &n ) = Next( &aft );
138                                Back( &n ) = &aft;
139                                // inserted node must be consistent before it is seen
140                                asm( "" : : : "memory" );                               // prevent code movement across barrier
141                                Back( Next( &n ) ) = &n;
142                                Next( &aft ) = &n;
143                        } // if
144                }         // post: n->listed() & *n in *s & succ(n) == bef
145               
146                // pre: n->listed() & *n in *s
147                void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
148#ifdef __CFA_DEBUG__
149                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
150#endif // __CFA_DEBUG__
151                        if ( &n == Root( s ) ) {
152                                if ( Next( Root( s ) ) == Root( s ) ) root = 0p;
153                                else root = Next( Root(s ) );
154                        } // if
155                        Back( Next( &n ) ) = Back( &n );
156                        Next( Back( &n ) ) = Next( &n );
157                        Next( &n ) = Back( &n ) = 0p;
158                }                                                       // post: !n->listed().
159
160                // Add an element to the head of the sequence.
161                void addHead( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
162                        insertAft( s, *0p, n );
163                }
164                // Add an element to the tail of the sequence.
165                void addTail( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
166                        insertBef( s, n, *0p );
167                }
168                // Add an element to the tail of the sequence.
169                void add( Sequence(T) & s, T & n ) {                    // pre: !n->listed(); post: n->listed() & head() == n
170                        addTail( s, n );
171                }
172                // Remove and return the head element in the sequence.
173                T & dropHead( Sequence(T) & s ) {
174                        T * n = head( s );
175                        return n ? remove( s, *n ), *n : *0p;
176                }
177                // Remove and return the head element in the sequence.
178                T & drop( Sequence(T) & s ) {
179                        return dropHead( s );
180                }
181                // Remove and return the tail element in the sequence.
182                T & dropTail( Sequence(T) & s ) {
183                        T & n = tail( s );
184                        return &n ? remove( s, n ), n : *0p;
185                }
186
187                // Transfer the "from" list to the end of s sequence; the "from" list is empty after the transfer.
188                void transfer( Sequence(T) & s, Sequence(T) & from ) with( s ) {
189                        if ( empty( from ) ) return;                            // "from" list empty ?
190                        if ( empty( s ) ) {                                                     // "to" list empty ?
191                                root = from.root;
192                        } else {                                                                        // "to" list not empty
193                                T * toEnd = Back( Root( s ) );
194                                T * fromEnd = Back( Root( from ) );
195                                Back( root ) = fromEnd;
196                                Next( fromEnd ) = Root( s );
197                                Back( from.root ) = toEnd;
198                                Next( toEnd ) = Root( from );
199                        } // if
200                        from.root = 0p;                                                         // mark "from" list empty
201                }
202
203                // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n".
204                // Node "n" must be in the "from" list.
205                void split( Sequence(T) & s, Sequence(T) & from, T * n ) with( s ) {
206#ifdef __CFA_DEBUG__
207                        if ( ! listed( n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, n );
208#endif // __CFA_DEBUG__
209                        Sequence(T) to;
210                        to.root = from.root;                                            // start of "to" list
211                        from.root = Next( n );                                          // start of "from" list
212                        if ( to.root == from.root ) {                           // last node in list ?
213                                from.root = 0p;                                                 // mark "from" list empty
214                        } else {
215                                Back( Root( from ) ) = Back( Root( to ) ); // fix "from" list
216                                Next( Back( Root( to ) ) ) = Root( from );
217                                Next( n ) = Root( to );                                 // fix "to" list
218                                Back( Root( to ) ) = n;
219                        } // if
220                        transfer( s, to );
221                }
222        } // distribution
223} // distribution
224
225forall( dtype T ) {
226        // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order.
227        struct SeqIter {
228                inline ColIter;
229                Sequence(T) * seq;
230        };
231
232        inline {
233                // wrappers to make ColIter have T
234                T * Curr( SeqIter(T) & si ) with( si ) {
235                        return (T *)curr;
236                }
237
238                void ?{}( SeqIter(T) & si ) with( si ) {       
239                        ((ColIter &) si){};
240                        seq = 0p;
241                } // post: elts = null.
242
243                void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
244                        ((ColIter &) si){};
245                        seq = &s;
246                        curr = head( s );
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                Sequence(T) * seq;
269        };
270
271        inline {
272                // wrappers to make ColIter have T
273                T * Curr( SeqIterRev(T) & si ) with( si ) {
274                        return (T *)curr;
275                }
276
277                void ?{}( SeqIterRev(T) & si ) with( si ) {     
278                        ((ColIter &) si){};
279                        seq = 0p;
280                } // post: elts = null.
281
282                void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {   
283                        ((ColIter &) si){};
284                        seq = &s;
285                        curr = &tail( s );
286                } // post: elts = null.
287               
288                void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
289                        seq = &s;
290                        curr = &tail( s );
291                } // post: elts = {e in s}.
292
293                bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
294                        if ( curr ) {
295                                &tp = Curr( si );
296                                T * n = pred( *seq, Curr( si ) );
297                                curr = n == &tail( *seq ) ? 0p : n;
298                        } else &tp = 0p;
299                        return &tp != 0p;
300                }
301        } // distribution
302} // distribution
303
304// Local Variables: //
305// compile-command: "make install" //
306// End: //
Note: See TracBrowser for help on using the repository browser.