Changeset 2b4daf2 for libcfa/src/bits
- Timestamp:
- Jan 7, 2021, 5:06:22 PM (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:
- 5ad381b
- Parents:
- 42f6e07 (diff), 58fe85a (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:
-
- 7 edited
-
collection.hfa (modified) (5 diffs)
-
containers.hfa (modified) (1 diff)
-
defs.hfa (modified) (1 diff)
-
locks.hfa (modified) (3 diffs)
-
queue.hfa (modified) (11 diffs)
-
sequence.hfa (modified) (16 diffs)
-
stack.hfa (modified) (7 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/bits/collection.hfa
r42f6e07 r2b4daf2 1 1 #pragma once 2 #include <stdio.h> // REMOVE THIS AFTER DEBUGGING 3 2 4 3 5 struct Colable { 4 Colable * next; // next node in the list6 struct Colable * next; // next node in the list 5 7 // invariant: (next != 0) <=> listed() 6 8 }; 7 8 inline {9 #ifdef __cforall 10 static inline { 9 11 // PUBLIC 10 12 … … 28 30 } 29 31 30 // wrappers to make Collection have T 31 forall( dtype T ) { 32 T *& Next( T * n ) { 33 return (T *)Next( (Colable *)n ); 34 } 35 36 bool listed( T * n ) { 37 return Next( (Colable *)n ) != 0p; 38 } 39 } // distribution 32 // // wrappers to make Collection have T 33 // forall( dtype T ) { 34 // T *& Next( T * n ) { 35 // return (T *)Next( (Colable *)n ); 36 // } 37 // } // distribution 40 38 } // distribution 41 39 40 forall( dtype T | { T *& Next ( T * ); } ) { 41 bool listed( T * n ) { 42 return Next( n ) != 0p; 43 } 44 } 42 45 43 46 struct Collection { … … 45 48 }; 46 49 47 inline {50 static inline { 48 51 // class invariant: root == 0 & empty() | *root in *this 49 52 void ?{}( Collection &, const Collection & ) = void; // no copy … … 65 68 66 69 struct ColIter { 67 void * curr; // element to be returned by >>70 void * curr; // element returned by | 68 71 }; 69 72 70 inline {73 static inline { 71 74 void ?{}( ColIter & colIter ) with( colIter ) { 72 75 curr = 0p; … … 79 82 } // distribution 80 83 } // distribution 84 #endif -
libcfa/src/bits/containers.hfa
r42f6e07 r2b4daf2 36 36 #define __small_array_t(T) __small_array(T) 37 37 #else 38 #define __small_array_t(T) struct__small_array38 #define __small_array_t(T) __small_array 39 39 #endif 40 40 -
libcfa/src/bits/defs.hfa
r42f6e07 r2b4daf2 29 29 #define __cfa_anonymous_object(x) inline struct x 30 30 #else 31 #define __cfa_anonymous_object(x) x __cfa_anonymous_object31 #define __cfa_anonymous_object(x) struct x __cfa_anonymous_object 32 32 #endif 33 33 -
libcfa/src/bits/locks.hfa
r42f6e07 r2b4daf2 283 283 void ^?{}(future_t &) {} 284 284 285 void reset(future_t & this) { 286 // needs to be in 0p or 1p 287 __atomic_exchange_n( &this.ptr, 0p, __ATOMIC_SEQ_CST); 288 } 289 285 290 // check if the future is available 286 291 bool available( future_t & this ) { … … 340 345 341 346 // Mark the future as abandoned, meaning it will be deleted by the server 342 void abandon( future_t & this ) { 347 bool abandon( future_t & this ) { 348 /* paranoid */ verify( this.ptr != 3p ); 349 350 // Mark the future as abandonned 343 351 struct oneshot * got = __atomic_exchange_n( &this.ptr, 3p, __ATOMIC_SEQ_CST); 352 353 // If the future isn't already fulfilled, let the server delete it 354 if( got == 0p ) return false; 344 355 345 356 // got == 2p: the future is ready but the context hasn't fully been consumed … … 347 358 if( got == 2p ) { 348 359 while( this.ptr != 1p ) Pause(); 349 } 350 return; 360 got = 1p; 361 } 362 363 // The future is completed delete it now 364 /* paranoid */ verify( this.ptr != 1p ); 365 free( &this ); 366 return true; 351 367 } 352 368 -
libcfa/src/bits/queue.hfa
r42f6e07 r2b4daf2 3 3 #include "bits/collection.hfa" 4 4 5 forall( dtype T ) { 5 // A Queue(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the same order from those 6 // added by add(). T must be a public descendant of uColable. 7 8 // The implementation is a typical singly-linked list, except the next field of the last element points to itself 9 // instead of being null. 10 11 forall( dtype T | { T *& Next ( T * ); } ) { 6 12 struct Queue { 7 13 inline Collection; // Plan 9 inheritance … … 34 40 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *q 35 41 36 voidaddHead( Queue(T) & q, T & n ) with( q ) {42 T & addHead( Queue(T) & q, T & n ) with( q ) { 37 43 #ifdef __CFA_DEBUG__ 38 44 if ( listed( &n ) ) abort( "(Queue &)%p.addHead( %p ) : Node is already on another list.", &q, &n ); … … 45 51 Next( &n ) = &n; // last node points to itself 46 52 } 53 return n; 47 54 } 48 55 49 voidaddTail( Queue(T) & q, T & n ) with( q ) {56 T & addTail( Queue(T) & q, T & n ) with( q ) { 50 57 #ifdef __CFA_DEBUG__ 51 58 if ( listed( &n ) ) abort( "(Queue &)%p.addTail( %p ) : Node is already on another list.", &q, &n ); … … 55 62 last = &n; 56 63 Next( &n ) = &n; // last node points to itself 64 return n; 57 65 } 58 66 59 voidadd( Queue(T) & q, T & n ) with( q ) {60 addTail( q, n );67 T & add( Queue(T) & q, T & n ) with( q ) { 68 return addTail( q, n ); 61 69 } 62 70 … … 64 72 T & t = head( q ); 65 73 if ( root ) { 66 root = Next( root );74 root = Next( (T *)root ); 67 75 if ( &head( q ) == &t ) { 68 76 root = last = 0p; // only one element … … 77 85 } 78 86 79 voidremove( Queue(T) & q, T & n ) with( q ) { // O(n)87 T & remove( Queue(T) & q, T & n ) with( q ) { // O(n) 80 88 #ifdef __CFA_DEBUG__ 81 89 if ( ! listed( (Colable &)n ) ) abort( "(Queue &)%p.remove( %p ) : Node is not on a list.", &q, &n ); … … 103 111 curr = Next( curr ); 104 112 } 113 return n; 105 114 } // post: ! listed( n ) 106 115 107 T & dropTail( Queue(T) & q ) with( q ) { 116 T & dropTail( Queue(T) & q ) with( q ) { // O(n) 108 117 T & n = tail( q ); 109 118 return &n ? remove( q, n ), n : *0p; … … 142 151 } // distribution 143 152 144 forall( dtype T ) {153 forall( dtype T | { T *& Next ( T * ); } ) { 145 154 struct QueueIter { 146 155 inline ColIter; // Plan 9 inheritance … … 152 161 } // post: curr == 0p 153 162 154 // create an iterator active in Queue q163 // create an iterator active in queue q 155 164 void ?{}( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 156 165 curr = &head( q ); … … 161 170 } // post: curr = {e in q} 162 171 163 // make existing iterator active in Queue q172 // make existing iterator active in queue q 164 173 void over( QueueIter(T) & qi, Queue(T) & q ) with( qi ) { 165 174 curr = &head( q ); 166 175 } // post: curr = {e in q} 167 176 168 bool ? >>?( QueueIter(T) & qi, T && tp ) with( qi ) {177 bool ?|?( QueueIter(T) & qi, T && tp ) with( qi ) { 169 178 if ( curr ) { 170 179 &tp = Curr( qi ); … … 174 183 return &tp != 0p; 175 184 } 176 // post: elts == null & !operator >>(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator>>(tp)185 // post: elts == null & !operator|(tp) | elts != null & *tp' in elts & elts' == elts - *tp & operator|(tp) 177 186 } // distribution 178 187 } // distribution -
libcfa/src/bits/sequence.hfa
r42f6e07 r2b4daf2 2 2 3 3 #include "bits/collection.hfa" 4 #include "bits/defs.hfa" 4 5 5 6 struct Seqable { 6 inline Colable;7 Seqable * back; // pointer to previous node in the list7 __cfa_anonymous_object(Colable); 8 struct Seqable * back; // pointer to previous node in the list 8 9 }; 9 10 10 inline { 11 #ifdef __cforall 12 static inline { 11 13 // PUBLIC 12 14 … … 26 28 } 27 29 28 // wrappers to make Collection have T29 forall( dtype T ) {30 T *& Back( T * n ) {31 return (T *)Back( (Seqable *)n );32 }33 } // distribution30 // // wrappers to make Collection have T 31 // forall( dtype T ) { 32 // T *& Back( T * n ) { 33 // return (T *)Back( (Seqable *)n ); 34 // } 35 // } // distribution 34 36 } // distribution 35 37 36 forall( dtype T ) { 38 39 // A Sequence(T) is a Collection(T) defining the ordering of a uStack and uQueue, and to insert and remove elements 40 // anywhere in the sequence. T must be a public descendant of uSeqable. 41 42 // The implementation is a typical doubly-linked list, except the next field of the last node points at the first node 43 // and the back field of the last node points at the first node (circular). 44 45 forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) { 37 46 struct Sequence { 38 47 inline Collection; // Plan 9 inheritance 39 48 }; 40 49 41 inline {50 static inline { 42 51 // wrappers to make Collection have T 43 52 T & head( Sequence(T) & s ) with( s ) { … … 50 59 void ?{}( Sequence(T) & s ) with( s ) { 51 60 ((Collection &)s){}; 52 } // post: isEmpty() .53 54 // Return a pointer to the last sequence element, without removing it. 61 } // post: isEmpty() 62 63 // Return a pointer to the last sequence element, without removing it. 55 64 T & tail( Sequence(T) & s ) with( s ) { 56 65 return root ? (T &)*Back( &head( s ) ) : *0p; … … 65 74 } // post: n == tail() & succ(n) == 0 | n != tail() & *succ(n) in *s 66 75 67 // Return a pointer to the element before *n, or 0p if there isn't one.76 // Return a pointer to the element before *n, or 0p if list empty. 68 77 T * pred( Sequence(T) & s, T * n ) with( s ) { // pre: *n in *s 69 78 #ifdef __CFA_DEBUG__ … … 71 80 #endif // __CFA_DEBUG__ 72 81 return n == &head( s ) ? 0p : Back( n ); 73 } 74 75 76 // Insert *n into the sequence before *bef, or at the end if bef == 0 .77 voidinsertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s82 } // post: n == head() & head(n) == 0 | n != head() & *pred(n) in *s 83 84 85 // Insert *n into the sequence before *bef, or at the end if bef == 0p. 86 T & insertBef( Sequence(T) & s, T & n, T & bef ) with( s ) { // pre: !n->listed() & *bef in *s 78 87 #ifdef __CFA_DEBUG__ 79 88 if ( listed( &n ) ) abort( "(Sequence &)%p.insertBef( %p, %p ) : Node is already on another list.", &s, n, &bef ); … … 103 112 Next( Back( &n ) ) = &n; 104 113 } // if 114 return n; 105 115 } // post: n->listed() & *n in *s & succ(n) == bef 106 116 107 117 108 118 // Insert *n into the sequence after *aft, or at the beginning if aft == 0. 109 voidinsertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s119 T & insertAft( Sequence(T) & s, T & aft, T & n ) with( s ) { // pre: !n->listed() & *aft in *s 110 120 #ifdef __CFA_DEBUG__ 111 121 if ( listed( &n ) ) abort( "(Sequence &)%p.insertAft( %p, %p ) : Node is already on another list.", &s, &aft, &n ); … … 133 143 Next( &aft ) = &n; 134 144 } // if 135 } // post: n->listed() & *n in *s & succ(n) == bef 145 return n; 146 } // post: n->listed() & *n in *s & succ(n) == bef 136 147 137 148 // pre: n->listed() & *n in *s 138 voidremove( Sequence(T) & s, T & n ) with( s ) { // O(1)149 T & remove( Sequence(T) & s, T & n ) with( s ) { // O(1) 139 150 #ifdef __CFA_DEBUG__ 140 151 if ( ! listed( &n ) ) abort( "(Sequence &)%p.remove( %p ) : Node is not on a list.", &s, &n ); … … 147 158 Next( Back( &n ) ) = Next( &n ); 148 159 Next( &n ) = Back( &n ) = 0p; 149 } // post: !n->listed(). 160 return n; 161 } // post: !n->listed() 150 162 151 163 // Add an element to the head of the sequence. 152 void addHead( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 153 insertAft( s, *0p, n ); 154 } 164 T & addHead( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 165 return insertAft( s, *0p, n ); 166 } 167 155 168 // Add an element to the tail of the sequence. 156 void addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 157 insertBef( s, n, *0p ); 158 } 169 T & addTail( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 170 return insertBef( s, n, *0p ); 171 } 172 159 173 // Add an element to the tail of the sequence. 160 void add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 161 addTail( s, n ); 162 } 174 T & add( Sequence(T) & s, T & n ) { // pre: !n->listed(); post: n->listed() & head() == n 175 return addTail( s, n ); 176 } 177 163 178 // Remove and return the head element in the sequence. 164 179 T & dropHead( Sequence(T) & s ) { … … 166 181 return &n ? remove( s, n ), n : *0p; 167 182 } 183 168 184 // Remove and return the head element in the sequence. 169 185 T & drop( Sequence(T) & s ) { 170 186 return dropHead( s ); 171 187 } 188 172 189 // Remove and return the tail element in the sequence. 173 190 T & dropTail( Sequence(T) & s ) { … … 184 201 T * toEnd = Back( &head( s ) ); 185 202 T * fromEnd = Back( &head( from ) ); 186 Back( root ) = fromEnd;203 Back( (T *)root ) = fromEnd; 187 204 Next( fromEnd ) = &head( s ); 188 Back( from.root ) = toEnd;205 Back( (T *)from.root ) = toEnd; 189 206 Next( toEnd ) = &head( from ); 190 207 } // if … … 214 231 } // distribution 215 232 216 forall( dtype T ) {233 forall( dtype T | { T *& Back ( T * ); T *& Next ( T * ); } ) { 217 234 // SeqIter(T) is used to iterate over a Sequence(T) in head-to-tail order. 218 235 struct SeqIter { … … 224 241 }; 225 242 226 inline {243 static inline { 227 244 void ?{}( SeqIter(T) & si ) with( si ) { 228 245 ((ColIter &)si){}; 229 246 seq = 0p; 230 } // post: elts = null. 231 247 } // post: elts = null 248 249 // Create a iterator active in sequence s. 232 250 void ?{}( SeqIter(T) & si, Sequence(T) & s ) with( si ) { 233 251 ((ColIter &)si){}; 234 252 seq = &s; 235 253 curr = &head( s ); 236 } // post: elts = null .254 } // post: elts = null 237 255 238 256 void ?{}( SeqIter(T) & si, Sequence(T) & s, T & start ) with( si ) { … … 240 258 seq = &s; 241 259 curr = &start; 242 } // post: elts = null. 243 260 } // post: elts = null 261 262 // Make the iterator active in sequence s. 244 263 void over( SeqIter(T) & si, Sequence(T) & s ) with( si ) { 245 264 seq = &s; 246 265 curr = &head( s ); 247 } // post: elts = {e in s} .248 249 bool ? >>?( SeqIter(T) & si, T && tp ) with( si ) {266 } // post: elts = {e in s} 267 268 bool ?|?( SeqIter(T) & si, T && tp ) with( si ) { 250 269 if ( curr ) { 251 270 &tp = Curr( si ); … … 265 284 }; 266 285 267 inline {286 static inline { 268 287 void ?{}( SeqIterRev(T) & si ) with( si ) { 269 288 ((ColIter &)si){}; 270 289 seq = 0p; 271 } // post: elts = null. 272 290 } // post: elts = null 291 292 // Create a iterator active in sequence s. 273 293 void ?{}( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 274 294 ((ColIter &)si){}; 275 295 seq = &s; 276 296 curr = &tail( s ); 277 } // post: elts = null .297 } // post: elts = null 278 298 279 299 void ?{}( SeqIterRev(T) & si, Sequence(T) & s, T & start ) with( si ) { … … 281 301 seq = &s; 282 302 curr = &start; 283 } // post: elts = null. 284 303 } // post: elts = null 304 305 // Make the iterator active in sequence s. 285 306 void over( SeqIterRev(T) & si, Sequence(T) & s ) with( si ) { 286 307 seq = &s; 287 308 curr = &tail( s ); 288 } // post: elts = {e in s} .289 290 bool ? >>?( SeqIterRev(T) & si, T && tp ) with( si ) {309 } // post: elts = {e in s} 310 311 bool ?|?( SeqIterRev(T) & si, T && tp ) with( si ) { 291 312 if ( curr ) { 292 313 &tp = Curr( si ); … … 298 319 } // distribution 299 320 } // distribution 321 322 #endif -
libcfa/src/bits/stack.hfa
r42f6e07 r2b4daf2 3 3 #include "bits/collection.hfa" 4 4 5 forall( dtype T ) { 5 // A Stack(T) is a Collection(T) defining the ordering that nodes are returned by drop() in the reverse order from those 6 // added by add(). T must be a public descendant of uColable. 7 8 // The implementation is a typical singly-linked list, except the next field of the last element points to itself 9 // instead of being null. 10 11 forall( dtype T | { T *& Next ( T * ); } ) { 6 12 struct Stack { 7 13 inline Collection; // Plan 9 inheritance … … 25 31 } 26 32 27 voidaddHead( Stack(T) & s, T & n ) with( s ) {33 T & addHead( Stack(T) & s, T & n ) with( s ) { 28 34 #ifdef __CFA_DEBUG__ 29 35 if ( listed( (Colable &)(n) ) ) abort( "(Stack &)%p.addHead( %p ) : Node is already on another list.", &s, n ); … … 31 37 Next( &n ) = &head( s ) ? &head( s ) : &n; 32 38 root = &n; 39 return n; 33 40 } 34 41 35 voidadd( Stack(T) & s, T & n ) with( s ) {36 addHead( s, n );42 T & add( Stack(T) & s, T & n ) with( s ) { 43 return addHead( s, n ); 37 44 } 38 45 39 voidpush( Stack(T) & s, T & n ) with( s ) {40 addHead( s, n );46 T & push( Stack(T) & s, T & n ) with( s ) { 47 return addHead( s, n ); 41 48 } 42 49 … … 44 51 T & t = head( s ); 45 52 if ( root ) { 46 root = ( T *)Next( root );53 root = ( T *)Next( (T *)root ); 47 54 if ( &head( s ) == &t ) root = 0p; // only one element ? 48 55 Next( &t ) = 0p; … … 57 64 } // distribution 58 65 66 // A StackIter(T) is a subclass of ColIter(T) that generates the elements of a Stack(T). It returns the elements in the 67 // order returned by drop(). 59 68 60 forall( dtype T ) {69 forall( dtype T | { T *& Next ( T * ); } ) { 61 70 struct StackIter { 62 71 inline ColIter; // Plan 9 inheritance … … 68 77 } // post: curr == 0p 69 78 70 // create an iterator active in Stack s79 // create an iterator active in stack s 71 80 void ?{}( StackIter(T) & si, Stack(T) & s ) with( si ) { 72 81 curr = &head( s ); … … 77 86 } // post: curr = {e in s} 78 87 79 // make existing iterator active in Stack q88 // make existing iterator active in stack s 80 89 void over( StackIter(T) & si, Stack(T) & s ) with( si ) { 81 90 curr = &head( s ); 82 91 } // post: curr = {e in s} 83 92 84 bool ? >>?( StackIter(T) & si, T && tp ) with( si ) {93 bool ?|?( StackIter(T) & si, T && tp ) with( si ) { 85 94 if ( curr ) { 86 95 &tp = Curr( si );
Note:
See TracChangeset
for help on using the changeset viewer.
