Changeset a78c3ff for libcfa/src/bits
- Timestamp:
- Dec 3, 2020, 3:32:44 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:
- aeb31b1
- Parents:
- 636d3715
- Location:
- libcfa/src/bits
- Files:
-
- 3 edited
-
queue.hfa (modified) (7 diffs)
-
queue_example.cfa (modified) (6 diffs)
-
sequence.hfa (modified) (14 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/queue.hfa
r636d3715 ra78c3ff 11 11 inline { 12 12 // wrappers to make Collection have T 13 T *head( Queue(T) & q ) with( q ) {14 return (T *)head( (Collection &)q );13 T & head( Queue(T) & q ) with( q ) { 14 return *(T *)head( (Collection &)q ); 15 15 } // post: empty() & head() == 0 | !empty() & head() in *q 16 16 … … 23 23 } // post: empty() 24 24 25 T *tail( Queue(T) & q ) with( q ) {26 return last;25 T & tail( Queue(T) & q ) with( q ) { 26 return *last; 27 27 } 28 28 29 T * succ( Queue(T) & q, T *n ) with( q ) { // pre: *n in *q29 T & succ( Queue(T) & q, T & n ) with( q ) { // pre: *n in *q 30 30 #ifdef __CFA_DEBUG__ 31 if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q,n );31 if ( ! listed( &n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, &n ); 32 32 #endif // __CFA_DEBUG__ 33 return (Next( n ) == n) ? 0p : Next(n );33 return (Next( &n ) == &n) ? *0p : *Next( &n ); 34 34 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q 35 35 36 void addHead( Queue(T) & q, T *n ) with( q ) {36 void addHead( Queue(T) & q, T & n ) with( q ) { 37 37 #ifdef __CFA_DEBUG__ 38 if ( listed( n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q,n );38 if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n ); 39 39 #endif // __CFA_DEBUG__ 40 40 if ( last ) { 41 Next( n ) =head( q );42 q.root = n;41 Next( &n ) = &head( q ); 42 q.root = &n; 43 43 } else { 44 root = last = n;45 Next( n ) =n; // last node points to itself44 root = last = &n; 45 Next( &n ) = &n; // last node points to itself 46 46 } 47 47 } 48 48 49 void addTail( Queue(T) & q, T *n ) with( q ) {49 void addTail( Queue(T) & q, T & n ) with( q ) { 50 50 #ifdef __CFA_DEBUG__ 51 if ( listed( n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q,n );51 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n ); 52 52 #endif // __CFA_DEBUG__ 53 if ( last ) Next( last ) = n;54 else root = n;55 last = n;56 Next( n ) =n; // last node points to itself53 if ( last ) Next( last ) = &n; 54 else root = &n; 55 last = &n; 56 Next( &n ) = &n; // last node points to itself 57 57 } 58 58 59 void add( Queue(T) & q, T *n ) with( q ) {59 void add( Queue(T) & q, T & n ) with( q ) { 60 60 addTail( q, n ); 61 61 } 62 62 63 T *dropHead( Queue(T) & q ) with( q ) {64 T * t = head( q );63 T & dropHead( Queue(T) & q ) with( q ) { 64 T * t = &head( q ); 65 65 if ( root ) { 66 66 root = Next( root ); 67 if ( head( q ) == t ) {67 if ( &head( q ) == t ) { 68 68 root = last = 0p; // only one element 69 69 } 70 70 Next( t ) = 0p; 71 71 } 72 return t;72 return *t; 73 73 } 74 74 75 T *drop( Queue(T) & q ) with( q ) {75 T & drop( Queue(T) & q ) with( q ) { 76 76 return dropHead( q ); 77 77 } 78 78 79 void remove( Queue(T) & q, T *n ) with( q ) { // O(n)79 void remove( Queue(T) & q, T & n ) with( q ) { // O(n) 80 80 #ifdef __CFA_DEBUG__ 81 if ( ! listed( (Colable &) (*n) ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q,n );81 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n ); 82 82 #endif // __CFA_DEBUG__ 83 83 T * prev = 0; 84 84 T * curr = (T *)root; 85 85 for ( ;; ) { 86 if ( n == curr) { // found => remove87 if ((T *)root == n) {86 if (&n == curr) { // found => remove 87 if ((T *)root == &n) { 88 88 dropHead( q ); 89 } else if (last == n) {89 } else if (last == &n) { 90 90 last = prev; 91 91 Next( last ) = last; … … 93 93 Next( prev ) = Next( curr ); 94 94 } 95 Next( n ) = 0p;95 Next( &n ) = 0p; 96 96 break; 97 97 } 98 98 #ifdef __CFA_DEBUG__ 99 99 // not found => error 100 if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, n );100 if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n ); 101 101 #endif // __CFA_DEBUG__ 102 102 prev = curr; … … 105 105 } // post: ! listed( n ) 106 106 107 T *dropTail( Queue(T) & q ) with( q ) { // O(n)108 T *n = tail( q );109 return n ? remove( q, n ), n :0p;107 T & dropTail( Queue(T) & q ) with( q ) { // O(n) 108 T & n = tail( q ); 109 return &n ? remove( q, n ), n : *0p; 110 110 } 111 111 … … 116 116 root = from.root; 117 117 } else { // "to" list not empty 118 Next( last ) = head( from );118 Next( last ) = &head( from ); 119 119 } 120 120 last = from.last; … … 124 124 // Transfer the "from" list up to node "n" to the end of queue list; the "from" list becomes the list after node "n". 125 125 // Node "n" must be in the "from" list. 126 void split( Queue(T) & q, Queue(T) & from, T *n ) with( q ) {126 void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) { 127 127 #ifdef __CFA_DEBUG__ 128 if ( ! listed( (Colable &) (*n) ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q,n );128 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n ); 129 129 #endif // __CFA_DEBUG__ 130 130 Queue(T) to; 131 131 to.root = from.root; // start of "to" list 132 to.last = n; // end of "to" list133 from.root = Next( n ); // start of "from" list134 if ( n ==head( from ) ) { // last node in list ?132 to.last = &n; // end of "to" list 133 from.root = Next( &n ); // start of "from" list 134 if ( &n == &head( from ) ) { // last node in list ? 135 135 from.root = from.last = 0p; // mark "from" list empty 136 136 } else { 137 Next( n ) =n; // fix end of "to" list137 Next( &n ) = &n; // fix end of "to" list 138 138 } 139 139 transfer( q, to ); … … 154 154 // create an iterator active in Queue q 155 155 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 156 curr = head( q );156 curr = &head( q ); 157 157 } // post: curr = {e in q} 158 158 159 void ?{}( QueueIter(T) & qi, T *start ) with( qi ) {160 curr = start;159 void ?{}( QueueIter(T) & qi, T & start ) with( qi ) { 160 curr = &start; 161 161 } // post: curr = {e in q} 162 162 163 163 // make existing iterator active in Queue q 164 164 void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 165 curr = head( q );165 curr = &head( q ); 166 166 } // post: curr = {e in q} 167 167 -
libcfa/src/bits/queue_example.cfa
r636d3715 ra78c3ff 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( drop( fred ) );38 delete( &drop( fred ) ); 39 39 } 40 40 … … 45 45 46 46 for ( i; 10 ) { 47 add( fred, new( 2 * i + 1 ) );47 add( fred, *new( 2 * i + 1 ) ); 48 48 } 49 49 for ( over( fredIter, fred ); fredIter >> f; ) { … … 78 78 79 79 for ( i; 10 ) { 80 add( mary, new( 2 * i ) );80 add( mary, *new( 2 * i ) ); 81 81 } 82 82 … … 87 87 88 88 for ( i; 9 ) { 89 delete( drop( mary ) );89 delete( &drop( mary ) ); 90 90 } 91 91 … … 96 96 97 97 for ( i; 10 ) { 98 add( mary, new( 2 * i + 1 ) );98 add( mary, *new( 2 * i + 1 ) ); 99 99 } 100 100 for ( over( maryIter, mary ); maryIter >> m; ) { -
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.
