Ignore:
Timestamp:
Apr 19, 2025, 4:33:18 PM (5 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
0e4e43d
Parents:
e86735ba
Message:

formatting and adding alternate-named list routines

File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/collections/list.hfa

    re86735ba r0eacfd4  
    1010// Created On       : Wed Apr 22 18:00:00 2020
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Apr 17 07:28:47 2025
    13 // Update Count     : 3
     12// Last Modified On : Sat Apr 19 16:24:09 2025
     13// Update Count     : 27
    1414//
    1515
    … …  
    2929
    3030// embedded is reflexive, with no info (void) as the type tag
    31 forall (T &)
     31forall( T & )
    3232static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
    3333
    … …  
    6666        }
    6767
    68 #define EMBEDDED_VIA( OUTER, MID, INNER ) \
    69    (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
    70 
    71 #define DLINK_VIA( TE, TLINK ) \
    72    EMBEDDED_VIA( TE, TLINK, dlink(TE) )
    73 
    74 
    75 // The origin is the position encountered at the start of iteration,
    76 // signifying, "need to advance to the first element," and at the end
    77 // of iteration, signifying, "no more elements."  Normal comsumption of
    78 // an iterator runs ?`moveNext as the first step, and uses the return
    79 // of ?`moveNext as a guard, before dereferencing the iterator.  So
    80 // normal consumption of an iterator does not dereference an iterator
    81 // in origin position.  The value of a pointer (underlying a refence)
    82 // that is exposed publicly as an iteraor, and also a pointer stored
    83 // internally in a link field, is tagged, to indicate "is the origin"
    84 // (internally, is the list-head sentinel node), or untagged, to indicate
    85 // "is a regular node."  Intent is to help a user who dereferences an
    86 // iterator in origin position (which would be an API-use error on their
     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) )
     71
     72
     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 ?`moveNext as
     75// the first step, and uses the return of ?`moveNext as a guard, before dereferencing the iterator.  So normal
     76// consumption of an iterator does not dereference an iterator in origin position.  The value of a pointer (underlying a
     77// refence) that is exposed publicly as an iteraor, and also a pointer stored internally in a link field, is tagged, to
     78// indicate "is the origin" (internally, is the list-head sentinel node), or untagged, to indicate "is a regular node."
     79// Intent is to help a user who dereferences an iterator in origin position (which would be an API-use error on their
    8780// part), by failing fast.
    8881
    8982#if defined( __x86_64 )
    90         // Preferred case: tag in the most-significant bit.  Dereference
    91         // has been shown to segfault consistently.  Maintenance should
    92         // list more architectures as "ok" here, to let them use the
    93         // preferred case, when valid.
     83        // Preferred case: tag in the most-significant bit.  Dereference has been shown to segfault consistently.
     84        // Maintenance should list more architectures as "ok" here, to let them use the preferred case, when valid.
    9485        #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
    9586#else
    96         // Fallback case: tag in the least-significant bit.  Dereference
    97         // will often give an alignment error, but may not, e.g. if
    98         // accessing a char-typed member.  32-bit x86 uses the most-
    99         // significant bit for real room on the heap.
     87        // Fallback case: tag in the least-significant bit.  Dereference will often give an alignment error, but may not,
     88        // e.g. if accessing a char-typed member.  32-bit x86 uses the most- significant bit for real room on the heap.
    10089        #define ORIGIN_TAG_BITNO 0
    10190#endif
    … …  
    10695#define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
    10796
    108 
    10997forall( tE & ) {
    110 
    11198        struct dlink{
    112                 tE *next;
    113                 tE *prev;
     99                tE * next;
     100                tE * prev;
    114101        };
    115102
    116103        static inline void ?{}( dlink(tE) & this ) {
    117                 this.next = 0p;
    118                 this.prev = 0p;
     104                this.next = this.prev = 0p;
    119105        }
    120106
    … …  
    135121                static inline void ?{}( dlist(tE, tLinks) & this ) {
    136122                        tE * listOrigin = $get_list_origin_addr( this );
    137                         ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
     123                        ((dlink(tE) &)this){ listOrigin, listOrigin };
    138124                }
    139125        }
    140 
    141126}
    142127
    143128
    144 forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    145 
    146         static inline void insert_after(tE & list_pos, tE &to_insert) {
    147                 verify (&list_pos != 0p);
    148                 verify (&to_insert != 0p);
     129static 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
    149134                dlink(tE) & linkToInsert = to_insert`inner;
    150                 verify(linkToInsert.prev == 0p);
    151                 verify(linkToInsert.next == 0p);
    152                 tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
     135
     136                verify( linkToInsert.prev == 0p );
     137                verify( linkToInsert.next == 0p );
     138
     139                tE & list_pos_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&list_pos );
    153140                dlink(tE) & list_pos_links = list_pos_elem`inner;
    154141                asm( "" : : : "memory" );
    155                 tE & after_raw = * list_pos_links.next;
    156                 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    157                 linkToInsert.prev = & list_pos;
    158                 linkToInsert.next = & after_raw;
     142                tE & after_raw = *list_pos_links.next;
     143                tE & after_elem = *(tE *)ORIGIN_TAG_CLEAR( (size_t)&after_raw );
     144                linkToInsert.prev = &list_pos;
     145                linkToInsert.next = &after_raw;
    159146                dlink(tE) & afterLinks = after_elem`inner;
    160147                afterLinks.prev = &to_insert;
    … …  
    162149                asm( "" : : : "memory" );
    163150        }
    164 
    165         static inline void insert_before(tE & list_pos, tE &to_insert) {
    166                 verify (&list_pos != 0p);
    167                 verify (&to_insert != 0p);
     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
    168159                dlink(tE) & linkToInsert = to_insert`inner;
    169                 verify(linkToInsert.next == 0p);
    170                 verify(linkToInsert.prev == 0p);
    171                 tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
     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 );
    172165                dlink(tE) & list_pos_links = list_pos_elem`inner;
    173166                asm( "" : : : "memory" );
    174                 tE & before_raw = * (list_pos_links).prev;
    175                 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     167                tE & before_raw = *(list_pos_links).prev;
     168                tE & before_elem = *(tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
    176169                linkToInsert.next = & list_pos;
    177170                linkToInsert.prev = & before_raw;
    178171                dlink(tE) & beforeLinks = before_elem`inner;
    179172                beforeLinks.next = &to_insert;
    180                 (list_pos_links).prev = &to_insert;
    181                 asm( "" : : : "memory" );
    182         }
    183 
    184         static inline tE & remove(tE & list_pos) {
    185                 verify (&list_pos != 0p);
    186                 verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
     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
    187181                dlink(tE) & list_pos_links = list_pos`inner;
    188182                tE & before_raw = * list_pos_links.prev;
    189                 tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     183                tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&before_raw );
    190184                dlink(tE) & before_links = before_elem`inner;
    191185                tE & after_raw = * list_pos_links.next;
    192                 tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     186                tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t)&after_raw );
    193187                dlink(tE) & after_links = after_elem`inner;
    194188                before_links.next = &after_raw;
    … …  
    200194                return list_pos;
    201195        }
    202 
    203         static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
     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 ) {
    204203                tE * firstPtr = lst.next;
    205204                if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    206205                return *firstPtr;
    207206        }
    208         static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
     207        tE & ?`last( dlist(tE, tLinks) &lst ) {
    209208                tE * lastPtr = lst.prev;
    210209                if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
    … …  
    212211        }
    213212
    214         static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
     213        bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
    215214                tE * firstPtr = lst.next;
    216215                if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    … …  
    218217        }
    219218
    220         static inline bool ?`isListed( tE & e ) {
    221                 verify (&e != 0p);
     219        bool ?`isListed( tE & e ) {
     220                verify( &e != 0p);
    222221                dlink(tE) & e_links = e`inner;
    223222                return (e_links.prev != 0p) || (e_links.next != 0p);
    224223        }
    225224
    226         static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
     225        tE & ?`elems( dlist(tE, tLinks) & lst ) {
    227226                tE * origin = $get_list_origin_addr( lst );
    228227                return *origin;
    229228        }
    230 
    231         static inline bool ?`moveNext( tE && refx ) {
     229        tE & ?`head( dlist(tE, tLinks) & lst ) {
     230                return lst`elems;
     231        }
     232
     233        bool ?`moveNext( tE && refx ) {
    232234                tE && ref_inner = refx;
    233235                tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    234236                &ref_inner = oldReferent`inner.next;
    235                 return &ref_inner != 0p  &&
    236                         ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
    237         }
    238 
    239         static inline bool ?`movePrev( tE && refx ) {
     237                return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
     238        }
     239        bool ?`next( tE && refx ) {                                                     // alternate name
     240                return refx`moveNext;
     241        }
     242
     243        bool ?`movePrev( tE && refx ) {
    240244                tE && ref_inner = refx;
    241245                tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    242246                &ref_inner = oldReferent`inner.prev;
    243                 return &ref_inner != 0p  &&
    244                         ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
    245         }
    246 
    247         static inline bool ?`hasNext( tE & e ) {
     247                return &ref_inner != 0p && ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
     248        }
     249        bool ?`prev( tE && refx ) {                                                     // alternate name
     250                return refx`movePrev;
     251        }
     252
     253        bool ?`hasNext( tE & e ) {
    248254                return e`moveNext;
    249255        }
    250256
    251         static inline bool ?`hasPrev( tE & e ) {
     257        bool ?`hasPrev( tE & e ) {
    252258                return e`movePrev;
    253259        }
    254260
    255         static inline tE & ?`next( tE & e ) {
    256                 if( e`moveNext ) return e;
    257                 return * 0p;
    258         }
    259 
    260         static inline tE & ?`prev( tE & e ) {
    261                 if( e`movePrev ) return e;
    262                 return * 0p;
    263         }
    264 
    265         static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    266                 insert_after(lst`elems, e);
    267         }
    268 
    269         static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    270                 insert_before(lst`elems, e);
    271         }
    272 
    273         static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
     261        tE & ?`next( tE & e ) {
     262                if ( e`moveNext ) return e;
     263                return *0p;
     264        }
     265
     266        tE & ?`prev( tE & e ) {
     267                if ( e`movePrev ) return e;
     268                return *0p;
     269        }
     270
     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 ) {
    274283                tE & first_inlist = lst`first;
    275284                tE & first_item = first_inlist;
    276                 if (&first_item) remove(first_inlist);
     285                if ( &first_item) remove( first_inlist );
    277286                return first_item;
    278287        }
    279288
    280         static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
     289        tE & try_pop_back( dlist(tE, tLinks) &lst ) {
    281290                tE & last_inlist = lst`last;
    282291                tE & last_item = last_inlist;
    283                 if (&last_item) remove(last_inlist);
     292                if ( &last_item) remove( last_inlist );
    284293                return last_item;
    285294        }
    286295
    287296
    288   #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
    289         static bool $validate_fwd( dlist(tE, tLinks) & this ) {
    290                 if ( ! & this`first ) return ( (& this`last) == 0p);
     297        #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);
    291300
    292301                tE & lagElem = *0p;
    293 
    294302                while ( tE & it = this`elems; it`moveNext ) {
    295                         if (& lagElem == 0p &&  &it != & this`first ) return false;
    296                         & lagElem = & it;
     303                        if ( & lagElem == 0p &&  &it != & this`first ) return false;
     304                        &lagElem = &it;
    297305                }
    298306
    299                 if (& lagElem != & this`last) return false;
     307                if ( &lagElem != &this`last ) return false;
    300308
    301309                // TODO: verify that it is back at this`elems;
    302310                return true;
    303311        }
    304         static bool $validate_rev( dlist(tE, tLinks) & this ) {
    305                 if ( ! & this`last ) return ( (& this`first) == 0p);
     312
     313        bool $validate_rev( dlist(tE, tLinks) & this ) {
     314                if ( ! & this`last ) return ( (&this`first) == 0p);
    306315
    307316                tE & lagElem = *0p;
    308 
    309317                while ( tE & it = this`elems; it`movePrev ) {
    310                         if (& lagElem == 0p && &it != & this`last ) return false;
    311                         & lagElem = & it;
     318                        if ( &lagElem == 0p && &it != & this`last ) return false;
     319                        &lagElem = &it;
    312320                }
    313321
    314                 if (& lagElem != & this`first) return false;
     322                if ( &lagElem != &this`first) return false;
    315323
    316324                // TODO: verify that it is back at this`elems;
    317325                return true;
    318326        }
    319         static inline bool validate( dlist(tE, tLinks) & this ) {
     327
     328        bool validate( dlist(tE, tLinks) & this ) {
    320329                return $validate_fwd(this) && $validate_rev(this);
    321330        }
    322   #endif
    323 
     331        #endif
    324332}
    325333
     334// TEMPORARY, until foreach statement created.
     335#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); )
     337#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); )
Note: See TracChangeset for help on using the changeset viewer.