Changeset 9dd1dd6 for libcfa


Ignore:
Timestamp:
Apr 18, 2025, 8:43:09 AM (5 months ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
e86735ba
Parents:
4740281
Message:

formatting

File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/collections/list.hfa

    r4740281 r9dd1dd6  
    1010// Created On       : Wed Apr 22 18:00:00 2020
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Feb  2 11:32:26 2023
    13 // Update Count     : 2
     12// Last Modified On : Thu Apr 17 07:28:47 2025
     13// Update Count     : 3
    1414//
    1515
    … …  
    2020forall( Decorator &, T & )
    2121struct tytagref {
    22     inline T &;
     22        inline T &;
    2323};
    2424
    2525forall( tOuter &, tMid &, tInner & )
    2626trait embedded {
    27     tytagref( tMid, tInner ) ?`inner( tOuter & );
     27        tytagref( tMid, tInner ) ?`inner( tOuter & );
    2828};
    2929
    … …  
    3737//
    3838// struct foo {
    39 //    int a, b, c;
    40 //    inline (bar);
     39//      int a, b, c;
     40//      inline (bar);
    4141// };
    4242// P9_EMBEDDED( foo, bar )
    … …  
    4444
    4545// usual version, for structs that are top-level declarations
    46 #define P9_EMBEDDED(        derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
     46#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
    4747
    4848// special version, for structs that are declared in functions
    49 #define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase,        ) P9_EMBEDDED_BDY_( immedBase )
     49#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase )
    5050
    5151// forward declarations of both the above; generally not needed
    5252// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it
    53 #define P9_EMBEDDED_FWD(        derived, immedBase )      P9_EMBEDDED_DECL_( derived, immedBase, static ) ;
    54 #define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase,        ) ;
     53#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ;
     54#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ;
    5555
    5656// private helpers
    5757#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \
    58     forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
    59     STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this )
    60    
     58        forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
     59        STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this )
     60
    6161#define P9_EMBEDDED_BDY_( immedBase ) { \
    62         immedBase & ib = this; \
    63         Tbase & b = ib`inner; \
    64         tytagref(immedBase, Tbase) result = { b }; \
    65         return result; \
    66     }
     62                immedBase & ib = this; \
     63                Tbase & b = ib`inner; \
     64                tytagref(immedBase, Tbase) result = { b }; \
     65                return result; \
     66        }
    6767
    6868#define EMBEDDED_VIA( OUTER, MID, INNER ) \
    … …  
    8888
    8989#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.
    94     #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
     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.
     94        #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
    9595#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.
    100     #define ORIGIN_TAG_BITNO 0
     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.
     100        #define ORIGIN_TAG_BITNO 0
    101101#endif
    102102#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
    … …  
    109109forall( tE & ) {
    110110
    111     struct dlink{
    112         tE *next;
    113         tE *prev;
    114     };
    115 
    116     static inline void ?{}( dlink(tE) & this ) {
    117         this.next = 0p;
    118         this.prev = 0p;
    119     }
    120 
    121     forall( tLinks & = dlink(tE) )
    122     struct dlist {
    123         inline dlink(tE);
    124     };
    125 
    126     forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    127         static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
    128             dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
    129             ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
    130             size_t origin_addr = ((size_t) & lst) - link_offset;
    131             size_t preResult = ORIGIN_TAG_SET( origin_addr );
    132             return (tE *)preResult;
    133         }
    134 
    135         static inline void ?{}( dlist(tE, tLinks) & this ) {
    136             tE * listOrigin = $get_list_origin_addr( this );
    137             ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
    138         }
    139     }
     111        struct dlink{
     112                tE *next;
     113                tE *prev;
     114        };
     115
     116        static inline void ?{}( dlink(tE) & this ) {
     117                this.next = 0p;
     118                this.prev = 0p;
     119        }
     120
     121        forall( tLinks & = dlink(tE) )
     122        struct dlist {
     123                inline dlink(tE);
     124        };
     125
     126        forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
     127                static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
     128                        dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
     129                        ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
     130                        size_t origin_addr = ((size_t) & lst) - link_offset;
     131                        size_t preResult = ORIGIN_TAG_SET( origin_addr );
     132                        return (tE *)preResult;
     133                }
     134
     135                static inline void ?{}( dlist(tE, tLinks) & this ) {
     136                        tE * listOrigin = $get_list_origin_addr( this );
     137                        ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
     138                }
     139        }
    140140
    141141}
    … …  
    147147                verify (&list_pos != 0p);
    148148                verify (&to_insert != 0p);
    149         dlink(tE) & linkToInsert = to_insert`inner;
     149                dlink(tE) & linkToInsert = to_insert`inner;
    150150                verify(linkToInsert.prev == 0p);
    151151                verify(linkToInsert.next == 0p);
    152         tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
    153         dlink(tE) & list_pos_links = list_pos_elem`inner;
    154         asm( "" : : : "memory" );
    155         tE & after_raw = * list_pos_links.next;
    156         tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     152                tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
     153                dlink(tE) & list_pos_links = list_pos_elem`inner;
     154                asm( "" : : : "memory" );
     155                tE & after_raw = * list_pos_links.next;
     156                tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    157157                linkToInsert.prev = & list_pos;
    158158                linkToInsert.next = & after_raw;
    159         dlink(tE) & afterLinks = after_elem`inner;
    160         afterLinks.prev = &to_insert;
     159                dlink(tE) & afterLinks = after_elem`inner;
     160                afterLinks.prev = &to_insert;
    161161                list_pos_links.next = &to_insert;
    162         asm( "" : : : "memory" );
     162                asm( "" : : : "memory" );
    163163        }
    164164
    … …  
    166166                verify (&list_pos != 0p);
    167167                verify (&to_insert != 0p);
    168         dlink(tE) & linkToInsert = to_insert`inner;
     168                dlink(tE) & linkToInsert = to_insert`inner;
    169169                verify(linkToInsert.next == 0p);
    170170                verify(linkToInsert.prev == 0p);
    171         tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
    172         dlink(tE) & list_pos_links = list_pos_elem`inner;
    173         asm( "" : : : "memory" );
    174         tE & before_raw = * (list_pos_links).prev;
    175         tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     171                tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos );
     172                dlink(tE) & list_pos_links = list_pos_elem`inner;
     173                asm( "" : : : "memory" );
     174                tE & before_raw = * (list_pos_links).prev;
     175                tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    176176                linkToInsert.next = & list_pos;
    177177                linkToInsert.prev = & before_raw;
    178         dlink(tE) & beforeLinks = before_elem`inner;
    179         beforeLinks.next = &to_insert;
     178                dlink(tE) & beforeLinks = before_elem`inner;
     179                beforeLinks.next = &to_insert;
    180180                (list_pos_links).prev = &to_insert;
    181         asm( "" : : : "memory" );
     181                asm( "" : : : "memory" );
    182182        }
    183183
    184184        static inline tE & remove(tE & list_pos) {
    185185                verify (&list_pos != 0p);
    186         verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
    187         dlink(tE) & list_pos_links = list_pos`inner;
    188         tE & before_raw = * list_pos_links.prev;
    189         tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    190         dlink(tE) & before_links = before_elem`inner;
    191         tE & after_raw = * list_pos_links.next;
    192         tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    193         dlink(tE) & after_links = after_elem`inner;
    194         before_links.next = &after_raw;
    195         after_links.prev = &before_raw;
    196         asm( "" : : : "memory" );
     186                verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
     187                dlink(tE) & list_pos_links = list_pos`inner;
     188                tE & before_raw = * list_pos_links.prev;
     189                tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     190                dlink(tE) & before_links = before_elem`inner;
     191                tE & after_raw = * list_pos_links.next;
     192                tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     193                dlink(tE) & after_links = after_elem`inner;
     194                before_links.next = &after_raw;
     195                after_links.prev = &before_raw;
     196                asm( "" : : : "memory" );
    197197                list_pos_links.prev = 0p;
    198198                list_pos_links.next = 0p;
    199         asm( "" : : : "memory" );
    200         return list_pos;
    201         }
    202 
    203     static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
    204         tE * firstPtr = lst.next;
    205         if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    206         return *firstPtr;
    207     }
    208     static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
    209         tE * lastPtr = lst.prev;
    210         if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
    211         return *lastPtr;
    212     }
    213 
    214     static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
    215         tE * firstPtr = lst.next;
    216         if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    217         return firstPtr == 0p;
    218     }
    219 
    220     static inline bool ?`isListed( tE & e ) {
     199                asm( "" : : : "memory" );
     200                return list_pos;
     201        }
     202
     203        static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
     204                tE * firstPtr = lst.next;
     205                if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     206                return *firstPtr;
     207        }
     208        static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
     209                tE * lastPtr = lst.prev;
     210                if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
     211                return *lastPtr;
     212        }
     213
     214        static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
     215                tE * firstPtr = lst.next;
     216                if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     217                return firstPtr == 0p;
     218        }
     219
     220        static inline bool ?`isListed( tE & e ) {
    221221                verify (&e != 0p);
    222         dlink(tE) & e_links = e`inner;
     222                dlink(tE) & e_links = e`inner;
    223223                return (e_links.prev != 0p) || (e_links.next != 0p);
    224     }
    225 
    226     static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
    227         tE * origin = $get_list_origin_addr( lst );
    228         return *origin;
    229     }
    230 
    231     static inline bool ?`moveNext( tE && refx ) {
    232         tE && ref_inner = refx;
    233         tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    234         &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 ) {
    240         tE && ref_inner = refx;
    241         tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    242         &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 ) {
    248         return e`moveNext;
    249     }
    250 
    251     static inline bool ?`hasPrev( tE & e ) {
    252         return e`movePrev;
    253     }
    254 
    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 ) {
    274         tE & first_inlist = lst`first;
    275         tE & first_item = first_inlist;
    276         if (&first_item) remove(first_inlist);
    277         return first_item;
    278     }
    279 
    280     static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
    281         tE & last_inlist = lst`last;
    282         tE & last_item = last_inlist;
    283         if (&last_item) remove(last_inlist);
    284         return last_item;
    285     }
     224        }
     225
     226        static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
     227                tE * origin = $get_list_origin_addr( lst );
     228                return *origin;
     229        }
     230
     231        static inline bool ?`moveNext( tE && refx ) {
     232                tE && ref_inner = refx;
     233                tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     234                &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 ) {
     240                tE && ref_inner = refx;
     241                tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     242                &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 ) {
     248                return e`moveNext;
     249        }
     250
     251        static inline bool ?`hasPrev( tE & e ) {
     252                return e`movePrev;
     253        }
     254
     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 ) {
     274                tE & first_inlist = lst`first;
     275                tE & first_item = first_inlist;
     276                if (&first_item) remove(first_inlist);
     277                return first_item;
     278        }
     279
     280        static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
     281                tE & last_inlist = lst`last;
     282                tE & last_item = last_inlist;
     283                if (&last_item) remove(last_inlist);
     284                return last_item;
     285        }
    286286
    287287
    288288  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
    289289        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
    290         if ( ! & this`first ) return ( (& this`last) == 0p);
    291 
    292         tE & lagElem = *0p;
    293 
    294         while ( tE & it = this`elems; it`moveNext ) {
    295             if (& lagElem == 0p &&  &it != & this`first ) return false;
    296             & lagElem = & it;
    297         }
    298 
    299         if (& lagElem != & this`last) return false;
    300 
    301         // TODO: verify that it is back at this`elems;
    302         return true;
     290                if ( ! & this`first ) return ( (& this`last) == 0p);
     291
     292                tE & lagElem = *0p;
     293
     294                while ( tE & it = this`elems; it`moveNext ) {
     295                        if (& lagElem == 0p &&  &it != & this`first ) return false;
     296                        & lagElem = & it;
     297                }
     298
     299                if (& lagElem != & this`last) return false;
     300
     301                // TODO: verify that it is back at this`elems;
     302                return true;
    303303        }
    304304        static bool $validate_rev( dlist(tE, tLinks) & this ) {
    305         if ( ! & this`last ) return ( (& this`first) == 0p);
    306 
    307         tE & lagElem = *0p;
    308 
    309         while ( tE & it = this`elems; it`movePrev ) {
    310             if (& lagElem == 0p &&  &it != & this`last ) return false;
    311             & lagElem = & it;
    312         }
    313 
    314         if (& lagElem != & this`first) return false;
    315 
    316         // TODO: verify that it is back at this`elems;
    317         return true;
     305                if ( ! & this`last ) return ( (& this`first) == 0p);
     306
     307                tE & lagElem = *0p;
     308
     309                while ( tE & it = this`elems; it`movePrev ) {
     310                        if (& lagElem == 0p &&  &it != & this`last ) return false;
     311                        & lagElem = & it;
     312                }
     313
     314                if (& lagElem != & this`first) return false;
     315
     316                // TODO: verify that it is back at this`elems;
     317                return true;
    318318        }
    319319        static inline bool validate( dlist(tE, tLinks) & this ) {
Note: See TracChangeset for help on using the changeset viewer.