Index: libcfa/src/collections/list.hfa =================================================================== --- libcfa/src/collections/list.hfa (revision 0eacfd4bdfa495bf0363708f64b2f7ec3f511ca0) +++ libcfa/src/collections/list.hfa (revision 65b0402655546e1fea596afe650e9a1b34129bd8) @@ -10,6 +10,6 @@ // Created On : Wed Apr 22 18:00:00 2020 // Last Modified By : Peter A. Buhr -// Last Modified On : Sat Apr 19 16:24:09 2025 -// Update Count : 27 +// Last Modified On : Sun Apr 20 19:04:50 2025 +// Update Count : 51 // @@ -57,16 +57,16 @@ #define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \ forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \ - STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this ) + STORAGE inline tytagref( immedBase, Tbase ) ?`inner( derived & this ) #define P9_EMBEDDED_BDY_( immedBase ) { \ immedBase & ib = this; \ Tbase & b = ib`inner; \ - tytagref(immedBase, Tbase) result = { b }; \ + tytagref( immedBase, Tbase ) result = { b }; \ return result; \ } -#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } - -#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink(TE) ) +#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref( MID, INNER ) ( * ?`inner ) ( OUTER & ); }){ ?`inner } + +#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink( TE ) ) @@ -91,7 +91,7 @@ #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO) -#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK) -#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK) -#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK) +#define ORIGIN_TAG_SET( p ) ((p) | ORIGIN_TAG_MASK) +#define ORIGIN_TAG_CLEAR( p ) ((p) & ~ORIGIN_TAG_MASK) +#define ORIGIN_TAG_QUERY( p ) ((p) & ORIGIN_TAG_MASK) forall( tE & ) { @@ -101,25 +101,25 @@ }; - static inline void ?{}( dlink(tE) & this ) { + static inline void ?{}( dlink( tE ) & this ) { this.next = this.prev = 0p; } - forall( tLinks & = dlink(tE) ) + forall( tLinks & = dlink( tE ) ) struct dlist { - inline dlink(tE); + inline dlink( tE ); }; - forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) { - dlink(tE) & link_from_null = ( * (tE *) 0p )`inner; - ptrdiff_t link_offset = (ptrdiff_t) & link_from_null; - size_t origin_addr = ((size_t) & lst) - link_offset; + forall( tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) { + static inline tE * $get_list_origin_addr( dlist( tE, tLinks ) & list ) { + dlink( tE ) & link_from_null = (*(tE *)0p)`inner; + ptrdiff_t link_offset = (ptrdiff_t)&link_from_null; + size_t origin_addr = ((size_t)&list) - link_offset; size_t preResult = ORIGIN_TAG_SET( origin_addr ); return (tE *)preResult; } - static inline void ?{}( dlist(tE, tLinks) & this ) { + static inline void ?{}( dlist( tE, tLinks ) & this ) { tE * listOrigin = $get_list_origin_addr( this ); - ((dlink(tE) &)this){ listOrigin, listOrigin }; + ((dlink( tE ) &)this){ listOrigin, listOrigin }; } } @@ -127,63 +127,62 @@ -static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - void insert_after( tE & list_pos, tE & to_insert ) { - verify( &list_pos != 0p ); - verify( &to_insert != 0p ); - - dlink(tE) & linkToInsert = to_insert`inner; +static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) { + tE & insert_before( tE & before, tE & node ) { + verify( &before != 0p ); + verify( &node != 0p ); + + dlink( tE ) & linkToInsert = node`inner; + + verify( linkToInsert.next == 0p ); + verify( linkToInsert.prev == 0p ); + + tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before ); + dlink( tE ) & list_pos_links = list_pos_elem`inner; + asm( "" : : : "memory" ); + tE & before_raw = *list_pos_links.prev; + tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw ); + linkToInsert.next = &before; + linkToInsert.prev = &before_raw; + dlink( tE ) & beforeLinks = before_elem`inner; + beforeLinks.next = &node; + list_pos_links.prev = &node; + asm( "" : : : "memory" ); + return node; + } + + tE & insert_after( tE & after, tE & node ) { + verify( &after != 0p ); + verify( &node != 0p ); + + dlink( tE ) & linkToInsert = node`inner; verify( linkToInsert.prev == 0p ); verify( linkToInsert.next == 0p ); - tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos ); - dlink(tE) & list_pos_links = list_pos_elem`inner; + tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after ); + dlink( tE ) & list_pos_links = list_pos_elem`inner; asm( "" : : : "memory" ); tE & after_raw = *list_pos_links.next; tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw ); - linkToInsert.prev = &list_pos; + linkToInsert.prev = &after; linkToInsert.next = &after_raw; - dlink(tE) & afterLinks = after_elem`inner; - afterLinks.prev = &to_insert; - list_pos_links.next = &to_insert; - asm( "" : : : "memory" ); - } - void insert( tE & list_pos, tE & to_insert ) { // alternate name - insert_after( list_pos, to_insert ); - } - - void insert_before( tE & list_pos, tE &to_insert ) { - verify( &list_pos != 0p ); - verify( &to_insert != 0p ); - - dlink(tE) & linkToInsert = to_insert`inner; - - verify( linkToInsert.next == 0p ); - verify( linkToInsert.prev == 0p ); - - tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos ); - dlink(tE) & list_pos_links = list_pos_elem`inner; - asm( "" : : : "memory" ); - tE & before_raw = *(list_pos_links).prev; - tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw ); - linkToInsert.next = & list_pos; - linkToInsert.prev = & before_raw; - dlink(tE) & beforeLinks = before_elem`inner; - beforeLinks.next = &to_insert; - list_pos_links.prev = &to_insert; - asm( "" : : : "memory" ); - } - - tE & remove( tE & list_pos ) { - verify( &list_pos != 0p ); - verify( ! ORIGIN_TAG_QUERY( (size_t)&list_pos) ); - - dlink(tE) & list_pos_links = list_pos`inner; - tE & before_raw = * list_pos_links.prev; - tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw ); - dlink(tE) & before_links = before_elem`inner; - tE & after_raw = * list_pos_links.next; - tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&after_raw ); - dlink(tE) & after_links = after_elem`inner; + dlink( tE ) & afterLinks = after_elem`inner; + afterLinks.prev = &node; + list_pos_links.next = &node; + asm( "" : : : "memory" ); + return node; + } + + tE & remove( tE & node ) { + verify( &node != 0p ); + verify( ! ORIGIN_TAG_QUERY( (size_t)&node) ); + + dlink( tE ) & list_pos_links = node`inner; + tE & before_raw = *list_pos_links.prev; + tE & before_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before_raw ); + dlink( tE ) & before_links = before_elem`inner; + tE & after_raw = *list_pos_links.next; + tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw ); + dlink( tE ) & after_links = after_elem`inner; before_links.next = &after_raw; after_links.prev = &before_raw; @@ -192,48 +191,44 @@ list_pos_links.next = 0p; asm( "" : : : "memory" ); - return list_pos; - } - // forall( T &, List ... | { tE & remove( tE & ); } ) - // void remove( tE & list_pos, List rest ) { - // remove( list_pos ); - // remove( rest ); - // } - - tE & ?`first( dlist(tE, tLinks) &lst ) { - tE * firstPtr = lst.next; - if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + return node; + } + + 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) &lst ) { - tE * lastPtr = lst.prev; - if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; + + 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) & lst ) { - tE * firstPtr = lst.next; - if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + 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 & e ) { - verify( &e != 0p); - dlink(tE) & e_links = e`inner; - return (e_links.prev != 0p) || (e_links.next != 0p); - } - - tE & ?`elems( dlist(tE, tLinks) & lst ) { - tE * origin = $get_list_origin_addr( lst ); + 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 * origin = $get_list_origin_addr( list ); return *origin; } - tE & ?`head( dlist(tE, tLinks) & lst ) { - return lst`elems; + tE & ?`head( dlist( tE, tLinks ) & list ) { + return list`elems; } bool ?`moveNext( tE && refx ) { tE && ref_inner = refx; - tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner ); &ref_inner = oldReferent`inner.next; - return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); } bool ?`next( tE && refx ) { // alternate name @@ -243,7 +238,7 @@ bool ?`movePrev( tE && refx ) { tE && ref_inner = refx; - tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + 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 ); + return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner ); } bool ?`prev( tE && refx ) { // alternate name @@ -251,44 +246,91 @@ } - bool ?`hasNext( tE & e ) { - return e`moveNext; - } - - bool ?`hasPrev( tE & e ) { - return e`movePrev; - } - - tE & ?`next( tE & e ) { - if ( e`moveNext ) return e; + bool ?`hasNext( tE & node ) { + return node`moveNext; + } + + bool ?`hasPrev( tE & node ) { + return node`movePrev; + } + + tE & ?`next( tE & node ) { + if ( node`moveNext ) return node; return *0p; } - tE & ?`prev( tE & e ) { - if ( e`movePrev ) return e; + tE & ?`prev( tE & node ) { + if ( node`movePrev ) return node; return *0p; } - void insert_first( dlist(tE, tLinks) &lst, tE & e ) { - insert_after( lst`elems, e ); - } - - void insert_last( dlist(tE, tLinks) &lst, tE & e ) { - insert_before( lst`elems, e ); - } - void insert( dlist(tE, tLinks) &lst, tE & e ) { // alternate name - insert_last( lst, e ); - } - - tE & try_pop_front( dlist(tE, tLinks) &lst ) { - tE & first_inlist = lst`first; + tE & insert_first( dlist( tE, tLinks ) & list, tE & node ) { + insert_after( list`elems, 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_last( list, node ); + return node; + } + + tE & remove_first( dlist( tE, tLinks ) & list ) { + return remove( list`first ); + } + + tE & remove_last( dlist( tE, tLinks ) & list ) { + return remove( list`last ); + } + + // Transfer the "from" list to the end of this sequence; the "from" list is empty after the transfer. +// void transfer( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from ) { +// if ( isEmpty( from ) ) return; // "from" list empty ? +// if ( isEmpty( to ) ) { // "to" list empty ? +// root = from.root; +// } else { // "to" list not empty +// T * toEnd = (T *)uBack( root ); +// T * fromEnd = (T *)from.uBack( from.root ); +// uBack( root ) = fromEnd; +// from.uNext( fromEnd ) = root; +// from.uBack( from.root ) = toEnd; +// uNext( toEnd ) = from.root; +// } // if +// from.root = nullptr; // mark "from" list empty +// } + + // Transfer the "from" list up to node "n" to the end of this list; the "from" list becomes the sequence after node "n". + // Node "n" must be in the "from" list. +// void split( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from, tE & node ) { +// #ifdef __U_DEBUG__ +// if ( ! n->listed() ) abort( "(uSequence &)%p.split( %p ) : Node is not on a list.", this, n ); +// #endif // __U_DEBUG__ +// uSequence to; +// to.root = from.root; // start of "to" list +// from.root = (T *)uNext( n ); // start of "from" list +// if ( to.root == from.root ) { // last node in list ? +// from.root = nullptr; // mark "from" list empty +// } else { +// uBack( from.root ) = (T *)uBack( to.root ); // fix "from" list +// uNext( uBack( to.root ) ) = from.root; +// uNext( n ) = to.root; // fix "to" list +// uBack( to.root ) = n; +// } // if +// transfer( to ); +// } + + tE & try_pop_front( dlist( tE, tLinks ) & list ) { + tE & first_inlist = list`first; tE & first_item = first_inlist; - if ( &first_item) remove( first_inlist ); + if ( &first_item ) remove( first_inlist ); return first_item; } - tE & try_pop_back( dlist(tE, tLinks) &lst ) { - tE & last_inlist = lst`last; + tE & try_pop_back( dlist( tE, tLinks ) & list ) { + tE & last_inlist = list`last; tE & last_item = last_inlist; - if ( &last_item) remove( last_inlist ); + if ( &last_item ) remove( last_inlist ); return last_item; } @@ -296,6 +338,6 @@ #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) - bool $validate_fwd( dlist(tE, tLinks) & this ) { - if ( ! & this`first ) return ( (&this`last) == 0p); + bool $validate_fwd( dlist( tE, tLinks ) & this ) { + if ( ! & this`first ) return &this`last == 0p; tE & lagElem = *0p; @@ -311,6 +353,6 @@ } - bool $validate_rev( dlist(tE, tLinks) & this ) { - if ( ! & this`last ) return ( (&this`first) == 0p); + bool $validate_rev( dlist( tE, tLinks ) & this ) { + if ( ! & this`last ) return &this`first == 0p; tE & lagElem = *0p; @@ -320,5 +362,5 @@ } - if ( &lagElem != &this`first) return false; + if ( &lagElem != &this`first ) return false; // TODO: verify that it is back at this`elems; @@ -326,6 +368,6 @@ } - bool validate( dlist(tE, tLinks) & this ) { - return $validate_fwd(this) && $validate_rev(this); + bool validate( dlist( tE, tLinks ) & this ) { + return $validate_fwd( this ) && $validate_rev( this ); } #endif @@ -334,5 +376,5 @@ // TEMPORARY, until foreach statement created. #define FOREACH( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next; ) -#define FOREACH_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next && (expr); ) #define FOREACH_REV( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev; ) -#define FOREACH_REV_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev && (expr); ) +#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); )