Changeset b37515b for libcfa/src/bits
- Timestamp:
- Dec 2, 2020, 3:30:53 PM (4 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- cd6a6ff
- Parents:
- ddcedfe
- Location:
- libcfa/src/bits
- Files:
-
- 2 edited
-
sequence.hfa (modified) (5 diffs)
-
sequence_example.cfa (modified) (6 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/sequence.hfa
rddcedfe rb37515b 62 62 63 63 // Return a pointer to the last sequence element, without removing it. 64 T *tail( Sequence(T) & s ) with( s ) {65 return root ? (T *)Back( Root( s ) ) :0p; // needs cast?64 T & tail( Sequence(T) & s ) with( s ) { 65 return root ? (T &)Back( Root( s ) ) : *0p; // needs cast? 66 66 } // post: empty() & tail() == 0 | !empty() & tail() in *s 67 67 … … 84 84 85 85 // Insert *n into the sequence before *bef, or at the end if bef == 0. 86 void insertBef( Sequence(T) & s, T * n, T *bef ) with( s ) { // pre: !n->listed() & *bef in *s87 #ifdef __CFA_DEBUG__ 88 if ( listed( n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n,bef );89 #endif // __CFA_DEBUG__ 90 if ( bef == Root( s ) ) { // must change root86 void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s 87 #ifdef __CFA_DEBUG__ 88 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); 89 #endif // __CFA_DEBUG__ 90 if ( &bef == Root( s ) ) { // must change root 91 91 if ( root ) { 92 Next( n ) = Root( s );93 Back( n ) = Back( Root( s ) );92 Next( &n ) = Root( s ); 93 Back( &n ) = Back( Root( s ) ); 94 94 // inserted node must be consistent before it is seen 95 95 asm( "" : : : "memory" ); // prevent code movement across barrier 96 Back( Root( s ) ) = n;97 Next( Back( n ) ) =n;96 Back( Root( s ) ) = &n; 97 Next( Back( &n ) ) = &n; 98 98 } else { 99 Next( n ) =n;100 Back( n ) =n;99 Next( &n ) = &n; 100 Back( &n ) = &n; 101 101 } // if 102 102 // inserted node must be consistent before it is seen 103 103 asm( "" : : : "memory" ); // prevent code movement across barrier 104 root = n;104 root = &n; 105 105 } else { 106 if ( ! bef )bef = Root( s );107 Next( n ) =bef;108 Back( n ) = Back(bef );106 if ( ! &bef ) &bef = Root( s ); 107 Next( &n ) = &bef; 108 Back( &n ) = Back( &bef ); 109 109 // inserted node must be consistent before it is seen 110 110 asm( "" : : : "memory" ); // prevent code movement across barrier 111 Back( bef ) =n;112 Next( Back( n ) ) =n;111 Back( &bef ) = &n; 112 Next( Back( &n ) ) = &n; 113 113 } // if 114 114 } // post: n->listed() & *n in *s & succ(n) == bef … … 116 116 117 117 // Insert *n into the sequence after *aft, or at the beginning if aft == 0. 118 void insertAft( Sequence(T) & s, T * aft, T *n ) with( s ) { // pre: !n->listed() & *aft in *s119 #ifdef __CFA_DEBUG__ 120 if ( listed( n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, aft,n );121 #endif // __CFA_DEBUG__ 122 if ( ! aft ) { // must change root118 void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s 119 #ifdef __CFA_DEBUG__ 120 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n ); 121 #endif // __CFA_DEBUG__ 122 if ( ! &aft ) { // must change root 123 123 if ( root ) { 124 Next( n ) = Root( s );125 Back( n ) = Back( Root( s ) );124 Next( &n ) = Root( s ); 125 Back( &n ) = Back( Root( s ) ); 126 126 // inserted node must be consistent before it is seen 127 127 asm( "" : : : "memory" ); // prevent code movement across barrier 128 Back( Root( s ) ) = n;129 Next( Back( n ) ) =n;128 Back( Root( s ) ) = &n; 129 Next( Back( &n ) ) = &n; 130 130 } else { 131 Next( n ) =n;132 Back( n ) =n;131 Next( &n ) = &n; 132 Back( &n ) = &n; 133 133 } // if 134 134 asm( "" : : : "memory" ); // prevent code movement across barrier 135 root = n;135 root = &n; 136 136 } else { 137 Next( n ) = Next(aft );138 Back( n ) =aft;137 Next( &n ) = Next( &aft ); 138 Back( &n ) = &aft; 139 139 // inserted node must be consistent before it is seen 140 140 asm( "" : : : "memory" ); // prevent code movement across barrier 141 Back( Next( n ) ) =n;142 Next( aft ) =n;141 Back( Next( &n ) ) = &n; 142 Next( &aft ) = &n; 143 143 } // if 144 144 } // post: n->listed() & *n in *s & succ(n) == bef 145 145 146 146 // pre: n->listed() & *n in *s 147 void remove( Sequence(T) & s, T *n ) with( s ) { // O(1)148 #ifdef __CFA_DEBUG__ 149 if ( ! listed( n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s,n );150 #endif // __CFA_DEBUG__ 151 if ( n == Root( s ) ) {147 void remove( Sequence(T) & s, T & n ) with( s ) { // O(1) 148 #ifdef __CFA_DEBUG__ 149 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); 150 #endif // __CFA_DEBUG__ 151 if ( &n == Root( s ) ) { 152 152 if ( Next( Root( s ) ) == Root( s ) ) root = 0p; 153 153 else root = Next( Root(s ) ); 154 154 } // if 155 Back( Next( n ) ) = Back(n );156 Next( Back( n ) ) = Next(n );157 Next( n ) = Back(n ) = 0p;155 Back( Next( &n ) ) = Back( &n ); 156 Next( Back( &n ) ) = Next( &n ); 157 Next( &n ) = Back( &n ) = 0p; 158 158 } // post: !n->listed(). 159 159 160 160 // Add an element to the head of the sequence. 161 void addHead( Sequence(T) & s, T *n ) { // pre: !n->listed(); post: n->listed() & head() == n162 insertAft( s, 0, n );161 void addHead( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 162 insertAft( s, *0p, n ); 163 163 } 164 164 // Add an element to the tail of the sequence. 165 void addTail( Sequence(T) & s, T *n ) { // pre: !n->listed(); post: n->listed() & head() == n166 insertBef( s, n, 0);165 void addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 166 insertBef( s, n, *0p ); 167 167 } 168 168 // Add an element to the tail of the sequence. 169 void add( Sequence(T) & s, T *n ) { // pre: !n->listed(); post: n->listed() & head() == n169 void add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 170 170 addTail( s, n ); 171 171 } 172 172 // Remove and return the head element in the sequence. 173 T *dropHead( Sequence(T) & s ) {173 T & dropHead( Sequence(T) & s ) { 174 174 T * n = head( s ); 175 return n ? remove( s, n ), n :0p;175 return n ? remove( s, *n ), *n : *0p; 176 176 } 177 177 // Remove and return the head element in the sequence. 178 T *drop( Sequence(T) & s ) {178 T & drop( Sequence(T) & s ) { 179 179 return dropHead( s ); 180 180 } 181 181 // Remove and return the tail element in the sequence. 182 T *dropTail( Sequence(T) & s ) {183 T *n = tail( s );184 return n ? remove( s, n ), n :0p;182 T & dropTail( Sequence(T) & s ) { 183 T & n = tail( s ); 184 return &n ? remove( s, n ), n : *0p; 185 185 } 186 186 … … 283 283 ((ColIter &) si){}; 284 284 seq = &s; 285 curr = tail( s );285 curr = &tail( s ); 286 286 } // post: elts = null. 287 287 288 288 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 289 289 seq = &s; 290 curr = tail( s );290 curr = &tail( s ); 291 291 } // post: elts = {e in s}. 292 292 … … 295 295 &tp = Curr( si ); 296 296 T * n = pred( *seq, Curr( si ) ); 297 curr = n == tail( *seq ) ? 0p : n;297 curr = n == &tail( *seq ) ? 0p : n; 298 298 } else &tp = 0p; 299 299 return &tp != 0p; -
libcfa/src/bits/sequence_example.cfa
rddcedfe rb37515b 27 27 28 28 for ( i; 10 ) { 29 add( fred, new( 2 * i ) );29 add( fred, *new( 2 * i ) ); 30 30 } 31 31 … … 36 36 37 37 for ( i; 9 ) { 38 delete( dropHead( fred ) );38 delete( &dropHead( fred ) ); 39 39 } 40 40 … … 45 45 46 46 for ( i; 10 ) { 47 addTail( fred, new( 2 * i + 1 ) );47 addTail( fred, *new( 2 * i + 1 ) ); 48 48 } 49 49 for ( over( fredIter, fred ); fredIter >> f; ) { … … 87 87 88 88 for ( i; 10 ) { 89 add( mary, new( 2 * i ) );90 add( baz, new( 2 * i ) );89 add( mary, *new( 2 * i ) ); 90 add( baz, *new( 2 * i ) ); 91 91 } 92 92 … … 97 97 98 98 for ( i; 9 ) { 99 delete( dropHead( mary ) );99 delete( &dropHead( mary ) ); 100 100 } 101 101 … … 106 106 107 107 for ( i; 10 ) { 108 addTail( mary, new( 2 * i + 1 ) );108 addTail( mary, *new( 2 * i + 1 ) ); 109 109 } 110 110 for ( over( maryIter, mary ); maryIter >> m; ) {
Note: See TracChangeset
for help on using the changeset viewer.
