Changeset 69914cbc


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.

Files:
2 added
3 deleted
10 edited

Legend:

Unmodified
Added
Removed

  • libcfa/src/Makefile.am

    r67b421c r69914cbc  
    5959        concurrency/iofwd.hfa \
    6060        containers/list.hfa \
    61         containers/list2.hfa \
    6261        containers/queueLockFree.hfa \
    6362        containers/stackLockFree.hfa \

  • libcfa/src/concurrency/alarm.hfa

    r67b421c r69914cbc  
    4949        Duration period;                        // if > 0 => period of alarm
    5050
    51         DLISTED_MGD_IMPL_IN(alarm_node_t)
     51        inline dlink(alarm_node_t);
    5252
    5353        union {
    … …  
    6060        enum alarm_type type;           // true if this is not a user defined alarm
    6161};
    62 DLISTED_MGD_IMPL_OUT(alarm_node_t)
     62P9_EMBEDDED( alarm_node_t, dlink(alarm_node_t) )
    6363
    6464void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period );
    … …  
    6767void ^?{}( alarm_node_t & this );
    6868
    69 typedef dlist(alarm_node_t, alarm_node_t) alarm_list_t;
     69typedef dlist(alarm_node_t) alarm_list_t;
    7070
    7171void insert( alarm_list_t * this, alarm_node_t * n );

  • libcfa/src/concurrency/kernel.cfa

    r67b421c r69914cbc  
    908908        }
    909909
    910         static void crawl_list( cluster * cltr, dlist(processor, processor) & list, unsigned count ) {
     910        static void crawl_list( cluster * cltr, dlist(processor) & list, unsigned count ) {
    911911                /* paranoid */ verify( cltr->stats );
    912912

  • libcfa/src/concurrency/kernel.hfa

    r67b421c r69914cbc  
    107107
    108108        // Link lists fields
    109         DLISTED_MGD_IMPL_IN(processor)
     109        inline dlink(processor);
    110110
    111111        // special init fields
    … …  
    129129#endif
    130130};
     131P9_EMBEDDED( processor, dlink(processor) )
    131132
    132133void  ?{}(processor & this, const char name[], struct cluster & cltr);
    … …  
    136137static inline void  ?{}(processor & this, struct cluster & cltr) { this{ "Anonymous Processor", cltr}; }
    137138static inline void  ?{}(processor & this, const char name[])     { this{name, *mainCluster}; }
    138 
    139 DLISTED_MGD_IMPL_OUT(processor)
    140139
    141140//-----------------------------------------------------------------------------
    … …  
    186185
    187186        // List of idle processors
    188         dlist(processor, processor) idles;
     187        dlist(processor) idles;
    189188
    190189        // List of active processors
    191         dlist(processor, processor) actives;
     190        dlist(processor) actives;
    192191};
    193192

  • libcfa/src/concurrency/ready_queue.cfa

    r67b421c r69914cbc  
    554554}
    555555
    556 static void assign_list(unsigned & value, dlist(processor, processor) & list, unsigned count) {
     556static void assign_list(unsigned & value, dlist(processor) & list, unsigned count) {
    557557        processor * it = &list`first;
    558558        for(unsigned i = 0; i < count; i++) {

  • 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}

  • libcfa/src/executor.cfa

    r67b421c r69914cbc  
    77#include <containers/list.hfa>
    88
    9 forall( T & | $dlistable(T, T) ) {
     9forall( T &, TLink& = dlink(T) | embedded(T, TLink, dlink(T)) ) {
    1010        monitor Buffer {                                                                        // unbounded buffer
    11                 dlist( T, T ) queue;                                                    // unbounded list of work requests
     11                dlist( T, TLink ) queue;                                                // unbounded list of work requests
    1212                condition delay;
    1313        }; // Buffer
    1414
    15         void insert( Buffer(T) & mutex buf, T * elem ) with(buf) {
    16                 dlist( T, T ) * qptr = &queue;                                  // workaround https://cforall.uwaterloo.ca/trac/ticket/166
     15        void insert( Buffer(T, TLink) & mutex buf, T * elem ) with(buf) {
     16                dlist( T, TLink ) * qptr = &queue;                              // workaround https://cforall.uwaterloo.ca/trac/ticket/166
    1717                insert_last( *qptr, *elem );                                    // insert element into buffer
    1818                signal( delay );                                                                // restart
    1919        } // insert
    2020
    21         T * remove( Buffer(T) & mutex buf ) with(buf) {
    22                 dlist( T, T ) * qptr = &queue;                                  // workaround https://cforall.uwaterloo.ca/trac/ticket/166
    23                 // if ( (*qptr)`is_empty ) wait( delay );                       // no request to process ? => wait
    24           if ( (*qptr)`is_empty ) return 0p;                            // no request to process ? => wait
    25                 return &pop_first( *qptr );
     21        T * remove( Buffer(T, TLink) & mutex buf ) with(buf) {
     22                dlist( T, TLink ) * qptr = &queue;                              // workaround https://cforall.uwaterloo.ca/trac/ticket/166
     23                // if ( (*qptr)`isEmpty ) wait( delay );                // no request to process ? => wait
     24          if ( (*qptr)`isEmpty ) return 0p;                                     // no request to process ? => wait
     25                return &try_pop_front( *qptr );
    2626        } // remove
    2727} // forall
    … …  
    2929struct WRequest {                                                                               // client request, no return
    3030        void (* action)( void );
    31         DLISTED_MGD_IMPL_IN(WRequest)
     31        inline dlink(WRequest);
    3232}; // WRequest
    33 DLISTED_MGD_IMPL_OUT(WRequest)
     33P9_EMBEDDED(WRequest, dlink(WRequest))
    3434
    3535void ?{}( WRequest & req ) with(req) { action = 0; }

  • tests/list/.expect/dlist-insert-remove.txt

    r67b421c r69914cbc  
    1 ~~~~~~~~~~~~~~~~~ Headless List Tests - insert_after ~~~~~~~~~~~~~~~~
    2 
    3 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    4 Test 1-i:  Modifying Freds on MINE
    5 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    6 ==== fred by MINE before
    7 3.14
    8 -
    9 3.14
    10 -
    11 0.5
    12 -
    13 0.5
    14 -
    15 ==== fred by YOURS before
    16 3.14
    17 -
    18 3.14
    19 -
    20 0.5
    21 -
    22 0.5
    23 -
    24 ==== fred by MINE after
    25 3.14
    26 0.5
    27 -
    28 3.14
    29 -
    30 0.5
    31 -
    32 0.5
    33 3.14
    34 -
    35 ==== fred by YOURS after
    36 3.14
    37 -
    38 3.14
    39 -
    40 0.5
    41 -
    42 0.5
    43 -
    44 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    45 Test 2-i.  Modifying Freds on YOURS
    46 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    47 ==== fred by MINE before
    48 3.14
    49 -
    50 3.14
    51 -
    52 0.5
    53 -
    54 0.5
    55 -
    56 ==== fred by YOURS before
    57 3.14
    58 -
    59 3.14
    60 -
    61 0.5
    62 -
    63 0.5
    64 -
    65 ==== fred by MINE after
    66 3.14
    67 -
    68 3.14
    69 -
    70 0.5
    71 -
    72 0.5
    73 -
    74 ==== fred by YOURS after
    75 3.14
    76 0.5
    77 -
    78 3.14
    79 -
    80 0.5
    81 -
    82 0.5
    83 3.14
    84 -
    85 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    86 Test 3-i.  Modifying Maries
    87 ~~~~~~~~~~~~~~~~~~~~~~~~~~~
    88 ==== mary before
    89 3.14
    90 -
    91 3.14
    92 -
    93 0.5
    94 -
    95 0.5
    96 -
    97 ==== mary after
    98 3.14
    99 0.5
    100 -
    101 3.14
    102 -
    103 0.5
    104 -
    105 0.5
    106 3.14
    107 -
    108 
    109 ~~~~~~~~~~~~~~~~ Headless List Tests - insert_before ~~~~~~~~~~~~~~~~
    110 
    111 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    112 Test 1-ii:  Modifying Freds on MINE
    113 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    114 ==== fred by MINE before
    115 3.14
    116 -
    117 3.14
    118 -
    119 0.5
    120 -
    121 0.5
    122 -
    123 ==== fred by YOURS before
    124 3.14
    125 -
    126 3.14
    127 -
    128 0.5
    129 -
    130 0.5
    131 -
    132 ==== fred by MINE after
    133 3.14
    134 0.5
    135 -
    136 3.14
    137 -
    138 0.5
    139 -
    140 0.5
    141 3.14
    142 -
    143 ==== fred by YOURS after
    144 3.14
    145 -
    146 3.14
    147 -
    148 0.5
    149 -
    150 0.5
    151 -
    152 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    153 Test 2-ii.  Modifying Freds on YOURS
    154 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    155 ==== fred by MINE before
    156 3.14
    157 -
    158 3.14
    159 -
    160 0.5
    161 -
    162 0.5
    163 -
    164 ==== fred by YOURS before
    165 3.14
    166 -
    167 3.14
    168 -
    169 0.5
    170 -
    171 0.5
    172 -
    173 ==== fred by MINE after
    174 3.14
    175 -
    176 3.14
    177 -
    178 0.5
    179 -
    180 0.5
    181 -
    182 ==== fred by YOURS after
    183 3.14
    184 0.5
    185 -
    186 3.14
    187 -
    188 0.5
    189 -
    190 0.5
    191 3.14
    192 -
    193 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    194 Test 3-ii.  Modifying Maries
    195 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    196 ==== mary before
    197 3.14
    198 -
    199 3.14
    200 -
    201 0.5
    202 -
    203 0.5
    204 -
    205 ==== mary after
    206 3.14
    207 0.5
    208 -
    209 3.14
    210 -
    211 0.5
    212 -
    213 0.5
    214 3.14
    215 -
    2161
    2172~~~~~~~~~~~~~~~~~ Headed List Tests - insert_first ~~~~~~~~~~~~~~~~~~
    … …  
    557342-
    558343
    559 ~~~~~~~~~~ Element removal tests on Headless List: mid ~~~~~~~~~~
    560 
    561 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    562 Test 10-i.  Modifying Freds on MINE
    563 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    564 ==== fred by MINE before
    565 1.7
    566 2.7
    567 3.7
    568 -
    569 1.7
    570 -
    571 3.7
    572 -
    573 3.7
    574 2.7
    575 1.7
    576 -
    577 ==== fred by YOURS before
    578 1.7
    579 2.7
    580 3.7
    581 -
    582 1.7
    583 -
    584 3.7
    585 -
    586 3.7
    587 2.7
    588 1.7
    589 -
    590 ==== fred by MINE after
    591 1.7
    592 3.7
    593 -
    594 1.7
    595 -
    596 3.7
    597 -
    598 3.7
    599 1.7
    600 -
    601 ==== fred by YOURS after
    602 1.7
    603 2.7
    604 3.7
    605 -
    606 1.7
    607 -
    608 3.7
    609 -
    610 3.7
    611 2.7
    612 1.7
    613 -
    614 ==== fred by MINE after
    615 2.7
    616 -
    617 2.7
    618 -
    619 -
    620 -
    621 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    622 Test 11-i.  Modifying Freds on YOURS
    623 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    624 ==== fred by MINE before
    625 1.7
    626 2.7
    627 3.7
    628 -
    629 1.7
    630 -
    631 3.7
    632 -
    633 3.7
    634 2.7
    635 1.7
    636 -
    637 ==== fred by YOURS before
    638 1.7
    639 2.7
    640 3.7
    641 -
    642 1.7
    643 -
    644 3.7
    645 -
    646 3.7
    647 2.7
    648 1.7
    649 -
    650 ==== fred by MINE after
    651 1.7
    652 2.7
    653 3.7
    654 -
    655 1.7
    656 -
    657 3.7
    658 -
    659 3.7
    660 2.7
    661 1.7
    662 -
    663 ==== fred by YOURS after
    664 1.7
    665 3.7
    666 -
    667 1.7
    668 -
    669 3.7
    670 -
    671 3.7
    672 1.7
    673 -
    674 ==== fred by YOURS after
    675 2.7
    676 -
    677 2.7
    678 -
    679 -
    680 -
    681 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    682 Test 12-i.  Modifying Maries
    683 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     344~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~
     345
     346~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     347Test 13-i.  Modifying Freds on MINE
     348~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     349==== fred by MINE before
     3501.7
     3512.7
     3523.7
     353-
     3541.7
     355-
     3563.7
     357-
     3583.7
     3592.7
     3601.7
     361-
     362==== fred by YOURS before
     3631.7
     3642.7
     3653.7
     366-
     3671.7
     368-
     3693.7
     370-
     3713.7
     3722.7
     3731.7
     374-
     375==== fred by MINE after
     3762.7
     3773.7
     378-
     3792.7
     380-
     3813.7
     382-
     3833.7
     3842.7
     385-
     386==== fred by YOURS after
     3871.7
     3882.7
     3893.7
     390-
     3911.7
     392-
     3933.7
     394-
     3953.7
     3962.7
     3971.7
     398-
     399==== fred by MINE after
     4001.7
     401-
     4021.7
     403-
     404-
     405-
     406~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     407Test 14-i.  Modifying Freds on YOURS
     408~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     409==== fred by MINE before
     4101.7
     4112.7
     4123.7
     413-
     4141.7
     415-
     4163.7
     417-
     4183.7
     4192.7
     4201.7
     421-
     422==== fred by YOURS before
     4231.7
     4242.7
     4253.7
     426-
     4271.7
     428-
     4293.7
     430-
     4313.7
     4322.7
     4331.7
     434-
     435==== fred by MINE after
     4361.7
     4372.7
     4383.7
     439-
     4401.7
     441-
     4423.7
     443-
     4443.7
     4452.7
     4461.7
     447-
     448==== fred by YOURS after
     4492.7
     4503.7
     451-
     4522.7
     453-
     4543.7
     455-
     4563.7
     4572.7
     458-
     459==== fred by YOURS after
     4601.7
     461-
     4621.7
     463-
     464-
     465-
     466~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     467Test 15-i.  Modifying Maries
     468~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    684469==== mary before
    6854701.7
    … …  
    696481-
    697482==== mary after
    698 1.7
    699 3.7
    700 -
    701 1.7
    702 -
    703 3.7
    704 -
    705 3.7
    706 1.7
    707 -
    708 ==== mary after
    709 2.7
    710 -
    711 2.7
    712 -
    713 -
    714 -
    715 
    716 ~~~~~~~~~~ Element removal tests on Headless List: at first ~~~~~~~~~~
    717 
    718 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    719 Test 10-ii.  Modifying Freds on MINE
    720 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    721 ==== fred by MINE before
    722 1.7
    723 2.7
    724 3.7
    725 -
    726 1.7
    727 -
    728 3.7
    729 -
    730 3.7
    731 2.7
    732 1.7
    733 -
    734 ==== fred by YOURS before
    735 1.7
    736 2.7
    737 3.7
    738 -
    739 1.7
    740 -
    741 3.7
    742 -
    743 3.7
    744 2.7
    745 1.7
    746 -
    747 ==== fred by MINE after
    748 2.7
    749 3.7
    750 -
    751 2.7
    752 -
    753 3.7
    754 -
    755 3.7
    756 2.7
    757 -
    758 ==== fred by YOURS after
    759 1.7
    760 2.7
    761 3.7
    762 -
    763 1.7
    764 -
    765 3.7
    766 -
    767 3.7
    768 2.7
    769 1.7
    770 -
    771 ==== fred by MINE after
    772 1.7
    773 -
    774 1.7
    775 -
    776 -
    777 -
    778 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    779 Test 11-ii.  Modifying Freds on YOURS
    780 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    781 ==== fred by MINE before
    782 1.7
    783 2.7
    784 3.7
    785 -
    786 1.7
    787 -
    788 3.7
    789 -
    790 3.7
    791 2.7
    792 1.7
    793 -
    794 ==== fred by YOURS before
    795 1.7
    796 2.7
    797 3.7
    798 -
    799 1.7
    800 -
    801 3.7
    802 -
    803 3.7
    804 2.7
    805 1.7
    806 -
    807 ==== fred by MINE after
    808 1.7
    809 2.7
    810 3.7
    811 -
    812 1.7
    813 -
    814 3.7
    815 -
    816 3.7
    817 2.7
    818 1.7
    819 -
    820 ==== fred by YOURS after
    821 2.7
    822 3.7
    823 -
    824 2.7
    825 -
    826 3.7
    827 -
    828 3.7
    829 2.7
    830 -
    831 ==== fred by YOURS after
    832 1.7
    833 -
    834 1.7
    835 -
    836 -
    837 -
    838 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    839 Test 12-ii.  Modifying Maries
    840 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     4832.7
     4843.7
     485-
     4862.7
     487-
     4883.7
     489-
     4903.7
     4912.7
     492-
     493==== mary after
     4941.7
     495-
     4961.7
     497-
     498-
     499-
     500
     501~~~~~~~~~~ Element removal tests on Headed List: at last ~~~~~~~~~~
     502
     503~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     504Test 13-ii.  Modifying Freds on MINE
     505~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     506==== fred by MINE before
     5071.7
     5082.7
     5093.7
     510-
     5111.7
     512-
     5133.7
     514-
     5153.7
     5162.7
     5171.7
     518-
     519==== fred by YOURS before
     5201.7
     5212.7
     5223.7
     523-
     5241.7
     525-
     5263.7
     527-
     5283.7
     5292.7
     5301.7
     531-
     532==== fred by MINE after
     5331.7
     5342.7
     535-
     5361.7
     537-
     5382.7
     539-
     5402.7
     5411.7
     542-
     543==== fred by YOURS after
     5441.7
     5452.7
     5463.7
     547-
     5481.7
     549-
     5503.7
     551-
     5523.7
     5532.7
     5541.7
     555-
     556==== fred by MINE after
     5573.7
     558-
     5593.7
     560-
     561-
     562-
     563~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     564Test 14-ii.  Modifying Freds on YOURS
     565~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     566==== fred by MINE before
     5671.7
     5682.7
     5693.7
     570-
     5711.7
     572-
     5733.7
     574-
     5753.7
     5762.7
     5771.7
     578-
     579==== fred by YOURS before
     5801.7
     5812.7
     5823.7
     583-
     5841.7
     585-
     5863.7
     587-
     5883.7
     5892.7
     5901.7
     591-
     592==== fred by MINE after
     5931.7
     5942.7
     5953.7
     596-
     5971.7
     598-
     5993.7
     600-
     6013.7
     6022.7
     6031.7
     604-
     605==== fred by YOURS after
     6061.7
     6072.7
     608-
     6091.7
     610-
     6112.7
     612-
     6132.7
     6141.7
     615-
     616==== fred by YOURS after
     6173.7
     618-
     6193.7
     620-
     621-
     622-
     623~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     624Test 15-ii.  Modifying Maries
     625~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    841626==== mary before
    8426271.7
    … …  
    853638-
    854639==== mary after
    855 2.7
    856 3.7
    857 -
    858 2.7
    859 -
    860 3.7
    861 -
    862 3.7
    863 2.7
    864 -
    865 ==== mary after
    866 1.7
    867 -
    868 1.7
    869 -
    870 -
    871 -
    872 
    873 ~~~~~~~~~~ Element removal tests on Headless List: at last ~~~~~~~~~~
    874 
    875 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    876 Test 10-iii.  Modifying Freds on MINE
    877 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    878 ==== fred by MINE before
    879 1.7
    880 2.7
    881 3.7
    882 -
    883 1.7
    884 -
    885 3.7
    886 -
    887 3.7
    888 2.7
    889 1.7
    890 -
    891 ==== fred by YOURS before
    892 1.7
    893 2.7
    894 3.7
    895 -
    896 1.7
    897 -
    898 3.7
    899 -
    900 3.7
    901 2.7
    902 1.7
    903 -
    904 ==== fred by MINE after
    905 1.7
    906 2.7
    907 -
    908 1.7
    909 -
    910 2.7
    911 -
    912 2.7
    913 1.7
    914 -
    915 ==== fred by YOURS after
    916 1.7
    917 2.7
    918 3.7
    919 -
    920 1.7
    921 -
    922 3.7
    923 -
    924 3.7
    925 2.7
    926 1.7
    927 -
    928 ==== fred by MINE after
    929 3.7
    930 -
    931 3.7
    932 -
    933 -
    934 -
    935 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    936 Test 11-iii.  Modifying Freds on YOURS
    937 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    938 ==== fred by MINE before
    939 1.7
    940 2.7
    941 3.7
    942 -
    943 1.7
    944 -
    945 3.7
    946 -
    947 3.7
    948 2.7
    949 1.7
    950 -
    951 ==== fred by YOURS before
    952 1.7
    953 2.7
    954 3.7
    955 -
    956 1.7
    957 -
    958 3.7
    959 -
    960 3.7
    961 2.7
    962 1.7
    963 -
    964 ==== fred by MINE after
    965 1.7
    966 2.7
    967 3.7
    968 -
    969 1.7
    970 -
    971 3.7
    972 -
    973 3.7
    974 2.7
    975 1.7
    976 -
    977 ==== fred by YOURS after
    978 1.7
    979 2.7
    980 -
    981 1.7
    982 -
    983 2.7
    984 -
    985 2.7
    986 1.7
    987 -
    988 ==== fred by YOURS after
    989 3.7
    990 -
    991 3.7
    992 -
    993 -
    994 -
    995 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    996 Test 12-iii.  Modifying Maries
    997 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     6401.7
     6412.7
     642-
     6431.7
     644-
     6452.7
     646-
     6472.7
     6481.7
     649-
     650==== mary after
     6513.7
     652-
     6533.7
     654-
     655-
     656-
     657
     658~~~~~~~~~~ Element removal tests on Headed List: of sole ~~~~~~~~~~
     659
     660~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     661Test 13-iii.  Modifying Freds on MINE
     662~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     663==== fred by MINE before
     6640.7
     665-
     6660.7
     667-
     6680.7
     669-
     6700.7
     671-
     672==== fred by YOURS before
     6730.7
     674-
     6750.7
     676-
     6770.7
     678-
     6790.7
     680-
     681==== fred by YOURS after
     6820.7
     683-
     6840.7
     685-
     6860.7
     687-
     6880.7
     689-
     690==== fred by MINE after
     6910.7
     692-
     6930.7
     694-
     695-
     696-
     697==== fred by MINE after
     6980.7
     699-
     7000.7
     701-
     7020.7
     703-
     7040.7
     705-
     706~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     707Test 14-iii.  Modifying Freds on YOURS
     708~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     709==== fred by MINE before
     7100.7
     711-
     7120.7
     713-
     7140.7
     715-
     7160.7
     717-
     718==== fred by YOURS before
     7190.7
     720-
     7210.7
     722-
     7230.7
     724-
     7250.7
     726-
     727==== fred by YOURS after
     7280.7
     729-
     7300.7
     731-
     7320.7
     733-
     7340.7
     735-
     736==== fred by YOURS after
     7370.7
     738-
     7390.7
     740-
     741-
     742-
     743==== fred by YOURS after
     7440.7
     745-
     7460.7
     747-
     7480.7
     749-
     7500.7
     751-
     752~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     753Test 15-iii.  Modifying Maries
     754~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    998755==== mary before
    999 1.7
    1000 2.7
    1001 3.7
    1002 -
    1003 1.7
    1004 -
    1005 3.7
    1006 -
    1007 3.7
    1008 2.7
    1009 1.7
    1010 -
    1011 ==== mary after
    1012 1.7
    1013 2.7
    1014 -
    1015 1.7
    1016 -
    1017 2.7
    1018 -
    1019 2.7
    1020 1.7
    1021 -
    1022 ==== mary after
    1023 3.7
    1024 -
    1025 3.7
    1026 -
    1027 -
    1028 -
    1029 
    1030 ~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~
    1031 
    1032 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1033 Test 13-i.  Modifying Freds on MINE
    1034 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1035 ==== fred by MINE before
    1036 1.7
    1037 2.7
    1038 3.7
    1039 -
    1040 1.7
    1041 -
    1042 3.7
    1043 -
    1044 3.7
    1045 2.7
    1046 1.7
    1047 -
    1048 ==== fred by YOURS before
    1049 1.7
    1050 2.7
    1051 3.7
    1052 -
    1053 1.7
    1054 -
    1055 3.7
    1056 -
    1057 3.7
    1058 2.7
    1059 1.7
    1060 -
    1061 ==== fred by MINE after
    1062 2.7
    1063 3.7
    1064 -
    1065 2.7
    1066 -
    1067 3.7
    1068 -
    1069 3.7
    1070 2.7
    1071 -
    1072 ==== fred by YOURS after
    1073 1.7
    1074 2.7
    1075 3.7
    1076 -
    1077 1.7
    1078 -
    1079 3.7
    1080 -
    1081 3.7
    1082 2.7
    1083 1.7
    1084 -
    1085 ==== fred by MINE after
    1086 1.7
    1087 -
    1088 1.7
    1089 -
    1090 -
    1091 -
    1092 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1093 Test 14-i.  Modifying Freds on YOURS
    1094 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1095 ==== fred by MINE before
    1096 1.7
    1097 2.7
    1098 3.7
    1099 -
    1100 1.7
    1101 -
    1102 3.7
    1103 -
    1104 3.7
    1105 2.7
    1106 1.7
    1107 -
    1108 ==== fred by YOURS before
    1109 1.7
    1110 2.7
    1111 3.7
    1112 -
    1113 1.7
    1114 -
    1115 3.7
    1116 -
    1117 3.7
    1118 2.7
    1119 1.7
    1120 -
    1121 ==== fred by MINE after
    1122 1.7
    1123 2.7
    1124 3.7
    1125 -
    1126 1.7
    1127 -
    1128 3.7
    1129 -
    1130 3.7
    1131 2.7
    1132 1.7
    1133 -
    1134 ==== fred by YOURS after
    1135 2.7
    1136 3.7
    1137 -
    1138 2.7
    1139 -
    1140 3.7
    1141 -
    1142 3.7
    1143 2.7
    1144 -
    1145 ==== fred by YOURS after
    1146 1.7
    1147 -
    1148 1.7
    1149 -
    1150 -
    1151 -
    1152 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1153 Test 15-i.  Modifying Maries
     7560.7
     757-
     7580.7
     759-
     7600.7
     761-
     7620.7
     763-
     764==== mary after
     7650.7
     766-
     7670.7
     768-
     769-
     770-
     771==== mary after
     7720.7
     773-
     7740.7
     775-
     7760.7
     777-
     7780.7
     779-
     780
     781~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~
     782
     783~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     784Test 16-i.  Modifying Freds on MINE
     785~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     786==== fred by MINE before
     7871.7
     7882.7
     7893.7
     790-
     7911.7
     792-
     7933.7
     794-
     7953.7
     7962.7
     7971.7
     798-
     799==== fred by YOURS before
     8001.7
     8012.7
     8023.7
     803-
     8041.7
     805-
     8063.7
     807-
     8083.7
     8092.7
     8101.7
     811-
     812==== fred by MINE after
     8132.7
     8143.7
     815-
     8162.7
     817-
     8183.7
     819-
     8203.7
     8212.7
     822-
     823==== fred by YOURS after
     8241.7
     8252.7
     8263.7
     827-
     8281.7
     829-
     8303.7
     831-
     8323.7
     8332.7
     8341.7
     835-
     836==== fred by MINE after
     8371.7
     838-
     8391.7
     840-
     841-
     842-
     843~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     844Test 16-ii.  Modifying Freds on YOURS
     845~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     846==== fred by MINE before
     8471.7
     8482.7
     8493.7
     850-
     8511.7
     852-
     8533.7
     854-
     8553.7
     8562.7
     8571.7
     858-
     859==== fred by YOURS before
     8601.7
     8612.7
     8623.7
     863-
     8641.7
     865-
     8663.7
     867-
     8683.7
     8692.7
     8701.7
     871-
     872==== fred by MINE after
     8731.7
     8742.7
     8753.7
     876-
     8771.7
     878-
     8793.7
     880-
     8813.7
     8822.7
     8831.7
     884-
     885==== fred by YOURS after
     8862.7
     8873.7
     888-
     8892.7
     890-
     8913.7
     892-
     8933.7
     8942.7
     895-
     896==== fred by YOURS after
     8971.7
     898-
     8991.7
     900-
     901-
     902-
     903~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     904Test 16-iii.  Modifying Maries
    1154905~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1155906==== mary before
    … …  
    1185936-
    1186937
    1187 ~~~~~~~~~~ Element removal tests on Headed List: at last ~~~~~~~~~~
    1188 
    1189 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1190 Test 13-ii.  Modifying Freds on MINE
    1191 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1192 ==== fred by MINE before
    1193 1.7
    1194 2.7
    1195 3.7
    1196 -
    1197 1.7
    1198 -
    1199 3.7
    1200 -
    1201 3.7
    1202 2.7
    1203 1.7
    1204 -
    1205 ==== fred by YOURS before
    1206 1.7
    1207 2.7
    1208 3.7
    1209 -
    1210 1.7
    1211 -
    1212 3.7
    1213 -
    1214 3.7
    1215 2.7
    1216 1.7
    1217 -
    1218 ==== fred by MINE after
    1219 1.7
    1220 2.7
    1221 -
    1222 1.7
    1223 -
    1224 2.7
    1225 -
    1226 2.7
    1227 1.7
    1228 -
    1229 ==== fred by YOURS after
    1230 1.7
    1231 2.7
    1232 3.7
    1233 -
    1234 1.7
    1235 -
    1236 3.7
    1237 -
    1238 3.7
    1239 2.7
    1240 1.7
    1241 -
    1242 ==== fred by MINE after
    1243 3.7
    1244 -
    1245 3.7
    1246 -
    1247 -
    1248 -
    1249 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1250 Test 14-ii.  Modifying Freds on YOURS
    1251 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1252 ==== fred by MINE before
    1253 1.7
    1254 2.7
    1255 3.7
    1256 -
    1257 1.7
    1258 -
    1259 3.7
    1260 -
    1261 3.7
    1262 2.7
    1263 1.7
    1264 -
    1265 ==== fred by YOURS before
    1266 1.7
    1267 2.7
    1268 3.7
    1269 -
    1270 1.7
    1271 -
    1272 3.7
    1273 -
    1274 3.7
    1275 2.7
    1276 1.7
    1277 -
    1278 ==== fred by MINE after
    1279 1.7
    1280 2.7
    1281 3.7
    1282 -
    1283 1.7
    1284 -
    1285 3.7
    1286 -
    1287 3.7
    1288 2.7
    1289 1.7
    1290 -
    1291 ==== fred by YOURS after
    1292 1.7
    1293 2.7
    1294 -
    1295 1.7
    1296 -
    1297 2.7
    1298 -
    1299 2.7
    1300 1.7
    1301 -
    1302 ==== fred by YOURS after
    1303 3.7
    1304 -
    1305 3.7
    1306 -
    1307 -
    1308 -
    1309 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1310 Test 15-ii.  Modifying Maries
     938~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~
     939
     940~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     941Test 17-i.  Modifying Freds on MINE
     942~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     943==== fred by MINE before
     9441.7
     9452.7
     9463.7
     947-
     9481.7
     949-
     9503.7
     951-
     9523.7
     9532.7
     9541.7
     955-
     956==== fred by YOURS before
     9571.7
     9582.7
     9593.7
     960-
     9611.7
     962-
     9633.7
     964-
     9653.7
     9662.7
     9671.7
     968-
     969==== fred by MINE after
     9701.7
     9712.7
     972-
     9731.7
     974-
     9752.7
     976-
     9772.7
     9781.7
     979-
     980==== fred by YOURS after
     9811.7
     9822.7
     9833.7
     984-
     9851.7
     986-
     9873.7
     988-
     9893.7
     9902.7
     9911.7
     992-
     993==== fred by MINE after
     9943.7
     995-
     9963.7
     997-
     998-
     999-
     1000~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1001Test 17-ii.  Modifying Freds on YOURS
     1002~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1003==== fred by MINE before
     10041.7
     10052.7
     10063.7
     1007-
     10081.7
     1009-
     10103.7
     1011-
     10123.7
     10132.7
     10141.7
     1015-
     1016==== fred by YOURS before
     10171.7
     10182.7
     10193.7
     1020-
     10211.7
     1022-
     10233.7
     1024-
     10253.7
     10262.7
     10271.7
     1028-
     1029==== fred by MINE after
     10301.7
     10312.7
     10323.7
     1033-
     10341.7
     1035-
     10363.7
     1037-
     10383.7
     10392.7
     10401.7
     1041-
     1042==== fred by YOURS after
     10431.7
     10442.7
     1045-
     10461.7
     1047-
     10482.7
     1049-
     10502.7
     10511.7
     1052-
     1053==== fred by YOURS after
     10543.7
     1055-
     10563.7
     1057-
     1058-
     1059-
     1060~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1061Test 17-iii.  Modifying Maries
    13111062~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    13121063==== mary before
    … …  
    13421093-
    13431094
    1344 ~~~~~~~~~~ Element removal tests on Headed List: of sole ~~~~~~~~~~
    1345 
    1346 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1347 Test 13-iii.  Modifying Freds on MINE
    1348 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1349 ==== fred by MINE before
    1350 0.7
    1351 -
    1352 0.7
    1353 -
    1354 0.7
    1355 -
    1356 0.7
    1357 -
    1358 ==== fred by YOURS before
    1359 0.7
    1360 -
    1361 0.7
    1362 -
    1363 0.7
    1364 -
    1365 0.7
    1366 -
    1367 ==== fred by YOURS after
    1368 0.7
    1369 -
    1370 0.7
    1371 -
    1372 0.7
    1373 -
    1374 0.7
    1375 -
    1376 ==== fred by MINE after
    1377 0.7
    1378 -
    1379 0.7
    1380 -
    1381 -
    1382 -
    1383 ==== fred by MINE after
    1384 0.7
    1385 -
    1386 0.7
    1387 -
    1388 0.7
    1389 -
    1390 0.7
    1391 -
    1392 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1393 Test 14-iii.  Modifying Freds on YOURS
    1394 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1395 ==== fred by MINE before
    1396 0.7
    1397 -
    1398 0.7
    1399 -
    1400 0.7
    1401 -
    1402 0.7
    1403 -
    1404 ==== fred by YOURS before
    1405 0.7
    1406 -
    1407 0.7
    1408 -
    1409 0.7
    1410 -
    1411 0.7
    1412 -
    1413 ==== fred by YOURS after
    1414 0.7
    1415 -
    1416 0.7
    1417 -
    1418 0.7
    1419 -
    1420 0.7
    1421 -
    1422 ==== fred by YOURS after
    1423 0.7
    1424 -
    1425 0.7
    1426 -
    1427 -
    1428 -
    1429 ==== fred by YOURS after
    1430 0.7
    1431 -
    1432 0.7
    1433 -
    1434 0.7
    1435 -
    1436 0.7
    1437 -
    1438 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1439 Test 15-iii.  Modifying Maries
    1440 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1441 ==== mary before
    1442 0.7
    1443 -
    1444 0.7
    1445 -
    1446 0.7
    1447 -
    1448 0.7
    1449 -
    1450 ==== mary after
    1451 0.7
    1452 -
    1453 0.7
    1454 -
    1455 -
    1456 -
    1457 ==== mary after
    1458 0.7
    1459 -
    1460 0.7
    1461 -
    1462 0.7
    1463 -
    1464 0.7
    1465 -
    1466 
    1467 ~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~
    1468 
    1469 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1470 Test 16-i.  Modifying Freds on MINE
    1471 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1472 ==== fred by MINE before
    1473 1.7
    1474 2.7
    1475 3.7
    1476 -
    1477 1.7
    1478 -
    1479 3.7
    1480 -
    1481 3.7
    1482 2.7
    1483 1.7
    1484 -
    1485 ==== fred by YOURS before
    1486 1.7
    1487 2.7
    1488 3.7
    1489 -
    1490 1.7
    1491 -
    1492 3.7
    1493 -
    1494 3.7
    1495 2.7
    1496 1.7
    1497 -
    1498 ==== fred by MINE after
    1499 2.7
    1500 3.7
    1501 -
    1502 2.7
    1503 -
    1504 3.7
    1505 -
    1506 3.7
    1507 2.7
    1508 -
    1509 ==== fred by YOURS after
    1510 1.7
    1511 2.7
    1512 3.7
    1513 -
    1514 1.7
    1515 -
    1516 3.7
    1517 -
    1518 3.7
    1519 2.7
    1520 1.7
    1521 -
    1522 ==== fred by MINE after
    1523 1.7
    1524 -
    1525 1.7
    1526 -
    1527 -
    1528 -
    1529 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1530 Test 16-ii.  Modifying Freds on YOURS
    1531 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1532 ==== fred by MINE before
    1533 1.7
    1534 2.7
    1535 3.7
    1536 -
    1537 1.7
    1538 -
    1539 3.7
    1540 -
    1541 3.7
    1542 2.7
    1543 1.7
    1544 -
    1545 ==== fred by YOURS before
    1546 1.7
    1547 2.7
    1548 3.7
    1549 -
    1550 1.7
    1551 -
    1552 3.7
    1553 -
    1554 3.7
    1555 2.7
    1556 1.7
    1557 -
    1558 ==== fred by MINE after
    1559 1.7
    1560 2.7
    1561 3.7
    1562 -
    1563 1.7
    1564 -
    1565 3.7
    1566 -
    1567 3.7
    1568 2.7
    1569 1.7
    1570 -
    1571 ==== fred by YOURS after
    1572 2.7
    1573 3.7
    1574 -
    1575 2.7
    1576 -
    1577 3.7
    1578 -
    1579 3.7
    1580 2.7
    1581 -
    1582 ==== fred by YOURS after
    1583 1.7
    1584 -
    1585 1.7
    1586 -
    1587 -
    1588 -
    1589 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1590 Test 16-iii.  Modifying Maries
    1591 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1592 ==== mary before
    1593 1.7
    1594 2.7
    1595 3.7
    1596 -
    1597 1.7
    1598 -
    1599 3.7
    1600 -
    1601 3.7
    1602 2.7
    1603 1.7
    1604 -
    1605 ==== mary after
    1606 2.7
    1607 3.7
    1608 -
    1609 2.7
    1610 -
    1611 3.7
    1612 -
    1613 3.7
    1614 2.7
    1615 -
    1616 ==== mary after
    1617 1.7
    1618 -
    1619 1.7
    1620 -
    1621 -
    1622 -
    1623 
    1624 ~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~
    1625 
    1626 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1627 Test 17-i.  Modifying Freds on MINE
    1628 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1629 ==== fred by MINE before
    1630 1.7
    1631 2.7
    1632 3.7
    1633 -
    1634 1.7
    1635 -
    1636 3.7
    1637 -
    1638 3.7
    1639 2.7
    1640 1.7
    1641 -
    1642 ==== fred by YOURS before
    1643 1.7
    1644 2.7
    1645 3.7
    1646 -
    1647 1.7
    1648 -
    1649 3.7
    1650 -
    1651 3.7
    1652 2.7
    1653 1.7
    1654 -
    1655 ==== fred by MINE after
    1656 1.7
    1657 2.7
    1658 -
    1659 1.7
    1660 -
    1661 2.7
    1662 -
    1663 2.7
    1664 1.7
    1665 -
    1666 ==== fred by YOURS after
    1667 1.7
    1668 2.7
    1669 3.7
    1670 -
    1671 1.7
    1672 -
    1673 3.7
    1674 -
    1675 3.7
    1676 2.7
    1677 1.7
    1678 -
    1679 ==== fred by MINE after
    1680 3.7
    1681 -
    1682 3.7
    1683 -
    1684 -
    1685 -
    1686 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1687 Test 17-ii.  Modifying Freds on YOURS
    1688 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1689 ==== fred by MINE before
    1690 1.7
    1691 2.7
    1692 3.7
    1693 -
    1694 1.7
    1695 -
    1696 3.7
    1697 -
    1698 3.7
    1699 2.7
    1700 1.7
    1701 -
    1702 ==== fred by YOURS before
    1703 1.7
    1704 2.7
    1705 3.7
    1706 -
    1707 1.7
    1708 -
    1709 3.7
    1710 -
    1711 3.7
    1712 2.7
    1713 1.7
    1714 -
    1715 ==== fred by MINE after
    1716 1.7
    1717 2.7
    1718 3.7
    1719 -
    1720 1.7
    1721 -
    1722 3.7
    1723 -
    1724 3.7
    1725 2.7
    1726 1.7
    1727 -
    1728 ==== fred by YOURS after
    1729 1.7
    1730 2.7
    1731 -
    1732 1.7
    1733 -
    1734 2.7
    1735 -
    1736 2.7
    1737 1.7
    1738 -
    1739 ==== fred by YOURS after
    1740 3.7
    1741 -
    1742 3.7
    1743 -
    1744 -
    1745 -
    1746 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1747 Test 17-iii.  Modifying Maries
    1748 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
    1749 ==== mary before
    1750 1.7
    1751 2.7
    1752 3.7
    1753 -
    1754 1.7
    1755 -
    1756 3.7
    1757 -
    1758 3.7
    1759 2.7
    1760 1.7
    1761 -
    1762 ==== mary after
    1763 1.7
    1764 2.7
    1765 -
    1766 1.7
    1767 -
    1768 2.7
    1769 -
    1770 2.7
    1771 1.7
    1772 -
    1773 ==== mary after
    1774 3.7
    1775 -
    1776 3.7
    1777 -
    1778 -
    1779 -
     1095~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~
     1096
     1097~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1098Test 18-i.  Modifying Freds on MINE
     1099~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1100Not implmented
     1101~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1102Test 18-ii.  Modifying Freds on YOURS
     1103~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1104Not implmented
     1105~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1106Test 18-iii.  Modifying Maries
     1107~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
     1108accessor_cases done
     1109try_pop cases done
     1110origin_mutation cases done

  • tests/list/dlist-insert-remove.cfa

    r67b421c r69914cbc  
    1919struct fred {
    2020        float adatum;
    21         DLISTED_MGD_EXPL_IN(fred, mine)
    22         DLISTED_MGD_EXPL_IN(fred, yours)
     21        inline struct mine { inline dlink(fred); };
     22        inline struct yours { inline dlink(fred); };
    2323};
    24 
    25 DLISTED_MGD_EXPL_OUT(fred, mine)
    26 DLISTED_MGD_EXPL_OUT(fred, yours)
     24P9_EMBEDDED(fred, fred.mine)
     25P9_EMBEDDED(fred, fred.yours)
     26P9_EMBEDDED(fred.mine, dlink(fred))
     27P9_EMBEDDED(fred.yours, dlink(fred))
     28
    2729
    2830void ?{}(fred &this, float adatum) {
    … …  
    3335struct mary {
    3436        float anotherdatum;
    35         DLISTED_MGD_IMPL_IN(mary)
     37        inline dlink(mary);
    3638};
    3739
    38 DLISTED_MGD_IMPL_OUT(mary)
     40P9_EMBEDDED(mary, dlink(mary))
    3941
    4042void ?{}(mary &this, float anotherdatum) {
    … …  
    5355////////////////////////////////////////////////////////////
    5456
    55 void printMyFredsFwd(fred &f) {
    56         while (&f != 0p) {
     57void printMyFredsFwd(fred & f) {
     58    with( DLINK_VIA( fred, fred.mine ) )
     59        do {
    5760                sout | f.adatum;
    58                 &f = &f`in_mine`next;
    59         }
    60 }
    61 
    62 void printMyFredsRev(fred &f) {
    63         while (&f != 0p) {
     61        } while (f`moveNext);
     62}
     63
     64void printMyFredsRev(fred & f) {
     65    with( DLINK_VIA( fred, fred.mine ) )
     66        do {
    6467                sout | f.adatum;
    65                 &f = &f`in_mine`prev;
    66         }
    67 }
     68        } while (f`movePrev);
     69}
     70
    6871
    6972void printMyFreddies(fred &f1, fred &f2, int isBefore) {
    … …  
    7376                sout | "==== fred by MINE after ";
    7477        }
    75         printMyFredsFwd(f1);    sout | '-';
    76         printMyFredsRev(f1);    sout | '-';
    77         printMyFredsFwd(f2);    sout | '-';
    78         printMyFredsRev(f2);    sout | '-';
    79 }
    80 
    81 void printYourFredsFwd(fred &f) {
    82         while (&f != 0p) {
     78        if (&f1) {
     79                printMyFredsFwd(f1);    sout | '-';
     80                printMyFredsRev(f1);    sout | '-';
     81        } else {
     82                sout | '-'; sout | '-';
     83        }
     84        if (&f2) {
     85                printMyFredsFwd(f2);    sout | '-';
     86                printMyFredsRev(f2);    sout | '-';
     87        } else {
     88                sout | '-'; sout | '-';
     89        }
     90}
     91
     92void printYourFredsFwd(fred & f) {
     93    with( DLINK_VIA( fred, fred.yours ) )
     94        do {
    8395                sout | f.adatum;
    84                 &f = &f`in_yours`next;
    85         }
    86 }
    87 
    88 void printYourFredsRev(fred &f) {
    89         while (&f != 0p) {
     96        } while (f`moveNext);
     97}
     98
     99void printYourFredsRev(fred & f) {
     100    with( DLINK_VIA( fred, fred.yours ) )
     101        do {
    90102                sout | f.adatum;
    91                 &f = &f`in_yours`prev;
    92         }
     103        } while (f`movePrev);
    93104}
    94105
    … …  
    99110                sout | "==== fred by YOURS after ";
    100111        }
    101         printYourFredsFwd(f1);  sout | '-';
    102         printYourFredsRev(f1);  sout | '-';
    103         printYourFredsFwd(f2);  sout | '-';
    104         printYourFredsRev(f2);  sout | '-';
     112        if (&f1) {
     113                printYourFredsFwd(f1);  sout | '-';
     114                printYourFredsRev(f1);  sout | '-';
     115        } else {
     116                sout | '-'; sout | '-';
     117        }
     118        if (&f2) {
     119                printYourFredsFwd(f2);  sout | '-';
     120                printYourFredsRev(f2);  sout | '-';
     121        } else {
     122                sout | '-'; sout | '-';
     123        }
    105124}
    106125
    107126void printMariesFwd(mary &m) {
    108         while (&m != 0p) {
     127        do {
    109128                sout | m.anotherdatum;
    110                 &m = &m`next;
    111         }
     129        } while (m`moveNext);
    112130}
    113131
    114132void printMariesRev(mary &m) {
    115         while (&m != 0p) {
     133        do {
    116134                sout | m.anotherdatum;
    117                 &m = &m`prev;
    118         }
     135        } while (m`movePrev);
    119136}
    120137
    … …  
    125142                sout | "==== mary after ";
    126143        }
    127         printMariesFwd(m1);     sout | '-';
    128         printMariesRev(m1);     sout | '-';
    129         printMariesFwd(m2);     sout | '-';
    130         printMariesRev(m2);     sout | '-';
     144        if (&m1) {
     145                printMariesFwd(m1);     sout | '-';
     146                printMariesRev(m1);     sout | '-';
     147        } else {
     148                sout | '-'; sout | '-';
     149        }
     150        if (&m2) {
     151                printMariesFwd(m2);     sout | '-';
     152                printMariesRev(m2);     sout | '-';
     153        } else {
     154                sout | '-'; sout | '-';
     155        }
    131156}
    132157
    … …  
    153178//  - from list position #2 moving backward (d)
    154179// The expected-output comments are in form a;b;c;d where a::=num,num,num
    155 
     180#if 0
    156181void test__insertafter_singleton_on_singleton__fred_mine () {
    157182        fred f1 = {3.14};
    … …  
    161186        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    162187
    163         insert_after(f1`in_mine, f2);
     188        diref(fred, fred.mine) f1_mine = f1`from;
     189        insert_after(f1_mine, f2);
    164190
    165191        printMyFreddies(f1, f2, 0);     // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    174200        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    175201
    176         insert_after(f1`in_yours, f2);
     202        diref(fred, fred.yours) f1_yours = f1`from;
     203        insert_after(f1_yours, f2);
    177204
    178205        printMyFreddies(f1, f2, 0);     // 3.14; 3.14; 0.5; 0.5 (unmodified)
    … …  
    208235        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    209236
    210         insert_before(f2`in_mine, f1);
     237        diref(fred, fred.mine) f2_mine = f2`from;
     238        insert_before(f2_mine, f1);
    211239
    212240        printMyFreddies(f1, f2, 0);     // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    … …  
    221249        printYourFreddies(f1, f2, 1);   // 3.14; 3.14; 0.5; 0.5
    222250
    223         insert_before(f2`in_yours, f1);
     251        diref(fred, fred.yours) f2_yours = f2`from;
     252        insert_before(f2_yours, f1);
    224253
    225254        printMyFreddies(f1, f2, 0);     // 3.14; 3.14; 0.5; 0.5 (unmodified)
    … …  
    237266        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    238267}
    239 
     268#endif
    240269////////////////////////////////////////////////////////////
    241270//
    … …  
    250279// All three tests exercise the case of creating an empty container and
    251280// adding two items to it.
    252 
    253281void test__insertfirst_two_on_empty__fred_mine() {
    254282
    … …  
    256284        fred f2 = {0.5};
    257285
    258         dlist(fred_in_mine, fred) lf;
     286        dlist(fred, fred.mine) lf;
    259287
    260288        verify(validate(lf));
    … …  
    277305        fred f2 = {0.5};
    278306
    279         dlist(fred_in_yours, fred) lf;
     307        dlist(fred, fred.yours) lf;
    280308
    281309        verify(validate(lf));
    … …  
    292320        printYourFreddies(f1, f2, 0);   // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    293321}
    294 
    295322void test__insertfirst_two_on_empty__mary() {
    296323
    … …  
    298325        mary m2 = {0.5};
    299326
    300         dlist(mary, mary) lm;
     327        dlist(mary) lm;
    301328
    302329        verify(validate(lm));
    … …  
    325352        fred f2 = {0.5};
    326353
    327         dlist(fred_in_mine, fred) lf;
     354        dlist(fred, fred.mine) lf;
    328355
    329356        verify(validate(lf));
    … …  
    346373        fred f2 = {0.5};
    347374
    348         dlist(fred_in_yours, fred) lf;
     375        dlist(fred, fred.yours) lf;
    349376
    350377        verify(validate(lf));
    … …  
    367394        mary m2 = {0.5};
    368395
    369         dlist(mary, mary) lm;
     396        dlist(mary) lm;
    370397
    371398        verify(validate(lm));
    … …  
    394421        fred f2 = {0.5};
    395422
    396         dlist(fred_in_mine, fred) lf;
    397 
    398         assert(& lf`first == 0p);
    399         assert(& lf`last == 0p);
     423        dlist(fred, fred.mine) lf;
     424
     425        assert( & lf`first == 0p );
     426        assert( & lf`last == 0p );
    400427
    401428        insert_first(lf, f1);
    402429
    403         assert(& lf`first == & f1);
    404         assert(& lf`last == & f1);
     430        assert( & lf`first == & f1 );
     431        assert( & lf`last  == & f1 );
    405432
    406433        verify(validate(lf));
    407434
    408         insert_after(f1`in_mine, f2);
     435        with ( DLINK_VIA(fred, fred.mine) ) insert_after(f1, f2);
    409436
    410437        verify(validate(lf));
    … …  
    413440        printYourFreddies(f1, f2, 0);   // 3.14; 3.14; 0.5; 0.5 (unmodified)
    414441
    415         assert(& lf`first == & f1);
    416         assert(& lf`last == & f2);
     442        assert( & lf`first == & f1 );
     443        assert( & lf`last  == & f2 );
    417444}
    418445
    … …  
    422449        fred f2 = {0.5};
    423450
    424         dlist(fred_in_yours, fred) lf;
    425 
    426         assert(& lf`first == 0p);
    427         assert(& lf`last == 0p);
     451        dlist(fred, fred.yours) lf;
     452
     453        assert( & lf`first == 0p );
     454        assert( & lf`last == 0p );
    428455
    429456        insert_first(lf, f1);
    430457
    431         assert(& lf`first == & f1);
    432         assert(& lf`last == & f1);
     458        assert( & lf`first == & f1 );
     459        assert( & lf`last  == & f1 );
    433460
    434461        verify(validate(lf));
    435462
    436         insert_after(f1`in_yours, f2);
     463    with ( DLINK_VIA(fred, fred.yours) ) insert_after(f1, f2);
    437464
    438465        verify(validate(lf));
    … …  
    441468        printYourFreddies(f1, f2, 0);   // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    442469
    443         assert(& lf`first == & f1);
    444         assert(& lf`last == & f2);
     470        assert( & lf`first == & f1 );
     471        assert( & lf`last  == & f2 );
    445472}
    446473
    … …  
    450477        mary m2 = {0.5};
    451478
    452         dlist(mary, mary) lm;
    453 
    454         assert(& lm`first == 0p);
    455         assert(& lm`last == 0p);
     479        dlist(mary) lm;
     480
     481        assert( & lm`first == 0p );
     482        assert( & lm`last == 0p );
    456483
    457484        insert_first(lm, m1);
    458485
    459         assert(& lm`first == & m1);
    460         assert(& lm`last == & m1);
     486        assert( & lm`first == & m1 );
     487        assert( & lm`last  == & m1 );
    461488
    462489        verify(validate(lm));
    … …  
    468495        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    469496
    470         assert(& lm`first == & m1);
    471         assert(& lm`last == & m2);
     497        assert( & lm`first == & m1 );
     498        assert( & lm`last  == & m2 );
    472499}
    473500
    … …  
    487514        fred f2 = {0.5};
    488515
    489         dlist(fred_in_mine, fred) lf;
    490 
    491         assert(& lf`first == 0p);
    492         assert(& lf`last == 0p);
     516        dlist(fred, fred.mine) lf;
     517
     518        assert( & lf`first == 0p );
     519        assert( & lf`last == 0p );
    493520
    494521        insert_last(lf, f2);
    495522
    496         assert(& lf`first == & f2);
    497         assert(& lf`last == & f2);
     523        assert( & lf`first == & f2 );
     524        assert( & lf`last  == & f2 );
    498525
    499526        verify(validate(lf));
    500527
    501         insert_before(f2`in_mine, f1);
     528        with ( DLINK_VIA(fred, fred.mine) ) insert_before(f2, f1);
    502529
    503530        verify(validate(lf));
    … …  
    506533        printYourFreddies(f1, f2, 0);   // 3.14; 3.14; 0.5; 0.5 (unmodified)
    507534
    508         assert(& lf`first == & f1);
    509         assert(& lf`last == & f2);
     535        assert( & lf`first == & f1 );
     536        assert( & lf`last  == & f2 );
    510537}
    511538
    … …  
    515542        fred f2 = {0.5};
    516543
    517         dlist(fred_in_yours, fred) lf;
    518 
    519         assert(& lf`first == 0p);
    520         assert(& lf`last == 0p);
     544        dlist(fred, fred.yours) lf;
     545
     546        assert( & lf`first == 0p );
     547        assert( & lf`last == 0p );
    521548
    522549        insert_last(lf, f2);
    523550
    524         assert(& lf`first == & f2);
    525         assert(& lf`last == & f2);
     551        assert( & lf`first == & f2 );
     552        assert( & lf`last  == & f2 );
    526553
    527554        verify(validate(lf));
    528555
    529         insert_before(f2`in_yours, f1);
     556        with ( DLINK_VIA(fred, fred.yours) )insert_before(f2, f1);
    530557
    531558        verify(validate(lf));
    … …  
    534561        printYourFreddies(f1, f2, 0);   // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    535562
    536         assert(& lf`first == & f1);
    537         assert(& lf`last == & f2);
     563        assert( & lf`first == & f1 );
     564        assert( & lf`last  == & f2 );
    538565}
    539566
    … …  
    543570        mary m2 = {0.5};
    544571
    545         dlist(mary, mary) lm;
    546 
    547         assert(& lm`first == 0p);
    548         assert(& lm`last == 0p);
     572        dlist(mary) lm;
     573
     574        assert( & lm`first == 0p );
     575        assert( & lm`last == 0p );
    549576
    550577        insert_last(lm, m2);
    551578
    552         assert(& lm`first == & m2);
    553         assert(& lm`last == & m2);
     579        assert( & lm`first == & m2 );
     580        assert( & lm`last  == & m2 );
    554581
    555582        verify(validate(lm));
    … …  
    561588        printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified)
    562589
    563         assert(& lm`first == & m1);
    564         assert(& lm`last == & m2);
    565 }
     590        assert( & lm`first == & m1 );
     591        assert( & lm`last  == & m2 );
     592}
     593#if 0
    566594
    567595////////////////////////////////////////////////////////////
    … …  
    846874//
    847875////////////////////////////////////////////////////////////
    848 
     876#endif
    849877void test__remove_at_head__fred_mine() {
    850878
    … …  
    853881        fred f3 = {3.7};
    854882
    855         dlist(fred_in_mine, fred) flm;
     883        dlist(fred, fred.mine) flm;
    856884        insert_last(flm, f1);
    857885        insert_last(flm, f2);
    858886        insert_last(flm, f3);
    859887
    860         dlist(fred_in_yours, fred) fly;
     888        dlist(fred, fred.yours) fly;
    861889        insert_last(fly, f1);
    862890        insert_last(fly, f2);
    … …  
    869897        verify(validate(flm));
    870898
    871         remove(f1`in_mine);
     899        with( DLINK_VIA(fred, fred.mine) ) remove(f1);
    872900
    873901        verify(validate(fly));
    … …  
    881909
    882910        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    883         assert(f1.$links_mine.next.is_terminator == false);
    884         assert(f1.$links_mine.prev.is_terminator == false);
    885 }
     911        // assert(f1.$links_mine.next.is_terminator == false);
     912        // assert(f1.$links_mine.prev.is_terminator == false);
     913}
     914
    886915
    887916void test__remove_at_head__fred_yours() {
    … …  
    891920        fred f3 = {3.7};
    892921
    893         dlist(fred_in_mine, fred) flm;
     922        dlist(fred, fred.mine) flm;
    894923        insert_last(flm, f1);
    895924        insert_last(flm, f2);
    896925        insert_last(flm, f3);
    897926
    898         dlist(fred_in_yours, fred) fly;
     927        dlist(fred, fred.yours) fly;
    899928        insert_last(fly, f1);
    900929        insert_last(fly, f2);
    … …  
    907936        verify(validate(flm));
    908937
    909         remove(f1`in_yours);
     938        with( DLINK_VIA(fred, fred.yours) ) remove(f1);
    910939
    911940        verify(validate(fly));
    … …  
    919948
    920949        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    921         assert(f1.$links_yours.next.is_terminator == false);
    922         assert(f1.$links_yours.prev.is_terminator == false);
     950        // assert(f1.$links_yours.next.is_terminator == false);
     951        // assert(f1.$links_yours.prev.is_terminator == false);
    923952}
    924953
    … …  
    929958        mary m3 = {3.7};
    930959
    931         dlist(mary, mary) ml;
     960        dlist(mary) ml;
    932961        insert_last(ml, m1);
    933962        insert_last(ml, m2);
    … …  
    948977
    949978        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    950         assert(m1.$links.next.is_terminator == false);
    951         assert(m1.$links.prev.is_terminator == false);
     979        // assert(m1.$links.next.is_terminator == false);
     980        // assert(m1.$links.prev.is_terminator == false);
    952981}
    953982
    … …  
    968997        fred f3 = {3.7};
    969998
    970         dlist(fred_in_mine, fred) flm;
     999        dlist(fred, fred.mine) flm;
    9711000        insert_last(flm, f1);
    9721001        insert_last(flm, f2);
    9731002        insert_last(flm, f3);
    9741003
    975         dlist(fred_in_yours, fred) fly;
     1004        dlist(fred, fred.yours) fly;
    9761005        insert_last(fly, f1);
    9771006        insert_last(fly, f2);
    … …  
    9841013        verify(validate(flm));
    9851014
    986         remove(f3`in_mine);
     1015        with( DLINK_VIA(fred, fred.mine) ) remove(f3);
    9871016
    9881017        verify(validate(fly));
    … …  
    9961025
    9971026        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    998         assert(f3.$links_mine.next.is_terminator == false);
    999         assert(f3.$links_mine.prev.is_terminator == false);
     1027        // assert(f3.$links_mine.next.is_terminator == false);
     1028        // assert(f3.$links_mine.prev.is_terminator == false);
    10001029}
    10011030
    … …  
    10061035        fred f3 = {3.7};
    10071036
    1008         dlist(fred_in_mine, fred) flm;
     1037        dlist(fred, fred.mine) flm;
    10091038        insert_last(flm, f1);
    10101039        insert_last(flm, f2);
    10111040        insert_last(flm, f3);
    10121041
    1013         dlist(fred_in_yours, fred) fly;
     1042        dlist(fred, fred.yours) fly;
    10141043        insert_last(fly, f1);
    10151044        insert_last(fly, f2);
    … …  
    10221051        verify(validate(flm));
    10231052
    1024         remove(f3`in_yours);
     1053        with( DLINK_VIA(fred, fred.yours) ) remove(f3);
    10251054
    10261055        verify(validate(fly));
    … …  
    10341063
    10351064        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    1036         assert(f3.$links_yours.next.is_terminator == false);
    1037         assert(f3.$links_yours.prev.is_terminator == false);
     1065        // assert(f3.$links_yours.next.is_terminator == false);
     1066        // assert(f3.$links_yours.prev.is_terminator == false);
    10381067}
    10391068
    … …  
    10441073        mary m3 = {3.7};
    10451074
    1046         dlist(mary, mary) ml;
     1075        dlist(mary) ml;
    10471076        insert_last(ml, m1);
    10481077        insert_last(ml, m2);
    … …  
    10631092
    10641093        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    1065         assert(m3.$links.next.is_terminator == false);
    1066         assert(m3.$links.prev.is_terminator == false);
     1094        // assert(m3.$links.next.is_terminator == false);
     1095        // assert(m3.$links.prev.is_terminator == false);
    10671096}
    10681097
    … …  
    10811110        fred f = {0.7};
    10821111
    1083         dlist(fred_in_mine, fred) flm;
     1112        dlist(fred, fred.mine) flm;
    10841113        insert_last(flm, f);
    10851114
    1086         dlist(fred_in_yours, fred) fly;
     1115        dlist(fred, fred.yours) fly;
    10871116        insert_last(fly, f);
    10881117
    … …  
    10931122        verify(validate(flm));
    10941123
    1095         remove(f`in_mine);
    1096 
    1097         verify(validate(fly));
    1098         verify(validate(flm));
    1099 
    1100         assert(& flm`first == 0p);
    1101         assert(& flm`last  == 0p);
     1124        with( DLINK_VIA(fred, fred.mine) ) remove(f);
     1125
     1126        verify(validate(fly));
     1127        verify(validate(flm));
     1128
     1129        assert( & flm`first == 0p );
     1130        assert( & flm`last == 0p );
    11021131
    11031132        printYourFreddies(fly`first, fly`last, 0);   // 0.7; 0.7; 0.7; 0.7 (unmodified)
    … …  
    11071136
    11081137        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    1109         assert(f.$links_mine.next.is_terminator == false);
    1110         assert(f.$links_mine.prev.is_terminator == false);
     1138        // assert(f.$links_mine.next.is_terminator == false);
     1139        // assert(f.$links_mine.prev.is_terminator == false);
    11111140
    11121141        insert_last(flm, f);
    … …  
    11201149        fred f = {0.7};
    11211150
    1122         dlist(fred_in_mine, fred) flm;
     1151        dlist(fred, fred.mine) flm;
    11231152        insert_last(flm, f);
    11241153
    1125         dlist(fred_in_yours, fred) fly;
     1154        dlist(fred, fred.yours) fly;
    11261155        insert_last(fly, f);
    11271156
    … …  
    11321161        verify(validate(flm));
    11331162
    1134         remove(f`in_yours);
    1135 
    1136         verify(validate(fly));
    1137         verify(validate(flm));
    1138 
    1139         assert(& fly`first == 0p);
    1140         assert(& fly`last  == 0p);
     1163        with( DLINK_VIA(fred, fred.yours) ) remove(f);
     1164
     1165        verify(validate(fly));
     1166        verify(validate(flm));
     1167
     1168        assert( & fly`first == 0p );
     1169        assert( & fly`last == 0p );
    11411170
    11421171        printYourFreddies(flm`first, flm`last, 0);   // 0.7; 0.7; 0.7; 0.7 (unmodified)
    … …  
    11461175
    11471176        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    1148         assert(f.$links_yours.next.is_terminator == false);
    1149         assert(f.$links_yours.prev.is_terminator == false);
     1177        // assert(f.$links_yours.next.is_terminator == false);
     1178        // assert(f.$links_yours.prev.is_terminator == false);
    11501179
    11511180        insert_last(fly, f);
    … …  
    11591188        mary m = {0.7};
    11601189
    1161         dlist(mary, mary) ml;
     1190        dlist(mary) ml;
    11621191        insert_last(ml, m);
    11631192
    … …  
    11701199        verify(validate(ml));
    11711200
    1172         assert(& ml`first == 0p);
    1173         assert(& ml`last  == 0p);
     1201        assert( & ml`first == 0p );
     1202        assert( & ml`last == 0p );
    11741203
    11751204        // observe f is solo in mine (now unlisted); in yours, it was just traversed
    … …  
    11771206
    11781207        // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics
    1179         assert(m.$links.next.is_terminator == false);
    1180         assert(m.$links.prev.is_terminator == false);
     1208        // assert(m.$links.next.is_terminator == false);
     1209        // assert(m.$links.prev.is_terminator == false);
    11811210
    11821211        insert_last(ml, m);
    … …  
    12031232        fred f3 = {3.7};
    12041233
    1205         dlist(fred_in_mine, fred) flm;
     1234        dlist(fred, fred.mine) flm;
    12061235        insert_last(flm, f1);
    12071236        insert_last(flm, f2);
    12081237        insert_last(flm, f3);
    12091238
    1210         dlist(fred_in_yours, fred) fly;
     1239        dlist(fred, fred.yours) fly;
    12111240        insert_last(fly, f1);
    12121241        insert_last(fly, f2);
    … …  
    12191248        verify(validate(flm));
    12201249
    1221         fred & popped = pop_first(flm);
     1250        fred & popped = try_pop_front(flm);
    12221251
    12231252        verify(validate(fly));
    … …  
    12391268        fred f3 = {3.7};
    12401269
    1241         dlist(fred_in_mine, fred) flm;
     1270        dlist(fred, fred.mine) flm;
    12421271        insert_last(flm, f1);
    12431272        insert_last(flm, f2);
    12441273        insert_last(flm, f3);
    12451274
    1246         dlist(fred_in_yours, fred) fly;
     1275        dlist(fred, fred.yours) fly;
    12471276        insert_last(fly, f1);
    12481277        insert_last(fly, f2);
    … …  
    12551284        verify(validate(flm));
    12561285
    1257         fred & popped = pop_first(fly);
     1286        fred & popped = try_pop_front(fly);
    12581287
    12591288        verify(validate(fly));
    … …  
    12751304        mary m3 = {3.7};
    12761305
    1277         dlist(mary, mary) ml;
     1306        dlist(mary) ml;
    12781307        insert_last(ml, m1);
    12791308        insert_last(ml, m2);
    … …  
    12841313        verify(validate(ml));
    12851314
    1286         mary & popped = pop_first(ml);
     1315        mary & popped = try_pop_front(ml);
    12871316
    12881317        verify(validate(ml));
    … …  
    13021331        fred f3 = {3.7};
    13031332
    1304         dlist(fred_in_mine, fred) flm;
     1333        dlist(fred, fred.mine) flm;
    13051334        insert_last(flm, f1);
    13061335        insert_last(flm, f2);
    13071336        insert_last(flm, f3);
    13081337
    1309         dlist(fred_in_yours, fred) fly;
     1338        dlist(fred, fred.yours) fly;
    13101339        insert_last(fly, f1);
    13111340        insert_last(fly, f2);
    … …  
    13181347        verify(validate(flm));
    13191348
    1320         fred & popped = pop_last(flm);
     1349        fred & popped = try_pop_back(flm);
    13211350
    13221351        verify(validate(fly));
    … …  
    13381367        fred f3 = {3.7};
    13391368
    1340         dlist(fred_in_mine, fred) flm;
     1369        dlist(fred, fred.mine) flm;
    13411370        insert_last(flm, f1);
    13421371        insert_last(flm, f2);
    13431372        insert_last(flm, f3);
    13441373
    1345         dlist(fred_in_yours, fred) fly;
     1374        dlist(fred, fred.yours) fly;
    13461375        insert_last(fly, f1);
    13471376        insert_last(fly, f2);
    … …  
    13541383        verify(validate(flm));
    13551384
    1356         fred & popped = pop_last(fly);
     1385        fred & popped = try_pop_back(fly);
    13571386
    13581387        verify(validate(fly));
    … …  
    13741403        mary m3 = {3.7};
    13751404
    1376         dlist(mary, mary) ml;
     1405        dlist(mary) ml;
    13771406        insert_last(ml, m1);
    13781407        insert_last(ml, m2);
    … …  
    13831412        verify(validate(ml));
    13841413
    1385         mary & popped = pop_last(ml);
     1414        mary & popped = try_pop_back(ml);
    13861415
    13871416        verify(validate(ml));
    … …  
    13971426////////////////////////////////////////////////////////////
    13981427//
     1428// Section 4g
     1429//
     1430// Test cases of `isEmpty, `hasPrev, `hasNext,
     1431// try_pop_front, try_pop_back, modifications via `elems
     1432//
     1433// Example of call-side user code
     1434//
     1435////////////////////////////////////////////////////////////
     1436
     1437void test__accessor_cases__mary() {
     1438
     1439        mary m1 = {1.7};
     1440        mary m2 = {2.7};
     1441        mary m3 = {3.7};
     1442
     1443        dlist(mary) ml;                 assert( ml`isEmpty);
     1444
     1445        insert_last(ml, m1);    assert(!ml`isEmpty);
     1446        insert_last(ml, m2);    assert(!ml`isEmpty);
     1447        insert_last(ml, m3);    assert(!ml`isEmpty);
     1448
     1449        mary & m1prev = m1`prev;
     1450        mary & m1next = m1`next;
     1451        mary & m2prev = m2`prev;
     1452        mary & m2next = m2`next;
     1453        mary & m3prev = m3`prev;
     1454        mary & m3next = m3`next;
     1455
     1456        assert (&m1prev == 0p);
     1457        assert (&m1next == &m2);
     1458        assert (&m2prev == &m1);
     1459        assert (&m2next == &m3);
     1460        assert (&m3prev == &m2);
     1461        assert (&m3next == 0p);
     1462
     1463        assert(!m1`hasPrev);
     1464        assert( m1`hasNext);
     1465        assert( m2`hasPrev);
     1466        assert( m2`hasNext);
     1467        assert( m3`hasPrev);
     1468        assert(!m3`hasNext);
     1469
     1470        printf("accessor_cases done\n");
     1471}
     1472
     1473void test__try_pop__mary() {
     1474
     1475        mary m1 = {1.7};
     1476        mary m2 = {2.7};
     1477        mary m3 = {3.7};
     1478
     1479        dlist(mary) ml;
     1480
     1481        mary &m1r = *0p;
     1482        mary &m2r = *0p;
     1483        mary &m3r = *0p;
     1484        mary &mxr = *0p;
     1485
     1486        // queue, back to front
     1487
     1488        assert( ml`isEmpty);
     1489
     1490        insert_last(ml, m1);
     1491        insert_last(ml, m2);
     1492        insert_last(ml, m3);
     1493
     1494        &m1r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1495        &m2r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1496        &m3r = & try_pop_front(ml);     assert( ml`isEmpty);
     1497        &mxr = & try_pop_front(ml);     assert( ml`isEmpty);
     1498
     1499        assert( &m1r == &m1 );
     1500        assert( &m2r == &m2 );
     1501        assert( &m3r == &m3 );
     1502        assert( &mxr == 0p  );
     1503
     1504        &m1r = 0p;
     1505        &m2r = 0p;
     1506        &m3r = 0p;
     1507
     1508        // queue, front to back
     1509
     1510        assert( ml`isEmpty);
     1511
     1512        insert_first(ml, m1);
     1513        insert_first(ml, m2);
     1514        insert_first(ml, m3);
     1515
     1516        &m1r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1517        &m2r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1518        &m3r = & try_pop_back(ml);      assert( ml`isEmpty);
     1519        &mxr = & try_pop_back(ml);      assert( ml`isEmpty);
     1520
     1521        assert( &m1r == &m1 );
     1522        assert( &m2r == &m2 );
     1523        assert( &m3r == &m3 );
     1524        assert( &mxr == 0p  );
     1525
     1526        &m1r = 0p;
     1527        &m2r = 0p;
     1528        &m3r = 0p;
     1529
     1530        // stack at front
     1531
     1532        assert( ml`isEmpty);
     1533
     1534        insert_first(ml, m1);
     1535        insert_first(ml, m2);
     1536        insert_first(ml, m3);
     1537
     1538        &m3r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1539        &m2r = & try_pop_front(ml);     assert(!ml`isEmpty);
     1540        &m1r = & try_pop_front(ml);     assert( ml`isEmpty);
     1541        &mxr = & try_pop_front(ml);     assert( ml`isEmpty);
     1542
     1543        assert( &m1r == &m1 );
     1544        assert( &m2r == &m2 );
     1545        assert( &m3r == &m3 );
     1546        assert( &mxr == 0p  );
     1547
     1548        &m1r = 0p;
     1549        &m2r = 0p;
     1550        &m3r = 0p;
     1551
     1552        // stack at back
     1553
     1554        assert( ml`isEmpty);
     1555
     1556        insert_last(ml, m1);
     1557        insert_last(ml, m2);
     1558        insert_last(ml, m3);
     1559
     1560        &m3r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1561        &m2r = & try_pop_back(ml);      assert(!ml`isEmpty);
     1562        &m1r = & try_pop_back(ml);      assert( ml`isEmpty);
     1563        &mxr = & try_pop_back(ml);      assert( ml`isEmpty);
     1564
     1565        assert( &m1r == &m1 );
     1566        assert( &m2r == &m2 );
     1567        assert( &m3r == &m3 );
     1568        assert( &mxr == 0p  );
     1569
     1570        &m1r = 0p;
     1571        &m2r = 0p;
     1572        &m3r = 0p;
     1573
     1574        printf("try_pop cases done\n");
     1575}
     1576
     1577void test__origin_mutation__mary() {
     1578
     1579        mary m1 = {1.7};
     1580
     1581        dlist(mary) ml;
     1582        mary & mlorigin = ml`elems;
     1583
     1584        // insert before the origin
     1585
     1586        insert_before( ml`elems, m1 );
     1587        assert( ! ml`isEmpty );
     1588
     1589        mary & mlfirst = ml`first;
     1590        mary & mllast = ml`last;
     1591
     1592        assert( &m1 == & mlfirst );
     1593        assert( &m1 == & mllast );
     1594
     1595        // moveNext after last goes back to origin, &vv
     1596
     1597        bool canMoveNext = mllast`moveNext;
     1598        bool canMovePrev = mlfirst`movePrev;
     1599
     1600        assert( ! canMoveNext );
     1601        assert( ! canMovePrev );
     1602
     1603        assert( &mlorigin == & mlfirst );
     1604        assert( &mlorigin == & mllast );
     1605
     1606        printf("origin_mutation cases done\n");
     1607}
     1608
     1609////////////////////////////////////////////////////////////
     1610//
    13991611// Section 5
    14001612//
    … …  
    14041616
    14051617int main() {
    1406 
     1618#if 0
    14071619        sout | "~~~~~~~~~~~~~~~~~ Headless List Tests - insert_after ~~~~~~~~~~~~~~~~";
    14081620        sout | "";
    … …  
    14411653        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
    14421654        test__insertbefore_singleton_on_singleton__mary();
    1443 
     1655#endif
    14441656        sout | "";
    14451657        sout | "~~~~~~~~~~~~~~~~~ Headed List Tests - insert_first ~~~~~~~~~~~~~~~~~~";
    … …  
    15171729        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
    15181730        test__insertbefore_before_first__mary();
     1731#if 0
    15191732
    15201733        sout | "";
    … …  
    15741787        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
    15751788        test__remove_at_last__mary();
    1576 
     1789#endif
    15771790        sout | "";
    15781791        sout | "~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~";
    … …  
    16701883        test__pop_last__maries();
    16711884
     1885        sout | "";
     1886        sout | "~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~";
     1887        sout | "";
     1888
     1889        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1890        sout | "Test 18-i.  Modifying Freds on MINE";
     1891        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1892        sout | "Not implmented";
     1893
     1894        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1895        sout | "Test 18-ii.  Modifying Freds on YOURS";
     1896        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1897        sout | "Not implmented";
     1898
     1899        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1900        sout | "Test 18-iii.  Modifying Maries";
     1901        sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~";
     1902
     1903        test__accessor_cases__mary();
     1904        test__try_pop__mary();
     1905        test__origin_mutation__mary();
     1906
    16721907        return 0;
    16731908}

  • tests/zombies/linked-list-perf/experiment.koad

    r67b421c r69914cbc  
    4949#elif defined IMPL_CFA_MIKE_OLD
    5050
     51        #include "mike-old.hfa"
     52        struct S {
     53                int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
     54                DLISTED_MGD_IMPL_IN(S)
     55        };
     56        DLISTED_MGD_IMPL_OUT(S)
     57
     58#elif defined IMPL_CFA_MIKE_POC
     59
     60        #include "mike-proto-list.hfa"
     61        struct S {
     62                int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
     63                inline dlink(S);
     64        };
     65        P9_EMBEDDED( S, dlink(S) )
     66
     67#elif defined IMPL_CFA_MIKE_NEW
     68
    5169        #include <containers/list.hfa>
    52         struct S {
    53                 int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
    54                 DLISTED_MGD_IMPL_IN(S)
    55         };
    56         DLISTED_MGD_IMPL_OUT(S)
    57 
    58 #elif defined IMPL_CFA_MIKE_POC
    59 
    60         #include "mike-proto-list.hfa"
    61         struct S {
    62                 int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
    63                 inline dlink(S);
    64         };
    65         P9_EMBEDDED( S, dlink(S) )
    66 
    67 #elif defined IMPL_CFA_MIKE_NEW
    68 
    69         #include <containers/list2.hfa>
    7070        struct S {
    7171                int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD
Note: See TracChangeset for help on using the changeset viewer.