Changeset 54f89d5 for libcfa/src/bits
- Timestamp:
- Dec 4, 2020, 11:39:23 AM (5 years ago)
- Branches:
- ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
- Children:
- 3c6480b7
- Parents:
- ab0257b9 (diff), a32cbac2 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the(diff)links above to see all the changes relative to each parent. - Location:
- libcfa/src/bits
- Files:
-
- 1 added
- 5 edited
-
containers.hfa (modified) (7 diffs)
-
multi_list.cfa (added)
-
queue.hfa (modified) (9 diffs)
-
queue_example.cfa (modified) (6 diffs)
-
sequence.hfa (modified) (18 diffs)
-
stack.hfa (modified) (6 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/containers.hfa
rab0257b9 r54f89d5 17 17 #include "bits/align.hfa" 18 18 #include "bits/defs.hfa" 19 19 #include <stdio.h> 20 20 //----------------------------------------------------------------------------- 21 21 // Array … … 146 146 static inline forall( dtype T | is_node(T) ) { 147 147 void ?{}( __queue(T) & this ) with( this ) { 148 head{ 1p };149 tail{ &head };150 verify(*t ail == 1p);148 (this.head){ 1p }; 149 (this.tail){ &this.head }; 150 verify(*this.tail == 1p); 151 151 } 152 152 153 153 void append( __queue(T) & this, T * val ) with( this ) { 154 verify(t ail != 0p);155 verify(*t ail == 1p);156 *t ail = val;157 t ail = &get_next( *val );158 *t ail = 1p;154 verify(this.tail != 0p); 155 verify(*this.tail == 1p); 156 *this.tail = val; 157 this.tail = &get_next( *val ); 158 *this.tail = 1p; 159 159 } 160 160 161 161 T * peek( __queue(T) & this ) { 162 162 verify(*this.tail == 1p); 163 T * head= this.head;164 if( head!= 1p ) {163 T * front = this.head; 164 if( front != 1p ) { 165 165 verify(*this.tail == 1p); 166 return head;166 return front; 167 167 } 168 168 verify(*this.tail == 1p); … … 172 172 T * pop_head( __queue(T) & this ) { 173 173 verify(*this.tail == 1p); 174 T * head = this.head;175 if( head != 1p ) {176 this.head = get_next( * head );177 if( get_next( * head ) == 1p ) {174 T * _head = this.head; 175 if( _head != 1p ) { 176 this.head = get_next( *_head ); 177 if( get_next( *_head ) == 1p ) { 178 178 this.tail = &this.head; 179 179 } 180 get_next( * head ) = 0p;180 get_next( *_head ) = 0p; 181 181 verify(*this.tail == 1p); 182 verify( get_next(* head) == 0p );183 return head;182 verify( get_next(*_head) == 0p ); 183 return _head; 184 184 } 185 185 verify(*this.tail == 1p); … … 193 193 (*it) = get_next( *val ); 194 194 195 if( t ail == &get_next( *val ) ) {196 t ail = it;195 if( this.tail == &get_next( *val ) ) { 196 this.tail = it; 197 197 } 198 198 199 199 get_next( *val ) = 0p; 200 200 201 verify( ( head == 1p) == (&head ==tail) );202 verify( *t ail == 1p );201 verify( (this.head == 1p) == (&this.head == this.tail) ); 202 verify( *this.tail == 1p ); 203 203 return val; 204 204 } … … 239 239 forall(dtype T ) 240 240 static inline [void] ?{}( __dllist(T) & this, * [T * & next, T * & prev] ( T & ) __get ) { 241 this.head{ 0p };241 (this.head){ 0p }; 242 242 this.__get = __get; 243 243 } … … 248 248 void push_front( __dllist(T) & this, T & node ) with( this ) { 249 249 verify(__get); 250 if ( head ) {251 __get( node ).next = head;252 __get( node ).prev = __get( * head ).prev;250 if ( this.head ) { 251 __get( node ).next = this.head; 252 __get( node ).prev = __get( *this.head ).prev; 253 253 // inserted node must be consistent before it is seen 254 254 // prevent code movement across barrier 255 255 asm( "" : : : "memory" ); 256 __get( * head ).prev = &node;256 __get( *this.head ).prev = &node; 257 257 T & _prev = *__get( node ).prev; 258 258 __get( _prev ).next = &node; … … 264 264 // prevent code movement across barrier 265 265 asm( "" : : : "memory" ); 266 head = &node;266 this.head = &node; 267 267 } 268 268 269 269 void remove( __dllist(T) & this, T & node ) with( this ) { 270 270 verify(__get); 271 if ( &node == head ) {272 if ( __get( * head ).next ==head ) {273 head = 0p;271 if ( &node == this.head ) { 272 if ( __get( *this.head ).next == this.head ) { 273 this.head = 0p; 274 274 } else { 275 head = __get( *head ).next;275 this.head = __get( *this.head ).next; 276 276 } 277 277 } -
libcfa/src/bits/queue.hfa
rab0257b9 r54f89d5 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 … … 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 Next( t ) = 0p;70 Next( &t ) = 0p; 71 71 } 72 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 T * prev = 0 ;83 T * prev = 0p; 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 … … 179 179 180 180 // Local Variables: // 181 // compile-command: " make install" //181 // compile-command: "cfa queue.cfa" // 182 182 // End: // -
libcfa/src/bits/queue_example.cfa
rab0257b9 r54f89d5 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
rab0257b9 r54f89d5 14 14 } // post: ! listed() 15 15 16 Seqable *getBack( Seqable & sq ) with( sq ) {17 return back;16 Seqable & getBack( Seqable & sq ) with( sq ) { 17 return *back; 18 18 } 19 19 … … 30 30 inline { 31 31 // wrappers to make Collection have T 32 T *head( Sequence(T) & s ) with( s ) {33 return (T *)head( (Collection &)s );32 T & head( Sequence(T) & s ) with( s ) { 33 return *(T *)head( (Collection &)s ); 34 34 } // post: empty() & head() == 0 | !empty() & head() in *s 35 35 … … 47 47 // Return a pointer to the last sequence element, without removing it. 48 48 T & tail( Sequence(T) & s ) with( s ) { 49 return root ? (T &) Back( head( s ) ) : *0p; // needs cast?49 return root ? (T &)*Back( &head( s ) ) : *0p; 50 50 } // post: empty() & tail() == 0 | !empty() & tail() in *s 51 51 … … 55 55 if ( ! listed( n ) ) abort( "(Sequence &)%p.succ( %p ) : Node is not on a list.", &s, n ); 56 56 #endif // __CFA_DEBUG__ 57 return Next( n ) == head( s ) ? 0p : Next( n );58 } 57 return Next( n ) == &head( s ) ? 0p : Next( n ); 58 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 59 59 60 60 // Return a pointer to the element before *n, or 0p if there isn't one. … … 63 63 if ( ! listed( n ) ) abort( "(Sequence &)%p.pred( %p ) : Node is not on a list.", &s, n ); 64 64 #endif // __CFA_DEBUG__ 65 return n == head( s ) ? 0p : Back( n );65 return n == &head( s ) ? 0p : Back( n ); 66 66 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 67 67 … … 72 72 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); 73 73 #endif // __CFA_DEBUG__ 74 if ( &bef == head( s ) ) { // must change root74 if ( &bef == &head( s ) ) { // must change root 75 75 if ( root ) { 76 Next( &n ) = head( s );77 Back( &n ) = Back( head( s ) );76 Next( &n ) = &head( s ); 77 Back( &n ) = Back( &head( s ) ); 78 78 // inserted node must be consistent before it is seen 79 79 asm( "" : : : "memory" ); // prevent code movement across barrier 80 Back( head( s ) ) = &n;80 Back( &head( s ) ) = &n; 81 81 Next( Back( &n ) ) = &n; 82 82 } else { … … 88 88 root = &n; 89 89 } else { 90 if ( ! &bef ) &bef = head( s );90 if ( ! &bef ) &bef = &head( s ); 91 91 Next( &n ) = &bef; 92 92 Back( &n ) = Back( &bef ); … … 106 106 if ( ! &aft ) { // must change root 107 107 if ( root ) { 108 Next( &n ) = head( s );109 Back( &n ) = Back( head( s ) );108 Next( &n ) = &head( s ); 109 Back( &n ) = Back( &head( s ) ); 110 110 // inserted node must be consistent before it is seen 111 111 asm( "" : : : "memory" ); // prevent code movement across barrier 112 Back( head( s ) ) = &n;112 Back( &head( s ) ) = &n; 113 113 Next( Back( &n ) ) = &n; 114 114 } else { … … 133 133 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); 134 134 #endif // __CFA_DEBUG__ 135 if ( &n == head( s ) ) {136 if ( Next( head( s ) ) ==head( s ) ) root = 0p;137 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 ) ); 138 138 } // if 139 139 Back( Next( &n ) ) = Back( &n ); … … 156 156 // Remove and return the head element in the sequence. 157 157 T & dropHead( Sequence(T) & s ) { 158 T *n = head( s );159 return n ? remove( s, *n ), *n : *0p;158 T & n = head( s ); 159 return &n ? remove( s, n ), n : *0p; 160 160 } 161 161 // Remove and return the head element in the sequence. … … 175 175 root = from.root; 176 176 } else { // "to" list not empty 177 T * toEnd = Back( head( s ) );178 T * fromEnd = Back( head( from ) );177 T * toEnd = Back( &head( s ) ); 178 T * fromEnd = Back( &head( from ) ); 179 179 Back( root ) = fromEnd; 180 Next( fromEnd ) = head( s );180 Next( fromEnd ) = &head( s ); 181 181 Back( from.root ) = toEnd; 182 Next( toEnd ) = head( from );182 Next( toEnd ) = &head( from ); 183 183 } // if 184 184 from.root = 0p; // mark "from" list empty … … 187 187 // Transfer the "from" list up to node "n" to the end of s list; the "from" list becomes the sequence after node "n". 188 188 // 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 );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 ); 192 192 #endif // __CFA_DEBUG__ 193 193 Sequence(T) to; 194 194 to.root = from.root; // start of "to" list 195 from.root = Next( n ); // start of "from" list195 from.root = Next( &n ); // start of "from" list 196 196 if ( to.root == from.root ) { // last node in list ? 197 197 from.root = 0p; // mark "from" list empty 198 198 } 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;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; 203 203 } // if 204 204 transfer( s, to ); … … 211 211 struct SeqIter { 212 212 inline ColIter; 213 // The Sequence must be passed to pred and succ to check for the end of the Sequence and return 0p. Without 214 // passing the sequence, traversing would require its length. Thus the iterator needs a pointer to the sequence 215 // to pass to succ/pred. Both stack and queue just encounter 0p since the lists are not circular. 213 216 Sequence(T) * seq; 214 217 }; … … 223 226 ((ColIter &) si){}; 224 227 seq = &s; 225 curr = head( s ); 226 } // post: elts = null. 227 228 curr = &head( s ); 229 } // post: elts = null. 230 231 void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) { 232 ((ColIter &) si){}; 233 seq = &s; 234 curr = &start; 235 } // post: elts = null. 236 228 237 void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) { 229 238 seq = &s; 230 curr = head( s );239 curr = &head( s ); 231 240 } // post: elts = {e in s}. 232 241 … … 235 244 &tp = Curr( si ); 236 245 T * n = succ( *seq, Curr( si ) ); 237 curr = n == head( *seq ) ? 0p : n;246 curr = n == &head( *seq ) ? 0p : n; 238 247 } else &tp = 0p; 239 248 return &tp != 0p; … … 245 254 struct SeqIterRev { 246 255 inline ColIter; 256 // See above for explanation. 247 257 Sequence(T) * seq; 248 258 }; … … 259 269 curr = &tail( s ); 260 270 } // post: elts = null. 261 271 272 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { 273 ((ColIter &) si){}; 274 seq = &s; 275 curr = &start; 276 } // post: elts = null. 277 262 278 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 263 279 seq = &s; … … 277 293 278 294 // Local Variables: // 279 // compile-command: " make install" //295 // compile-command: "cfa sequence.hfa" // 280 296 // End: // -
libcfa/src/bits/stack.hfa
rab0257b9 r54f89d5 10 10 inline { 11 11 // wrappers to make Collection have T 12 T *head( Stack(T) & s ) with( s ) {13 return (T *)head( (Collection &)s );12 T & head( Stack(T) & s ) with( s ) { 13 return *(T *)head( (Collection &)s ); 14 14 } // post: empty() & head() == 0 | !empty() & head() in *this 15 15 … … 22 22 23 23 T & top( Stack(T) & s ) with( s ) { 24 return *head( s );24 return head( s ); 25 25 } 26 26 … … 29 29 if ( listed( (Colable &)(n) ) ) abort( "(Stack &)%p.addHead( %p ) : Node is already on another list.", &s, n ); 30 30 #endif // __CFA_DEBUG__ 31 Next( &n ) = head( s ) ?head( s ) : &n;31 Next( &n ) = &head( s ) ? &head( s ) : &n; 32 32 root = &n; 33 33 } … … 42 42 43 43 T & drop( Stack(T) & s ) with( s ) { 44 T & t = *head( s );44 T & t = head( s ); 45 45 if ( root ) { 46 46 root = ( T *)Next(root); 47 if ( head( s ) == &t ) root = 0p; // only one element ?47 if ( &head( s ) == &t ) root = 0p; // only one element ? 48 48 Next( &t ) = 0p; 49 49 } // if … … 70 70 // create an iterator active in Stack s 71 71 void ?{}( StackIter(T) & si, Stack(T) & s ) with( si ) { 72 curr = head( s );72 curr = &head( s ); 73 73 } // post: curr = {e in s} 74 74 … … 79 79 // make existing iterator active in Stack q 80 80 void over( StackIter(T) & si, Stack(T) & s ) with( si ) { 81 curr = head( s );81 curr = &head( s ); 82 82 } // post: curr = {e in s} 83 83
Note:
See TracChangeset
for help on using the changeset viewer.
