source: libcfa/src/bits/sequence.hfa @ 54f89d5

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 54f89d5 was a32cbac2, checked in by Peter A. Buhr <pabuhr@…>, 3 years ago

add comments to SeqIter?

  • Property mode set to 100644
File size: 9.5 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                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. 
48                T & tail( Sequence(T) & s ) with( s ) {
49                        return root ? (T &)*Back( &head( s ) ) : *0p;
50                }       // post: empty() & tail() == 0 | !empty() & tail() in *s
51
52                // Return a pointer to the element after *n, or 0p if there isn't one.
53                T * succ( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
54#ifdef __CFA_DEBUG__
55                        if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n );
56#endif // __CFA_DEBUG__
57                        return Next( n ) == &head( s ) ? 0p : Next( n );
58                } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s
59
60                // Return a pointer to the element before *n, or 0p if there isn't one.
61                T * pred( Sequence(T) & s, T * n ) with( s ) {  // pre: *n in *s
62#ifdef __CFA_DEBUG__
63                        if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n );
64#endif // __CFA_DEBUG__
65                        return n == &head( s ) ? 0p : Back( n );
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.
70                void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s
71#ifdef __CFA_DEBUG__
72                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef );
73#endif // __CFA_DEBUG__
74                        if ( &bef == &head( s ) ) {                                     // must change root
75                                if ( root ) {
76                                        Next( &n ) = &head( s );
77                                        Back( &n ) = Back( &head( s ) );
78                                        // inserted node must be consistent before it is seen
79                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
80                                        Back( &head( s ) ) = &n;
81                                        Next( Back( &n ) ) = &n;
82                                } else {
83                                        Next( &n ) = &n;
84                                        Back( &n ) = &n;
85                                } // if
86                                // inserted node must be consistent before it is seen
87                                asm( "" : : : "memory" );                               // prevent code movement across barrier
88                                root = &n;
89                        } else {
90                                if ( ! &bef ) &bef = &head( s );
91                                Next( &n ) = &bef;
92                                Back( &n ) = Back( &bef );
93                                // inserted node must be consistent before it is seen
94                                asm( "" : : : "memory" );                               // prevent code movement across barrier
95                                Back( &bef ) = &n;
96                                Next( Back( &n ) ) = &n;
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.
102                void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) {   // pre: !n->listed() & *aft in *s
103#ifdef __CFA_DEBUG__
104                        if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n );
105#endif // __CFA_DEBUG__
106                        if ( ! &aft ) {                                                         // must change root
107                                if ( root ) {
108                                        Next( &n ) = &head( s );
109                                        Back( &n ) = Back( &head( s ) );
110                                        // inserted node must be consistent before it is seen
111                                        asm( "" : : : "memory" );                       // prevent code movement across barrier
112                                        Back( &head( s ) ) = &n;
113                                        Next( Back( &n ) ) = &n;
114                                } else {
115                                        Next( &n ) = &n;
116                                        Back( &n ) = &n;
117                                } // if
118                                asm( "" : : : "memory" );                               // prevent code movement across barrier
119                                root = &n;
120                        } else {
121                                Next( &n ) = Next( &aft );
122                                Back( &n ) = &aft;
123                                // inserted node must be consistent before it is seen
124                                asm( "" : : : "memory" );                               // prevent code movement across barrier
125                                Back( Next( &n ) ) = &n;
126                                Next( &aft ) = &n;
127                        } // if
128                }         // post: n->listed() & *n in *s & succ(n) == bef
129               
130                // pre: n->listed() & *n in *s
131                void remove( Sequence(T) & s, T & n ) with( s ) { // O(1)
132#ifdef __CFA_DEBUG__
133                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n );
134#endif // __CFA_DEBUG__
135                        if ( &n == &head( s ) ) {
136                                if ( Next( &head( s ) ) == &head( s ) ) root = 0p;
137                                else root = Next( &head( s ) );
138                        } // if
139                        Back( Next( &n ) ) = Back( &n );
140                        Next( Back( &n ) ) = Next( &n );
141                        Next( &n ) = Back( &n ) = 0p;
142                }                                                       // post: !n->listed().
143
144                // Add an element to the head of the sequence.
145                void addHead( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
146                        insertAft( s, *0p, n );
147                }
148                // Add an element to the tail of the sequence.
149                void addTail( Sequence(T) & s, T & n ) {                // pre: !n->listed(); post: n->listed() & head() == n
150                        insertBef( s, n, *0p );
151                }
152                // Add an element to the tail of the sequence.
153                void add( Sequence(T) & s, T & n ) {                    // pre: !n->listed(); post: n->listed() & head() == n
154                        addTail( s, n );
155                }
156                // Remove and return the head element in the sequence.
157                T & dropHead( Sequence(T) & s ) {
158                        T & n = head( s );
159                        return &n ? remove( s, n ), n : *0p;
160                }
161                // Remove and return the head element in the sequence.
162                T & drop( Sequence(T) & s ) {
163                        return dropHead( s );
164                }
165                // Remove and return the tail element in the sequence.
166                T & dropTail( Sequence(T) & s ) {
167                        T & n = tail( s );
168                        return &n ? remove( s, n ), n : *0p;
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
177                                T * toEnd = Back( &head( s ) );
178                                T * fromEnd = Back( &head( from ) );
179                                Back( root ) = fromEnd;
180                                Next( fromEnd ) = &head( s );
181                                Back( from.root ) = toEnd;
182                                Next( toEnd ) = &head( from );
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.
189                void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) {
190#ifdef __CFA_DEBUG__
191                        if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n );
192#endif // __CFA_DEBUG__
193                        Sequence(T) to;
194                        to.root = from.root;                                            // start of "to" list
195                        from.root = Next( &n );                                         // start of "from" list
196                        if ( to.root == from.root ) {                           // last node in list ?
197                                from.root = 0p;                                                 // mark "from" list empty
198                        } else {
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;
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;
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.
216                Sequence(T) * seq;
217        };
218
219        inline {
220                void ?{}( SeqIter(T) & si ) with( si ) {
221                        ((ColIter &)si){};
222                        seq = 0p;
223                } // post: elts = null.
224
225                void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
226                        ((ColIter &) si){};
227                        seq = &s;
228                        curr = &head( s );
229                } // post: elts = null.
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
237                void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) {
238                        seq = &s;
239                        curr = &head( s );
240                } // post: elts = {e in s}.
241
242                bool ?>>?( SeqIter(T) & si, T && tp ) with( si ) {
243                        if ( curr ) {
244                                &tp = Curr( si );
245                                T * n = succ( *seq, Curr( si ) );
246                                curr = n == &head( *seq ) ? 0p : n;
247                        } else &tp = 0p;
248                        return &tp != 0p;
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;
256                // See above for explanation.
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;
269                        curr = &tail( s );
270                } // post: elts = null.
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
278                void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) {
279                        seq = &s;
280                        curr = &tail( s );
281                } // post: elts = {e in s}.
282
283                bool ?>>?( SeqIterRev(T) & si, T && tp ) with( si ) {
284                        if ( curr ) {
285                                &tp = Curr( si );
286                                T * n = pred( *seq, Curr( si ) );
287                                curr = n == &tail( *seq ) ? 0p : n;
288                        } else &tp = 0p;
289                        return &tp != 0p;
290                }
291        } // distribution
292} // distribution
293
294// Local Variables: //
295// compile-command: "cfa sequence.hfa" //
296// End: //
Note: See TracBrowser for help on using the repository browser.