Ignore:
Timestamp:
Apr 20, 2025, 8:27:55 PM (5 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
9d9fd81
Parents:
0e4e43d
Message:

formatting and add return values

File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/collections/list.hfa

    r0e4e43d r65b0402  
    1010// Created On       : Wed Apr 22 18:00:00 2020
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Apr 19 16:24:09 2025
    13 // Update Count     : 27
     12// Last Modified On : Sun Apr 20 19:04:50 2025
     13// Update Count     : 51
    1414//
    1515
    … …  
    5757#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \
    5858        forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
    59         STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this )
     59        STORAGE inline tytagref( immedBase, Tbase ) ?`inner( derived & this )
    6060
    6161#define P9_EMBEDDED_BDY_( immedBase ) { \
    6262                immedBase & ib = this; \
    6363                Tbase & b = ib`inner; \
    64                 tytagref(immedBase, Tbase) result = { b }; \
     64                tytagref( immedBase, Tbase ) result = { b }; \
    6565                return result; \
    6666        }
    6767
    68 #define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
    69 
    70 #define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink(TE) )
     68#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref( MID, INNER ) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
     69
     70#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink( TE ) )
    7171
    7272
    … …  
    9191#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
    9292
    93 #define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
    94 #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
    95 #define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
     93#define ORIGIN_TAG_SET( p )   ((p) |  ORIGIN_TAG_MASK)
     94#define ORIGIN_TAG_CLEAR( p ) ((p) & ~ORIGIN_TAG_MASK)
     95#define ORIGIN_TAG_QUERY( p ) ((p) &  ORIGIN_TAG_MASK)
    9696
    9797forall( tE & ) {
    … …  
    101101        };
    102102
    103         static inline void ?{}( dlink(tE) & this ) {
     103        static inline void ?{}( dlink( tE ) & this ) {
    104104                this.next = this.prev = 0p;
    105105        }
    106106
    107         forall( tLinks & = dlink(tE) )
     107        forall( tLinks & = dlink( tE ) )
    108108        struct dlist {
    109                 inline dlink(tE);
     109                inline dlink( tE );
    110110        };
    111111
    112         forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    113                 static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
    114                         dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
    115                         ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
    116                         size_t origin_addr = ((size_t) & lst) - link_offset;
     112        forall( tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
     113                static inline tE * $get_list_origin_addr( dlist( tE, tLinks ) & list ) {
     114                        dlink( tE ) & link_from_null = (*(tE *)0p)`inner;
     115                        ptrdiff_t link_offset = (ptrdiff_t)&link_from_null;
     116                        size_t origin_addr = ((size_t)&list) - link_offset;
    117117                        size_t preResult = ORIGIN_TAG_SET( origin_addr );
    118118                        return (tE *)preResult;
    119119                }
    120120
    121                 static inline void ?{}( dlist(tE, tLinks) & this ) {
     121                static inline void ?{}( dlist( tE, tLinks ) & this ) {
    122122                        tE * listOrigin = $get_list_origin_addr( this );
    123                         ((dlink(tE) &)this){ listOrigin, listOrigin };
     123                        ((dlink( tE ) &)this){ listOrigin, listOrigin };
    124124                }
    125125        }
    … …  
    127127
    128128
    129 static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    130         void insert_after( tE & list_pos, tE & to_insert ) {
    131                 verify( &list_pos != 0p );
    132                 verify( &to_insert != 0p );
    133 
    134                 dlink(tE) & linkToInsert = to_insert`inner;
     129static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
     130        tE & insert_before( tE & before, tE & node ) {
     131                verify( &before != 0p );
     132                verify( &node != 0p );
     133
     134                dlink( tE ) & linkToInsert = node`inner;
     135
     136                verify( linkToInsert.next == 0p );
     137                verify( linkToInsert.prev == 0p );
     138
     139                tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before );
     140                dlink( tE ) & list_pos_links = list_pos_elem`inner;
     141                asm( "" : : : "memory" );
     142                tE & before_raw = *list_pos_links.prev;
     143                tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
     144                linkToInsert.next = &before;
     145                linkToInsert.prev = &before_raw;
     146                dlink( tE ) & beforeLinks = before_elem`inner;
     147                beforeLinks.next = &node;
     148                list_pos_links.prev = &node;
     149                asm( "" : : : "memory" );
     150                return node;
     151        }
     152
     153        tE & insert_after( tE & after, tE & node ) {
     154                verify( &after != 0p );
     155                verify( &node != 0p );
     156
     157                dlink( tE ) & linkToInsert = node`inner;
    135158
    136159                verify( linkToInsert.prev == 0p );
    137160                verify( linkToInsert.next == 0p );
    138161
    139                 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos );
    140                 dlink(tE) & list_pos_links = list_pos_elem`inner;
     162                tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after );
     163                dlink( tE ) & list_pos_links = list_pos_elem`inner;
    141164                asm( "" : : : "memory" );
    142165                tE & after_raw = *list_pos_links.next;
    143166                tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
    144                 linkToInsert.prev = &list_pos;
     167                linkToInsert.prev = &after;
    145168                linkToInsert.next = &after_raw;
    146                 dlink(tE) & afterLinks = after_elem`inner;
    147                 afterLinks.prev = &to_insert;
    148                 list_pos_links.next = &to_insert;
    149                 asm( "" : : : "memory" );
    150         }
    151         void insert( tE & list_pos, tE & to_insert ) {          // alternate name
    152                 insert_after( list_pos, to_insert );
    153         }
    154 
    155         void insert_before( tE & list_pos, tE &to_insert ) {
    156                 verify( &list_pos != 0p );
    157                 verify( &to_insert != 0p );
    158 
    159                 dlink(tE) & linkToInsert = to_insert`inner;
    160 
    161                 verify( linkToInsert.next == 0p );
    162                 verify( linkToInsert.prev == 0p );
    163 
    164                 tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos );
    165                 dlink(tE) & list_pos_links = list_pos_elem`inner;
    166                 asm( "" : : : "memory" );
    167                 tE & before_raw = *(list_pos_links).prev;
    168                 tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
    169                 linkToInsert.next = & list_pos;
    170                 linkToInsert.prev = & before_raw;
    171                 dlink(tE) & beforeLinks = before_elem`inner;
    172                 beforeLinks.next = &to_insert;
    173                 list_pos_links.prev = &to_insert;
    174                 asm( "" : : : "memory" );
    175         }
    176 
    177         tE & remove( tE & list_pos ) {
    178                 verify( &list_pos != 0p );
    179                 verify( ! ORIGIN_TAG_QUERY( (size_t)&list_pos) );
    180 
    181                 dlink(tE) & list_pos_links = list_pos`inner;
    182                 tE & before_raw = * list_pos_links.prev;
    183                 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
    184                 dlink(tE) & before_links = before_elem`inner;
    185                 tE & after_raw = * list_pos_links.next;
    186                 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&after_raw );
    187                 dlink(tE) & after_links = after_elem`inner;
     169                dlink( tE ) & afterLinks = after_elem`inner;
     170                afterLinks.prev = &node;
     171                list_pos_links.next = &node;
     172                asm( "" : : : "memory" );
     173                return node;
     174        }
     175
     176        tE & remove( tE & node ) {
     177                verify( &node != 0p );
     178                verify( ! ORIGIN_TAG_QUERY( (size_t)&node) );
     179
     180                dlink( tE ) & list_pos_links = node`inner;
     181                tE & before_raw = *list_pos_links.prev;
     182                tE & before_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&before_raw );
     183                dlink( tE ) & before_links = before_elem`inner;
     184                tE & after_raw = *list_pos_links.next;
     185                tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
     186                dlink( tE ) & after_links = after_elem`inner;
    188187                before_links.next = &after_raw;
    189188                after_links.prev = &before_raw;
    … …  
    192191                list_pos_links.next = 0p;
    193192                asm( "" : : : "memory" );
    194                 return list_pos;
    195         }
    196         // forall( T &, List ... | { tE & remove( tE & ); } )
    197         // void remove( tE & list_pos, List rest ) {
    198         //      remove( list_pos );
    199         //      remove( rest );
    200         // }
    201 
    202         tE & ?`first( dlist(tE, tLinks) &lst ) {
    203                 tE * firstPtr = lst.next;
    204                 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     193                return node;
     194        }
     195
     196        tE & ?`first( dlist( tE, tLinks ) & list ) {
     197                tE * firstPtr = list.next;
     198                if ( ORIGIN_TAG_QUERY( (size_t)firstPtr ) ) firstPtr = 0p;
    205199                return *firstPtr;
    206200        }
    207         tE & ?`last( dlist(tE, tLinks) &lst ) {
    208                 tE * lastPtr = lst.prev;
    209                 if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
     201
     202        tE & ?`last( dlist( tE, tLinks ) & list ) {
     203                tE * lastPtr = list.prev;
     204                if ( ORIGIN_TAG_QUERY( (size_t)lastPtr) ) lastPtr = 0p;
    210205                return *lastPtr;
    211206        }
    212207
    213         bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
    214                 tE * firstPtr = lst.next;
    215                 if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     208        bool ?`isEmpty( dlist( tE, tLinks ) & list ) {
     209                tE * firstPtr = list.next;
     210                if ( ORIGIN_TAG_QUERY(( size_t)firstPtr) ) firstPtr = 0p;
    216211                return firstPtr == 0p;
    217212        }
    218213
    219         bool ?`isListed( tE & e ) {
    220                 verify( &e != 0p);
    221                 dlink(tE) & e_links = e`inner;
    222                 return (e_links.prev != 0p) || (e_links.next != 0p);
    223         }
    224 
    225         tE & ?`elems( dlist(tE, tLinks) & lst ) {
    226                 tE * origin = $get_list_origin_addr( lst );
     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 ) {
     221                tE * origin = $get_list_origin_addr( list );
    227222                return *origin;
    228223        }
    229         tE & ?`head( dlist(tE, tLinks) & lst ) {
    230                 return lst`elems;
     224        tE & ?`head( dlist( tE, tLinks ) & list ) {
     225                return list`elems;
    231226        }
    232227
    233228        bool ?`moveNext( tE && refx ) {
    234229                tE && ref_inner = refx;
    235                 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     230                tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner );
    236231                &ref_inner = oldReferent`inner.next;
    237                 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
     232                return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner );
    238233        }
    239234        bool ?`next( tE && refx ) {                                                     // alternate name
    … …  
    243238        bool ?`movePrev( tE && refx ) {
    244239                tE && ref_inner = refx;
    245                 tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     240                tE & oldReferent = *(tE*)ORIGIN_TAG_CLEAR( (size_t)&ref_inner );
    246241                &ref_inner = oldReferent`inner.prev;
    247                 return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
     242                return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t)&ref_inner );
    248243        }
    249244        bool ?`prev( tE && refx ) {                                                     // alternate name
    … …  
    251246        }
    252247
    253         bool ?`hasNext( tE & e ) {
    254                 return e`moveNext;
    255         }
    256 
    257         bool ?`hasPrev( tE & e ) {
    258                 return e`movePrev;
    259         }
    260 
    261         tE & ?`next( tE & e ) {
    262                 if ( e`moveNext ) return e;
     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;
    263258                return *0p;
    264259        }
    265260
    266         tE & ?`prev( tE & e ) {
    267                 if ( e`movePrev ) return e;
     261        tE & ?`prev( tE & node ) {
     262                if ( node`movePrev ) return node;
    268263                return *0p;
    269264        }
    270265
    271         void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    272                 insert_after( lst`elems, e );
    273         }
    274 
    275         void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    276                 insert_before( lst`elems, e );
    277         }
    278         void insert( dlist(tE, tLinks) &lst, tE & e ) {         // alternate name
    279                 insert_last( lst, e );
    280         }
    281 
    282         tE & try_pop_front( dlist(tE, tLinks) &lst ) {
    283                 tE & first_inlist = lst`first;
     266        tE & insert_first( dlist( tE, tLinks ) & list, tE & node ) {
     267                insert_after( list`elems, node );
     268                return node;
     269        }
     270
     271        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 name
     276                insert_last( list, node );
     277                return node;
     278        }
     279
     280        tE & remove_first( dlist( tE, tLinks ) & list ) {
     281                return remove( list`first );
     282        }
     283
     284        tE & remove_last( dlist( tE, tLinks ) & list ) {
     285                return remove( list`last );
     286        }
     287
     288        // Transfer the "from" list to the end of this sequence; the "from" list is empty after the transfer.
     289//      void transfer( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from ) {
     290//              if ( isEmpty( from ) ) return;                                  // "from" list empty ?
     291//              if ( isEmpty( to ) ) {                                                  // "to" list empty ?
     292//                      root = from.root;
     293//              } else {                                                                                // "to" list not empty
     294//                      T * toEnd = (T *)uBack( root );
     295//                      T * fromEnd = (T *)from.uBack( from.root );
     296//                      uBack( root ) = fromEnd;
     297//                      from.uNext( fromEnd ) = root;
     298//                      from.uBack( from.root ) = toEnd;
     299//                      uNext( toEnd ) = from.root;
     300//              } // if
     301//              from.root = nullptr;                                                    // mark "from" list empty
     302//      }
     303
     304        // Transfer the "from" list up to node "n" to the end of this list; the "from" list becomes the sequence after node "n".
     305        // Node "n" must be in the "from" list.
     306//      void split( dlist( tE, tLinks ) & to, dlist( tE, tLinks ) & from, tE & node ) {
     307//              #ifdef __U_DEBUG__
     308//              if ( ! n->listed() ) abort( "(uSequence &)%p.split( %p ) : Node is not on a list.", this, n );
     309//              #endif // __U_DEBUG__
     310//              uSequence<T> to;
     311//              to.root = from.root;                                                    // start of "to" list
     312//              from.root = (T *)uNext( n );                                    // start of "from" list
     313//              if ( to.root == from.root ) {                                   // last node in list ?
     314//                      from.root = nullptr;                                            // mark "from" list empty
     315//              } else {
     316//                      uBack( from.root ) = (T *)uBack( to.root );     // fix "from" list
     317//                      uNext( uBack( to.root ) ) = from.root;
     318//                      uNext( n ) = to.root;                                           // fix "to" list
     319//                      uBack( to.root ) = n;
     320//              } // if
     321//              transfer( to );
     322//      }
     323
     324        tE & try_pop_front( dlist( tE, tLinks ) & list ) {
     325                tE & first_inlist = list`first;
    284326                tE & first_item = first_inlist;
    285                 if ( &first_item) remove( first_inlist );
     327                if ( &first_item ) remove( first_inlist );
    286328                return first_item;
    287329        }
    288330
    289         tE & try_pop_back( dlist(tE, tLinks) &lst ) {
    290                 tE & last_inlist = lst`last;
     331        tE & try_pop_back( dlist( tE, tLinks ) & list ) {
     332                tE & last_inlist = list`last;
    291333                tE & last_item = last_inlist;
    292                 if ( &last_item) remove( last_inlist );
     334                if ( &last_item ) remove( last_inlist );
    293335                return last_item;
    294336        }
    … …  
    296338
    297339        #if ! defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
    298         bool $validate_fwd( dlist(tE, tLinks) & this ) {
    299                 if ( ! & this`first ) return ( (&this`last) == 0p);
     340        bool $validate_fwd( dlist( tE, tLinks ) & this ) {
     341                if ( ! & this`first ) return &this`last == 0p;
    300342
    301343                tE & lagElem = *0p;
    … …  
    311353        }
    312354
    313         bool $validate_rev( dlist(tE, tLinks) & this ) {
    314                 if ( ! & this`last ) return ( (&this`first) == 0p);
     355        bool $validate_rev( dlist( tE, tLinks ) & this ) {
     356                if ( ! & this`last ) return &this`first == 0p;
    315357
    316358                tE & lagElem = *0p;
    … …  
    320362                }
    321363
    322                 if ( &lagElem != &this`first) return false;
     364                if ( &lagElem != &this`first ) return false;
    323365
    324366                // TODO: verify that it is back at this`elems;
    … …  
    326368        }
    327369
    328         bool validate( dlist(tE, tLinks) & this ) {
    329                 return $validate_fwd(this) && $validate_rev(this);
     370        bool validate( dlist( tE, tLinks ) & this ) {
     371                return $validate_fwd( this ) && $validate_rev( this );
    330372        }
    331373        #endif
    … …  
    334376// TEMPORARY, until foreach statement created.
    335377#define FOREACH( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next; )
    336 #define FOREACH_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`next && (expr); )
    337378#define FOREACH_REV( list, index ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev; )
    338 #define FOREACH_REV_COND( list, index, expr ) for ( typeof((list)`head) & (index) = (list)`head; (index)`prev && (expr); )
     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); )
Note: See TracChangeset for help on using the changeset viewer.