Changes in libcfa/src/bits/sequence.hfa [7c1144b:a32cbac2]
- File:
-
- 1 edited
-
libcfa/src/bits/sequence.hfa (modified) (13 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/sequence.hfa
r7c1144b ra32cbac2 9 9 10 10 inline { 11 // PUBLIC12 13 11 void ?{}( Seqable & sq ) with( sq ) { 14 12 ((Colable &) sq){}; … … 20 18 } 21 19 22 // PRIVATE23 24 20 Seqable *& Back( Seqable * sq ) { 25 21 return sq->back; 26 22 } 27 28 // wrappers to make Collection have T29 forall( dtype T ) {30 T *& Back( T & n ) {31 return (T *)Back( (Seqable *)&n );32 }33 34 T & head( Sequence(T) & s ) with( s ) {35 return *(T *)head( (Collection &)s );36 } // post: empty() & head() == 0 | !empty() & head() in *s37 } // distribution38 23 } // distribution 39 24 … … 44 29 45 30 inline { 31 // wrappers to make Collection have T 32 T & head( Sequence(T) & s ) with( s ) { 33 return *(T *)head( (Collection &)s ); 34 } // post: empty() & head() == 0 | !empty() & head() in *s 35 36 T *& Back( T * n ) { 37 return (T *)Back( (Seqable *)n ); 38 } 39 46 40 void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy 47 41 Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment … … 53 47 // Return a pointer to the last sequence element, without removing it. 54 48 T & tail( Sequence(T) & s ) with( s ) { 55 return root ? (T &)*Back( head( s ) ) : *0p;49 return root ? (T &)*Back( &head( s ) ) : *0p; 56 50 } // post: empty() & tail() == 0 | !empty() & tail() in *s 57 51 58 // Return a pointer to the element after *n, or 0p if list empty.52 // Return a pointer to the element after *n, or 0p if there isn't one. 59 53 T * succ( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s 60 54 #ifdef __CFA_DEBUG__ 61 55 if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n ); 62 63 return Next( *n ) == &head( s ) ? 0p : Next( *n );56 #endif // __CFA_DEBUG__ 57 return Next( n ) == &head( s ) ? 0p : Next( n ); 64 58 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 65 59 66 60 // Return a pointer to the element before *n, or 0p if there isn't one. 67 61 T * pred( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s 68 62 #ifdef __CFA_DEBUG__ 69 63 if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n ); 70 71 return n == &head( s ) ? 0p : Back( *n );64 #endif // __CFA_DEBUG__ 65 return n == &head( s ) ? 0p : Back( n ); 72 66 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 73 67 … … 75 69 // Insert *n into the sequence before *bef, or at the end if bef == 0. 76 70 void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s 77 71 #ifdef __CFA_DEBUG__ 78 72 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); 79 73 #endif // __CFA_DEBUG__ 80 74 if ( &bef == &head( s ) ) { // must change root 81 75 if ( root ) { 82 Next( n ) = &head( s );83 Back( n ) = Back(head( s ) );76 Next( &n ) = &head( s ); 77 Back( &n ) = Back( &head( s ) ); 84 78 // inserted node must be consistent before it is seen 85 79 asm( "" : : : "memory" ); // prevent code movement across barrier 86 Back( head( s ) ) = &n;87 Next( *Back(n ) ) = &n;80 Back( &head( s ) ) = &n; 81 Next( Back( &n ) ) = &n; 88 82 } else { 89 Next( n ) = &n;90 Back( n ) = &n;83 Next( &n ) = &n; 84 Back( &n ) = &n; 91 85 } // if 92 86 // inserted node must be consistent before it is seen … … 95 89 } else { 96 90 if ( ! &bef ) &bef = &head( s ); 97 Next( n ) = &bef;98 Back( n ) = Back(bef );91 Next( &n ) = &bef; 92 Back( &n ) = Back( &bef ); 99 93 // inserted node must be consistent before it is seen 100 94 asm( "" : : : "memory" ); // prevent code movement across barrier 101 Back( bef ) = &n;102 Next( *Back(n ) ) = &n;95 Back( &bef ) = &n; 96 Next( Back( &n ) ) = &n; 103 97 } // if 104 98 } // post: n->listed() & *n in *s & succ(n) == bef … … 107 101 // Insert *n into the sequence after *aft, or at the beginning if aft == 0. 108 102 void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s 109 103 #ifdef __CFA_DEBUG__ 110 104 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n ); 111 105 #endif // __CFA_DEBUG__ 112 106 if ( ! &aft ) { // must change root 113 107 if ( root ) { 114 Next( n ) = &head( s );115 Back( n ) = Back(head( s ) );108 Next( &n ) = &head( s ); 109 Back( &n ) = Back( &head( s ) ); 116 110 // inserted node must be consistent before it is seen 117 111 asm( "" : : : "memory" ); // prevent code movement across barrier 118 Back( head( s ) ) = &n;119 Next( *Back(n ) ) = &n;112 Back( &head( s ) ) = &n; 113 Next( Back( &n ) ) = &n; 120 114 } else { 121 Next( n ) = &n;122 Back( n ) = &n;115 Next( &n ) = &n; 116 Back( &n ) = &n; 123 117 } // if 124 118 asm( "" : : : "memory" ); // prevent code movement across barrier 125 119 root = &n; 126 120 } else { 127 Next( n ) = Next(aft );128 Back( n ) = &aft;121 Next( &n ) = Next( &aft ); 122 Back( &n ) = &aft; 129 123 // inserted node must be consistent before it is seen 130 124 asm( "" : : : "memory" ); // prevent code movement across barrier 131 Back( *Next(n ) ) = &n;132 Next( aft ) = &n;125 Back( Next( &n ) ) = &n; 126 Next( &aft ) = &n; 133 127 } // if 134 128 } // post: n->listed() & *n in *s & succ(n) == bef … … 136 130 // pre: n->listed() & *n in *s 137 131 void remove( Sequence(T) & s, T & n ) with( s ) { // O(1) 138 132 #ifdef __CFA_DEBUG__ 139 133 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); 140 134 #endif // __CFA_DEBUG__ 141 135 if ( &n == &head( s ) ) { 142 if ( Next( head( s ) ) == &head( s ) ) root = 0p;143 else root = Next( head( s ) );144 } // if 145 Back( *Next( n ) ) = Back(n );146 Next( *Back( n ) ) = Next(n );147 Next( n ) = Back(n ) = 0p;136 if ( Next( &head( s ) ) == &head( s ) ) root = 0p; 137 else root = Next( &head( s ) ); 138 } // if 139 Back( Next( &n ) ) = Back( &n ); 140 Next( Back( &n ) ) = Next( &n ); 141 Next( &n ) = Back( &n ) = 0p; 148 142 } // post: !n->listed(). 149 143 … … 181 175 root = from.root; 182 176 } else { // "to" list not empty 183 T * toEnd = Back( head( s ) );184 T * fromEnd = Back( head( from ) );185 Back( *root ) = fromEnd;186 Next( *fromEnd ) = &head( s );187 Back( *from.root ) = toEnd;188 Next( *toEnd ) = &head( from );177 T * toEnd = Back( &head( s ) ); 178 T * fromEnd = Back( &head( from ) ); 179 Back( root ) = fromEnd; 180 Next( fromEnd ) = &head( s ); 181 Back( from.root ) = toEnd; 182 Next( toEnd ) = &head( from ); 189 183 } // if 190 184 from.root = 0p; // mark "from" list empty … … 194 188 // Node "n" must be in the "from" list. 195 189 void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) { 196 190 #ifdef __CFA_DEBUG__ 197 191 if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n ); 198 192 #endif // __CFA_DEBUG__ 199 193 Sequence(T) to; 200 194 to.root = from.root; // start of "to" list 201 from.root = Next( n ); // start of "from" list195 from.root = Next( &n ); // start of "from" list 202 196 if ( to.root == from.root ) { // last node in list ? 203 197 from.root = 0p; // mark "from" list empty 204 198 } else { 205 Back( head( from ) ) = Back(head( to ) ); // fix "from" list206 Next( *Back(head( to ) ) ) = &head( from );207 Next( n ) = &head( to );// fix "to" list208 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; 209 203 } // if 210 204 transfer( s, to ); … … 220 214 // passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence 221 215 // to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular. 222 Sequence(T) * seq; // FIX ME: cannot be reference216 Sequence(T) * seq; 223 217 }; 224 218 … … 261 255 inline ColIter; 262 256 // See above for explanation. 263 Sequence(T) * seq; // FIX ME: cannot be reference257 Sequence(T) * seq; 264 258 }; 265 259 … … 297 291 } // distribution 298 292 } // distribution 293 294 // Local Variables: // 295 // compile-command: "cfa sequence.hfa" // 296 // End: //
Note:
See TracChangeset
for help on using the changeset viewer.
