Changeset 6cbc5a62 for libcfa


Ignore:
Timestamp:
Mar 24, 2026, 10:50:51 PM (7 days ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
master
Children:
e426c6f
Parents:
402f249
Message:

add tuple-type insert and remove functions to list type

Location:
libcfa/src/collections
Files:
2 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/collections/list.hfa

    r402f249 r6cbc5a62  
    1010// Created On       : Wed Apr 22 18:00:00 2020
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Aug  7 10:46:08 2025
    13 // Update Count     : 75
     12// Last Modified On : Tue Mar 24 11:25:34 2026
     13// Update Count     : 98
    1414//
    1515
    … …  
    7272
    7373// 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 "advance" as
    75 // the first step, and uses the return of "advance" 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
    80 // part), by failing fast.
     74// and at the end of iteration, signifying, "no more elements."  Normal comsumption of an iterator runs "advance" as the
     75// first step, and uses the return of "advance" as a guard, before dereferencing the iterator.  So normal consumption of
     76// an iterator does not dereference an iterator in origin position.  The value of a pointer (underlying a refence) that
     77// is exposed publicly as an iteraor, and also a pointer stored internally in a link field, is tagged, to indicate "is
     78// the origin" (internally, is the list-head sentinel node), or untagged, to indicate "is a regular node."  Intent is to
     79// help a user who dereferences an iterator in origin position (which would be an API-use error on their part), by
     80// failing fast.
    8181
    8282#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode
    8383
    84     // With origin tagging disabled, iteration never reports "no more elements."
    85     // In this mode, the list API is buggy.
    86     // This mode is used to quantify the cost of the normal tagging scheme.
    87 
    88     #define ORIGIN_TAG_SET(p)   (p)
    89     #define ORIGIN_TAG_CLEAR(p) (p)
    90     #define ORIGIN_TAG_QUERY(p) 0
    91     #define ORIGIN_TAG_ASGN(p, v) (p)
    92     #define ORIGIN_TAG_EITHER(p, v) (p)
    93     #define ORIGIN_TAG_NEQ(v1, v2) 0
     84        // With origin tagging disabled, iteration never reports "no more elements."
     85        // In this mode, the list API is buggy.
     86        // This mode is used to quantify the cost of the normal tagging scheme.
     87
     88        #define ORIGIN_TAG_SET(p)   (p)
     89        #define ORIGIN_TAG_CLEAR(p) (p)
     90        #define ORIGIN_TAG_QUERY(p) 0
     91        #define ORIGIN_TAG_ASGN(p, v) (p)
     92        #define ORIGIN_TAG_EITHER(p, v) (p)
     93        #define ORIGIN_TAG_NEQ(v1, v2) 0
    9494
    9595#else // Normal
    9696
    97     #if defined( __x86_64 )
    98         // Preferred case: tag in the most-significant bit.  Dereference
    99         // has been shown to segfault consistently.  Maintenance should
    100         // list more architectures as "ok" here, to let them use the
    101         // preferred case, when valid.
    102         #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
    103     #else
    104         // Fallback case: tag in the least-significant bit.  Dereference
    105         // will often give an alignment error, but may not, e.g. if
    106         // accessing a char-typed member.  32-bit x86 uses the most-
    107         // significant bit for real room on the heap.
    108         #define ORIGIN_TAG_BITNO 0
    109     #endif
    110 
    111     #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
    112 
    113     #define ORIGIN_TAG_SET(p) ((p) |  ORIGIN_TAG_MASK)
    114     #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
    115     #define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
    116 
    117     #define ORIGIN_TAG_ASGN(p, v) ( \
    118         verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \
    119         ORIGIN_TAG_EITHER((p), (v)) \
    120     )
    121 
    122     #define ORIGIN_TAG_EITHER(p, v) ( \
    123         verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \
    124         ( (p) | (v) ) \
    125     )
    126 
    127     #define ORIGIN_TAG_NEQ(v1, v2) ( \
    128         verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \
    129         verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \
    130         ( (v1) ^ (v2) ) \
    131     )
     97        #if defined( __x86_64 )
     98                // Preferred case: tag in the most-significant bit.  Dereference
     99                // has been shown to segfault consistently.  Maintenance should
     100                // list more architectures as "ok" here, to let them use the
     101                // preferred case, when valid.
     102                #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
     103        #else
     104                // Fallback case: tag in the least-significant bit.  Dereference
     105                // will often give an alignment error, but may not, e.g. if
     106                // accessing a char-typed member.  32-bit x86 uses the most-
     107                // significant bit for real room on the heap.
     108                #define ORIGIN_TAG_BITNO 0
     109        #endif
     110
     111        #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
     112
     113        #define ORIGIN_TAG_SET(p) ((p) |  ORIGIN_TAG_MASK)
     114        #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
     115        #define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
     116
     117        #define ORIGIN_TAG_ASGN(p, v) ( \
     118                verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \
     119                ORIGIN_TAG_EITHER((p), (v)) \
     120        )
     121
     122        #define ORIGIN_TAG_EITHER(p, v) ( \
     123                verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \
     124                ( (p) | (v) ) \
     125        )
     126
     127        #define ORIGIN_TAG_NEQ(v1, v2) ( \
     128                verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \
     129                verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \
     130                ( (v1) ^ (v2) ) \
     131        )
    132132
    133133#endif
    134134
    135135
    136 
    137136#ifdef __EXPERIMENTAL_LOOSE_SINGLES__ // Perf experimention alt mode
    138137
    139     // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element,
    140     // it must not be listed already" checking.  The user must know separately whether an element is listed.
    141     // Other than inserting it, any list-api action on an unlisted element is undefined.  Notably, list iteration
    142     // starting from an unlisted element is not defined to respond "no more elements," and may instead continue
    143     // iterating from a formerly occupied list position.  This mode matches LQ usage.
    144 
    145     #define NOLOOSE(...)
    146     #define LOOSEONLY(...) __VA_ARGS__
     138        // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element,
     139        // it must not be listed already" checking.  The user must know separately whether an element is listed.
     140        // Other than inserting it, any list-api action on an unlisted element is undefined.  Notably, list iteration
     141        // starting from an unlisted element is not defined to respond "no more elements," and may instead continue
     142        // iterating from a formerly occupied list position.  This mode matches LQ usage.
     143
     144        #define NOLOOSE(...)
     145        #define LOOSEONLY(...) __VA_ARGS__
    147146
    148147#else // Normal
    149148
    150     #define NOLOOSE(...) __VA_ARGS__
    151     #define LOOSEONLY(...)
     149        #define NOLOOSE(...) __VA_ARGS__
     150        #define LOOSEONLY(...)
    152151
    153152#endif
    … …  
    190189static inline forall( tE &, tLinks & | embedded( tE, tLinks, dlink( tE ) ) ) {
    191190        bool isListed( tE & node ) {
    192       NOLOOSE(
     191          NOLOOSE(
    193192                verify( &node != 0p );
    194193                dlink( tE ) & node_links = node`inner;
    … …  
    196195          )
    197196          LOOSEONLY(
    198         verify(false && "isListed is undefined");
     197                verify(false && "isListed is undefined");
    199198                return true;
    200199          )
    … …  
    224223
    225224                dlink( tE ) & linkToInsert = node`inner;
    226       NOLOOSE(
     225          NOLOOSE(
    227226                verify( linkToInsert.next == 0p );
    228227                verify( linkToInsert.prev == 0p );
    … …  
    242241                return node;
    243242        }
     243        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     244        forall( List ... | { void insert_before( tE & before, List ); } )
     245        void insert_before( tE & before, tE * node, List args ) {
     246                insert_before( before, *node );
     247                insert_before( before, args );
     248        }
     249        void insert_before( tE & before, tE * node ) {
     250                insert_before( before, *node );
     251        }
    244252
    245253        tE & insert_after( tE & after, tE & node ) {
    … …  
    248256
    249257                dlink( tE ) & linkToInsert = node`inner;
    250       NOLOOSE(
     258          NOLOOSE(
    251259                verify( linkToInsert.prev == 0p );
    252260                verify( linkToInsert.next == 0p );
    … …  
    265273                asm( "" : : : "memory" );
    266274                return node;
     275        }
     276        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     277        forall( List ... | { void insert_after( tE & after, List ); } )
     278        void insert_after( tE & after, tE * node, List args ) {
     279                insert_after( after, *node );
     280                insert_after( after, args );
     281        }
     282        void insert_after( tE & after, tE * node ) {
     283                insert_after( after, *node );
    267284        }
    268285
    … …  
    281298                after_links.prev = &before_raw;
    282299
    283       NOLOOSE(
     300          NOLOOSE(
    284301                asm( "" : : : "memory" );
    285302                list_pos_links.prev = 0p;
    … …  
    288305          )
    289306                return node;
     307        }
     308        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     309        forall( List ... | { void remove( List ); } )
     310        void remove( tE * node, List args ) {
     311                remove( *node );
     312                remove( args );
     313        }
     314        void remove( tE * node ) {
     315                remove( *node );
    290316        }
    291317
    … …  
    309335        }
    310336
    311     bool isFirst( tE & node ) {
    312         return recede( node );
    313     }
    314 
    315     bool isLast( tE & node ) {
    316         return advance( node );
     337        bool isFirst( tE & node ) {
     338                return recede( node );
     339        }
     340
     341        bool isLast( tE & node ) {
     342                return advance( node );
    317343    }
    318344
    … …  
    331357                return node;
    332358        }
     359        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     360        forall( List ... | { void insert_first( dlist( tE, tLinks ) & list, List ); } )
     361        void insert_first( dlist( tE, tLinks ) & list, tE * node, List args ) {
     362                insert_first( list, *node );
     363                insert_first( list, args );
     364        }
     365        void insert_first( dlist( tE, tLinks ) & list, tE * node ) {
     366                insert_first( list, *node );
     367        }
    333368
    334369        tE & insert_last( dlist( tE, tLinks ) & list, tE & node ) {
    … …  
    336371                return node;
    337372        }
     373        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     374        forall( List ... | { void insert_last( dlist( tE, tLinks ) & list, List ); } )
     375        void insert_last( dlist( tE, tLinks ) & list, tE * node, List args ) {
     376                insert_last( list, *node );
     377                insert_last( list, args );
     378        }
     379        void insert_last( dlist( tE, tLinks ) & list, tE * node ) {
     380                insert_last( list, *node );
     381        }
     382
    338383        tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // synonym for insert_last
    339384                insert_last( list, node );
    340385                return node;
     386        }
     387        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     388        forall( List ... | { void insert( dlist( tE, tLinks ) & list, List ); } )
     389        void insert( dlist( tE, tLinks ) & list, tE * node, List args ) {
     390                insert( list, *node );
     391                insert( list, args );
     392        }
     393        void insert( dlist( tE, tLinks ) & list, tE * node ) {
     394                insert( list, *node );
    341395        }
    342396

  • libcfa/src/collections/list2.hfa

    r402f249 r6cbc5a62  
    1919// Created On       : Wed Apr 22 18:00:00 2020
    2020// Last Modified By : Peter A. Buhr
    21 // Last Modified On : Thu Feb  2 11:32:26 2023
    22 // Update Count     : 2
     21// Last Modified On : Tue Mar 24 22:20:56 2026
     22// Update Count     : 8
    2323//
    2424
    … …  
    2929forall( Decorator &, T & )
    3030struct tytagref {
    31     inline T &;
     31        inline T &;
    3232};
    3333
    3434forall( tOuter &, tMid &, tInner & )
    3535trait embedded {
    36     tytagref( tMid, tInner ) ?`inner( tOuter & );
     36        tytagref( tMid, tInner ) ?`inner( tOuter & );
    3737};
    3838
    3939// embedded is reflexive, with no info (void) as the type tag
    40 forall (T &)
     40forall( T & )
    4141static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
    4242
    … …  
    4646//
    4747// struct foo {
    48 //    int a, b, c;
    49 //    inline (bar);
     48//      int a, b, c;
     49//      inline (bar);
    5050// };
    5151// P9_EMBEDDED( foo, bar )
    … …  
    5353
    5454// usual version, for structs that are top-level declarations
    55 #define P9_EMBEDDED(        derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
     55#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase )
    5656
    5757// special version, for structs that are declared in functions
    58 #define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase,        ) P9_EMBEDDED_BDY_( immedBase )
     58#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase )
    5959
    6060// forward declarations of both the above; generally not needed
    6161// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it
    62 #define P9_EMBEDDED_FWD(        derived, immedBase )      P9_EMBEDDED_DECL_( derived, immedBase, static ) ;
    63 #define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase,        ) ;
     62#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ;
     63#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ;
    6464
    6565// private helpers
    6666#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \
    67     forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
    68     STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this )
    69    
     67        forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \
     68        STORAGE inline tytagref( immedBase, Tbase ) ?`inner( derived & this )
     69
    7070#define P9_EMBEDDED_BDY_( immedBase ) { \
    71         immedBase & ib = this; \
    72         Tbase & b = ib`inner; \
    73         tytagref(immedBase, Tbase) result = { b }; \
    74         return result; \
    75     }
    76 
    77 #define EMBEDDED_VIA( OUTER, MID, INNER ) \
    78    (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
    79 
    80 #define DLINK_VIA( TE, TLINK ) \
    81    EMBEDDED_VIA( TE, TLINK, dlink(TE) )
    82 
    83 // The origin is the position encountered at the start of iteration,
    84 // signifying, "need to advance to the first element," and at the end
    85 // of iteration, signifying, "no more elements."  Normal comsumption of
    86 // an iterator runs advance as the first step, and uses the return
    87 // of advance as a guard, before dereferencing the iterator.  So
    88 // normal consumption of an iterator does not dereference an iterator
    89 // in origin position.  The value of a pointer (underlying a refence)
    90 // that is exposed publicly as an iteraor, and also a pointer stored
    91 // internally in a link field, is tagged, to indicate "is the origin"
    92 // (internally, is the list-head sentinel node), or untagged, to indicate
    93 // "is a regular node."  Intent is to help a user who dereferences an
    94 // iterator in origin position (which would be an API-use error on their
    95 // part), by failing fast.
     71                immedBase & ib = this; \
     72                Tbase & b = ib`inner; \
     73                tytagref( immedBase, Tbase ) result = { b }; \
     74                return result; \
     75        }
     76
     77#define EMBEDDED_VIA( OUTER, MID, INNER ) (struct { tytagref( MID, INNER ) ( * ?`inner ) ( OUTER & ); }){ ?`inner }
     78
     79#define DLINK_VIA( TE, TLINK ) EMBEDDED_VIA( TE, TLINK, dlink( TE ) )
     80
     81
     82// The origin is the position encountered at the start of iteration, signifying, "need to advance to the first element,"
     83// and at the end of iteration, signifying, "no more elements."  Normal comsumption of an iterator runs "advance" as the
     84// first step, and uses the return of "advance" as a guard, before dereferencing the iterator.  So normal consumption of
     85// an iterator does not dereference an iterator in origin position.  The value of a pointer (underlying a refence) that
     86// is exposed publicly as an iteraor, and also a pointer stored internally in a link field, is tagged, to indicate "is
     87// the origin" (internally, is the list-head sentinel node), or untagged, to indicate "is a regular node."  Intent is to
     88// help a user who dereferences an iterator in origin position (which would be an API-use error on their part), by
     89// failing fast.
    9690
    9791#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode
    9892
    99     // With origin tagging disabled, iteration never reports "no more elements."
    100     // In this mode, the list API is buggy.
    101     // This mode is used to quantify the cost of the normal tagging scheme.
    102 
    103     #define ORIGIN_TAG_ENABL(p)   (p)
    104     #define ORIGIN_TAG_CLEAR(p) (p)
    105     #define ORIGIN_TAG_QUERY(p) 0
    106     #define ORIGIN_TAG_ASGN(p, v) (p)
    107     #define ORIGIN_TAG_EITHER(p, v) (p)
    108     #define ORIGIN_TAG_NEQ(v1, v2) 0
    109 
    110     #define TAGSONLY(...)
    111     #define NOTAGS(...) __VA_ARGS__
     93        // With origin tagging disabled, iteration never reports "no more elements."
     94        // In this mode, the list API is buggy.
     95        // This mode is used to quantify the cost of the normal tagging scheme.
     96
     97        #define ORIGIN_TAG_ENABL(p)   (p)
     98        #define ORIGIN_TAG_CLEAR(p) (p)
     99        #define ORIGIN_TAG_QUERY(p) 0
     100        #define ORIGIN_TAG_ASGN(p, v) (p)
     101        #define ORIGIN_TAG_EITHER(p, v) (p)
     102        #define ORIGIN_TAG_NEQ(v1, v2) 0
     103
     104        #define TAGSONLY(...)
     105        #define NOTAGS(...) __VA_ARGS__
    112106
    113107#else // Normal
    114108
    115     #if defined( __x86_64 )
    116         // Preferred case: tag in the most-significant bit.  Dereference
    117         // has been shown to segfault consistently.  Maintenance should
    118         // list more architectures as "ok" here, to let them use the
    119         // preferred case, when valid.
    120         #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
    121     #else
    122         // Fallback case: tag in the least-significant bit.  Dereference
    123         // will often give an alignment error, but may not, e.g. if
    124         // accessing a char-typed member.  32-bit x86 uses the most-
    125         // significant bit for real room on the heap.
    126         #define ORIGIN_TAG_BITNO 0
    127     #endif
    128 
    129     #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
    130 
    131     #define ORIGIN_TAG_ENABL(p) ((p) |  ORIGIN_TAG_MASK)
    132     #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
    133     #define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
    134 
    135     #define ORIGIN_TAG_ASGN(p, v) ( \
    136         verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \
    137         ORIGIN_TAG_EITHER((p), (v)) \
    138     )
    139 
    140     #define ORIGIN_TAG_EITHER(p, v) ( \
    141         verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \
    142         ( (p) | (v) ) \
    143     )
    144 
    145     #define ORIGIN_TAG_NEQ(v1, v2) ( \
    146         verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \
    147         verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \
    148         ( (v1) ^ (v2) ) \
    149     )
    150 
    151     #define TAGSONLY(...) __VA_ARGS__
    152     #define NOTAGS(...)
     109        #if defined( __x86_64 )
     110                // Preferred case: tag in the most-significant bit.  Dereference
     111                // has been shown to segfault consistently.  Maintenance should
     112                // list more architectures as "ok" here, to let them use the
     113                // preferred case, when valid.
     114                #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
     115        #else
     116                // Fallback case: tag in the least-significant bit.  Dereference
     117                // will often give an alignment error, but may not, e.g. if
     118                // accessing a char-typed member.  32-bit x86 uses the most-
     119                // significant bit for real room on the heap.
     120                #define ORIGIN_TAG_BITNO 0
     121        #endif
     122
     123        #define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
     124
     125        #define ORIGIN_TAG_ENABL(p) ((p) |  ORIGIN_TAG_MASK)
     126        #define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
     127        #define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
     128
     129        #define ORIGIN_TAG_ASGN(p, v) ( \
     130                verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \
     131                ORIGIN_TAG_EITHER((p), (v)) \
     132        )
     133
     134        #define ORIGIN_TAG_EITHER(p, v) ( \
     135                verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \
     136                ( (p) | (v) ) \
     137        )
     138
     139        #define ORIGIN_TAG_NEQ(v1, v2) ( \
     140                verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \
     141                verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \
     142                ( (v1) ^ (v2) ) \
     143        )
     144
     145        #define TAGSONLY(...) __VA_ARGS__
     146        #define NOTAGS(...)
    153147
    154148#endif
    155149
    156150
    157 
    158 
    159 
    160 
    161151#ifdef __EXPERIMENTAL_LOOSE_SINGLES__ // Perf experimention alt mode
    162152
    163     // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element,
    164     // it must not be listed already" checking.  The user must know separately whether an element is listed.
    165     // Other than inserting it, any list-api action on an unlisted element is undefined.  Notably, list iteration
    166     // starting from an unlisted element is not defined to respond "no more elements," and may instead continue
    167     // iterating from a formerly occupied list position.  This mode matches LQ usage.
    168 
    169     #define NOLOOSE(...)
    170     #define LOOSEONLY(...) __VA_ARGS__
     153        // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element,
     154        // it must not be listed already" checking.  The user must know separately whether an element is listed.
     155        // Other than inserting it, any list-api action on an unlisted element is undefined.  Notably, list iteration
     156        // starting from an unlisted element is not defined to respond "no more elements," and may instead continue
     157        // iterating from a formerly occupied list position.  This mode matches LQ usage.
     158
     159        #define NOLOOSE(...)
     160        #define LOOSEONLY(...) __VA_ARGS__
    171161
    172162#else // Normal
    173163
    174     #define NOLOOSE(...) __VA_ARGS__
    175     #define LOOSEONLY(...)
     164        #define NOLOOSE(...) __VA_ARGS__
     165        #define LOOSEONLY(...)
    176166
    177167#endif
    178168
    179169
    180 
    181 
    182 
    183 
    184 
    185 
    186170// struct workaround0_t {};
    187171
    188172forall( tE & ) {
    189 
    190     struct dlink;
    191 
    192     // do not use; presence of the field declaration unblocks ability to define dlink (#304)
    193     struct __dlink_selfref_workaround_t {
    194         dlink(tE) *ref_notSelfRef;
    195     };
    196 
    197     struct dlink {
    198         dlink(tE) *next;  // TODO: rename with $
    199         dlink(tE) *prev;
    200     };
    201 
    202     static inline void ?{}( dlink(tE) & this ) {
    203       NOLOOSE(
    204         dlink(tE) * toSelf = & this;
    205         size_t toSelfNum = (size_t) toSelf;
    206         size_t toSelfNumTagged = ORIGIN_TAG_ENABL( toSelfNum );
    207         dlink(tE) * toSelfPtrTagged = (dlink(tE) *) toSelfNumTagged;
    208         toSelf = toSelfPtrTagged;
    209         (this.next){ toSelf };
    210         (this.prev){ toSelf };
    211       )
    212     }
    213 
    214     // You can "copy" a dlink.  But the result won't be linked.
    215     // Lets you copy what you inline the dlink into.
    216     static inline void ?{}( dlink(tE) & this, dlink(tE) ) {
    217         this{};
    218     }
    219 
    220     forall( tLinks & = dlink(tE) | embedded(tE, tLinks, dlink(tE)) ) {
    221         struct dlist {
    222             inline dlink(tE);
    223         };
    224 
    225         static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
    226             dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
    227             ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
    228             size_t origin_addr = ((size_t) & lst) - link_offset;
    229             size_t preResult = ORIGIN_TAG_ENABL( origin_addr );
    230             return (tE *)preResult;
    231         }
    232 
    233         static inline void ?{}( dlist(tE, tLinks) & this ) {
    234           NOLOOSE(
    235             ( (dlink(tE) &) this ){};
    236           )
    237           LOOSEONLY(
     173        struct dlink;
     174
     175        // do not use; presence of the field declaration unblocks ability to define dlink (#304)
     176        struct __dlink_selfref_workaround_t {
     177                dlink(tE) *ref_notSelfRef;
     178        };
     179
     180        struct dlink {
     181                dlink(tE) *next;  // TODO: rename with $
     182                dlink(tE) *prev;
     183        };
     184
     185        static inline void ?{}( dlink(tE) & this ) {
     186          NOLOOSE(
     187                dlink(tE) * toSelf = & this;
     188                size_t toSelfNum = (size_t) toSelf;
     189                size_t toSelfNumTagged = ORIGIN_TAG_ENABL( toSelfNum );
     190                dlink(tE) * toSelfPtrTagged = (dlink(tE) *) toSelfNumTagged;
     191                toSelf = toSelfPtrTagged;
     192                (this.next){ toSelf };
     193                (this.prev){ toSelf };
     194          )
     195        }
     196
     197        // You can "copy" a dlink.  But the result won't be linked.
     198        // Lets you copy what you inline the dlink into.
     199        static inline void ?{}( dlink(tE) & this, dlink(tE) ) {
     200                this{};
     201        }
     202
     203        forall( tLinks & = dlink(tE) | embedded(tE, tLinks, dlink(tE)) ) {
     204                struct dlist {
     205                        inline dlink(tE);
     206                };
     207
     208                static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
     209                        dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
     210                        ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
     211                        size_t origin_addr = ((size_t) & lst) - link_offset;
     212                        size_t preResult = ORIGIN_TAG_ENABL( origin_addr );
     213                        return (tE *)preResult;
     214                }
     215
     216                static inline void ?{}( dlist(tE, tLinks) & this ) {
     217                  NOLOOSE(
     218                        ( (dlink(tE) &) this ){};
     219                  )
     220                  LOOSEONLY(
    238221                        dlink(tE) * listOrigin = (dlink(tE) *) $get_list_origin_addr( this );
    239             dlink( tE ) & thisl = this;
     222                        dlink( tE ) & thisl = this;
    240223                        (thisl.prev) = listOrigin;
    241             (thisl.next) = listOrigin;
    242           )
    243         }
    244     }
     224                        (thisl.next) = listOrigin;
     225                  )
     226                }
     227        }
    245228}
     229
    246230
    247231forall( tE & ) {
    248232#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode
    249     static inline size_t origin_tag_query_arith$( tE & raw ) {
    250         return 0;
    251     }
    252     static inline tE & nullif$( tE & val, size_t arith_ctrl ) {
    253         verify( arith_ctrl == 0 );  (void) arith_ctrl;
    254         return val;
    255     }
     233        static inline size_t origin_tag_query_arith$( tE & raw ) {
     234                return 0;
     235        }
     236        static inline tE & nullif$( tE & val, size_t arith_ctrl ) {
     237                verify( arith_ctrl == 0 );  (void) arith_ctrl;
     238                return val;
     239        }
    256240#else // Normal
    257     // like ORIGIN_TAG_QUERY, but return is arithmetic number 0 or 1 (rather than 0 or non-0)
    258     static inline size_t origin_tag_query_arith$( tE & raw ) {
    259         size_t ret = (((size_t) & raw) >> ORIGIN_TAG_BITNO) & 1;
    260         verify( ORIGIN_TAG_QUERY( (size_t) & raw ) ? ret == 1 : ret == 0 );
    261         return ret;
    262     }
    263     // Requires arith_ctrl being 0 or 1.
    264     // When 0, passes val through; when 1, returns null reference.
    265     // Importantly, implemented without jumps or tests.
    266     static inline tE & nullif$( tE & val, size_t arith_ctrl ) {
    267         verify( ! ORIGIN_TAG_QUERY( (size_t) & val ) );
    268         verify( arith_ctrl == 0 || arith_ctrl == 1 );
    269         size_t mask_ctrl = ~ - arith_ctrl;
    270         verify( arith_ctrl == 0 && mask_ctrl == -1 || arith_ctrl == 1 && mask_ctrl ==0 );
    271         tE & ret = * (tE*) ( ((size_t) & val) & mask_ctrl);
    272         verify( arith_ctrl == 0 && &ret == &val || arith_ctrl == 1 && &ret == 0p );
    273         return ret;
    274     }
     241        // like ORIGIN_TAG_QUERY, but return is arithmetic number 0 or 1 (rather than 0 or non-0)
     242        static inline size_t origin_tag_query_arith$( tE & raw ) {
     243                size_t ret = (((size_t) & raw) >> ORIGIN_TAG_BITNO) & 1;
     244                verify( ORIGIN_TAG_QUERY( (size_t) & raw ) ? ret == 1 : ret == 0 );
     245                return ret;
     246        }
     247        // Requires arith_ctrl being 0 or 1.
     248        // When 0, passes val through; when 1, returns null reference.
     249        // Importantly, implemented without jumps or tests.
     250        static inline tE & nullif$( tE & val, size_t arith_ctrl ) {
     251                verify( ! ORIGIN_TAG_QUERY( (size_t) & val ) );
     252                verify( arith_ctrl == 0 || arith_ctrl == 1 );
     253                size_t mask_ctrl = ~ - arith_ctrl;
     254                verify( arith_ctrl == 0 && mask_ctrl == -1 || arith_ctrl == 1 && mask_ctrl ==0 );
     255                tE & ret = * (tE*) ( ((size_t) & val) & mask_ctrl);
     256                verify( arith_ctrl == 0 && &ret == &val || arith_ctrl == 1 && &ret == 0p );
     257                return ret;
     258        }
    275259#endif
    276260}
    … …  
    305289
    306290forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
    307 
    308         static inline void insert_after(tE & list_pos, tE &to_insert) {
    309         size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert after the origin is fine
    310         tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
     291        static inline void insert_before(tE & list_pos, tE &to_insert) {
     292                size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert before the origin is fine
     293                tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
    311294                verify (&list_pos_real != 0p);
    312295
    313296                verify (&to_insert != 0p);
    314       NOLOOSE(
     297          NOLOOSE(
    315298                verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
    316       )
    317         dlink(tE) & linkToInsert = to_insert`inner;
    318       NOLOOSE(
    319        TAGSONLY(
     299          )
     300                dlink(tE) & linkToInsert = to_insert`inner;
     301          NOLOOSE(
     302           TAGSONLY(
    320303                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
    321304                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
    322        )
     305           )
    323306                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
    324307                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
    325       )
    326         dlink(tE) & list_pos_links = list_pos_real`inner;
    327       MAYBE_INSERT_READ_EARLY(
    328         dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
    329       )
    330         MAYBE_CMEM_BARRIER;
    331         size_t list_pos_links_num = (size_t)(& list_pos_links);
    332         size_t to_insert_prev_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
    333         dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
     308          )
     309                dlink(tE) & list_pos_links = list_pos_real`inner;
     310          MAYBE_INSERT_READ_EARLY(
     311                dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
     312          )
     313                MAYBE_CMEM_BARRIER;
     314                size_t list_pos_links_num = (size_t)(& list_pos_links);
     315                size_t to_insert_next_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
     316                dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
     317                linkToInsert.next = to_insert_next;
     318                linkToInsert.prev = list_pos_links.prev;
     319          MAYBE_INSERT_READ_LATE(
     320                dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
     321          )
     322                size_t beforeLinks_next_tag = ORIGIN_TAG_QUERY((size_t)beforeLinks.next);
     323                size_t linkToInsert_num = (size_t)(& linkToInsert);
     324                size_t beforeLinks_next_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, beforeLinks_next_tag));
     325                beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
     326                list_pos_links.prev = &linkToInsert;
     327                MAYBE_CMEM_BARRIER;
     328        }
     329        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     330        forall( List ... | { void insert_before( tE & before, List ); } )
     331        void insert_before( tE & before, tE * node, List args ) {
     332                insert_before( before, *node );
     333                insert_before( before, args );
     334        }
     335        void insert_before( tE & before, tE * node ) {
     336                insert_before( before, *node );
     337        }
     338
     339        static inline void insert_after(tE & list_pos, tE &to_insert) {
     340                size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert after the origin is fine
     341                tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
     342                verify (&list_pos_real != 0p);
     343
     344                verify (&to_insert != 0p);
     345          NOLOOSE(
     346                verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
     347          )
     348                dlink(tE) & linkToInsert = to_insert`inner;
     349          NOLOOSE(
     350           TAGSONLY(
     351                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
     352                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
     353           )
     354                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
     355                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
     356          )
     357                dlink(tE) & list_pos_links = list_pos_real`inner;
     358          MAYBE_INSERT_READ_EARLY(
     359                dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
     360          )
     361                MAYBE_CMEM_BARRIER;
     362                size_t list_pos_links_num = (size_t)(& list_pos_links);
     363                size_t to_insert_prev_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
     364                dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
    334365                linkToInsert.prev = to_insert_prev;
    335366                linkToInsert.next = list_pos_links.next;
    336       MAYBE_INSERT_READ_LATE(
    337         dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
    338       )
    339         size_t afterLinks_prev_tag = ORIGIN_TAG_QUERY((size_t)afterLinks.prev);
    340         size_t linkToInsert_num = (size_t)(& linkToInsert);
    341         size_t afterLinks_prev_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, afterLinks_prev_tag));
    342         afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
     367          MAYBE_INSERT_READ_LATE(
     368                dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
     369          )
     370                size_t afterLinks_prev_tag = ORIGIN_TAG_QUERY((size_t)afterLinks.prev);
     371                size_t linkToInsert_num = (size_t)(& linkToInsert);
     372                size_t afterLinks_prev_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, afterLinks_prev_tag));
     373                afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
    343374                list_pos_links.next = &linkToInsert;
    344         MAYBE_CMEM_BARRIER;
    345         }
    346 
    347         static inline void insert_before(tE & list_pos, tE &to_insert) {
    348         size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert before the origin is fine
    349         tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos);
    350                 verify (&list_pos_real != 0p);
    351 
    352                 verify (&to_insert != 0p);
    353       NOLOOSE(
    354                 verify(! ORIGIN_TAG_QUERY((size_t) & to_insert));
    355       )
    356         dlink(tE) & linkToInsert = to_insert`inner;
    357       NOLOOSE(
    358        TAGSONLY(
     375                MAYBE_CMEM_BARRIER;
     376        }
     377        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     378        forall( List ... | { void insert_after( tE & after, List ); } )
     379        void insert_after( tE & after, tE * node, List args ) {
     380                insert_after( after, *node );
     381                insert_after( after, args );
     382        }
     383        void insert_after( tE & after, tE * node ) {
     384                insert_after( after, *node );
     385        }
     386
     387        static inline tE & remove(tE & list_pos) {
     388                verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
     389                verify (&list_pos != 0p);
     390
     391                dlink(tE) & list_pos_links = list_pos`inner;
     392                dlink(tE) & before_raw = * list_pos_links.prev;
     393                dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     394                size_t before_links_next_tag = ORIGIN_TAG_QUERY( (size_t) (before_links.next) );
     395
     396                dlink(tE) & after_raw = * list_pos_links.next;
     397                dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     398                size_t after_links_prev_tag = ORIGIN_TAG_QUERY( (size_t) (after_links.prev) );
     399
     400                size_t before_links_next_rslt = ORIGIN_TAG_EITHER( ((size_t) & after_raw), before_links_next_tag );
     401                size_t after_links_prev_rslt = ORIGIN_TAG_EITHER( ((size_t) & before_raw), after_links_prev_tag );
     402                before_links.next = (dlink(tE) *) before_links_next_rslt;
     403                after_links.prev = (dlink(tE) *) after_links_prev_rslt;
     404
     405          NOLOOSE(
     406                MAYBE_CMEM_BARRIER;
     407                size_t list_pos_links_num = (size_t) &list_pos_links;
     408                size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
     409                list_pos_links.next = list_pos_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
     410                MAYBE_CMEM_BARRIER;
     411          )
     412                return list_pos;
     413        }
     414        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     415        forall( List ... | { void remove( List ); } )
     416        void remove( tE * node, List args ) {
     417                remove( *node );
     418                remove( args );
     419        }
     420        void remove( tE * node ) {
     421                remove( *node );
     422        }
     423
     424        static inline tE & downcast$( tytagref( tLinks, dlink(tE) ) ref ) {
     425                dlink(tE) & lnk = ref;
     426                dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
     427                ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
     428                size_t elm_addr = ((size_t) & lnk) - link_offset;
     429                return * (tE*) elm_addr;
     430        }
     431
     432        static inline tE & first( dlist(tE, tLinks) & lst ) {
     433                verify (&lst != 0p);
     434                dlink(tE) * firstLnk = lst.next;
     435                if (ORIGIN_TAG_QUERY((size_t)firstLnk)) return * 0p;
     436                tytagref( tLinks, dlink(tE) ) firstLnkTagged = {*firstLnk};
     437                return downcast$( firstLnkTagged );
     438        }
     439        static inline tE & last ( dlist(tE, tLinks) & lst ) {
     440                verify (&lst != 0p);
     441                dlink(tE) * lastLnk = lst.prev;
     442                if (ORIGIN_TAG_QUERY((size_t)lastLnk)) return * 0p;
     443                tytagref( tLinks, dlink(tE) ) lastLnkTagged = {*lastLnk};
     444                return downcast$( lastLnkTagged );
     445        }
     446
     447        static inline bool isEmpty( dlist(tE, tLinks) & lst ) {
     448                verify (&lst != 0p);
     449                if ( & first(lst) == 0p || & last(lst) == 0p ) {
     450                        verify( & last(lst) == 0p && & last(lst) == 0p );
     451                        return true;
     452                }
     453                return false;
     454        }
     455
     456        static inline bool isListed( tE & e ) {
     457          NOLOOSE(
     458                verify (&e != 0p);
     459                verify(! ORIGIN_TAG_QUERY( (size_t) & e ));
     460                dlink(tE) & e_links = e`inner;
     461                dlink(tE) * lprev = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.prev);
     462                dlink(tE) * lnext = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.next);
     463                return ( lprev != &e_links ) || ( lnext != &e_links );
     464          )
     465          LOOSEONLY(
     466                verify(false && "isListed is undefined");
     467                return true;
     468          )
     469        }
     470
     471        static inline tE & iter( dlist(tE, tLinks) & lst ) {
     472                tE * origin = $get_list_origin_addr( lst );
     473                return *origin;
     474        }
     475
     476
     477        // todo: resolve the pun:
     478        //  tag as in proxy (tytagref)
     479        //  tag as in bit manipulation on a funny pointer
     480
     481        static inline bool advance( tE && refx ) {
     482                tE && ref_inner = refx;
     483                tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     484                verify (& oldReferent != 0p);
     485                dlink(tE) * tgt = oldReferent`inner.next;
     486                size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
     487                dlink(tE) * nextl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
     488                tytagref( tLinks, dlink(tE) ) nextLnkTagged = { * nextl };
     489                tE & nexte = downcast$( nextLnkTagged );
     490                size_t next_te_num = (size_t) & nexte;
     491                size_t new_ref_inner_num = ORIGIN_TAG_ASGN(next_te_num, tgt_tags);
     492                tE * new_ref_inner = (tE *) new_ref_inner_num;
     493                &ref_inner = new_ref_inner;
     494                return ! tgt_tags;
     495        }
     496
     497        static inline bool recede( tE && refx ) {
     498                tE && ref_inner = refx;
     499                tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     500                verify (& oldReferent != 0p);
     501                dlink(tE) * tgt = oldReferent`inner.prev;
     502                size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
     503                dlink(tE) * prevl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
     504                tytagref( tLinks, dlink(tE) ) prevLnkTagged = { * prevl };
     505                tE & preve = downcast$( prevLnkTagged );
     506                size_t prev_te_num = (size_t) & preve;
     507                size_t new_ref_inner_num = ORIGIN_TAG_ASGN(prev_te_num, tgt_tags);
     508                tE * new_ref_inner = (tE *) new_ref_inner_num;
     509                &ref_inner = new_ref_inner;
     510                return ! tgt_tags;
     511        }
     512
     513        bool isFirst( tE & node ) {
     514                // Probable bug copied from master
     515                // should be `! recede(node)`
     516                // correct: "is first iff cannot recede"
     517                // used backward in test suite too, probably victim of a grep rename
     518                return recede( node );
     519        }
     520
     521        bool isLast( tE & node ) {
     522                // ditto, vice versa
     523                return advance( node );
     524        }
     525
     526        static inline tE & next( tE & e ) {
     527                if( advance(e) ) return e;
     528                return * 0p;
     529        }
     530
     531        static inline tE & prev( tE & e ) {
     532                if( recede(e) ) return e;
     533                return * 0p;
     534        }
     535
     536        // Next 4 headed operations:
     537        // Manual inline of the equivalent headless operation, manually simplified.
     538        // Applies knowledge of tag pattern around head (unknown to optimizer) to reduce runtime tag operations.
     539
     540        static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
     541                dlink(tE) & linkToInsert = e`inner;
     542          NOLOOSE(
     543           TAGSONLY(
    359544                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
    360545                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
    361        )
     546           )
    362547                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
    363548                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
    364       )
    365         dlink(tE) & list_pos_links = list_pos_real`inner;
    366       MAYBE_INSERT_READ_EARLY(
    367         dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
    368       )
    369         MAYBE_CMEM_BARRIER;
    370         size_t list_pos_links_num = (size_t)(& list_pos_links);
    371         size_t to_insert_next_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag);
    372         dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
     549          )
     550                dlink(tE) & list_pos_links = lst;
     551          MAYBE_INSERT_READ_EARLY(
     552                dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
     553          )
     554                MAYBE_CMEM_BARRIER;
     555                size_t list_pos_links_num = (size_t)(& list_pos_links);
     556                size_t to_insert_prev_num = ORIGIN_TAG_ENABL(list_pos_links_num);
     557                dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
     558                linkToInsert.prev = to_insert_prev;
     559                linkToInsert.next = list_pos_links.next;
     560          MAYBE_INSERT_READ_LATE(
     561                dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
     562          )
     563                size_t linkToInsert_num = (size_t)(& linkToInsert);
     564                size_t afterLinks_prev_num = linkToInsert_num;
     565                afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
     566                list_pos_links.next = &linkToInsert;
     567                MAYBE_CMEM_BARRIER;
     568        }
     569        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     570        forall( List ... | { void insert_first( dlist( tE, tLinks ) & list, List ); } )
     571        void insert_first( dlist( tE, tLinks ) & list, tE * node, List args ) {
     572                insert_first( list, *node );
     573                insert_first( list, args );
     574        }
     575        void insert_first( dlist( tE, tLinks ) & list, tE * node ) {
     576                insert_first( list, *node );
     577        }
     578
     579        static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
     580                dlink(tE) & linkToInsert = e`inner;
     581          NOLOOSE(
     582           TAGSONLY(
     583                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
     584                verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
     585           )
     586                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
     587                verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
     588          )
     589                dlink(tE) & list_pos_links = lst;
     590          MAYBE_INSERT_READ_EARLY(
     591                dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
     592          )
     593                MAYBE_CMEM_BARRIER;
     594                size_t list_pos_links_num = (size_t)(& list_pos_links);
     595                size_t to_insert_next_num = ORIGIN_TAG_ENABL(list_pos_links_num);
     596                dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
    373597                linkToInsert.next = to_insert_next;
    374598                linkToInsert.prev = list_pos_links.prev;
    375       MAYBE_INSERT_READ_LATE(
    376         dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
    377       )
    378         size_t beforeLinks_next_tag = ORIGIN_TAG_QUERY((size_t)beforeLinks.next);
    379         size_t linkToInsert_num = (size_t)(& linkToInsert);
    380         size_t beforeLinks_next_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, beforeLinks_next_tag));
    381         beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
     599          MAYBE_INSERT_READ_LATE(
     600                dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
     601          )
     602                size_t linkToInsert_num = (size_t)(& linkToInsert);
     603                size_t beforeLinks_next_num = linkToInsert_num;
     604                beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
    382605                list_pos_links.prev = &linkToInsert;
    383         MAYBE_CMEM_BARRIER;
    384         }
    385 
    386         static inline tE & remove(tE & list_pos) {
    387         verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) );
    388                 verify (&list_pos != 0p);
    389 
    390         dlink(tE) & list_pos_links = list_pos`inner;
    391         dlink(tE) & before_raw = * list_pos_links.prev;
    392         dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    393         size_t before_links_next_tag = ORIGIN_TAG_QUERY( (size_t) (before_links.next) );
    394 
    395         dlink(tE) & after_raw = * list_pos_links.next;
    396         dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    397         size_t after_links_prev_tag = ORIGIN_TAG_QUERY( (size_t) (after_links.prev) );
    398 
    399         size_t before_links_next_rslt = ORIGIN_TAG_EITHER( ((size_t) & after_raw), before_links_next_tag );
    400         size_t after_links_prev_rslt = ORIGIN_TAG_EITHER( ((size_t) & before_raw), after_links_prev_tag );
    401         before_links.next = (dlink(tE) *) before_links_next_rslt;
    402         after_links.prev = (dlink(tE) *) after_links_prev_rslt;
    403 
    404       NOLOOSE(
    405         MAYBE_CMEM_BARRIER;
    406         size_t list_pos_links_num = (size_t) &list_pos_links;
    407         size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
    408                 list_pos_links.next = list_pos_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
    409         MAYBE_CMEM_BARRIER;
    410       )
    411         return list_pos;
    412         }
    413 
    414     static inline tE & downcast$( tytagref( tLinks, dlink(tE) ) ref ) {
    415         dlink(tE) & lnk = ref;
    416         dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
    417         ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
    418         size_t elm_addr = ((size_t) & lnk) - link_offset;
    419         return * (tE*) elm_addr;
    420     }
    421 
    422     static inline tE & first( dlist(tE, tLinks) & lst ) {
     606                MAYBE_CMEM_BARRIER;
     607        }
     608        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     609        forall( List ... | { void insert_last( dlist( tE, tLinks ) & list, List ); } )
     610        void insert_last( dlist( tE, tLinks ) & list, tE * node, List args ) {
     611                insert_last( list, *node );
     612                insert_last( list, args );
     613        }
     614        void insert_last( dlist( tE, tLinks ) & list, tE * node ) {
     615                insert_last( list, *node );
     616        }
     617
     618        tE & insert( dlist( tE, tLinks ) & list, tE & node ) { // synonym for insert_last
     619                insert_last( list, node );
     620                return node;
     621        }
     622        // FIXME: Change from pointer to reference for node, when tuple type can handle references.
     623        forall( List ... | { void insert( dlist( tE, tLinks ) & list, List ); } )
     624        void insert( dlist( tE, tLinks ) & list, tE * node, List args ) {
     625                insert( list, *node );
     626                insert( list, args );
     627        }
     628        void insert( dlist( tE, tLinks ) & list, tE * node ) {
     629                insert( list, *node );
     630        }
     631
     632        static inline tE & remove_first( dlist(tE, tLinks) &lst ) {
    423633                verify (&lst != 0p);
    424         dlink(tE) * firstLnk = lst.next;
    425         if (ORIGIN_TAG_QUERY((size_t)firstLnk)) return * 0p;
    426         tytagref( tLinks, dlink(tE) ) firstLnkTagged = {*firstLnk};
    427         return downcast$( firstLnkTagged );
    428     }
    429     static inline tE & last ( dlist(tE, tLinks) & lst ) {
     634                dlink(tE) & list_links = lst;
     635                // call is valid on empty list; when so, list_links.next and after_links.prev have otags set
     636
     637                dlink(tE) & fst_raw = * list_links.next;
     638                dlink(tE) & fst_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & fst_raw );
     639                size_t fst_tagval = origin_tag_query_arith$( fst_raw );
     640
     641                dlink(tE) & after_raw = * fst_links.next;
     642                dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     643
     644                size_t before_links_next_rslt = ((size_t) & after_raw);
     645                size_t after_links_prev_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
     646                list_links.next = (dlink(tE) *) before_links_next_rslt;
     647                after_links.prev = (dlink(tE) *) after_links_prev_rslt;
     648
     649                MAYBE_CMEM_BARRIER;
     650                size_t list_pos_links_num = (size_t) &fst_links;
     651                size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
     652                fst_links.next = fst_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
     653                MAYBE_CMEM_BARRIER;
     654
     655                tytagref( tLinks, dlink(tE) ) retExt = { fst_links };
     656                return nullif$( downcast$( retExt ), fst_tagval );
     657        }
     658
     659        static inline tE & remove_last( dlist(tE, tLinks) &lst ) {
    430660                verify (&lst != 0p);
    431         dlink(tE) * lastLnk = lst.prev;
    432         if (ORIGIN_TAG_QUERY((size_t)lastLnk)) return * 0p;
    433         tytagref( tLinks, dlink(tE) ) lastLnkTagged = {*lastLnk};
    434         return downcast$( lastLnkTagged );
    435     }
    436 
    437     static inline bool isEmpty( dlist(tE, tLinks) & lst ) {
    438                 verify (&lst != 0p);
    439         if ( & first(lst) == 0p || & last(lst) == 0p ) {
    440             verify( & last(lst) == 0p && & last(lst) == 0p );
    441             return true;
    442         }
    443         return false;
    444     }
    445 
    446     static inline bool isListed( tE & e ) {
    447       NOLOOSE(
    448                 verify (&e != 0p);
    449                 verify(! ORIGIN_TAG_QUERY( (size_t) & e ));
    450         dlink(tE) & e_links = e`inner;
    451         dlink(tE) * lprev = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.prev);
    452         dlink(tE) * lnext = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.next);
    453                 return ( lprev != &e_links ) || ( lnext != &e_links );
    454       )
    455       LOOSEONLY(
    456         verify(false && "isListed is undefined");
    457         return true;
    458       )
    459     }
    460 
    461     static inline tE & iter( dlist(tE, tLinks) & lst ) {
    462         tE * origin = $get_list_origin_addr( lst );
    463         return *origin;
    464     }
    465 
    466 
    467     // todo: resolve the pun:
    468     //  tag as in proxy (tytagref)
    469     //  tag as in bit manipulation on a funny pointer
    470 
    471     static inline bool advance( tE && refx ) {
    472         tE && ref_inner = refx;
    473         tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    474                 verify (& oldReferent != 0p);
    475         dlink(tE) * tgt = oldReferent`inner.next;
    476         size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
    477         dlink(tE) * nextl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
    478         tytagref( tLinks, dlink(tE) ) nextLnkTagged = { * nextl };
    479         tE & nexte = downcast$( nextLnkTagged );
    480         size_t next_te_num = (size_t) & nexte;
    481         size_t new_ref_inner_num = ORIGIN_TAG_ASGN(next_te_num, tgt_tags);
    482         tE * new_ref_inner = (tE *) new_ref_inner_num;
    483         &ref_inner = new_ref_inner;
    484         return ! tgt_tags;
    485     }
    486 
    487     static inline bool recede( tE && refx ) {
    488         tE && ref_inner = refx;
    489         tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
    490                 verify (& oldReferent != 0p);
    491         dlink(tE) * tgt = oldReferent`inner.prev;
    492         size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt);
    493         dlink(tE) * prevl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt);
    494         tytagref( tLinks, dlink(tE) ) prevLnkTagged = { * prevl };
    495         tE & preve = downcast$( prevLnkTagged );
    496         size_t prev_te_num = (size_t) & preve;
    497         size_t new_ref_inner_num = ORIGIN_TAG_ASGN(prev_te_num, tgt_tags);
    498         tE * new_ref_inner = (tE *) new_ref_inner_num;
    499         &ref_inner = new_ref_inner;
    500         return ! tgt_tags;
    501     }
    502 
    503     bool isFirst( tE & node ) {
    504         // Probable bug copied from master
    505         // should be `! recede(node)`
    506         // correct: "is first iff cannot recede"
    507         // used backward in test suite too, probably victim of a grep rename
    508         return recede( node );
    509     }
    510 
    511     bool isLast( tE & node ) {
    512         // ditto, vice versa
    513         return advance( node );
    514     }
    515 
    516     static inline tE & next( tE & e ) {
    517         if( advance(e) ) return e;
    518         return * 0p;
    519     }
    520 
    521     static inline tE & prev( tE & e ) {
    522         if( recede(e) ) return e;
    523         return * 0p;
    524     }
    525 
    526     // Next 4 headed operations:
    527     // Manual inline of the equivalent headless operation, manually simplified.
    528     // Applies knowledge of tag pattern around head (unknown to optimizer) to reduce runtime tag operations.
    529 
    530     static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
    531         dlink(tE) & linkToInsert = e`inner;
    532       NOLOOSE(
    533        TAGSONLY(
    534                 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
    535                 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
    536        )
    537                 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
    538                 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
    539       )
    540         dlink(tE) & list_pos_links = lst;
    541       MAYBE_INSERT_READ_EARLY(
    542         dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
    543       )
    544         MAYBE_CMEM_BARRIER;
    545         size_t list_pos_links_num = (size_t)(& list_pos_links);
    546         size_t to_insert_prev_num = ORIGIN_TAG_ENABL(list_pos_links_num);
    547         dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num;
    548                 linkToInsert.prev = to_insert_prev;
    549                 linkToInsert.next = list_pos_links.next;
    550       MAYBE_INSERT_READ_LATE(
    551         dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next );
    552       )
    553         size_t linkToInsert_num = (size_t)(& linkToInsert);
    554         size_t afterLinks_prev_num = linkToInsert_num;
    555         afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num);
    556                 list_pos_links.next = &linkToInsert;
    557         MAYBE_CMEM_BARRIER;
    558     }
    559 
    560     static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
    561         dlink(tE) & linkToInsert = e`inner;
    562       NOLOOSE(
    563        TAGSONLY(
    564                 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next));
    565                 verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev));
    566        )
    567                 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert);
    568                 verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert);
    569       )
    570         dlink(tE) & list_pos_links = lst;
    571       MAYBE_INSERT_READ_EARLY(
    572         dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
    573       )
    574         MAYBE_CMEM_BARRIER;
    575         size_t list_pos_links_num = (size_t)(& list_pos_links);
    576         size_t to_insert_next_num = ORIGIN_TAG_ENABL(list_pos_links_num);
    577         dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num;
    578                 linkToInsert.next = to_insert_next;
    579                 linkToInsert.prev = list_pos_links.prev;
    580       MAYBE_INSERT_READ_LATE(
    581         dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev );
    582       )
    583         size_t linkToInsert_num = (size_t)(& linkToInsert);
    584         size_t beforeLinks_next_num = linkToInsert_num;
    585         beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num);
    586                 list_pos_links.prev = &linkToInsert;
    587         MAYBE_CMEM_BARRIER;
    588     }
    589 
    590     static inline tE & remove_first( dlist(tE, tLinks) &lst ) {
    591                 verify (&lst != 0p);
    592         dlink(tE) & list_links = lst;
    593         // call is valid on empty list; when so, list_links.next and after_links.prev have otags set
    594 
    595         dlink(tE) & fst_raw = * list_links.next;
    596         dlink(tE) & fst_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & fst_raw );
    597         size_t fst_tagval = origin_tag_query_arith$( fst_raw );
    598 
    599         dlink(tE) & after_raw = * fst_links.next;
    600         dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
    601 
    602         size_t before_links_next_rslt = ((size_t) & after_raw);
    603         size_t after_links_prev_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
    604         list_links.next = (dlink(tE) *) before_links_next_rslt;
    605         after_links.prev = (dlink(tE) *) after_links_prev_rslt;
    606 
    607         MAYBE_CMEM_BARRIER;
    608         size_t list_pos_links_num = (size_t) &fst_links;
    609         size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
    610                 fst_links.next = fst_links.prev = (dlink(tE)*) list_pos_links_tagged_num;
    611         MAYBE_CMEM_BARRIER;
    612 
    613         tytagref( tLinks, dlink(tE) ) retExt = { fst_links };
    614         return nullif$( downcast$( retExt ), fst_tagval );
    615     }
    616 
    617     static inline tE & remove_last( dlist(tE, tLinks) &lst ) {
    618                 verify (&lst != 0p);
    619         dlink(tE) & list_links = lst;
    620         // call is valid on empty list; when so, list_links.prev and before_links.next have otags set
    621 
    622         dlink(tE) & last_raw = * list_links.prev;
    623         dlink(tE) & last_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & last_raw );
    624         size_t last_tagval = origin_tag_query_arith$( last_raw );
    625 
    626         dlink(tE) & before_raw = * last_links.prev;
    627         dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
    628 
    629         size_t after_links_prev_rslt = ((size_t) & before_raw);
    630         size_t before_links_next_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
    631         list_links.prev = (dlink(tE) *) after_links_prev_rslt;
    632         before_links.next = (dlink(tE) *) before_links_next_rslt;
    633 
    634         MAYBE_CMEM_BARRIER;
    635         size_t list_pos_links_num = (size_t) &last_links;
    636         size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
     661                dlink(tE) & list_links = lst;
     662                // call is valid on empty list; when so, list_links.prev and before_links.next have otags set
     663
     664                dlink(tE) & last_raw = * list_links.prev;
     665                dlink(tE) & last_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & last_raw );
     666                size_t last_tagval = origin_tag_query_arith$( last_raw );
     667
     668                dlink(tE) & before_raw = * last_links.prev;
     669                dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     670
     671                size_t after_links_prev_rslt = ((size_t) & before_raw);
     672                size_t before_links_next_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links );
     673                list_links.prev = (dlink(tE) *) after_links_prev_rslt;
     674                before_links.next = (dlink(tE) *) before_links_next_rslt;
     675
     676                MAYBE_CMEM_BARRIER;
     677                size_t list_pos_links_num = (size_t) &last_links;
     678                size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num );
    637679                last_links.prev = last_links.next = (dlink(tE)*) list_pos_links_tagged_num;
    638         MAYBE_CMEM_BARRIER;
    639 
    640         tytagref( tLinks, dlink(tE) ) lpLnkTagged = { last_links };
    641         return nullif$( downcast$( lpLnkTagged ), last_tagval );
    642     }
    643 
    644     static inline tE & try_pop_first( dlist(tE, tLinks) &lst ) {
    645         tE & first_inlist = first(lst);
    646         tE & first_item = first_inlist;
    647         if (&first_item) remove(first_inlist);  // TODO: should it use pop_front?
    648         return first_item;
    649     }
    650 
    651     static inline tE & try_pop_last( dlist(tE, tLinks) &lst ) {
    652         tE & last_inlist = last(lst);
    653         tE & last_item = last_inlist;
    654         if (&last_item) remove(last_inlist);  // TODO: should it use pop_back?
    655         return last_item;
    656     }
     680                MAYBE_CMEM_BARRIER;
     681
     682                tytagref( tLinks, dlink(tE) ) lpLnkTagged = { last_links };
     683                return nullif$( downcast$( lpLnkTagged ), last_tagval );
     684        }
     685
     686        static inline tE & try_pop_first( dlist(tE, tLinks) &lst ) {
     687                tE & first_inlist = first(lst);
     688                tE & first_item = first_inlist;
     689                if (&first_item) remove(first_inlist);  // TODO: should it use pop_front?
     690                return first_item;
     691        }
     692
     693        static inline tE & try_pop_last( dlist(tE, tLinks) &lst ) {
     694                tE & last_inlist = last(lst);
     695                tE & last_item = last_inlist;
     696                if (&last_item) remove(last_inlist);  // TODO: should it use pop_back?
     697                return last_item;
     698        }
    657699
    658700
    659701  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
    660702        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
    661         tE & lagElem = *0p;
    662 
    663         while ( tE & it = iter(this); advance(it) ) {
    664             if (& lagElem == 0p &&  &it != & first(this) ) return false;
    665             & lagElem = & it;
    666         }
    667 
    668         if (& lagElem != & last(this)) return false;
    669 
    670         // TODO: verify that it is back at iter(this);
    671         return true;
     703                tE & lagElem = *0p;
     704
     705                while ( tE & it = iter(this); advance(it) ) {
     706                        if (& lagElem == 0p &&  &it != & first(this) ) return false;
     707                        & lagElem = & it;
     708                }
     709
     710                if (& lagElem != & last(this)) return false;
     711
     712                // TODO: verify that it is back at iter(this);
     713                return true;
    672714        }
    673715        static bool $validate_rev( dlist(tE, tLinks) & this ) {
    674         tE & lagElem = *0p;
    675 
    676         while ( tE & it = iter(this); recede(it) ) {
    677             if (& lagElem == 0p &&  &it != & last(this) ) return false;
    678             & lagElem = & it;
    679         }
    680 
    681         if (& lagElem != & first(this)) return false;
    682 
    683         // TODO: verify that it is back at iter(this);
    684         return true;
     716                tE & lagElem = *0p;
     717
     718                while ( tE & it = iter(this); recede(it) ) {
     719                        if (& lagElem == 0p &&  &it != & last(this) ) return false;
     720                        & lagElem = & it;
     721                }
     722
     723                if (& lagElem != & first(this)) return false;
     724
     725                // TODO: verify that it is back at iter(this);
     726                return true;
    685727        }
    686728        static inline bool validate( dlist(tE, tLinks) & this ) {
    687         bool reportsHavingFirst = ((& first(this)) == 0p);
    688         bool reportsHavingLast = ((& last(this)) == 0p);
    689         if ( reportsHavingFirst != reportsHavingLast ) return false;
     729                bool reportsHavingFirst = ((& first(this)) == 0p);
     730                bool reportsHavingLast = ((& last(this)) == 0p);
     731                if ( reportsHavingFirst != reportsHavingLast ) return false;
    690732
    691733                return $validate_fwd(this) && $validate_rev(this);
Note: See TracChangeset for help on using the changeset viewer.