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

arm-ehjacob/cs343-translationnew-ast-unique-expr
Last change on this file since a78c3ff was a78c3ff, checked in by Colby Alexander Parsons <caparsons@…>, 11 months ago

switched queue and sequence to use references

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