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