Changeset 7c1144b
- Timestamp:
- Dec 5, 2020, 8:48:32 AM (3 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- ec5d599
- Parents:
- a32cbac2
- Location:
- libcfa/src/bits
- Files:
-
- 8 edited
-
collection.hfa (modified) (3 diffs)
-
multi_list.cfa (modified) (1 diff)
-
queue.hfa (modified) (7 diffs)
-
queue_example.cfa (modified) (1 diff)
-
sequence.hfa (modified) (13 diffs)
-
sequence_example.cfa (modified) (1 diff)
-
stack.hfa (modified) (4 diffs)
-
stack_example.cfa (modified) (1 diff)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/collection.hfa
ra32cbac2 r7c1144b 7 7 8 8 inline { 9 // PUBLIC 10 9 11 void ?{}( Colable & co ) with( co ) { 10 12 next = 0p; … … 16 18 } 17 19 18 Colable *getNext( Colable & co ) with( co ) {19 return next;20 Colable & getNext( Colable & co ) with( co ) { 21 return *next; 20 22 } 23 24 // PRIVATE 21 25 22 26 Colable *& Next( Colable * cp ) { … … 24 28 } 25 29 30 // wrappers to make Collection have T 26 31 forall( dtype T ) { 27 T *& Next( T *n ) {28 return (T *)Next( (Colable *) n );32 T *& Next( T & n ) { 33 return (T *)Next( (Colable *)&n ); 29 34 } 30 35 -
libcfa/src/bits/multi_list.cfa
ra32cbac2 r7c1144b 57 57 58 58 SeqIter(TaskDL) sqiter; 59 TaskDL & dl; 59 TaskDL & dl; // iterator index 60 60 TaskSL & sl; 61 61 -
libcfa/src/bits/queue.hfa
ra32cbac2 r7c1144b 28 28 29 29 T * succ( Queue(T) & q, T * n ) with( q ) { // pre: *n in *q 30 #ifdef __CFA_DEBUG__30 #ifdef __CFA_DEBUG__ 31 31 if ( ! listed( n ) ) abort( "(Queue &)%p.succ( %p ) : Node is not on a list.", &q, n ); 32 #endif // __CFA_DEBUG__33 return (Next( n ) == n) ? 0p : Next(n );32 #endif // __CFA_DEBUG__ 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 36 void addHead( Queue(T) & q, T & n ) with( q ) { 37 #ifdef __CFA_DEBUG__37 #ifdef __CFA_DEBUG__ 38 38 if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n ); 39 #endif // __CFA_DEBUG__39 #endif // __CFA_DEBUG__ 40 40 if ( last ) { 41 Next( &n ) = &head( q );41 Next( n ) = &head( q ); 42 42 q.root = &n; 43 43 } else { 44 44 root = last = &n; 45 Next( &n ) = &n; // last node points to itself45 Next( n ) = &n; // last node points to itself 46 46 } 47 47 } 48 48 49 49 void addTail( Queue(T) & q, T & n ) with( q ) { 50 #ifdef __CFA_DEBUG__50 #ifdef __CFA_DEBUG__ 51 51 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n ); 52 #endif // __CFA_DEBUG__53 if ( last ) Next( last ) = &n;52 #endif // __CFA_DEBUG__ 53 if ( last ) Next( *last ) = &n; 54 54 else root = &n; 55 55 last = &n; 56 Next( &n ) = &n; // last node points to itself56 Next( n ) = &n; // last node points to itself 57 57 } 58 58 … … 64 64 T & t = head( q ); 65 65 if ( root ) { 66 root = Next( root );66 root = Next( *root ); 67 67 if ( &head( q ) == &t ) { 68 68 root = last = 0p; // only one element 69 69 } 70 Next( &t ) = 0p;70 Next( t ) = 0p; 71 71 } 72 72 return t; … … 78 78 79 79 void remove( Queue(T) & q, T & n ) with( q ) { // O(n) 80 #ifdef __CFA_DEBUG__80 #ifdef __CFA_DEBUG__ 81 81 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n ); 82 #endif // __CFA_DEBUG__83 T * prev =0p;84 T * curr =(T *)root;82 #endif // __CFA_DEBUG__ 83 T & prev = *0p; 84 T & curr = *(T *)root; 85 85 for ( ;; ) { 86 if ( &n == curr ) { // found => remove86 if ( &n == &curr ) { // found => remove 87 87 if ( (T *)root == &n ) { 88 88 dropHead( q ); 89 89 } else if ( last == &n ) { 90 last = prev;91 Next( last ) = last;90 last = &prev; 91 Next( *last ) = last; 92 92 } else { 93 93 Next( prev ) = Next( curr ); 94 94 } 95 Next( &n ) = 0p;95 Next( n ) = 0p; 96 96 break; 97 97 } 98 #ifdef __CFA_DEBUG__99 98 // not found => error 100 if (curr == last) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n ); 101 #endif // __CFA_DEBUG__ 102 prev = curr; 103 curr = Next( curr ); 99 #ifdef __CFA_DEBUG__ 100 if ( &curr == last ) abort( "(Queue &)%p.remove( %p ) : Node is not in list.", &q, &n ); 101 #endif // __CFA_DEBUG__ 102 &prev = &curr; 103 &curr = Next( curr ); 104 104 } 105 105 } // post: ! listed( n ) … … 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; … … 125 125 // Node "n" must be in the "from" list. 126 126 void split( Queue(T) & q, Queue(T) & from, T & n ) with( q ) { 127 #ifdef __CFA_DEBUG__127 #ifdef __CFA_DEBUG__ 128 128 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.split( %p ) : Node is not on a list.", &q, &n ); 129 #endif // __CFA_DEBUG__129 #endif // __CFA_DEBUG__ 130 130 Queue(T) to; 131 131 to.root = from.root; // start of "to" list 132 132 to.last = &n; // end of "to" list 133 from.root = Next( &n ); // start of "from" list133 from.root = Next( n ); // start of "from" list 134 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 ); … … 169 169 if ( curr ) { 170 170 &tp = Curr( qi ); 171 T * n = Next( Curr( qi ) );171 T * n = Next( *Curr( qi ) ); 172 172 curr = (n == Curr( qi ) ) ? 0p : n; 173 173 } else &tp = 0p; … … 177 177 } // distribution 178 178 } // distribution 179 180 // Local Variables: //181 // compile-command: "cfa queue.cfa" //182 // End: // -
libcfa/src/bits/queue_example.cfa
ra32cbac2 r7c1144b 107 107 } 108 108 } 109 110 // Local Variables: //111 // compile-command: "cfa queue_example.cfa" //112 // End: // -
libcfa/src/bits/sequence.hfa
ra32cbac2 r7c1144b 9 9 10 10 inline { 11 // PUBLIC 12 11 13 void ?{}( Seqable & sq ) with( sq ) { 12 14 ((Colable &) sq){}; … … 18 20 } 19 21 22 // PRIVATE 23 20 24 Seqable *& Back( Seqable * sq ) { 21 25 return sq->back; 22 26 } 27 28 // wrappers to make Collection have T 29 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 *s 37 } // distribution 23 38 } // distribution 24 39 … … 29 44 30 45 inline { 31 // wrappers to make Collection have T32 T & head( Sequence(T) & s ) with( s ) {33 return *(T *)head( (Collection &)s );34 } // post: empty() & head() == 0 | !empty() & head() in *s35 36 T *& Back( T * n ) {37 return (T *)Back( (Seqable *)n );38 }39 40 46 void ?{}( Sequence(T) &, const Sequence(T) & ) = void; // no copy 41 47 Sequence(T) & ?=?( const Sequence(T) & ) = void; // no assignment … … 47 53 // Return a pointer to the last sequence element, without removing it. 48 54 T & tail( Sequence(T) & s ) with( s ) { 49 return root ? (T &)*Back( &head( s ) ) : *0p;55 return root ? (T &)*Back( head( s ) ) : *0p; 50 56 } // post: empty() & tail() == 0 | !empty() & tail() in *s 51 57 52 // Return a pointer to the element after *n, or 0p if there isn't one.58 // Return a pointer to the element after *n, or 0p if list empty. 53 59 T * succ( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s 54 #ifdef __CFA_DEBUG__60 #ifdef __CFA_DEBUG__ 55 61 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 );62 #endif // __CFA_DEBUG__ 63 return Next( *n ) == &head( s ) ? 0p : Next( *n ); 58 64 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 59 65 60 66 // Return a pointer to the element before *n, or 0p if there isn't one. 61 67 T * pred( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s 62 #ifdef __CFA_DEBUG__68 #ifdef __CFA_DEBUG__ 63 69 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 );70 #endif // __CFA_DEBUG__ 71 return n == &head( s ) ? 0p : Back( *n ); 66 72 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 67 73 … … 69 75 // Insert *n into the sequence before *bef, or at the end if bef == 0. 70 76 void insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s 71 #ifdef __CFA_DEBUG__77 #ifdef __CFA_DEBUG__ 72 78 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); 73 #endif // __CFA_DEBUG__79 #endif // __CFA_DEBUG__ 74 80 if ( &bef == &head( s ) ) { // must change root 75 81 if ( root ) { 76 Next( &n ) = &head( s );77 Back( &n ) = Back( &head( s ) );82 Next( n ) = &head( s ); 83 Back( n ) = Back( head( s ) ); 78 84 // inserted node must be consistent before it is seen 79 85 asm( "" : : : "memory" ); // prevent code movement across barrier 80 Back( &head( s ) ) = &n;81 Next( Back( &n ) ) = &n;86 Back( head( s ) ) = &n; 87 Next( *Back( n ) ) = &n; 82 88 } else { 83 Next( &n ) = &n;84 Back( &n ) = &n;89 Next( n ) = &n; 90 Back( n ) = &n; 85 91 } // if 86 92 // inserted node must be consistent before it is seen … … 89 95 } else { 90 96 if ( ! &bef ) &bef = &head( s ); 91 Next( &n ) = &bef;92 Back( &n ) = Back( &bef );97 Next( n ) = &bef; 98 Back( n ) = Back( bef ); 93 99 // inserted node must be consistent before it is seen 94 100 asm( "" : : : "memory" ); // prevent code movement across barrier 95 Back( &bef ) = &n;96 Next( Back( &n ) ) = &n;101 Back( bef ) = &n; 102 Next( *Back( n ) ) = &n; 97 103 } // if 98 104 } // post: n->listed() & *n in *s & succ(n) == bef … … 101 107 // Insert *n into the sequence after *aft, or at the beginning if aft == 0. 102 108 void insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s 103 #ifdef __CFA_DEBUG__109 #ifdef __CFA_DEBUG__ 104 110 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n ); 105 #endif // __CFA_DEBUG__111 #endif // __CFA_DEBUG__ 106 112 if ( ! &aft ) { // must change root 107 113 if ( root ) { 108 Next( &n ) = &head( s );109 Back( &n ) = Back( &head( s ) );114 Next( n ) = &head( s ); 115 Back( n ) = Back( head( s ) ); 110 116 // inserted node must be consistent before it is seen 111 117 asm( "" : : : "memory" ); // prevent code movement across barrier 112 Back( &head( s ) ) = &n;113 Next( Back( &n ) ) = &n;118 Back( head( s ) ) = &n; 119 Next( *Back( n ) ) = &n; 114 120 } else { 115 Next( &n ) = &n;116 Back( &n ) = &n;121 Next( n ) = &n; 122 Back( n ) = &n; 117 123 } // if 118 124 asm( "" : : : "memory" ); // prevent code movement across barrier 119 125 root = &n; 120 126 } else { 121 Next( &n ) = Next( &aft );122 Back( &n ) = &aft;127 Next( n ) = Next( aft ); 128 Back( n ) = &aft; 123 129 // inserted node must be consistent before it is seen 124 130 asm( "" : : : "memory" ); // prevent code movement across barrier 125 Back( Next( &n ) ) = &n;126 Next( &aft ) = &n;131 Back( *Next( n ) ) = &n; 132 Next( aft ) = &n; 127 133 } // if 128 134 } // post: n->listed() & *n in *s & succ(n) == bef … … 130 136 // pre: n->listed() & *n in *s 131 137 void remove( Sequence(T) & s, T & n ) with( s ) { // O(1) 132 #ifdef __CFA_DEBUG__138 #ifdef __CFA_DEBUG__ 133 139 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); 134 #endif // __CFA_DEBUG__140 #endif // __CFA_DEBUG__ 135 141 if ( &n == &head( s ) ) { 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;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; 142 148 } // post: !n->listed(). 143 149 … … 175 181 root = from.root; 176 182 } else { // "to" list not empty 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 );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 ); 183 189 } // if 184 190 from.root = 0p; // mark "from" list empty … … 188 194 // Node "n" must be in the "from" list. 189 195 void split( Sequence(T) & s, Sequence(T) & from, T & n ) with( s ) { 190 #ifdef __CFA_DEBUG__196 #ifdef __CFA_DEBUG__ 191 197 if ( ! listed( &n ) ) abort( "(Sequence &)%p.split( %p ) : Node is not on a list.", &s, &n ); 192 #endif // __CFA_DEBUG__198 #endif // __CFA_DEBUG__ 193 199 Sequence(T) to; 194 200 to.root = from.root; // start of "to" list 195 from.root = Next( &n ); // start of "from" list201 from.root = Next( n ); // start of "from" list 196 202 if ( to.root == from.root ) { // last node in list ? 197 203 from.root = 0p; // mark "from" list empty 198 204 } 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;205 Back( head( from ) ) = Back( head( to ) ); // fix "from" list 206 Next( *Back( head( to ) ) ) = &head( from ); 207 Next( n ) = &head( to ); // fix "to" list 208 Back( head( to ) ) = &n; 203 209 } // if 204 210 transfer( s, to ); … … 214 220 // passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence 215 221 // to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular. 216 Sequence(T) * seq; 222 Sequence(T) * seq; // FIX ME: cannot be reference 217 223 }; 218 224 … … 255 261 inline ColIter; 256 262 // See above for explanation. 257 Sequence(T) * seq; 263 Sequence(T) * seq; // FIX ME: cannot be reference 258 264 }; 259 265 … … 291 297 } // distribution 292 298 } // distribution 293 294 // Local Variables: //295 // compile-command: "cfa sequence.hfa" //296 // End: // -
libcfa/src/bits/sequence_example.cfa
ra32cbac2 r7c1144b 137 137 } 138 138 } 139 140 // Local Variables: //141 // compile-command: "cfa sequence_example.cfa" //142 // End: // -
libcfa/src/bits/stack.hfa
ra32cbac2 r7c1144b 26 26 27 27 void addHead( Stack(T) & s, T & n ) with( s ) { 28 #ifdef __CFA_DEBUG__28 #ifdef __CFA_DEBUG__ 29 29 if ( listed( (Colable &)(n) ) ) abort( "(Stack &)%p.addHead( %p ) : Node is already on another list.", &s, n ); 30 #endif // __CFA_DEBUG__31 Next( &n ) = &head( s ) ? &head( s ) : &n;30 #endif // __CFA_DEBUG__ 31 Next( n ) = &head( s ) ? &head( s ) : &n; 32 32 root = &n; 33 33 } … … 44 44 T & t = head( s ); 45 45 if ( root ) { 46 root = ( T *)Next( root);46 root = ( T *)Next( *root ); 47 47 if ( &head( s ) == &t ) root = 0p; // only one element ? 48 Next( &t ) = 0p;48 Next( t ) = 0p; 49 49 } // if 50 50 return t; … … 85 85 if ( curr ) { 86 86 &tp = Curr( si ); 87 T * n = Next( Curr( si ) );87 T * n = Next( *Curr( si ) ); 88 88 curr = n == Curr( si ) ? 0p : n; 89 89 } else &tp = 0p; … … 92 92 } // distribution 93 93 } // distribution 94 95 // Local Variables: //96 // compile-command: "make install" //97 // End: // -
libcfa/src/bits/stack_example.cfa
ra32cbac2 r7c1144b 107 107 } 108 108 } 109 110 // Local Variables: //111 // compile-command: "cfa stack_example.cfa" //112 // End: //
Note: See TracChangeset
for help on using the changeset viewer.
