Changeset 1e5cd9a for libcfa


Ignore:
Timestamp:
May 12, 2021, 1:37:09 PM (3 years ago)
Author:
Thierry Delisle <tdelisle@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
8cd40bf
Parents:
1680072 (diff), 7d51ef8 (diff)
Note: this is a merge changeset, the changes displayed below correspond to the merge itself.
Use the (diff) links above to see all the changes relative to each parent.
Message:

Merge branch 'master' of plg.uwaterloo.ca:software/cfa/cfa-cc

File:
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/containers/list2.hfa

    r1680072 r1e5cd9a  
    1818#include <assert.h>
    1919
    20 forall( T & ) struct tag {};
    21 #define ttag(T) ((tag(T)){})
    22 #define ztag(n) ttag(Z(n))
    23 
    24 extern "C" {
    25     void * memset ( void * ptr, int value, size_t num );
    26 }
    27 
    28 trait embedded( tOuter &, tInner & ) {
    29     tInner & ?`inner( tOuter & );
     20forall( Decorator &, T & )
     21struct tytagref {
     22    inline T &;
    3023};
    3124
    32 // embedded is reflexive
    33 forall( tX & )
    34 static inline tX & ?`inner( tX & this ) { return this; }
     25trait embedded( tOuter &, tMid &, tInner & ) {
     26    tytagref( tMid, tInner ) ?`inner( tOuter & );
     27};
     28
     29// embedded is reflexive, with no info (void) as the type tag
     30forall (T &)
     31tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
    3532
    3633// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
    37 #define P9_EMBEDDED( tOuter, tInner ) \
    38    static inline tInner & ?`inner( tOuter & this ) { return this; }
     34#define P9_EMBEDDED( derived, immedBase ) \
     35forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
     36    static inline tytagref(immedBase, Tbase) ?`inner( derived & this ) { \
     37        immedBase & ib = this; \
     38        Tbase & b = ib`inner; \
     39        tytagref(immedBase, Tbase) result = { b }; \
     40        return result; \
     41    }
     42
     43#define EMBEDDED_VIA( OUTER, MID, INNER ) \
     44   (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
     45
     46#define DLINK_VIA( TE, TLINK ) \
     47   EMBEDDED_VIA( TE, TLINK, dlink(TE) )
    3948
    4049
    … …  
    8594    }
    8695
    87     forall( tLinks & = tE ) {
    88 
    89         struct dlist {
    90             inline dlink(tE);
    91         };
    92 
    93         struct diref {
    94             inline tE &;
    95         };
    96     }
    97 
    98     forall( tLinks & = tE | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
     96    forall( tLinks & = dlink(tE) )
     97    struct dlist {
     98        inline dlink(tE);
     99    };
     100
     101    forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    99102        static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
    100             dlink(tE) & link_from_null = ( * (tE *) 0p )`inner`inner;
     103            dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
    101104            ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
    102105            size_t origin_addr = ((size_t) & lst) - link_offset;
    … …  
    109112            ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
    110113        }
    111 
    112         // redundant
    113         // void ?{}( diref(tE, tLinks) & this, tE & target ) {
    114         //     tE && ref = this;
    115         //     &ref = &target;
    116         // }
    117114    }
    118115
    … …  
    120117
    121118
    122 forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) {
    123 
    124         static inline void insert_after(diref(tE, tLinks) list_pos, tE &to_insert) {
     119forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
     120
     121        static inline void insert_after(tE & list_pos, tE &to_insert) {
    125122                verify (&list_pos != 0p);
    126123                verify (&to_insert != 0p);
    127         dlink(tE) & linkToInsert = to_insert`inner`inner;
     124        dlink(tE) & linkToInsert = to_insert`inner;
    128125                verify(linkToInsert.prev == 0p);
    129126                verify(linkToInsert.next == 0p);
    130127        tE & list_pos_raw = list_pos;
    131128        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
    132         asm( "" : : : "memory" );
    133         tE & after_raw = * (list_pos_elem`inner`inner).next;
     129        dlink(tE) & list_pos_links = list_pos_elem`inner;
     130        asm( "" : : : "memory" );
     131        tE & after_raw = * list_pos_links.next;
    134132        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    135133                linkToInsert.prev = & list_pos_raw;
    136134                linkToInsert.next = & after_raw;
    137         (after_elem`inner`inner).prev = &to_insert;
    138                 (list_pos_elem`inner`inner).next = &to_insert;
    139         asm( "" : : : "memory" );
    140         }
    141 
    142         static inline void insert_before(diref(tE, tLinks) list_pos, tE &to_insert) {
     135        dlink(tE) & afterLinks = after_elem`inner;
     136        afterLinks.prev = &to_insert;
     137                list_pos_links.next = &to_insert;
     138        asm( "" : : : "memory" );
     139        }
     140
     141        static inline void insert_before(tE & list_pos, tE &to_insert) {
    143142                verify (&list_pos != 0p);
    144143                verify (&to_insert != 0p);
    145         dlink(tE) & linkToInsert = to_insert`inner`inner;
     144        dlink(tE) & linkToInsert = to_insert`inner;
    146145                verify(linkToInsert.next == 0p);
    147146                verify(linkToInsert.prev == 0p);
    148147        tE & list_pos_raw = list_pos;
    149148        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
    150         asm( "" : : : "memory" );
    151         tE & before_raw = * (list_pos_elem`inner`inner).prev;
     149        dlink(tE) & list_pos_links = list_pos_elem`inner;
     150        asm( "" : : : "memory" );
     151        tE & before_raw = * (list_pos_links).prev;
    152152        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    153153                linkToInsert.next = & list_pos_raw;
    154154                linkToInsert.prev = & before_raw;
    155         (before_elem`inner`inner).next = &to_insert;
    156                 (list_pos_elem`inner`inner).prev = &to_insert;
    157         asm( "" : : : "memory" );
    158         }
    159 
    160         static inline tE & remove(diref(tE, tLinks) list_pos) {
     155        dlink(tE) & beforeLinks = before_elem`inner;
     156        beforeLinks.next = &to_insert;
     157                (list_pos_links).prev = &to_insert;
     158        asm( "" : : : "memory" );
     159        }
     160
     161        static inline tE & remove(tE & list_pos) {
    161162                verify (&list_pos != 0p);
    162163        tE & list_pos_elem = list_pos;
    163164        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
    164         dlink(tE) & list_pos_links = list_pos_elem`inner`inner;
     165        dlink(tE) & list_pos_links = list_pos_elem`inner;
    165166        tE & before_raw = * list_pos_links.prev;
    166167        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    167         dlink(tE) & before_links = before_elem`inner`inner;
     168        dlink(tE) & before_links = before_elem`inner;
    168169        tE & after_raw = * list_pos_links.next;
    169170        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    170         dlink(tE) & after_links = after_elem`inner`inner;
     171        dlink(tE) & after_links = after_elem`inner;
    171172        before_links.next = &after_raw;
    172173        after_links.prev = &before_raw;
    … …  
    178179        }
    179180
    180     static inline diref(tE, tLinks) ?`first( dlist(tE, tLinks) &lst ) {
     181    static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
    181182        tE * firstPtr = lst.next;
    182183        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
    183         diref(tE, tLinks) ret = { *firstPtr };
    184         return ret;
    185     }
    186     static inline diref(tE, tLinks) ?`last ( dlist(tE, tLinks) &lst ) {
     184        return *firstPtr;
     185    }
     186    static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
    187187        tE * lastPtr = lst.prev;
    188188        if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
    189         diref(tE, tLinks) ret = { *lastPtr };
    190         return ret;
    191     }
    192 
    193     static inline int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) {
    194         tE & list_pos_elem = list_pos;
    195         if (ORIGIN_TAG_QUERY((size_t) & list_pos_elem)) return 0;
    196         return & list_pos_elem != 0p;
    197     }
    198 
    199     static inline int DUMB_COMPARE( diref(tE, tLinks) list_pos, tE * elem ) {
    200         tE & signifiedLhs = list_pos;
    201         return &signifiedLhs == elem;
    202     }
    203 
    204     static inline diref(tE, tLinks) ?`from( tE & elem ) {
    205         diref(tE, tLinks) ret = { elem };
    206         return ret;
    207     }
    208 
    209     static inline diref(tE, tLinks) ?`elems( dlist(tE, tLinks) & lst ) {
     189        return *lastPtr;
     190    }
     191
     192    static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) {
     193        tE * firstPtr = lst.next;
     194        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     195        return firstPtr == 0p;
     196    }
     197
     198    static inline tE & ?`elems( dlist(tE, tLinks) & lst ) {
    210199        tE * origin = $get_list_origin_addr( lst );
    211         diref(tE, tLinks) ret = { *origin };
    212         return ret;
    213     }
    214 
    215     static inline bool ?`moveNext( diref(tE, tLinks) & refx ) {
     200        return *origin;
     201    }
     202
     203    static inline bool ?`moveNext( tE && refx ) {
    216204        tE && ref_inner = refx;
    217205        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    218         &ref_inner = oldReferent`inner`inner.next;
     206        &ref_inner = oldReferent`inner.next;
    219207        return &ref_inner != 0p  &&
    220208            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
    221209    }
    222210
    223     static inline bool ?`movePrev( diref(tE, tLinks) & refx ) {
     211    static inline bool ?`movePrev( tE && refx ) {
    224212        tE && ref_inner = refx;
    225213        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    226         &ref_inner = oldReferent`inner`inner.prev;
     214        &ref_inner = oldReferent`inner.prev;
    227215        return &ref_inner != 0p  &&
    228216            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
    229217    }
    230218
     219    static inline bool ?`hasNext( tE & e ) {
     220        return e`moveNext;
     221    }
     222
     223    static inline bool ?`hasPrev( tE & e ) {
     224        return e`movePrev;
     225    }
     226
     227    static inline tE & ?`next( tE & e ) {
     228        if( e`moveNext ) return e;
     229        return * 0p;
     230    }
     231
     232    static inline tE & ?`prev( tE & e ) {
     233        if( e`movePrev ) return e;
     234        return * 0p;
     235    }
     236
    231237    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    232238        insert_after(lst`elems, e);
    … …  
    235241    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    236242        insert_before(lst`elems, e);
     243    }
     244
     245    static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) {
     246        tE & first_inlist = lst`first;
     247        tE & first_item = first_inlist;
     248        if (&first_item) remove(first_inlist);
     249        return first_item;
     250    }
     251
     252    static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) {
     253        tE & last_inlist = lst`last;
     254        tE & last_item = last_inlist;
     255        if (&last_item) remove(last_inlist);
     256        return last_item;
    237257    }
    238258
    … …  
    244264        tE & lagElem = *0p;
    245265
    246         while ( diref(tE, tLinks) it = this`elems; it`moveNext ) {
     266        while ( tE & it = this`elems; it`moveNext ) {
    247267            if (& lagElem == 0p &&  &it != & this`first ) return false;
    248268            & lagElem = & it;
    … …  
    259279        tE & lagElem = *0p;
    260280
    261         while ( diref(tE, tLinks) it = this`elems; it`movePrev ) {
     281        while ( tE & it = this`elems; it`movePrev ) {
    262282            if (& lagElem == 0p &&  &it != & this`last ) return false;
    263283            & lagElem = & it;
    … …  
    276296}
    277297
    278 forall( tE & | embedded( tE, dlink(tE) ) ) {
    279         static inline void insert_after(tE & list_pos, tE &to_insert ) {
    280         diref(tE, tE) list_pos_ref = list_pos`from;
    281         insert_after( list_pos_ref, to_insert );
    282     }
    283         static inline void insert_before(tE & list_pos, tE &to_insert ) {
    284         diref(tE, tE) list_pos_ref = list_pos`from;
    285         insert_before( list_pos_ref, to_insert );
    286     }
    287         static inline tE & remove(tE & list_pos ) {
    288         diref(tE, tE) list_pos_ref = list_pos`from;
    289         return remove( list_pos_ref );
    290     }
    291     static inline bool ?`moveNext( tE && ref ) {
    292         diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
    293         return ref_dird`moveNext;
    294     }
    295     static inline bool ?`movePrev( tE && ref ) {
    296         diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref;
    297         return ref_dird`movePrev;
    298     }
    299 
    300 }
Note: See TracChangeset for help on using the changeset viewer.