Index: libcfa/src/collections/list.hfa =================================================================== --- libcfa/src/collections/list.hfa (revision 9dd1dd6f547ddd569b2e2a944a2e8311e7736008) +++ libcfa/src/collections/list.hfa (revision 0e4e43dc3938ca1279a84c98fd7d8edc4ea9e5d8) @@ -10,6 +10,6 @@ // Created On : Wed Apr 22 18:00:00 2020 // Last Modified By : Peter A. Buhr -// Last Modified On : Thu Apr 17 07:28:47 2025 -// Update Count : 3 +// Last Modified On : Sat Apr 19 16:24:09 2025 +// Update Count : 27 // @@ -29,5 +29,5 @@ // embedded is reflexive, with no info (void) as the type tag -forall (T &) +forall( T & ) static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; } @@ -66,36 +66,25 @@ } -#define EMBEDDED_VIA( OUTER, MID, INNER ) \ - (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } - -#define DLINK_VIA( TE, TLINK ) \ - EMBEDDED_VIA( TE, TLINK, dlink(TE) ) - - -// 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 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 indicate "is the origin" -// (internally, is the list-head sentinel node), or untagged, to indicate -// "is a regular node." Intent is to help a user who dereferences an -// iterator in origin position (which would be an API-use error on their +#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } + +#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink(TE) ) + + +// 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 +// 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 +// indicate "is the origin" (internally, is the list-head sentinel node), or untagged, to indicate "is a regular node." +// Intent is to help a user who dereferences an iterator in origin position (which would be an API-use error on their // part), by failing fast. #if defined( __x86_64 ) - // Preferred case: tag in the most-significant bit. Dereference - // has been shown to segfault consistently. Maintenance should - // list more architectures as "ok" here, to let them use the - // preferred case, when valid. + // Preferred case: tag in the most-significant bit. Dereference has been shown to segfault consistently. + // Maintenance should list more architectures as "ok" here, to let them use the preferred case, when valid. #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 ) #else - // Fallback case: tag in the least-significant bit. Dereference - // will often give an alignment error, but may not, e.g. if - // accessing a char-typed member. 32-bit x86 uses the most- - // significant bit for real room on the heap. + // Fallback case: tag in the least-significant bit. Dereference will often give an alignment error, but may not, + // e.g. if accessing a char-typed member. 32-bit x86 uses the most- significant bit for real room on the heap. #define ORIGIN_TAG_BITNO 0 #endif @@ -106,15 +95,12 @@ #define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK) - forall( tE & ) { - struct dlink{ - tE *next; - tE *prev; + tE * next; + tE * prev; }; static inline void ?{}( dlink(tE) & this ) { - this.next = 0p; - this.prev = 0p; + this.next = this.prev = 0p; } @@ -135,26 +121,27 @@ static inline void ?{}( dlist(tE, tLinks) & this ) { tE * listOrigin = $get_list_origin_addr( this ); - ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ; + ((dlink(tE) &)this){ listOrigin, listOrigin }; } } - } -forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - - static inline void insert_after(tE & list_pos, tE &to_insert) { - verify (&list_pos != 0p); - verify (&to_insert != 0p); +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; - verify(linkToInsert.prev == 0p); - verify(linkToInsert.next == 0p); - tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos ); + + 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; 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.next = & after_raw; + tE & after_raw = *list_pos_links.next; + tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw ); + linkToInsert.prev = &list_pos; + linkToInsert.next = &after_raw; dlink(tE) & afterLinks = after_elem`inner; afterLinks.prev = &to_insert; @@ -162,33 +149,40 @@ asm( "" : : : "memory" ); } - - static inline void insert_before(tE & list_pos, tE &to_insert) { - verify (&list_pos != 0p); - verify (&to_insert != 0p); + 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 ); + + 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 ); + 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" ); - } - - static inline tE & remove(tE & list_pos) { - verify (&list_pos != 0p); - verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) ); + 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 ); + 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 ); + tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&after_raw ); dlink(tE) & after_links = after_elem`inner; before_links.next = &after_raw; @@ -200,11 +194,16 @@ return list_pos; } - - static inline tE & ?`first( dlist(tE, tLinks) &lst ) { + // 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 *firstPtr; } - static inline tE & ?`last ( dlist(tE, tLinks) &lst ) { + tE & ?`last( dlist(tE, tLinks) &lst ) { tE * lastPtr = lst.prev; if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; @@ -212,5 +211,5 @@ } - static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) { + bool ?`isEmpty( dlist(tE, tLinks) & lst ) { tE * firstPtr = lst.next; if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; @@ -218,108 +217,122 @@ } - static inline bool ?`isListed( tE & e ) { - verify (&e != 0p); + bool ?`isListed( tE & e ) { + verify( &e != 0p); dlink(tE) & e_links = e`inner; return (e_links.prev != 0p) || (e_links.next != 0p); } - static inline tE & ?`elems( dlist(tE, tLinks) & lst ) { + tE & ?`elems( dlist(tE, tLinks) & lst ) { tE * origin = $get_list_origin_addr( lst ); return *origin; } - - static inline bool ?`moveNext( tE && refx ) { + tE & ?`head( dlist(tE, tLinks) & lst ) { + return lst`elems; + } + + bool ?`moveNext( tE && refx ) { tE && ref_inner = refx; 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 ); - } - - static inline bool ?`movePrev( tE && refx ) { + 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 ); - } - - static inline bool ?`hasNext( tE & e ) { + return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + bool ?`prev( tE && refx ) { // alternate name + return refx`movePrev; + } + + bool ?`hasNext( tE & e ) { return e`moveNext; } - static inline bool ?`hasPrev( tE & e ) { + bool ?`hasPrev( tE & e ) { return e`movePrev; } - static inline tE & ?`next( tE & e ) { - if( e`moveNext ) return e; - return * 0p; - } - - static inline tE & ?`prev( tE & e ) { - if( e`movePrev ) return e; - return * 0p; - } - - static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) { - insert_after(lst`elems, e); - } - - static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { - insert_before(lst`elems, e); - } - - static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) { + tE & ?`next( tE & e ) { + if ( e`moveNext ) return e; + return *0p; + } + + tE & ?`prev( tE & e ) { + if ( e`movePrev ) return e; + 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 & first_item = first_inlist; - if (&first_item) remove(first_inlist); + if ( &first_item) remove( first_inlist ); return first_item; } - static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) { + tE & try_pop_back( dlist(tE, tLinks) &lst ) { tE & last_inlist = lst`last; tE & last_item = last_inlist; - if (&last_item) remove(last_inlist); + if ( &last_item) remove( last_inlist ); return last_item; } - #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) - static bool $validate_fwd( dlist(tE, tLinks) & this ) { - if ( ! & this`first ) return ( (& this`last) == 0p); + #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) + bool $validate_fwd( dlist(tE, tLinks) & this ) { + if ( ! & this`first ) return ( (&this`last) == 0p); tE & lagElem = *0p; - while ( tE & it = this`elems; it`moveNext ) { - if (& lagElem == 0p && &it != & this`first ) return false; - & lagElem = & it; + if ( & lagElem == 0p && &it != & this`first ) return false; + &lagElem = ⁢ } - if (& lagElem != & this`last) return false; + if ( &lagElem != &this`last ) return false; // TODO: verify that it is back at this`elems; return true; } - static 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; - while ( tE & it = this`elems; it`movePrev ) { - if (& lagElem == 0p && &it != & this`last ) return false; - & lagElem = & it; + if ( &lagElem == 0p && &it != & this`last ) return false; + &lagElem = ⁢ } - if (& lagElem != & this`first) return false; + if ( &lagElem != &this`first) return false; // TODO: verify that it is back at this`elems; return true; } - static inline bool validate( dlist(tE, tLinks) & this ) { + + bool validate( dlist(tE, tLinks) & this ) { return $validate_fwd(this) && $validate_rev(this); } - #endif - + #endif } +// 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); )