source: libcfa/src/bits/sequence.hfa@ 953d433

ADT arm-eh ast-experimental enum forall-pointer-decay jacob/cs343-translation new-ast-unique-expr pthread-emulation qualifiedEnum
Last change on this file since 953d433 was a78c3ff, checked in by Colby Alexander Parsons <caparsons@…>, 5 years 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.