Index: libcfa/src/collections/list.hfa =================================================================== --- libcfa/src/collections/list.hfa (revision 65b0402655546e1fea596afe650e9a1b34129bd8) +++ libcfa/src/collections/list.hfa (revision 6b33e891da6ed781bdcec69c5dfdd3cb8a9d0e44) @@ -10,6 +10,6 @@ // Created On : Wed Apr 22 18:00:00 2020 // Last Modified By : Peter A. Buhr -// Last Modified On : Sun Apr 20 19:04:50 2025 -// Update Count : 51 +// Last Modified On : Thu Apr 24 18:12:59 2025 +// Update Count : 72 // @@ -72,6 +72,6 @@ // The origin is the position encountered at the start of iteration, signifying, "need to advance to the first element," -// and at the end of iteration, signifying, "no more elements." Normal comsumption of an iterator runs ?`moveNext as -// the first step, and uses the return of ?`moveNext as a guard, before dereferencing the iterator. So normal +// and at the end of iteration, signifying, "no more elements." Normal comsumption of an iterator runs "advance" as +// the first step, and uses the return of "advance" as a guard, before dereferencing the iterator. So normal // consumption of an iterator does not dereference an iterator in origin position. The value of a pointer (underlying a // refence) that is exposed publicly as an iteraor, and also a pointer stored internally in a link field, is tagged, to @@ -128,4 +128,28 @@ static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) { + bool isListed( tE & node ) { + verify( &node != 0p ); + dlink( tE ) & node_links = node`inner; + return (node_links.prev != 0p) || (node_links.next != 0p); + } + + bool isEmpty( dlist( tE, tLinks ) & list ) { + tE * firstPtr = list.next; + if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p; + return firstPtr == 0p; + } + + tE & first( dlist( tE, tLinks ) & list ) { + tE * firstPtr = list.next; + if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p; + return *firstPtr; + } + + tE & last( dlist( tE, tLinks ) & list ) { + tE * lastPtr = list.prev; + if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p; + return *lastPtr; + } + tE & insert_before( tE & before, tE & node ) { verify( &before != 0p ); @@ -194,37 +218,17 @@ } - tE & ?`first( dlist( tE, tLinks ) & list ) { - tE * firstPtr = list.next; - if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p; - return *firstPtr; - } - - tE & ?`last( dlist( tE, tLinks ) & list ) { - tE * lastPtr = list.prev; - if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p; - return *lastPtr; - } - - bool ?`isEmpty( dlist( tE, tLinks ) & list ) { - tE * firstPtr = list.next; - if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p; - return firstPtr == 0p; - } - - bool ?`isListed( tE & node ) { - verify( &node != 0p ); - dlink( tE ) & node_links = node`inner; - return (node_links.prev != 0p) || (node_links.next != 0p); - } - - tE & ?`elems( dlist( tE, tLinks ) & list ) { + tE & iter( dlist( tE, tLinks ) & list ) { tE * origin = $get_list_origin_addr( list ); return *origin; } - tE & ?`head( dlist( tE, tLinks ) & list ) { - return list`elems; - } - - bool ?`moveNext( tE && refx ) { + + bool recede( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); + &ref_inner = oldReferent`inner.prev; + return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); + } + + bool advance( tE && refx ) { tE && ref_inner = refx; tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); @@ -232,46 +236,33 @@ return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); } - bool ?`next( tE && refx ) { // alternate name - return refx`moveNext; - } - - bool ?`movePrev( tE && refx ) { - tE && ref_inner = refx; - tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); - &ref_inner = oldReferent`inner.prev; - return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); - } - bool ?`prev( tE && refx ) { // alternate name - return refx`movePrev; - } - - bool ?`hasNext( tE & node ) { - return node`moveNext; - } - - bool ?`hasPrev( tE & node ) { - return node`movePrev; - } - - tE & ?`next( tE & node ) { - if ( node`moveNext ) return node; + + bool isFirst( tE & node ) { + return recede( node ); + } + + bool isLast( tE & node ) { + return advance( node ); + } + + tE & prev( tE & node ) { + if ( recede( node ) ) return node; return *0p; } - tE & ?`prev( tE & node ) { - if ( node`movePrev ) return node; + tE & next( tE & node ) { + if ( advance( node ) ) return node; return *0p; } tE & insert_first( dlist( tE, tLinks ) & list, tE & node ) { - insert_after( list`elems, node ); + insert_after( iter( list ), node ); return node; } tE & insert_last( dlist( tE, tLinks ) & list, tE & node ) { - insert_before( list`elems, node ); - return node; - } - tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // alternate name + insert_before( iter( list ), node ); + return node; + } + tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // synonym for insert_last insert_last( list, node ); return node; @@ -279,9 +270,13 @@ tE & remove_first( dlist( tE, tLinks ) & list ) { - return remove( list`first ); + tE & first_node = first( list ); + if ( &first_node ) return remove( first_node ); + return first_node; } tE & remove_last( dlist( tE, tLinks ) & list ) { - return remove( list`last ); + tE & last_node = last( list ); + if ( &last_node ) return remove( last_node ); + return last_node; } @@ -322,47 +317,32 @@ // } - tE & try_pop_front( dlist( tE, tLinks ) & list ) { - tE & first_inlist = list`first; - tE & first_item = first_inlist; - if ( &first_item ) remove( first_inlist ); - return first_item; - } - - tE & try_pop_back( dlist( tE, tLinks ) & list ) { - tE & last_inlist = list`last; - tE & last_item = last_inlist; - if ( &last_item ) remove( last_inlist ); - return last_item; - } - - #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) bool $validate_fwd( dlist( tE, tLinks ) & this ) { - if ( ! & this`first ) return &this`last == 0p; + if ( ! & first( this ) ) return &last( this ) == 0p; tE & lagElem = *0p; - while ( tE & it = this`elems; it`moveNext ) { - if ( & lagElem == 0p && &it != & this`first ) return false; + while ( tE & it = iter( this ); advance( it ) ) { + if ( & lagElem == 0p && &it != & first( this ) ) return false; &lagElem = ⁢ } - if ( &lagElem != &this`last ) return false; - - // TODO: verify that it is back at this`elems; + if ( &lagElem != &last( this ) ) return false; + + // TODO: verify that it is back at iter( this ); return true; } bool $validate_rev( dlist( tE, tLinks ) & this ) { - if ( ! & this`last ) return &this`first == 0p; + if ( ! & last( this ) ) return &first( this ) == 0p; tE & lagElem = *0p; - while ( tE & it = this`elems; it`movePrev ) { - if ( &lagElem == 0p && &it != & this`last ) return false; + while ( tE & it = iter( this ); recede( it ) ) { + if ( &lagElem == 0p && &it != & last( this ) ) return false; &lagElem = ⁢ } - if ( &lagElem != &this`first ) return false; - - // TODO: verify that it is back at this`elems; + if ( &lagElem != &first( this ) ) return false; + + // TODO: verify that it is back at iter( this ); return true; } @@ -375,6 +355,6 @@ // TEMPORARY, until foreach statement created. -#define FOREACH( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next; ) -#define FOREACH_REV( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev; ) -#define FOREACH_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next && !(expr); ) -#define FOREACH_REV_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev && !(expr); ) +#define FOREACH( list, index ) for ( typeof(iter( list )) & (index) = iter( list ); advance( index ); ) +#define FOREACH_REV( list, index ) for ( typeof(iter( list )) & (index) = iter( list ); recede( index ); ) +#define FOREACH_COND( list, index, expr ) for ( typeof(iter( list )) & (index) = iter( list ); advance( index ) && !(expr); ) +#define FOREACH_REV_COND( list, index, expr ) for ( typeof(iter( list )) & (index) = iter( list ); recede( index ) && !(expr); ) Index: libcfa/src/collections/lockfree.hfa =================================================================== --- libcfa/src/collections/lockfree.hfa (revision 65b0402655546e1fea596afe650e9a1b34129bd8) +++ libcfa/src/collections/lockfree.hfa (revision 6b33e891da6ed781bdcec69c5dfdd3cb8a9d0e44) @@ -16,20 +16,19 @@ }; - static inline void ?{}(mcs_queue(T) & this) { this.tail = 0p; } - static inline bool empty(const mcs_queue(T) & this) { return !this.tail; } - - static inline forall(| { T * volatile & ?`next ( T * ); }) - { + static inline void ?{}( mcs_queue(T) & this ) { this.tail = 0p; } + static inline bool empty( const mcs_queue(T) & this ) { return ! this.tail; } + + static inline forall( | { T * volatile & next ( T * ); }) { // Adds an element to the list // Multi-Thread Safe, Lock-Free - T * push(mcs_queue(T) & this, T * elem) __attribute__((artificial)); - T * push(mcs_queue(T) & this, T * elem) { - /* paranoid */ verify(!(elem`next)); + T * push( mcs_queue(T) & this, T * elem ) __attribute__((artificial)); + T * push( mcs_queue(T) & this, T * elem ) { + /* paranoid */ verify( ! next( elem ) ); // Race to add to the tail - T * prev = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); + T * prev_val = __atomic_exchange_n(&this.tail, elem, __ATOMIC_SEQ_CST); // If we aren't the first, we need to tell the person before us // No need to - if (prev) prev`next = elem; - return prev; + if ( prev_val ) next( prev_val ) = elem; + return prev_val; } @@ -37,6 +36,6 @@ // Passing an element that is not the head is undefined behavior // NOT Multi-Thread Safe, concurrent pushes are safe - T * advance(mcs_queue(T) & this, T * elem) __attribute__((artificial)); - T * advance(mcs_queue(T) & this, T * elem) { + T * advance( mcs_queue(T) & this, T * elem ) __attribute__((artificial)); + T * advance( mcs_queue(T) & this, T * elem ) { T * expected = elem; // Check if this is already the last item @@ -44,11 +43,11 @@ // If not wait for next item to show-up, filled by push - while (!(elem`next)) Pause(); + while ( ! next( elem ) ) Pause(); // we need to return if the next link was empty - T * ret = elem`next; + T * ret = next( elem ); // invalidate link to reset to initial state - elem`next = 0p; + next( elem ) = 0p; return ret; } @@ -65,38 +64,37 @@ }; - static inline void ?{}(mpsc_queue(T) & this) { + static inline void ?{}( mpsc_queue(T) & this ) { ((mcs_queue(T)&)this){}; this.head = 0p; } - static inline forall(| { T * volatile & ?`next ( T * ); }) - { + static inline forall( | { T * volatile & next ( T * ); }) { // Added a new element to the queue // Multi-Thread Safe, Lock-Free - T * push(mpsc_queue(T) & this, T * elem) __attribute__((artificial)); - T * push(mpsc_queue(T) & this, T * elem) { - T * prev = push((mcs_queue(T)&)this, elem); - if (!prev) this.head = elem; - return prev; + T * push( mpsc_queue(T) & this, T * elem ) __attribute__((artificial)); + T * push( mpsc_queue(T) & this, T * elem ) { + T * prev_val = push( (mcs_queue(T)&)this, elem ); + if ( ! prev_val ) this.head = elem; + return prev_val; } // Pop an element from the queue // return the element that was removed - // next is set to the new head of the queue + // head is set to the new head of the queue // NOT Multi-Thread Safe - T * pop(mpsc_queue(T) & this, T *& next) __attribute__((artificial)); - T * pop(mpsc_queue(T) & this, T *& next) { + T * pop( mpsc_queue(T) & this, T *& head ) __attribute__((artificial)); + T * pop( mpsc_queue(T) & this, T *& head ) { T * elem = this.head; // If head is empty just return - if (!elem) return 0p; + if ( ! elem ) return 0p; // If there is already someone in the list, then it's easy - if (elem`next) { - this.head = next = elem`next; + if ( next( elem ) ) { + this.head = head = next( elem ); // force memory sync __atomic_thread_fence(__ATOMIC_SEQ_CST); // invalidate link to reset to initial state - elem`next = 0p; + next( elem ) = 0p; } // Otherwise, there might be a race where it only looks but someone is enqueuing @@ -106,12 +104,11 @@ // after that point, it could overwrite the write in push this.head = 0p; - next = advance((mcs_queue(T)&)this, elem); + head = advance( (mcs_queue(T)&)this, elem ); // Only write to the head if there is a next element // it is the only way we can guarantee we are not overwriting // a write made in push - if (next) this.head = next; - } - + if ( head ) this.head = head; + } // return removed element return elem; @@ -119,5 +116,5 @@ // Same as previous function - T * pop(mpsc_queue(T) & this) { + T * pop( mpsc_queue(T) & this ) { T * _ = 0p; return pop(this, _); @@ -144,12 +141,12 @@ static inline bool is_poisoned( const poison_list(T) & this ) { return 1p == this.head; } - static inline forall(| { T * volatile & ?`next ( T * ); }) + static inline forall( | { T * volatile & next( T * ); }) { // Adds an element to the list // Multi-Thread Safe, Lock-Free - bool push(poison_list(T) & this, T * elem) __attribute__((artificial)); - bool push(poison_list(T) & this, T * elem) { - /* paranoid */ verify(0p == (elem`next)); - __atomic_store_n( &elem`next, (T*)1p, __ATOMIC_RELAXED ); + bool push( poison_list(T) & this, T * elem ) __attribute__((artificial)); + bool push( poison_list(T) & this, T * elem ) { + /* paranoid */ verify( 0p == next( elem ) ); + __atomic_store_n( &next( elem ), (T *)1p, __ATOMIC_RELAXED ); // read the head up-front @@ -164,10 +161,10 @@ // We should never succeed the CAS if it's poisonned and the elem should be 1p. - /* paranoid */ verify( expected != 1p ); - /* paranoid */ verify( elem`next == 1p ); + /* paranoid */ verify( expected != 1p ); + /* paranoid */ verify( next( elem ) == 1p ); // If we aren't the first, we need to tell the person before us // No need to - elem`next = expected; + next( elem ) = expected; return true; } @@ -178,10 +175,10 @@ // Passing an element that is not the head is undefined behavior // NOT Multi-Thread Safe, concurrent pushes are safe - T * advance(T * elem) __attribute__((artificial)); - T * advance(T * elem) { + T * advance( T * elem ) __attribute__((artificial)); + T * advance( T * elem ) { T * ret; // Wait for next item to show-up, filled by push - while (1p == (ret = __atomic_load_n(&elem`next, __ATOMIC_RELAXED))) Pause(); + while (1p == (ret = __atomic_load_n( &next( elem ), __ATOMIC_RELAXED ) ) ) Pause(); return ret; @@ -189,6 +186,6 @@ // Poison the queue, preveting new pushes and returning the head - T * poison(poison_list(T) & this) __attribute__((artificial)); - T * poison(poison_list(T) & this) { + T * poison( poison_list(T) & this ) __attribute__((artificial)); + T * poison( poison_list(T) & this ) { T * ret = __atomic_exchange_n( &this.head, (T*)1p, __ATOMIC_SEQ_CST ); /* paranoid */ verifyf( ret != (T*)1p, "Poison list %p poisoned more than once!", &this ); @@ -215,5 +212,5 @@ }; // Link -forall( T /*| sized(T)*/ | { Link(T) * ?`next( T * ); } ) { +forall( T /*| sized(T)*/ | { Link(T) * next( T * ); } ) { struct StackLF { Link(T) stack; @@ -226,7 +223,7 @@ void push( StackLF(T) & this, T & n ) with(this) { - *( &n )`next = stack; // atomic assignment unnecessary, or use CAA + *next( &n ) = stack; // atomic assignment unnecessary, or use CAA for () { // busy wait - 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 node + 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 } // for } // push @@ -236,5 +233,5 @@ for () { // busy wait if ( t.data.top == 0p ) return 0p; // empty stack ? - Link(T) * next = ( t.data.top )`next; + Link(T) * next = next( t.data.top ); 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 } // for @@ -246,11 +243,11 @@ // TODO: Avoiding some problems with double fields access. LinkData(T) * data = &link->data; - T * next = (T *)&(*data).top; - if ( next == node ) { - data->top = ( node )`next->data.top; + T * ntop = (T *)&(*data).top; + if ( ntop == node ) { + data->top = next( node )->data.top; return true; } - if ( next == 0p ) return false; - link = ( next )`next; + if ( ntop == 0p ) return false; + link = next( ntop ); } } Index: libcfa/src/collections/vector2.hfa =================================================================== --- libcfa/src/collections/vector2.hfa (revision 65b0402655546e1fea596afe650e9a1b34129bd8) +++ libcfa/src/collections/vector2.hfa (revision 6b33e891da6ed781bdcec69c5dfdd3cb8a9d0e44) @@ -10,6 +10,6 @@ // Created On : Thu Jun 23 22:00:00 2021 // Last Modified By : Peter A. Buhr -// Last Modified On : Tue Mar 14 08:40:53 2023 -// Update Count : 2 +// Last Modified On : Wed Apr 23 14:39:51 2025 +// Update Count : 6 // @@ -254,5 +254,5 @@ } - while ( vector_permit(T) & liveIter = this.live_iters_$`elems; liveIter`moveNext ) { + while ( vector_permit(T) & liveIter = iter( this.live_iters_$ ); advance( liveIter ) ) { liveIter.item_$ += (newItems - this.buffer_first_$); } @@ -350,5 +350,5 @@ *insertTarget = val; - while ( vector_permit(T) & liveIter = col.live_iters_$`elems; liveIter`moveNext ) { + while ( vector_permit(T) & liveIter = iter( col.live_iters_$ ); advance( liveIter ) ) { if ( inRange_$(liveIter.item_$, insertTarget, col.elems_end_$) ) { liveIter.item_$ += 1;