source: libcfa/src/bits/sequence.hfa @ 867fca3

ADTarm-ehast-experimentalenumforall-pointer-decayjacob/cs343-translationnew-ast-unique-exprpthread-emulationqualifiedEnum
Last change on this file since 867fca3 was 7d4ce2a, checked in by Peter A. Buhr <pabuhr@…>, 4 years ago

make collections publicly accessible in include directory

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