Changes in libcfa/src/bits/sequence.hfa [636d3715:a78c3ff]
- File:
-
- 1 edited
-
libcfa/src/bits/sequence.hfa (modified) (14 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/sequence.hfa
r636d3715 ra78c3ff 2 2 3 3 #include "collection.hfa" 4 #include <stdlib.hfa> 5 #include <stdio.h> 4 6 5 7 struct Seqable { … … 14 16 } // post: ! listed() 15 17 16 Seqable *getBack( Seqable & sq ) with( sq ) {17 return back;18 Seqable & getBack( Seqable & sq ) with( sq ) { 19 return *back; 18 20 } 19 21 … … 30 32 inline { 31 33 // wrappers to make Collection have T 32 T *head( Sequence(T) & s ) with( s ) {33 return (T *)head( (Collection &)s );34 T & head( Sequence(T) & s ) with( s ) { 35 return *(T *)head( (Collection &)s ); 34 36 } // post: empty() & head() == 0 | !empty() & head() in *s 35 37 … … 47 49 // Return a pointer to the last sequence element, without removing it. 48 50 T & tail( Sequence(T) & s ) with( s ) { 49 return root ? (T &) Back( head( s ) ) : *0p; // needs cast?50 } // post: empty() & tail() == 0 | !empty() & tail() in *s 51 return root ? (T &)*Back( &head( s ) ) : *0p; 52 } // post: empty() & tail() == 0 | !empty() & tail() in *s\ 51 53 52 54 // 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 *s54 #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 );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 ); 58 60 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 59 61 60 62 // 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 *s62 #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 );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 ); 66 68 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 67 69 … … 72 74 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); 73 75 #endif // __CFA_DEBUG__ 74 if ( &bef == head( s ) ) { // must change root76 if ( &bef == &head( s ) ) { // must change root 75 77 if ( root ) { 76 Next( &n ) = head( s );77 Back( &n ) = Back( head( s ) );78 Next( &n ) = &head( s ); 79 Back( &n ) = Back( &head( s ) ); 78 80 // inserted node must be consistent before it is seen 79 81 asm( "" : : : "memory" ); // prevent code movement across barrier 80 Back( head( s ) ) = &n;82 Back( &head( s ) ) = &n; 81 83 Next( Back( &n ) ) = &n; 82 84 } else { … … 88 90 root = &n; 89 91 } else { 90 if ( ! &bef ) &bef = head( s );92 if ( ! &bef ) &bef = &head( s ); 91 93 Next( &n ) = &bef; 92 94 Back( &n ) = Back( &bef ); … … 106 108 if ( ! &aft ) { // must change root 107 109 if ( root ) { 108 Next( &n ) = head( s );109 Back( &n ) = Back( head( s ) );110 Next( &n ) = &head( s ); 111 Back( &n ) = Back( &head( s ) ); 110 112 // inserted node must be consistent before it is seen 111 113 asm( "" : : : "memory" ); // prevent code movement across barrier 112 Back( head( s ) ) = &n;114 Back( &head( s ) ) = &n; 113 115 Next( Back( &n ) ) = &n; 114 116 } else { … … 133 135 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); 134 136 #endif // __CFA_DEBUG__ 135 if ( &n == head( s ) ) {136 if ( Next( head( s ) ) ==head( s ) ) root = 0p;137 else root = Next( head(s ) );137 if ( &n == &head( s ) ) { 138 if ( Next( &head( s ) ) == &head( s ) ) root = 0p; 139 else root = Next( &head(s ) ); 138 140 } // if 139 141 Back( Next( &n ) ) = Back( &n ); … … 156 158 // Remove and return the head element in the sequence. 157 159 T & dropHead( Sequence(T) & s ) { 158 T *n = head( s );159 return n ? remove( s, *n ), *n : *0p;160 T & n = head( s ); 161 return &n ? remove( s, n ), n : *0p; 160 162 } 161 163 // Remove and return the head element in the sequence. … … 175 177 root = from.root; 176 178 } else { // "to" list not empty 177 T * toEnd = Back( head( s ) );178 T * fromEnd = Back( head( from ) );179 T * toEnd = Back( &head( s ) ); 180 T * fromEnd = Back( &head( from ) ); 179 181 Back( root ) = fromEnd; 180 Next( fromEnd ) = head( s );182 Next( fromEnd ) = &head( s ); 181 183 Back( from.root ) = toEnd; 182 Next( toEnd ) = head( from );184 Next( toEnd ) = &head( from ); 183 185 } // if 184 186 from.root = 0p; // mark "from" list empty … … 187 189 // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n". 188 190 // 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 );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 ); 192 194 #endif // __CFA_DEBUG__ 193 195 Sequence(T) to; 194 196 to.root = from.root; // start of "to" list 195 from.root = Next( n ); // start of "from" list197 from.root = Next( &n ); // start of "from" list 196 198 if ( to.root == from.root ) { // last node in list ? 197 199 from.root = 0p; // mark "from" list empty 198 200 } else { 199 Back( head( from ) ) = Back(head( to ) ); // fix "from" list200 Next( Back( head( to ) ) ) =head( from );201 Next( n ) =head( to ); // fix "to" list202 Back( head( to ) ) =n;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; 203 205 } // if 204 206 transfer( s, to ); … … 223 225 ((ColIter &) si){}; 224 226 seq = &s; 225 curr = head( s );227 curr = &head( s ); 226 228 } // post: elts = null. 227 229 228 230 void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) { 229 231 seq = &s; 230 curr = head( s );232 curr = &head( s ); 231 233 } // post: elts = {e in s}. 232 234 … … 234 236 if ( curr ) { 235 237 &tp = Curr( si ); 236 T * n = succ( *seq,Curr( si ) );237 curr = n == head( *seq ) ? 0p : n;238 T * n = &succ( *seq, *Curr( si ) ); 239 curr = n == &head( *seq ) ? 0p : n; 238 240 } else &tp = 0p; 239 241 return &tp != 0p; … … 268 270 if ( curr ) { 269 271 &tp = Curr( si ); 270 T * n = pred( *seq,Curr( si ) );272 T * n = &pred( *seq, *Curr( si ) ); 271 273 curr = n == &tail( *seq ) ? 0p : n; 272 274 } else &tp = 0p;
Note:
See TracChangeset
for help on using the changeset viewer.
