Changeset 6b33e89 for libcfa/src/collections
- Timestamp:
- Apr 25, 2025, 7:39:09 AM (6 months ago)
- Branches:
- master
- Children:
- 65bd3c2
- Parents:
- b195498
- Location:
- libcfa/src/collections
- Files:
-
- 3 edited
-
list.hfa (modified) (8 diffs)
-
lockfree.hfa (modified) (14 diffs)
-
vector2.hfa (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
libcfa/src/collections/list.hfa
rb195498 r6b33e89 10 10 // Created On : Wed Apr 22 18:00:00 2020 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Sun Apr 20 19:04:50202513 // Update Count : 5112 // Last Modified On : Thu Apr 24 18:12:59 2025 13 // Update Count : 72 14 14 // 15 15 … … 72 72 73 73 // The origin is the position encountered at the start of iteration, signifying, "need to advance to the first element," 74 // and at the end of iteration, signifying, "no more elements." Normal comsumption of an iterator runs ?`moveNextas75 // the first step, and uses the return of ?`moveNextas a guard, before dereferencing the iterator. So normal74 // and at the end of iteration, signifying, "no more elements." Normal comsumption of an iterator runs "advance" as 75 // the first step, and uses the return of "advance" as a guard, before dereferencing the iterator. So normal 76 76 // consumption of an iterator does not dereference an iterator in origin position. The value of a pointer (underlying a 77 77 // refence) that is exposed publicly as an iteraor, and also a pointer stored internally in a link field, is tagged, to … … 128 128 129 129 static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) { 130 bool isListed( tE & node ) { 131 verify( &node != 0p ); 132 dlink( tE ) & node_links = node`inner; 133 return (node_links.prev != 0p) || (node_links.next != 0p); 134 } 135 136 bool isEmpty( dlist( tE, tLinks ) & list ) { 137 tE * firstPtr = list.next; 138 if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p; 139 return firstPtr == 0p; 140 } 141 142 tE & first( dlist( tE, tLinks ) & list ) { 143 tE * firstPtr = list.next; 144 if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p; 145 return *firstPtr; 146 } 147 148 tE & last( dlist( tE, tLinks ) & list ) { 149 tE * lastPtr = list.prev; 150 if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p; 151 return *lastPtr; 152 } 153 130 154 tE & insert_before( tE & before, tE & node ) { 131 155 verify( &before != 0p ); … … 194 218 } 195 219 196 tE & ?`first( dlist( tE, tLinks ) & list ) { 197 tE * firstPtr = list.next; 198 if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p; 199 return *firstPtr; 200 } 201 202 tE & ?`last( dlist( tE, tLinks ) & list ) { 203 tE * lastPtr = list.prev; 204 if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p; 205 return *lastPtr; 206 } 207 208 bool ?`isEmpty( dlist( tE, tLinks ) & list ) { 209 tE * firstPtr = list.next; 210 if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p; 211 return firstPtr == 0p; 212 } 213 214 bool ?`isListed( tE & node ) { 215 verify( &node != 0p ); 216 dlink( tE ) & node_links = node`inner; 217 return (node_links.prev != 0p) || (node_links.next != 0p); 218 } 219 220 tE & ?`elems( dlist( tE, tLinks ) & list ) { 220 tE & iter( dlist( tE, tLinks ) & list ) { 221 221 tE * origin = $get_list_origin_addr( list ); 222 222 return *origin; 223 223 } 224 tE & ?`head( dlist( tE, tLinks ) & list ) { 225 return list`elems; 226 } 227 228 bool ?`moveNext( tE && refx ) { 224 225 bool recede( tE && refx ) { 226 tE && ref_inner = refx; 227 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); 228 &ref_inner = oldReferent`inner.prev; 229 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); 230 } 231 232 bool advance( tE && refx ) { 229 233 tE && ref_inner = refx; 230 234 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); … … 232 236 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); 233 237 } 234 bool ?`next( tE && refx ) { // alternate name 235 return refx`moveNext; 236 } 237 238 bool ?`movePrev( tE && refx ) { 239 tE && ref_inner = refx; 240 tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); 241 &ref_inner = oldReferent`inner.prev; 242 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); 243 } 244 bool ?`prev( tE && refx ) { // alternate name 245 return refx`movePrev; 246 } 247 248 bool ?`hasNext( tE & node ) { 249 return node`moveNext; 250 } 251 252 bool ?`hasPrev( tE & node ) { 253 return node`movePrev; 254 } 255 256 tE & ?`next( tE & node ) { 257 if ( node`moveNext ) return node; 238 239 bool isFirst( tE & node ) { 240 return recede( node ); 241 } 242 243 bool isLast( tE & node ) { 244 return advance( node ); 245 } 246 247 tE & prev( tE & node ) { 248 if ( recede( node ) ) return node; 258 249 return *0p; 259 250 } 260 251 261 tE & ?`prev( tE & node ) {262 if ( node`movePrev) return node;252 tE & next( tE & node ) { 253 if ( advance( node ) ) return node; 263 254 return *0p; 264 255 } 265 256 266 257 tE & insert_first( dlist( tE, tLinks ) & list, tE & node ) { 267 insert_after( list`elems, node );258 insert_after( iter( list ), node ); 268 259 return node; 269 260 } 270 261 271 262 tE & insert_last( dlist( tE, tLinks ) & list, tE & node ) { 272 insert_before( list`elems, node );273 return node; 274 } 275 tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // alternate name263 insert_before( iter( list ), node ); 264 return node; 265 } 266 tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // synonym for insert_last 276 267 insert_last( list, node ); 277 268 return node; … … 279 270 280 271 tE & remove_first( dlist( tE, tLinks ) & list ) { 281 return remove( list`first ); 272 tE & first_node = first( list ); 273 if ( &first_node ) return remove( first_node ); 274 return first_node; 282 275 } 283 276 284 277 tE & remove_last( dlist( tE, tLinks ) & list ) { 285 return remove( list`last ); 278 tE & last_node = last( list ); 279 if ( &last_node ) return remove( last_node ); 280 return last_node; 286 281 } 287 282 … … 322 317 // } 323 318 324 tE & try_pop_front( dlist( tE, tLinks ) & list ) {325 tE & first_inlist = list`first;326 tE & first_item = first_inlist;327 if ( &first_item ) remove( first_inlist );328 return first_item;329 }330 331 tE & try_pop_back( dlist( tE, tLinks ) & list ) {332 tE & last_inlist = list`last;333 tE & last_item = last_inlist;334 if ( &last_item ) remove( last_inlist );335 return last_item;336 }337 338 339 319 #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) 340 320 bool $validate_fwd( dlist( tE, tLinks ) & this ) { 341 if ( ! & this`first ) return &this`last== 0p;321 if ( ! & first( this ) ) return &last( this ) == 0p; 342 322 343 323 tE & lagElem = *0p; 344 while ( tE & it = this`elems; it`moveNext) {345 if ( & lagElem == 0p && &it != & this`first) return false;324 while ( tE & it = iter( this ); advance( it ) ) { 325 if ( & lagElem == 0p && &it != & first( this ) ) return false; 346 326 &lagElem = ⁢ 347 327 } 348 328 349 if ( &lagElem != & this`last) return false;350 351 // TODO: verify that it is back at this`elems;329 if ( &lagElem != &last( this ) ) return false; 330 331 // TODO: verify that it is back at iter( this ); 352 332 return true; 353 333 } 354 334 355 335 bool $validate_rev( dlist( tE, tLinks ) & this ) { 356 if ( ! & this`last ) return &this`first== 0p;336 if ( ! & last( this ) ) return &first( this ) == 0p; 357 337 358 338 tE & lagElem = *0p; 359 while ( tE & it = this`elems; it`movePrev) {360 if ( &lagElem == 0p && &it != & this`last) return false;339 while ( tE & it = iter( this ); recede( it ) ) { 340 if ( &lagElem == 0p && &it != & last( this ) ) return false; 361 341 &lagElem = ⁢ 362 342 } 363 343 364 if ( &lagElem != & this`first) return false;365 366 // TODO: verify that it is back at this`elems;344 if ( &lagElem != &first( this ) ) return false; 345 346 // TODO: verify that it is back at iter( this ); 367 347 return true; 368 348 } … … 375 355 376 356 // TEMPORARY, until foreach statement created. 377 #define FOREACH( list, index ) for ( typeof( (list)`head) & (index) = (list)`head; (index)`next; )378 #define FOREACH_REV( list, index ) for ( typeof( (list)`head) & (index) = (list)`head; (index)`prev; )379 #define FOREACH_COND( list, index, expr ) for ( typeof( (list)`head) & (index) = (list)`head; (index)`next&& !(expr); )380 #define FOREACH_REV_COND( list, index, expr ) for ( typeof( (list)`head) & (index) = (list)`head; (index)`prev&& !(expr); )357 #define FOREACH( list, index ) for ( typeof(iter( list )) & (index) = iter( list ); advance( index ); ) 358 #define FOREACH_REV( list, index ) for ( typeof(iter( list )) & (index) = iter( list ); recede( index ); ) 359 #define FOREACH_COND( list, index, expr ) for ( typeof(iter( list )) & (index) = iter( list ); advance( index ) && !(expr); ) 360 #define FOREACH_REV_COND( list, index, expr ) for ( typeof(iter( list )) & (index) = iter( list ); recede( index ) && !(expr); ) -
libcfa/src/collections/lockfree.hfa
rb195498 r6b33e89 16 16 }; 17 17 18 static inline void ?{}(mcs_queue(T) & this) { this.tail = 0p; } 19 static inline bool empty(const mcs_queue(T) & this) { return !this.tail; } 20 21 static inline forall(| { T * volatile & ?`next ( T * ); }) 22 { 18 static inline void ?{}( mcs_queue(T) & this ) { this.tail = 0p; } 19 static inline bool empty( const mcs_queue(T) & this ) { return ! this.tail; } 20 21 static inline forall( | { T * volatile & next ( T * ); }) { 23 22 // Adds an element to the list 24 23 // Multi-Thread Safe, Lock-Free 25 T * push( mcs_queue(T) & this, T * elem) __attribute__((artificial));26 T * push( mcs_queue(T) & this, T * elem) {27 /* paranoid */ verify( !(elem`next));24 T * push( mcs_queue(T) & this, T * elem ) __attribute__((artificial)); 25 T * push( mcs_queue(T) & this, T * elem ) { 26 /* paranoid */ verify( ! next( elem ) ); 28 27 // Race to add to the tail 29 T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST);28 T * prev_val = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); 30 29 // If we aren't the first, we need to tell the person before us 31 30 // No need to 32 if ( prev) prev`next= elem;33 return prev ;31 if ( prev_val ) next( prev_val ) = elem; 32 return prev_val; 34 33 } 35 34 … … 37 36 // Passing an element that is not the head is undefined behavior 38 37 // NOT Multi-Thread Safe, concurrent pushes are safe 39 T * advance( mcs_queue(T) & this, T * elem) __attribute__((artificial));40 T * advance( mcs_queue(T) & this, T * elem) {38 T * advance( mcs_queue(T) & this, T * elem ) __attribute__((artificial)); 39 T * advance( mcs_queue(T) & this, T * elem ) { 41 40 T * expected = elem; 42 41 // Check if this is already the last item … … 44 43 45 44 // If not wait for next item to show-up, filled by push 46 while ( !(elem`next)) Pause();45 while ( ! next( elem ) ) Pause(); 47 46 48 47 // we need to return if the next link was empty 49 T * ret = elem`next;48 T * ret = next( elem ); 50 49 51 50 // invalidate link to reset to initial state 52 elem`next= 0p;51 next( elem ) = 0p; 53 52 return ret; 54 53 } … … 65 64 }; 66 65 67 static inline void ?{}( mpsc_queue(T) & this) {66 static inline void ?{}( mpsc_queue(T) & this ) { 68 67 ((mcs_queue(T)&)this){}; 69 68 this.head = 0p; 70 69 } 71 70 72 static inline forall(| { T * volatile & ?`next ( T * ); }) 73 { 71 static inline forall( | { T * volatile & next ( T * ); }) { 74 72 // Added a new element to the queue 75 73 // Multi-Thread Safe, Lock-Free 76 T * push( mpsc_queue(T) & this, T * elem) __attribute__((artificial));77 T * push( mpsc_queue(T) & this, T * elem) {78 T * prev = push((mcs_queue(T)&)this, elem);79 if ( !prev) this.head = elem;80 return prev ;74 T * push( mpsc_queue(T) & this, T * elem ) __attribute__((artificial)); 75 T * push( mpsc_queue(T) & this, T * elem ) { 76 T * prev_val = push( (mcs_queue(T)&)this, elem ); 77 if ( ! prev_val ) this.head = elem; 78 return prev_val; 81 79 } 82 80 83 81 // Pop an element from the queue 84 82 // return the element that was removed 85 // nextis set to the new head of the queue83 // head is set to the new head of the queue 86 84 // NOT Multi-Thread Safe 87 T * pop( mpsc_queue(T) & this, T *& next) __attribute__((artificial));88 T * pop( mpsc_queue(T) & this, T *& next) {85 T * pop( mpsc_queue(T) & this, T *& head ) __attribute__((artificial)); 86 T * pop( mpsc_queue(T) & this, T *& head ) { 89 87 T * elem = this.head; 90 88 // If head is empty just return 91 if ( !elem) return 0p;89 if ( ! elem ) return 0p; 92 90 93 91 // If there is already someone in the list, then it's easy 94 if ( elem`next) {95 this.head = next = elem`next;92 if ( next( elem ) ) { 93 this.head = head = next( elem ); 96 94 // force memory sync 97 95 __atomic_thread_fence(__ATOMIC_SEQ_CST); 98 96 99 97 // invalidate link to reset to initial state 100 elem`next= 0p;98 next( elem ) = 0p; 101 99 } 102 100 // Otherwise, there might be a race where it only looks but someone is enqueuing … … 106 104 // after that point, it could overwrite the write in push 107 105 this.head = 0p; 108 next = advance((mcs_queue(T)&)this, elem);106 head = advance( (mcs_queue(T)&)this, elem ); 109 107 110 108 // Only write to the head if there is a next element 111 109 // it is the only way we can guarantee we are not overwriting 112 110 // a write made in push 113 if (next) this.head = next; 114 } 115 111 if ( head ) this.head = head; 112 } 116 113 // return removed element 117 114 return elem; … … 119 116 120 117 // Same as previous function 121 T * pop( mpsc_queue(T) & this) {118 T * pop( mpsc_queue(T) & this ) { 122 119 T * _ = 0p; 123 120 return pop(this, _); … … 144 141 static inline bool is_poisoned( const poison_list(T) & this ) { return 1p == this.head; } 145 142 146 static inline forall( | { T * volatile & ?`next( T * ); })143 static inline forall( | { T * volatile & next( T * ); }) 147 144 { 148 145 // Adds an element to the list 149 146 // Multi-Thread Safe, Lock-Free 150 bool push( poison_list(T) & this, T * elem) __attribute__((artificial));151 bool push( poison_list(T) & this, T * elem) {152 /* paranoid */ verify( 0p == (elem`next));153 __atomic_store_n( & elem`next, (T*)1p, __ATOMIC_RELAXED );147 bool push( poison_list(T) & this, T * elem ) __attribute__((artificial)); 148 bool push( poison_list(T) & this, T * elem ) { 149 /* paranoid */ verify( 0p == next( elem ) ); 150 __atomic_store_n( &next( elem ), (T *)1p, __ATOMIC_RELAXED ); 154 151 155 152 // read the head up-front … … 164 161 165 162 // We should never succeed the CAS if it's poisonned and the elem should be 1p. 166 /* paranoid */ verify( expected 167 /* paranoid */ verify( elem`next== 1p );163 /* paranoid */ verify( expected != 1p ); 164 /* paranoid */ verify( next( elem ) == 1p ); 168 165 169 166 // If we aren't the first, we need to tell the person before us 170 167 // No need to 171 elem`next= expected;168 next( elem ) = expected; 172 169 return true; 173 170 } … … 178 175 // Passing an element that is not the head is undefined behavior 179 176 // NOT Multi-Thread Safe, concurrent pushes are safe 180 T * advance( T * elem) __attribute__((artificial));181 T * advance( T * elem) {177 T * advance( T * elem ) __attribute__((artificial)); 178 T * advance( T * elem ) { 182 179 T * ret; 183 180 184 181 // Wait for next item to show-up, filled by push 185 while (1p == (ret = __atomic_load_n( &elem`next, __ATOMIC_RELAXED))) Pause();182 while (1p == (ret = __atomic_load_n( &next( elem ), __ATOMIC_RELAXED ) ) ) Pause(); 186 183 187 184 return ret; … … 189 186 190 187 // Poison the queue, preveting new pushes and returning the head 191 T * poison( poison_list(T) & this) __attribute__((artificial));192 T * poison( poison_list(T) & this) {188 T * poison( poison_list(T) & this ) __attribute__((artificial)); 189 T * poison( poison_list(T) & this ) { 193 190 T * ret = __atomic_exchange_n( &this.head, (T*)1p, __ATOMIC_SEQ_CST ); 194 191 /* paranoid */ verifyf( ret != (T*)1p, "Poison list %p poisoned more than once!", &this ); … … 215 212 }; // Link 216 213 217 forall( T /*| sized(T)*/ | { Link(T) * ?`next( T * ); } ) {214 forall( T /*| sized(T)*/ | { Link(T) * next( T * ); } ) { 218 215 struct StackLF { 219 216 Link(T) stack; … … 226 223 227 224 void push( StackLF(T) & this, T & n ) with(this) { 228 * ( &n )`next= stack; // atomic assignment unnecessary, or use CAA225 *next( &n ) = stack; // atomic assignment unnecessary, or use CAA 229 226 for () { // busy wait 230 if ( __atomic_compare_exchange_n( &stack.atom, & ( &n )`next->atom, (Link(T))@{ (LinkData(T))@{ &n, ( &n )`next->data.count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node227 if ( __atomic_compare_exchange_n( &stack.atom, &next( &n )->atom, (Link(T))@{ (LinkData(T))@{ &n, next( &n )->data.count + 1} }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) break; // attempt to update top node 231 228 } // for 232 229 } // push … … 236 233 for () { // busy wait 237 234 if ( t.data.top == 0p ) return 0p; // empty stack ? 238 Link(T) * next = ( t.data.top )`next;235 Link(T) * next = next( t.data.top ); 239 236 if ( __atomic_compare_exchange_n( &stack.atom, &t.atom, (Link(T))@{ (LinkData(T))@{ next->data.top, t.data.count } }.atom, false, __ATOMIC_SEQ_CST, __ATOMIC_SEQ_CST ) ) return t.data.top; // attempt to update top node 240 237 } // for … … 246 243 // TODO: Avoiding some problems with double fields access. 247 244 LinkData(T) * data = &link->data; 248 T * n ext= (T *)&(*data).top;249 if ( n ext== node ) {250 data->top = ( node )`next->data.top;245 T * ntop = (T *)&(*data).top; 246 if ( ntop == node ) { 247 data->top = next( node )->data.top; 251 248 return true; 252 249 } 253 if ( n ext== 0p ) return false;254 link = ( next )`next;250 if ( ntop == 0p ) return false; 251 link = next( ntop ); 255 252 } 256 253 } -
libcfa/src/collections/vector2.hfa
rb195498 r6b33e89 10 10 // Created On : Thu Jun 23 22:00:00 2021 11 11 // Last Modified By : Peter A. Buhr 12 // Last Modified On : Tue Mar 14 08:40:53 202313 // Update Count : 212 // Last Modified On : Wed Apr 23 14:39:51 2025 13 // Update Count : 6 14 14 // 15 15 … … 254 254 } 255 255 256 while ( vector_permit(T) & liveIter = this.live_iters_$`elems; liveIter`moveNext) {256 while ( vector_permit(T) & liveIter = iter( this.live_iters_$ ); advance( liveIter ) ) { 257 257 liveIter.item_$ += (newItems - this.buffer_first_$); 258 258 } … … 350 350 *insertTarget = val; 351 351 352 while ( vector_permit(T) & liveIter = col.live_iters_$`elems; liveIter`moveNext) {352 while ( vector_permit(T) & liveIter = iter( col.live_iters_$ ); advance( liveIter ) ) { 353 353 if ( inRange_$(liveIter.item_$, insertTarget, col.elems_end_$) ) { 354 354 liveIter.item_$ += 1;
Note:
See TracChangeset
for help on using the changeset viewer.
