Ignore:
Timestamp:
May 12, 2021, 4:30:27 PM (3 years ago)
Author:
Michael Brooks <mlbrooks@…>
Branches:
ADT, arm-eh, ast-experimental, enum, forall-pointer-decay, jacob/cs343-translation, master, new-ast-unique-expr, pthread-emulation, qualifiedEnum
Children:
e2f601f
Parents:
67b421c
Message:

Replacing "Mike's old linked list" with "Mike's new linked list," including replatforming uses of the old one.

libcfa/src/containers/list.hfa ---[becomes]--> tests/zombies/linked-list-perf/mike-old.hfa
libcfa/src/containers/list2.hfa ---[becomes]--> libcfa/src/containers/list.hfa

There are no more multiple versions of "Mike's list" in libcfa, nor tests thereof.

The libcfa concurrency uses (alarm, kernel and ready_queue) are hereby ported to "Mike's new."

A best-effort port of executor, which was found not compiling with errors that seem unrelated to the linked list, is attempted too.

Location:
libcfa/src/containers
Files:
1 deleted
1 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/containers/list.hfa

    r67b421c r69914cbc  
    1818#include <assert.h>
    1919
    20 #define __DLISTED_MGD_COMMON(ELEM, NODE, LINKS_FLD) \
    21 static inline ELEM& $tempcv_n2e(NODE &node) { \
    22         return node; \
    23 } \
    24 \
    25 static inline NODE& $tempcv_e2n(ELEM &node) { \
    26         return ( NODE & ) node; \
    27 } \
    28 \
    29 static inline ELEM & ?`prev(NODE &node) { \
    30     $dlinks(ELEM) & ls = node.LINKS_FLD; \
    31         $mgd_link(ELEM) * l = &ls.prev; \
    32         ELEM * e = l->elem; \
    33         return *e; \
    34 } \
    35 \
    36 static inline ELEM & ?`next(NODE &node) { \
    37     $dlinks(ELEM) & ls = node.LINKS_FLD; \
    38         $mgd_link(ELEM) * l = &ls.next; \
    39         ELEM * e = l->elem; \
    40         return *e; \
    41 } \
    42 \
    43 static inline $mgd_link(ELEM) & $prev_link(NODE &node) { \
    44     $dlinks(ELEM) & ls = node.LINKS_FLD; \
    45         $mgd_link(ELEM) * l = &ls.prev; \
    46         return *l; \
    47 } \
    48 \
    49 static inline $mgd_link(ELEM) & $next_link(NODE &node) { \
    50     $dlinks(ELEM) & ls = node.LINKS_FLD; \
    51         $mgd_link(ELEM) * l = &ls.next; \
    52         return *l; \
     20forall( Decorator &, T & )
     21struct tytagref {
     22    inline T &;
     23};
     24
     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 &)
     31static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; }
     32
     33// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance
     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) )
     48
     49
     50// The origin is the position encountered at the start of iteration,
     51// signifying, "need to advance to the first element," and at the end
     52// of iteration, signifying, "no more elements."  Normal comsumption of
     53// an iterator runs ?`moveNext as the first step, and uses the return
     54// of ?`moveNext as a guard, before dereferencing the iterator.  So
     55// normal consumption of an iterator does not dereference an iterator
     56// in origin position.  The value of a pointer (underlying a refence)
     57// that is exposed publicly as an iteraor, and also a pointer stored
     58// internally in a link field, is tagged, to indicate "is the origin"
     59// (internally, is the list-head sentinel node), or untagged, to indicate
     60// "is a regular node."  Intent is to help a user who dereferences an
     61// iterator in origin position (which would be an API-use error on their
     62// part), by failing fast.
     63
     64#if defined( __x86_64 )
     65    // Preferred case: tag in the most-significant bit.  Dereference
     66    // has been shown to segfault consistently.  Maintenance should
     67    // list more architectures as "ok" here, to let them use the
     68    // preferred case, when valid.
     69    #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
     70#else
     71    // Fallback case: tag in the least-significant bit.  Dereference
     72    // will often give an alignment error, but may not, e.g. if
     73    // accessing a char-typed member.  32-bit x86 uses the most-
     74    // significant bit for real room on the heap.
     75    #define ORIGIN_TAG_BITNO 0
     76#endif
     77#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)
     78
     79#define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
     80#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
     81#define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)
     82
     83
     84forall( tE & ) {
     85
     86    struct dlink{
     87        tE *next;
     88        tE *prev;
     89    };
     90
     91    static inline void ?{}( dlink(tE) & this ) {
     92        this.next = 0p;
     93        this.prev = 0p;
     94    }
     95
     96    forall( tLinks & = dlink(tE) )
     97    struct dlist {
     98        inline dlink(tE);
     99    };
     100
     101    forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
     102        static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) {
     103            dlink(tE) & link_from_null = ( * (tE *) 0p )`inner;
     104            ptrdiff_t link_offset = (ptrdiff_t) & link_from_null;
     105            size_t origin_addr = ((size_t) & lst) - link_offset;
     106            size_t preResult = ORIGIN_TAG_SET( origin_addr );
     107            return (tE *)preResult;
     108        }
     109
     110        static inline void ?{}( dlist(tE, tLinks) & this ) {
     111            tE * listOrigin = $get_list_origin_addr( this );
     112            ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ;
     113        }
     114    }
     115
    53116}
    54117
    55 #define __DLISTED_MGD_JUSTEXPL(STRUCT, IN_THELIST, STRUCT_IN_THELIST) \
    56 struct STRUCT_IN_THELIST { \
    57         inline STRUCT; \
    58 }; \
    59 \
    60 void ?{}(STRUCT_IN_THELIST &) = void; \
    61 \
    62 static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \
    63         return (STRUCT_IN_THELIST&)this; \
    64 }
    65 
    66 #define __DLISTED_MGD_JUSTIMPL(STRUCT)
    67 
    68 forall( tE & ) {
    69         struct $mgd_link {
    70                 tE *elem;
    71                 void *terminator;
    72                 _Bool is_terminator;
    73                 // will collapse to single pointer with tag bit
    74         };
    75         static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
    76                 (this.elem){ elem };
    77                 (this.terminator){ 0p };
    78                 (this.is_terminator){ 0 };
    79         }
    80         static inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
    81                 (this.elem){ 0p };
    82                 (this.terminator){ terminator };
    83                 (this.is_terminator){ 1 };
    84         }
    85         static inline void ?=?( $mgd_link(tE) &this, tE* elem ) {
    86                 this.elem = elem ;
    87                 this.terminator = 0p;
    88                 this.is_terminator = 0;
    89         }
    90         static inline void ?=?( $mgd_link(tE) &this, void * terminator ) {
    91                 this.elem = 0p;
    92                 this.terminator = terminator;
    93                 this.is_terminator = 1;
    94         }
    95         struct $dlinks {
    96                 // containing item is not listed
    97                 // iff
    98                 // links have (elem == 0p && terminator == 0p)
    99                 $mgd_link(tE) next;
    100                 $mgd_link(tE) prev;
    101         };
    102         static inline void ?{}( $dlinks(tE) &this ) {
    103                 (this.next){ (tE *)0p };
    104                 (this.prev){ (tE *)0p };
    105         }
    106 }
    107 
    108 #define DLISTED_MGD_EXPL_IN(STRUCT, LIST_SUF) \
    109   $dlinks(STRUCT) $links_ ## LIST_SUF;
    110 
    111 #define DLISTED_MGD_EXPL_OUT(STRUCT, LIST_SUF) \
    112   __DLISTED_MGD_JUSTEXPL(STRUCT, in_##LIST_SUF, STRUCT ## _in_ ## LIST_SUF) \
    113   __DLISTED_MGD_COMMON(STRUCT, STRUCT##_in_##LIST_SUF,  $links_ ## LIST_SUF)
    114 
    115 #define DLISTED_MGD_IMPL_IN(STRUCT) \
    116   $dlinks(STRUCT) $links;
    117 
    118 #define DLISTED_MGD_IMPL_OUT(STRUCT) \
    119   __DLISTED_MGD_JUSTIMPL(STRUCT) \
    120   __DLISTED_MGD_COMMON(STRUCT, STRUCT, $links)
    121 
    122 trait $dlistable(Tnode &, Telem &) {
    123         $mgd_link(Telem) & $prev_link(Tnode &);
    124         $mgd_link(Telem) & $next_link(Tnode &);
    125         Telem& $tempcv_n2e(Tnode &);
    126         Tnode& $tempcv_e2n(Telem &);
    127 
    128         Telem& ?`next(Tnode &);
    129         Telem& ?`prev(Tnode &);
    130 };
    131 
    132 forall (Tnode &, Telem & | $dlistable(Tnode, Telem)) {
    133 
    134         // implemented as a sentinel item in an underlying cicrular list
    135         // theList.$links.next is first
    136         // theList.$links.prev is last
    137         // note this allocation preserves prev-next composition as an identity
    138         struct dlist {
    139                 $dlinks(Telem) $links;
    140         };
    141 
    142         // an empty dlist
    143         // links refer to self, making a tight circle
    144         static inline void ?{}( dlist(Tnode, Telem) & this ) {
    145                 $mgd_link(Telem) selfRef = (void *) &this;
    146                 ( this.$links ) { selfRef, selfRef };
    147         }
    148 
    149         static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
    150                 return * l.$links.next.elem;
    151         }
    152 
    153         static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
    154                 return * l.$links.prev.elem;
    155         }
    156 
    157         #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
    158         static bool $validate_fwd( dlist(Tnode, Telem) & this ) {
    159                 Tnode * it = & $tempcv_e2n( this`first );
    160                 if (!it) return (& this`last == 0p);
    161 
    162                 while( $next_link(*it).elem ) {
    163                         it = & $tempcv_e2n( * $next_link(*it).elem );
    164                 }
    165 
    166                 return ( it == & $tempcv_e2n( this`last ) ) &&
    167                            ( $next_link(*it).is_terminator ) &&
    168                            ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this );
    169         }
    170         static bool $validate_rev( dlist(Tnode, Telem) & this ) {
    171                 Tnode * it = & $tempcv_e2n( this`last );
    172                 if (!it) return (& this`first == 0p);
    173 
    174                 while( $prev_link(*it).elem ) {
    175                         it = & $tempcv_e2n( * $prev_link(*it).elem );
    176                 }
    177 
    178                 return ( it == & $tempcv_e2n( this`first ) ) &&
    179                            ( $prev_link(*it).is_terminator ) &&
    180                            ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this );
    181         }
    182         static bool validate( dlist(Tnode, Telem) & this ) {
    183                 return $validate_fwd(this) && $validate_rev(this);
    184         }
    185         #endif
    186 
    187         static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
     118
     119forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) {
     120
     121        static inline void insert_after(tE & list_pos, tE &to_insert) {
    188122                verify (&list_pos != 0p);
    189123                verify (&to_insert != 0p);
    190                 Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
    191                 verify($prev_link(singleton_to_insert).elem == 0p);
    192                 verify($next_link(singleton_to_insert).elem == 0p);
    193                 $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
    194                 $next_link(singleton_to_insert) = $next_link(list_pos);
    195                 if ($next_link(list_pos).is_terminator) {
    196                         dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
    197                         $dlinks(Telem) *list_links = & list->$links;
    198                         $mgd_link(Telem) *list_last = & list_links->prev;
    199                         *list_last = &to_insert;
    200                 } else {
    201                         Telem *list_pos_next = $next_link(list_pos).elem;
    202                         if (list_pos_next) {
    203                                 Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next);
    204                                 $prev_link(lpn_inlist) = &to_insert;
    205                         }
    206                 }
    207                 $next_link(list_pos) = &to_insert;
    208         }
    209 
    210         static inline void insert_before(Tnode &list_pos, Telem &to_insert) {
     124        dlink(tE) & linkToInsert = to_insert`inner;
     125                verify(linkToInsert.prev == 0p);
     126                verify(linkToInsert.next == 0p);
     127        tE & list_pos_raw = list_pos;
     128        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
     129        dlink(tE) & list_pos_links = list_pos_elem`inner;
     130        asm( "" : : : "memory" );
     131        tE & after_raw = * list_pos_links.next;
     132        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     133                linkToInsert.prev = & list_pos_raw;
     134                linkToInsert.next = & after_raw;
     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) {
    211142                verify (&list_pos != 0p);
    212143                verify (&to_insert != 0p);
    213                 Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
    214                 verify($prev_link(singleton_to_insert).elem == 0p);
    215                 verify($next_link(singleton_to_insert).elem == 0p);
    216                 $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
    217                 $prev_link(singleton_to_insert) = $prev_link(list_pos);
    218                 if ($prev_link(list_pos).is_terminator) {
    219                         dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
    220                         $dlinks(Telem) *list_links = & list->$links;
    221                         $mgd_link(Telem) *list_first = & list_links->next;
    222                         *list_first = &to_insert;
    223                 } else {
    224                         Telem *list_pos_prev = $prev_link(list_pos).elem;
    225                         if (list_pos_prev) {
    226                                 Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev);
    227                                 $next_link(lpp_inlist) = &to_insert;
    228                         }
    229                 }
    230                 $prev_link(list_pos) = &to_insert;
    231         }
    232 
    233     static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) {
    234                 verify (&list != 0p);
    235                 verify (&to_insert != 0p);
    236                 Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
    237                 verify($prev_link(singleton_to_insert).elem == 0p);
    238                 verify($next_link(singleton_to_insert).elem == 0p);
    239 
    240                 $prev_link(singleton_to_insert) = (void*) &list;
    241                 $next_link(singleton_to_insert) = list.$links.next;
    242 
    243                 $dlinks(Telem) *listLinks = & list.$links;
    244                 if (listLinks->next.is_terminator) {
    245                         $mgd_link(Telem) * listPrevReference = & listLinks->prev;
    246                         *listPrevReference = &to_insert;
    247                 } else {
    248                         Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem);
    249                         $prev_link(next_inlist) = &to_insert;
    250                 }
    251                 $mgd_link(Telem) * listNextReference = & listLinks->next;
    252                 *listNextReference = &to_insert;
    253         }
    254 
    255     static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) {
    256                 verify (&list != 0p);
    257                 verify (&to_insert != 0p);
    258                 Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
    259                 verify($next_link(singleton_to_insert).elem == 0p);
    260                 verify($prev_link(singleton_to_insert).elem == 0p);
    261 
    262                 $next_link(singleton_to_insert) = (void*) &list;
    263                 $prev_link(singleton_to_insert) = list.$links.prev;
    264 
    265                 $dlinks(Telem) *listLinks = & list.$links;
    266                 if (listLinks->prev.is_terminator) {
    267                         $mgd_link(Telem) * listNextReference = & listLinks->next;
    268                         *listNextReference = &to_insert;
    269                 } else {
    270                         Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem);
    271                         $next_link(prev_inlist) = &to_insert;
    272                 }
    273                 $mgd_link(Telem) * listPrevReference = & listLinks->prev;
    274                 *listPrevReference = &to_insert;
    275         }
    276 
    277     static inline void remove(Tnode &list_pos) {
    278                 verify( &list_pos != 0p );
    279 
    280                 $mgd_link(Telem) &incoming_from_prev = *0p;
    281                 $mgd_link(Telem) &incoming_from_next = *0p;
    282 
    283                 if ( $prev_link(list_pos).is_terminator ) {
    284                         dlist(Tnode, Telem) * tgt_before = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
    285                         $dlinks(Telem) * links_before = & tgt_before->$links;
    286                         &incoming_from_prev = & links_before->next;
    287                 } else if ($prev_link(list_pos).elem) {
    288                         Telem * tgt_before = $prev_link(list_pos).elem;
    289                         Tnode & list_pos_before = $tempcv_e2n(*tgt_before);
    290                         &incoming_from_prev = & $next_link(list_pos_before);
    291                 }
    292 
    293                 if ( $next_link(list_pos).is_terminator ) {
    294                         dlist(Tnode, Telem) * tgt_after = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
    295                         $dlinks(Telem) * links_after = & tgt_after->$links;
    296                         &incoming_from_next = & links_after->prev;
    297                 } else if ($next_link(list_pos).elem) {
    298                         Telem * tgt_after  = $next_link(list_pos).elem;
    299                         Tnode & list_pos_after  = $tempcv_e2n(*tgt_after );
    300                         &incoming_from_next = & $prev_link(list_pos_after );
    301                 }
    302 
    303                 if (& incoming_from_prev) {
    304                         incoming_from_prev = $next_link(list_pos);
    305                 }
    306                 if (& incoming_from_next) {
    307                         incoming_from_next = $prev_link(list_pos);
    308                 }
    309 
    310                 $next_link(list_pos) = (Telem*) 0p;
    311                 $prev_link(list_pos) = (Telem*) 0p;
    312         }
    313 
    314         static inline bool ?`is_empty(dlist(Tnode, Telem) &list) {
    315                 verify( &list != 0p );
    316                 $dlinks(Telem) *listLinks = & list.$links;
    317                 if (listLinks->next.is_terminator) {
    318                         verify(listLinks->prev.is_terminator);
    319                         verify(listLinks->next.terminator);
    320                         verify(listLinks->prev.terminator);
    321                         return true;
    322                 } else {
    323                         verify(!listLinks->prev.is_terminator);
    324                         verify(listLinks->next.elem);
    325                         verify(listLinks->prev.elem);
    326                         return false;
    327                 }
    328         }
    329 
    330         static inline Telem & pop_first(dlist(Tnode, Telem) &list) {
    331                 verify( &list != 0p );
    332                 verify( !list`is_empty );
    333                 $dlinks(Telem) *listLinks = & list.$links;
    334                 Telem & first = *listLinks->next.elem;
    335                 Tnode & list_pos_first  = $tempcv_e2n( first );
    336                 remove(list_pos_first);
    337                 return first;
    338         }
    339 
    340         static inline Telem & pop_last(dlist(Tnode, Telem) &list) {
    341                 verify( &list != 0p );
    342                 verify( !list`is_empty );
    343                 $dlinks(Telem) *listLinks = & list.$links;
    344                 Telem & last = *listLinks->prev.elem;
    345                 Tnode & list_pos_last  = $tempcv_e2n( last );
    346                 remove(list_pos_last);
    347                 return last;
    348         }
     144        dlink(tE) & linkToInsert = to_insert`inner;
     145                verify(linkToInsert.next == 0p);
     146                verify(linkToInsert.prev == 0p);
     147        tE & list_pos_raw = list_pos;
     148        tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw );
     149        dlink(tE) & list_pos_links = list_pos_elem`inner;
     150        asm( "" : : : "memory" );
     151        tE & before_raw = * (list_pos_links).prev;
     152        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     153                linkToInsert.next = & list_pos_raw;
     154                linkToInsert.prev = & before_raw;
     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) {
     162                verify (&list_pos != 0p);
     163        tE & list_pos_elem = list_pos;
     164        verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) );
     165        dlink(tE) & list_pos_links = list_pos_elem`inner;
     166        tE & before_raw = * list_pos_links.prev;
     167        tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw );
     168        dlink(tE) & before_links = before_elem`inner;
     169        tE & after_raw = * list_pos_links.next;
     170        tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw );
     171        dlink(tE) & after_links = after_elem`inner;
     172        before_links.next = &after_raw;
     173        after_links.prev = &before_raw;
     174        asm( "" : : : "memory" );
     175                list_pos_links.prev = 0p;
     176                list_pos_links.next = 0p;
     177        asm( "" : : : "memory" );
     178        return list_pos_elem;
     179        }
     180
     181    static inline tE & ?`first( dlist(tE, tLinks) &lst ) {
     182        tE * firstPtr = lst.next;
     183        if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p;
     184        return *firstPtr;
     185    }
     186    static inline tE & ?`last ( dlist(tE, tLinks) &lst ) {
     187        tE * lastPtr = lst.prev;
     188        if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p;
     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 ) {
     199        tE * origin = $get_list_origin_addr( lst );
     200        return *origin;
     201    }
     202
     203    static inline bool ?`moveNext( tE && refx ) {
     204        tE && ref_inner = refx;
     205        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     206        &ref_inner = oldReferent`inner.next;
     207        return &ref_inner != 0p  &&
     208            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
     209    }
     210
     211    static inline bool ?`movePrev( tE && refx ) {
     212        tE && ref_inner = refx;
     213        tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner );
     214        &ref_inner = oldReferent`inner.prev;
     215        return &ref_inner != 0p  &&
     216            ! ORIGIN_TAG_QUERY( (size_t) & ref_inner );
     217    }
     218
     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
     237    static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) {
     238        insert_after(lst`elems, e);
     239    }
     240
     241    static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) {
     242        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;
     257    }
     258
     259
     260  #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
     261        static bool $validate_fwd( dlist(tE, tLinks) & this ) {
     262        if ( ! & this`first ) return ( (& this`last) == 0p);
     263
     264        tE & lagElem = *0p;
     265
     266        while ( tE & it = this`elems; it`moveNext ) {
     267            if (& lagElem == 0p &&  &it != & this`first ) return false;
     268            & lagElem = & it;
     269        }
     270
     271        if (& lagElem != & this`last) return false;
     272
     273        // TODO: verify that it is back at this`elems;
     274        return true;
     275        }
     276        static bool $validate_rev( dlist(tE, tLinks) & this ) {
     277        if ( ! & this`last ) return ( (& this`first) == 0p);
     278
     279        tE & lagElem = *0p;
     280
     281        while ( tE & it = this`elems; it`movePrev ) {
     282            if (& lagElem == 0p &&  &it != & this`last ) return false;
     283            & lagElem = & it;
     284        }
     285
     286        if (& lagElem != & this`first) return false;
     287
     288        // TODO: verify that it is back at this`elems;
     289        return true;
     290        }
     291        static bool validate( dlist(tE, tLinks) & this ) {
     292                return $validate_fwd(this) && $validate_rev(this);
     293        }
     294  #endif
    349295
    350296}
Note: See TracChangeset for help on using the changeset viewer.