Index: libcfa/src/Makefile.am =================================================================== --- libcfa/src/Makefile.am (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/Makefile.am (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -59,5 +59,4 @@ concurrency/iofwd.hfa \ containers/list.hfa \ - containers/list2.hfa \ containers/queueLockFree.hfa \ containers/stackLockFree.hfa \ Index: libcfa/src/concurrency/alarm.hfa =================================================================== --- libcfa/src/concurrency/alarm.hfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/concurrency/alarm.hfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -49,5 +49,5 @@ Duration period; // if > 0 => period of alarm - DLISTED_MGD_IMPL_IN(alarm_node_t) + inline dlink(alarm_node_t); union { @@ -60,5 +60,5 @@ enum alarm_type type; // true if this is not a user defined alarm }; -DLISTED_MGD_IMPL_OUT(alarm_node_t) +P9_EMBEDDED( alarm_node_t, dlink(alarm_node_t) ) void ?{}( alarm_node_t & this, $thread * thrd, Time alarm, Duration period ); @@ -67,5 +67,5 @@ void ^?{}( alarm_node_t & this ); -typedef dlist(alarm_node_t, alarm_node_t) alarm_list_t; +typedef dlist(alarm_node_t) alarm_list_t; void insert( alarm_list_t * this, alarm_node_t * n ); Index: libcfa/src/concurrency/kernel.cfa =================================================================== --- libcfa/src/concurrency/kernel.cfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/concurrency/kernel.cfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -908,5 +908,5 @@ } - static void crawl_list( cluster * cltr, dlist(processor, processor) & list, unsigned count ) { + static void crawl_list( cluster * cltr, dlist(processor) & list, unsigned count ) { /* paranoid */ verify( cltr->stats ); Index: libcfa/src/concurrency/kernel.hfa =================================================================== --- libcfa/src/concurrency/kernel.hfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/concurrency/kernel.hfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -107,5 +107,5 @@ // Link lists fields - DLISTED_MGD_IMPL_IN(processor) + inline dlink(processor); // special init fields @@ -129,4 +129,5 @@ #endif }; +P9_EMBEDDED( processor, dlink(processor) ) void ?{}(processor & this, const char name[], struct cluster & cltr); @@ -136,6 +137,4 @@ static inline void ?{}(processor & this, struct cluster & cltr) { this{ "Anonymous Processor", cltr}; } static inline void ?{}(processor & this, const char name[]) { this{name, *mainCluster}; } - -DLISTED_MGD_IMPL_OUT(processor) //----------------------------------------------------------------------------- @@ -186,8 +185,8 @@ // List of idle processors - dlist(processor, processor) idles; + dlist(processor) idles; // List of active processors - dlist(processor, processor) actives; + dlist(processor) actives; }; Index: libcfa/src/concurrency/ready_queue.cfa =================================================================== --- libcfa/src/concurrency/ready_queue.cfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/concurrency/ready_queue.cfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -554,5 +554,5 @@ } -static void assign_list(unsigned & value, dlist(processor, processor) & list, unsigned count) { +static void assign_list(unsigned & value, dlist(processor) & list, unsigned count) { processor * it = &list`first; for(unsigned i = 0; i < count; i++) { Index: libcfa/src/containers/list.hfa =================================================================== --- libcfa/src/containers/list.hfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/containers/list.hfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -18,333 +18,279 @@ #include -#define __DLISTED_MGD_COMMON(ELEM, NODE, LINKS_FLD) \ -static inline ELEM& $tempcv_n2e(NODE &node) { \ - return node; \ -} \ -\ -static inline NODE& $tempcv_e2n(ELEM &node) { \ - return ( NODE & ) node; \ -} \ -\ -static inline ELEM & ?`prev(NODE &node) { \ - $dlinks(ELEM) & ls = node.LINKS_FLD; \ - $mgd_link(ELEM) * l = &ls.prev; \ - ELEM * e = l->elem; \ - return *e; \ -} \ -\ -static inline ELEM & ?`next(NODE &node) { \ - $dlinks(ELEM) & ls = node.LINKS_FLD; \ - $mgd_link(ELEM) * l = &ls.next; \ - ELEM * e = l->elem; \ - return *e; \ -} \ -\ -static inline $mgd_link(ELEM) & $prev_link(NODE &node) { \ - $dlinks(ELEM) & ls = node.LINKS_FLD; \ - $mgd_link(ELEM) * l = &ls.prev; \ - return *l; \ -} \ -\ -static inline $mgd_link(ELEM) & $next_link(NODE &node) { \ - $dlinks(ELEM) & ls = node.LINKS_FLD; \ - $mgd_link(ELEM) * l = &ls.next; \ - return *l; \ +forall( Decorator &, T & ) +struct tytagref { + inline T &; +}; + +trait embedded( tOuter &, tMid &, tInner & ) { + tytagref( tMid, tInner ) ?`inner( tOuter & ); +}; + +// embedded is reflexive, with no info (void) as the type tag +forall (T &) +static inline tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; } + +// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance +#define P9_EMBEDDED( derived, immedBase ) \ +forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \ + static inline tytagref(immedBase, Tbase) ?`inner( derived & this ) { \ + immedBase & ib = this; \ + Tbase & b = ib`inner; \ + tytagref(immedBase, Tbase) result = { b }; \ + return result; \ + } + +#define EMBEDDED_VIA( OUTER, MID, INNER ) \ + (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } + +#define DLINK_VIA( TE, TLINK ) \ + EMBEDDED_VIA( TE, TLINK, dlink(TE) ) + + +// The origin is the position encountered at the start of iteration, +// signifying, "need to advance to the first element," and at the end +// of iteration, signifying, "no more elements." Normal comsumption of +// an iterator runs ?`moveNext as the first step, and uses the return +// of ?`moveNext as a guard, before dereferencing the iterator. So +// normal consumption of an iterator does not dereference an iterator +// in origin position. The value of a pointer (underlying a refence) +// that is exposed publicly as an iteraor, and also a pointer stored +// internally in a link field, is tagged, to indicate "is the origin" +// (internally, is the list-head sentinel node), or untagged, to indicate +// "is a regular node." Intent is to help a user who dereferences an +// iterator in origin position (which would be an API-use error on their +// part), by failing fast. + +#if defined( __x86_64 ) + // Preferred case: tag in the most-significant bit. Dereference + // has been shown to segfault consistently. Maintenance should + // list more architectures as "ok" here, to let them use the + // preferred case, when valid. + #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 ) +#else + // Fallback case: tag in the least-significant bit. Dereference + // will often give an alignment error, but may not, e.g. if + // accessing a char-typed member. 32-bit x86 uses the most- + // significant bit for real room on the heap. + #define ORIGIN_TAG_BITNO 0 +#endif +#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO) + +#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK) +#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK) +#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK) + + +forall( tE & ) { + + struct dlink{ + tE *next; + tE *prev; + }; + + static inline void ?{}( dlink(tE) & this ) { + this.next = 0p; + this.prev = 0p; + } + + forall( tLinks & = dlink(tE) ) + struct dlist { + inline dlink(tE); + }; + + forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { + static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) { + dlink(tE) & link_from_null = ( * (tE *) 0p )`inner; + ptrdiff_t link_offset = (ptrdiff_t) & link_from_null; + size_t origin_addr = ((size_t) & lst) - link_offset; + size_t preResult = ORIGIN_TAG_SET( origin_addr ); + return (tE *)preResult; + } + + static inline void ?{}( dlist(tE, tLinks) & this ) { + tE * listOrigin = $get_list_origin_addr( this ); + ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ; + } + } + } -#define __DLISTED_MGD_JUSTEXPL(STRUCT, IN_THELIST, STRUCT_IN_THELIST) \ -struct STRUCT_IN_THELIST { \ - inline STRUCT; \ -}; \ -\ -void ?{}(STRUCT_IN_THELIST &) = void; \ -\ -static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \ - return (STRUCT_IN_THELIST&)this; \ -} - -#define __DLISTED_MGD_JUSTIMPL(STRUCT) - -forall( tE & ) { - struct $mgd_link { - tE *elem; - void *terminator; - _Bool is_terminator; - // will collapse to single pointer with tag bit - }; - static inline void ?{}( $mgd_link(tE) &this, tE* elem ) { - (this.elem){ elem }; - (this.terminator){ 0p }; - (this.is_terminator){ 0 }; - } - static inline void ?{}( $mgd_link(tE) &this, void * terminator ) { - (this.elem){ 0p }; - (this.terminator){ terminator }; - (this.is_terminator){ 1 }; - } - static inline void ?=?( $mgd_link(tE) &this, tE* elem ) { - this.elem = elem ; - this.terminator = 0p; - this.is_terminator = 0; - } - static inline void ?=?( $mgd_link(tE) &this, void * terminator ) { - this.elem = 0p; - this.terminator = terminator; - this.is_terminator = 1; - } - struct $dlinks { - // containing item is not listed - // iff - // links have (elem == 0p && terminator == 0p) - $mgd_link(tE) next; - $mgd_link(tE) prev; - }; - static inline void ?{}( $dlinks(tE) &this ) { - (this.next){ (tE *)0p }; - (this.prev){ (tE *)0p }; - } -} - -#define DLISTED_MGD_EXPL_IN(STRUCT, LIST_SUF) \ - $dlinks(STRUCT) $links_ ## LIST_SUF; - -#define DLISTED_MGD_EXPL_OUT(STRUCT, LIST_SUF) \ - __DLISTED_MGD_JUSTEXPL(STRUCT, in_##LIST_SUF, STRUCT ## _in_ ## LIST_SUF) \ - __DLISTED_MGD_COMMON(STRUCT, STRUCT##_in_##LIST_SUF, $links_ ## LIST_SUF) - -#define DLISTED_MGD_IMPL_IN(STRUCT) \ - $dlinks(STRUCT) $links; - -#define DLISTED_MGD_IMPL_OUT(STRUCT) \ - __DLISTED_MGD_JUSTIMPL(STRUCT) \ - __DLISTED_MGD_COMMON(STRUCT, STRUCT, $links) - -trait $dlistable(Tnode &, Telem &) { - $mgd_link(Telem) & $prev_link(Tnode &); - $mgd_link(Telem) & $next_link(Tnode &); - Telem& $tempcv_n2e(Tnode &); - Tnode& $tempcv_e2n(Telem &); - - Telem& ?`next(Tnode &); - Telem& ?`prev(Tnode &); -}; - -forall (Tnode &, Telem & | $dlistable(Tnode, Telem)) { - - // implemented as a sentinel item in an underlying cicrular list - // theList.$links.next is first - // theList.$links.prev is last - // note this allocation preserves prev-next composition as an identity - struct dlist { - $dlinks(Telem) $links; - }; - - // an empty dlist - // links refer to self, making a tight circle - static inline void ?{}( dlist(Tnode, Telem) & this ) { - $mgd_link(Telem) selfRef = (void *) &this; - ( this.$links ) { selfRef, selfRef }; - } - - static inline Telem & ?`first( dlist(Tnode, Telem) &l ) { - return * l.$links.next.elem; - } - - static inline Telem & ?`last( dlist(Tnode, Telem) &l ) { - return * l.$links.prev.elem; - } - - #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) - static bool $validate_fwd( dlist(Tnode, Telem) & this ) { - Tnode * it = & $tempcv_e2n( this`first ); - if (!it) return (& this`last == 0p); - - while( $next_link(*it).elem ) { - it = & $tempcv_e2n( * $next_link(*it).elem ); - } - - return ( it == & $tempcv_e2n( this`last ) ) && - ( $next_link(*it).is_terminator ) && - ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this ); - } - static bool $validate_rev( dlist(Tnode, Telem) & this ) { - Tnode * it = & $tempcv_e2n( this`last ); - if (!it) return (& this`first == 0p); - - while( $prev_link(*it).elem ) { - it = & $tempcv_e2n( * $prev_link(*it).elem ); - } - - return ( it == & $tempcv_e2n( this`first ) ) && - ( $prev_link(*it).is_terminator ) && - ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this ); - } - static bool validate( dlist(Tnode, Telem) & this ) { - return $validate_fwd(this) && $validate_rev(this); - } - #endif - - static inline void insert_after(Tnode &list_pos, Telem &to_insert) { + +forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { + + static inline void insert_after(tE & list_pos, tE &to_insert) { verify (&list_pos != 0p); verify (&to_insert != 0p); - Tnode &singleton_to_insert = $tempcv_e2n(to_insert); - verify($prev_link(singleton_to_insert).elem == 0p); - verify($next_link(singleton_to_insert).elem == 0p); - $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos); - $next_link(singleton_to_insert) = $next_link(list_pos); - if ($next_link(list_pos).is_terminator) { - dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator; - $dlinks(Telem) *list_links = & list->$links; - $mgd_link(Telem) *list_last = & list_links->prev; - *list_last = &to_insert; - } else { - Telem *list_pos_next = $next_link(list_pos).elem; - if (list_pos_next) { - Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next); - $prev_link(lpn_inlist) = &to_insert; - } - } - $next_link(list_pos) = &to_insert; - } - - static inline void insert_before(Tnode &list_pos, Telem &to_insert) { + dlink(tE) & linkToInsert = to_insert`inner; + verify(linkToInsert.prev == 0p); + verify(linkToInsert.next == 0p); + tE & list_pos_raw = list_pos; + tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw ); + dlink(tE) & list_pos_links = list_pos_elem`inner; + asm( "" : : : "memory" ); + tE & after_raw = * list_pos_links.next; + tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + linkToInsert.prev = & list_pos_raw; + linkToInsert.next = & after_raw; + dlink(tE) & afterLinks = after_elem`inner; + afterLinks.prev = &to_insert; + list_pos_links.next = &to_insert; + asm( "" : : : "memory" ); + } + + static inline void insert_before(tE & list_pos, tE &to_insert) { verify (&list_pos != 0p); verify (&to_insert != 0p); - Tnode &singleton_to_insert = $tempcv_e2n(to_insert); - verify($prev_link(singleton_to_insert).elem == 0p); - verify($next_link(singleton_to_insert).elem == 0p); - $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos); - $prev_link(singleton_to_insert) = $prev_link(list_pos); - if ($prev_link(list_pos).is_terminator) { - dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator; - $dlinks(Telem) *list_links = & list->$links; - $mgd_link(Telem) *list_first = & list_links->next; - *list_first = &to_insert; - } else { - Telem *list_pos_prev = $prev_link(list_pos).elem; - if (list_pos_prev) { - Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev); - $next_link(lpp_inlist) = &to_insert; - } - } - $prev_link(list_pos) = &to_insert; - } - - static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) { - verify (&list != 0p); - verify (&to_insert != 0p); - Tnode &singleton_to_insert = $tempcv_e2n(to_insert); - verify($prev_link(singleton_to_insert).elem == 0p); - verify($next_link(singleton_to_insert).elem == 0p); - - $prev_link(singleton_to_insert) = (void*) &list; - $next_link(singleton_to_insert) = list.$links.next; - - $dlinks(Telem) *listLinks = & list.$links; - if (listLinks->next.is_terminator) { - $mgd_link(Telem) * listPrevReference = & listLinks->prev; - *listPrevReference = &to_insert; - } else { - Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem); - $prev_link(next_inlist) = &to_insert; - } - $mgd_link(Telem) * listNextReference = & listLinks->next; - *listNextReference = &to_insert; - } - - static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) { - verify (&list != 0p); - verify (&to_insert != 0p); - Tnode &singleton_to_insert = $tempcv_e2n(to_insert); - verify($next_link(singleton_to_insert).elem == 0p); - verify($prev_link(singleton_to_insert).elem == 0p); - - $next_link(singleton_to_insert) = (void*) &list; - $prev_link(singleton_to_insert) = list.$links.prev; - - $dlinks(Telem) *listLinks = & list.$links; - if (listLinks->prev.is_terminator) { - $mgd_link(Telem) * listNextReference = & listLinks->next; - *listNextReference = &to_insert; - } else { - Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem); - $next_link(prev_inlist) = &to_insert; - } - $mgd_link(Telem) * listPrevReference = & listLinks->prev; - *listPrevReference = &to_insert; - } - - static inline void remove(Tnode &list_pos) { - verify( &list_pos != 0p ); - - $mgd_link(Telem) &incoming_from_prev = *0p; - $mgd_link(Telem) &incoming_from_next = *0p; - - if ( $prev_link(list_pos).is_terminator ) { - dlist(Tnode, Telem) * tgt_before = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator; - $dlinks(Telem) * links_before = & tgt_before->$links; - &incoming_from_prev = & links_before->next; - } else if ($prev_link(list_pos).elem) { - Telem * tgt_before = $prev_link(list_pos).elem; - Tnode & list_pos_before = $tempcv_e2n(*tgt_before); - &incoming_from_prev = & $next_link(list_pos_before); - } - - if ( $next_link(list_pos).is_terminator ) { - dlist(Tnode, Telem) * tgt_after = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator; - $dlinks(Telem) * links_after = & tgt_after->$links; - &incoming_from_next = & links_after->prev; - } else if ($next_link(list_pos).elem) { - Telem * tgt_after = $next_link(list_pos).elem; - Tnode & list_pos_after = $tempcv_e2n(*tgt_after ); - &incoming_from_next = & $prev_link(list_pos_after ); - } - - if (& incoming_from_prev) { - incoming_from_prev = $next_link(list_pos); - } - if (& incoming_from_next) { - incoming_from_next = $prev_link(list_pos); - } - - $next_link(list_pos) = (Telem*) 0p; - $prev_link(list_pos) = (Telem*) 0p; - } - - static inline bool ?`is_empty(dlist(Tnode, Telem) &list) { - verify( &list != 0p ); - $dlinks(Telem) *listLinks = & list.$links; - if (listLinks->next.is_terminator) { - verify(listLinks->prev.is_terminator); - verify(listLinks->next.terminator); - verify(listLinks->prev.terminator); - return true; - } else { - verify(!listLinks->prev.is_terminator); - verify(listLinks->next.elem); - verify(listLinks->prev.elem); - return false; - } - } - - static inline Telem & pop_first(dlist(Tnode, Telem) &list) { - verify( &list != 0p ); - verify( !list`is_empty ); - $dlinks(Telem) *listLinks = & list.$links; - Telem & first = *listLinks->next.elem; - Tnode & list_pos_first = $tempcv_e2n( first ); - remove(list_pos_first); - return first; - } - - static inline Telem & pop_last(dlist(Tnode, Telem) &list) { - verify( &list != 0p ); - verify( !list`is_empty ); - $dlinks(Telem) *listLinks = & list.$links; - Telem & last = *listLinks->prev.elem; - Tnode & list_pos_last = $tempcv_e2n( last ); - remove(list_pos_last); - return last; - } + dlink(tE) & linkToInsert = to_insert`inner; + verify(linkToInsert.next == 0p); + verify(linkToInsert.prev == 0p); + tE & list_pos_raw = list_pos; + tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw ); + dlink(tE) & list_pos_links = list_pos_elem`inner; + asm( "" : : : "memory" ); + tE & before_raw = * (list_pos_links).prev; + tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + linkToInsert.next = & list_pos_raw; + linkToInsert.prev = & before_raw; + dlink(tE) & beforeLinks = before_elem`inner; + beforeLinks.next = &to_insert; + (list_pos_links).prev = &to_insert; + asm( "" : : : "memory" ); + } + + static inline tE & remove(tE & list_pos) { + verify (&list_pos != 0p); + tE & list_pos_elem = list_pos; + verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) ); + dlink(tE) & list_pos_links = list_pos_elem`inner; + tE & before_raw = * list_pos_links.prev; + tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + dlink(tE) & before_links = before_elem`inner; + tE & after_raw = * list_pos_links.next; + tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + dlink(tE) & after_links = after_elem`inner; + before_links.next = &after_raw; + after_links.prev = &before_raw; + asm( "" : : : "memory" ); + list_pos_links.prev = 0p; + list_pos_links.next = 0p; + asm( "" : : : "memory" ); + return list_pos_elem; + } + + static inline tE & ?`first( dlist(tE, tLinks) &lst ) { + tE * firstPtr = lst.next; + if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + return *firstPtr; + } + static inline tE & ?`last ( dlist(tE, tLinks) &lst ) { + tE * lastPtr = lst.prev; + if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; + return *lastPtr; + } + + static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) { + tE * firstPtr = lst.next; + if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + return firstPtr == 0p; + } + + static inline tE & ?`elems( dlist(tE, tLinks) & lst ) { + tE * origin = $get_list_origin_addr( lst ); + return *origin; + } + + static inline bool ?`moveNext( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + &ref_inner = oldReferent`inner.next; + return &ref_inner != 0p && + ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + + static inline bool ?`movePrev( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + &ref_inner = oldReferent`inner.prev; + return &ref_inner != 0p && + ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + + static inline bool ?`hasNext( tE & e ) { + return e`moveNext; + } + + static inline bool ?`hasPrev( tE & e ) { + return e`movePrev; + } + + static inline tE & ?`next( tE & e ) { + if( e`moveNext ) return e; + return * 0p; + } + + static inline tE & ?`prev( tE & e ) { + if( e`movePrev ) return e; + return * 0p; + } + + static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) { + insert_after(lst`elems, e); + } + + static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { + insert_before(lst`elems, e); + } + + static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) { + tE & first_inlist = lst`first; + tE & first_item = first_inlist; + if (&first_item) remove(first_inlist); + return first_item; + } + + static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) { + tE & last_inlist = lst`last; + tE & last_item = last_inlist; + if (&last_item) remove(last_inlist); + return last_item; + } + + + #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) + static bool $validate_fwd( dlist(tE, tLinks) & this ) { + if ( ! & this`first ) return ( (& this`last) == 0p); + + tE & lagElem = *0p; + + while ( tE & it = this`elems; it`moveNext ) { + if (& lagElem == 0p && &it != & this`first ) return false; + & lagElem = & it; + } + + if (& lagElem != & this`last) return false; + + // TODO: verify that it is back at this`elems; + return true; + } + static bool $validate_rev( dlist(tE, tLinks) & this ) { + if ( ! & this`last ) return ( (& this`first) == 0p); + + tE & lagElem = *0p; + + while ( tE & it = this`elems; it`movePrev ) { + if (& lagElem == 0p && &it != & this`last ) return false; + & lagElem = & it; + } + + if (& lagElem != & this`first) return false; + + // TODO: verify that it is back at this`elems; + return true; + } + static bool validate( dlist(tE, tLinks) & this ) { + return $validate_fwd(this) && $validate_rev(this); + } + #endif } Index: bcfa/src/containers/list2.hfa =================================================================== --- libcfa/src/containers/list2.hfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ (revision ) @@ -1,297 +1,0 @@ -// -// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo -// -// The contents of this file are covered under the licence agreement in the -// file "LICENCE" distributed with Cforall. -// -// list -- lets a user-defined stuct form intrusive linked lists -// -// Author : Michael Brooks -// Created On : Wed Apr 22 18:00:00 2020 -// Last Modified By : Michael Brooks -// Last Modified On : Wed Apr 22 18:00:00 2020 -// Update Count : 1 -// - -#pragma once - -#include - -forall( Decorator &, T & ) -struct tytagref { - inline T &; -}; - -trait embedded( tOuter &, tMid &, tInner & ) { - tytagref( tMid, tInner ) ?`inner( tOuter & ); -}; - -// embedded is reflexive, with no info (void) as the type tag -forall (T &) -tytagref(void, T) ?`inner ( T & this ) { tytagref( void, T ) ret = {this}; return ret; } - -// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance -#define P9_EMBEDDED( derived, immedBase ) \ -forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \ - static inline tytagref(immedBase, Tbase) ?`inner( derived & this ) { \ - immedBase & ib = this; \ - Tbase & b = ib`inner; \ - tytagref(immedBase, Tbase) result = { b }; \ - return result; \ - } - -#define EMBEDDED_VIA( OUTER, MID, INNER ) \ - (struct { tytagref(MID, INNER) ( * ?`inner ) ( OUTER & ); }){ ?`inner } - -#define DLINK_VIA( TE, TLINK ) \ - EMBEDDED_VIA( TE, TLINK, dlink(TE) ) - - -// The origin is the position encountered at the start of iteration, -// signifying, "need to advance to the first element," and at the end -// of iteration, signifying, "no more elements." Normal comsumption of -// an iterator runs ?`moveNext as the first step, and uses the return -// of ?`moveNext as a guard, before dereferencing the iterator. So -// normal consumption of an iterator does not dereference an iterator -// in origin position. The value of a pointer (underlying a refence) -// that is exposed publicly as an iteraor, and also a pointer stored -// internally in a link field, is tagged, to indicate "is the origin" -// (internally, is the list-head sentinel node), or untagged, to indicate -// "is a regular node." Intent is to help a user who dereferences an -// iterator in origin position (which would be an API-use error on their -// part), by failing fast. - -#if defined( __x86_64 ) - // Preferred case: tag in the most-significant bit. Dereference - // has been shown to segfault consistently. Maintenance should - // list more architectures as "ok" here, to let them use the - // preferred case, when valid. - #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 ) -#else - // Fallback case: tag in the least-significant bit. Dereference - // will often give an alignment error, but may not, e.g. if - // accessing a char-typed member. 32-bit x86 uses the most- - // significant bit for real room on the heap. - #define ORIGIN_TAG_BITNO 0 -#endif -#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO) - -#define ORIGIN_TAG_SET(p) ((p) | ORIGIN_TAG_MASK) -#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK) -#define ORIGIN_TAG_QUERY(p) ((p) & ORIGIN_TAG_MASK) - - -forall( tE & ) { - - struct dlink{ - tE *next; - tE *prev; - }; - - static inline void ?{}( dlink(tE) & this ) { - this.next = 0p; - this.prev = 0p; - } - - forall( tLinks & = dlink(tE) ) - struct dlist { - inline dlink(tE); - }; - - forall( tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) { - dlink(tE) & link_from_null = ( * (tE *) 0p )`inner; - ptrdiff_t link_offset = (ptrdiff_t) & link_from_null; - size_t origin_addr = ((size_t) & lst) - link_offset; - size_t preResult = ORIGIN_TAG_SET( origin_addr ); - return (tE *)preResult; - } - - static inline void ?{}( dlist(tE, tLinks) & this ) { - tE * listOrigin = $get_list_origin_addr( this ); - ( ( dlink(tE) & ) this ){ listOrigin, listOrigin } ; - } - } - -} - - -forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { - - static inline void insert_after(tE & list_pos, tE &to_insert) { - verify (&list_pos != 0p); - verify (&to_insert != 0p); - dlink(tE) & linkToInsert = to_insert`inner; - verify(linkToInsert.prev == 0p); - verify(linkToInsert.next == 0p); - tE & list_pos_raw = list_pos; - tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw ); - dlink(tE) & list_pos_links = list_pos_elem`inner; - asm( "" : : : "memory" ); - tE & after_raw = * list_pos_links.next; - tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); - linkToInsert.prev = & list_pos_raw; - linkToInsert.next = & after_raw; - dlink(tE) & afterLinks = after_elem`inner; - afterLinks.prev = &to_insert; - list_pos_links.next = &to_insert; - asm( "" : : : "memory" ); - } - - static inline void insert_before(tE & list_pos, tE &to_insert) { - verify (&list_pos != 0p); - verify (&to_insert != 0p); - dlink(tE) & linkToInsert = to_insert`inner; - verify(linkToInsert.next == 0p); - verify(linkToInsert.prev == 0p); - tE & list_pos_raw = list_pos; - tE & list_pos_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & list_pos_raw ); - dlink(tE) & list_pos_links = list_pos_elem`inner; - asm( "" : : : "memory" ); - tE & before_raw = * (list_pos_links).prev; - tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); - linkToInsert.next = & list_pos_raw; - linkToInsert.prev = & before_raw; - dlink(tE) & beforeLinks = before_elem`inner; - beforeLinks.next = &to_insert; - (list_pos_links).prev = &to_insert; - asm( "" : : : "memory" ); - } - - static inline tE & remove(tE & list_pos) { - verify (&list_pos != 0p); - tE & list_pos_elem = list_pos; - verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos_elem) ); - dlink(tE) & list_pos_links = list_pos_elem`inner; - tE & before_raw = * list_pos_links.prev; - tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); - dlink(tE) & before_links = before_elem`inner; - tE & after_raw = * list_pos_links.next; - tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); - dlink(tE) & after_links = after_elem`inner; - before_links.next = &after_raw; - after_links.prev = &before_raw; - asm( "" : : : "memory" ); - list_pos_links.prev = 0p; - list_pos_links.next = 0p; - asm( "" : : : "memory" ); - return list_pos_elem; - } - - static inline tE & ?`first( dlist(tE, tLinks) &lst ) { - tE * firstPtr = lst.next; - if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; - return *firstPtr; - } - static inline tE & ?`last ( dlist(tE, tLinks) &lst ) { - tE * lastPtr = lst.prev; - if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; - return *lastPtr; - } - - static inline bool ?`isEmpty( dlist(tE, tLinks) & lst ) { - tE * firstPtr = lst.next; - if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; - return firstPtr == 0p; - } - - static inline tE & ?`elems( dlist(tE, tLinks) & lst ) { - tE * origin = $get_list_origin_addr( lst ); - return *origin; - } - - static inline bool ?`moveNext( tE && refx ) { - tE && ref_inner = refx; - tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); - &ref_inner = oldReferent`inner.next; - return &ref_inner != 0p && - ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); - } - - static inline bool ?`movePrev( tE && refx ) { - tE && ref_inner = refx; - tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); - &ref_inner = oldReferent`inner.prev; - return &ref_inner != 0p && - ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); - } - - static inline bool ?`hasNext( tE & e ) { - return e`moveNext; - } - - static inline bool ?`hasPrev( tE & e ) { - return e`movePrev; - } - - static inline tE & ?`next( tE & e ) { - if( e`moveNext ) return e; - return * 0p; - } - - static inline tE & ?`prev( tE & e ) { - if( e`movePrev ) return e; - return * 0p; - } - - static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) { - insert_after(lst`elems, e); - } - - static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { - insert_before(lst`elems, e); - } - - static inline tE & try_pop_front( dlist(tE, tLinks) &lst ) { - tE & first_inlist = lst`first; - tE & first_item = first_inlist; - if (&first_item) remove(first_inlist); - return first_item; - } - - static inline tE & try_pop_back( dlist(tE, tLinks) &lst ) { - tE & last_inlist = lst`last; - tE & last_item = last_inlist; - if (&last_item) remove(last_inlist); - return last_item; - } - - - #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) - static bool $validate_fwd( dlist(tE, tLinks) & this ) { - if ( ! & this`first ) return ( (& this`last) == 0p); - - tE & lagElem = *0p; - - while ( tE & it = this`elems; it`moveNext ) { - if (& lagElem == 0p && &it != & this`first ) return false; - & lagElem = & it; - } - - if (& lagElem != & this`last) return false; - - // TODO: verify that it is back at this`elems; - return true; - } - static bool $validate_rev( dlist(tE, tLinks) & this ) { - if ( ! & this`last ) return ( (& this`first) == 0p); - - tE & lagElem = *0p; - - while ( tE & it = this`elems; it`movePrev ) { - if (& lagElem == 0p && &it != & this`last ) return false; - & lagElem = & it; - } - - if (& lagElem != & this`first) return false; - - // TODO: verify that it is back at this`elems; - return true; - } - static bool validate( dlist(tE, tLinks) & this ) { - return $validate_fwd(this) && $validate_rev(this); - } - #endif - -} - Index: libcfa/src/executor.baseline.txt =================================================================== --- libcfa/src/executor.baseline.txt (revision 69914cbc38918b375971f7accca59529f62f2d08) +++ libcfa/src/executor.baseline.txt (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -0,0 +1,165 @@ +// Mutex buffer is embedded in the nomutex executor to allow the executor to delete the workers without causing a +// deadlock. If the executor is the monitor and the buffer is class, the thread calling the executor's destructor +// (which is mutex) blocks when deleting the workers, preventing outstanding workers from calling remove to drain the +// buffer. + +#include +#include + +forall( T & | $dlistable(T, T) ) { + monitor Buffer { // unbounded buffer + dlist( T, T ) queue; // unbounded list of work requests + condition delay; + }; // Buffer + + void insert( Buffer(T) & mutex buf, T * elem ) with(buf) { + dlist( T, T ) * qptr = &queue; // workaround https://cforall.uwaterloo.ca/trac/ticket/166 + insert_last( *qptr, *elem ); // insert element into buffer + signal( delay ); // restart + } // insert + + T * remove( Buffer(T) & mutex buf ) with(buf) { + dlist( T, T ) * qptr = &queue; // workaround https://cforall.uwaterloo.ca/trac/ticket/166 + // if ( (*qptr)`is_empty ) wait( delay ); // no request to process ? => wait + if ( (*qptr)`is_empty ) return 0p; // no request to process ? => wait + return &pop_first( *qptr ); + } // remove +} // forall + +struct WRequest { // client request, no return + void (* action)( void ); + DLISTED_MGD_IMPL_IN(WRequest) +}; // WRequest +DLISTED_MGD_IMPL_OUT(WRequest) + +void ?{}( WRequest & req ) with(req) { action = 0; } +void ?{}( WRequest & req, void (* action)( void ) ) with(req) { req.action = action; } +bool stop( WRequest & req ) { return req.action == 0; } +void doit( WRequest & req ) { req.action(); } + +// Each worker has its own set (when requests buffers > workers) of work buffers to reduce contention between client +// and server, where work requests arrive and are distributed into buffers in a roughly round-robin order. + +thread Worker { + Buffer(WRequest) * requests; + WRequest * request; + unsigned int start, range; +}; // Worker + +void main( Worker & w ) with(w) { + for ( int i = 0;; i = (i + 1) % range ) { + request = remove( requests[i + start] ); + if ( ! request ) { yield(); continue; } + if ( stop( *request ) ) break; + doit( *request ); + delete( request ); + } // for +} // Worker::main + +void ?{}( Worker & worker, cluster * wc, Buffer(WRequest) * requests, unsigned int start, unsigned int range ) { + ((thread &)worker){ *wc }; + worker.[requests, request, start, range] = [requests, ((WRequest *) 0), start, range]; +} // ?{} + +WRequest * current_request( Worker & worker ) { return worker.request; } + +struct Executor { + cluster * cluster; // if workers execute on separate cluster + processor ** processors; // array of virtual processors adding parallelism for workers + Buffer(WRequest) * requests; // list of work requests + Worker ** workers; // array of workers executing work requests + unsigned int nprocessors, nworkers, nrqueues; // number of processors/threads/request queues + bool sepClus; // use same or separate cluster for executor + unsigned int next; // demultiplexed across worker buffers +}; // Executor + +unsigned int tickets( Executor & ex ) with(ex) { + //return uFetchAdd( next, 1 ) % nrqueues; + return next++ % nrqueues; // no locking, interference randomizes +} // tickets + +void ?{}( Executor & ex, unsigned int np, unsigned int nw, unsigned int nr, bool sc = false ) with(ex) { + [nprocessors, nworkers, nrqueues, sepClus] = [np, nw, nr, sc]; + assert( nrqueues >= nworkers ); + cluster = 0p; + processors = aalloc( nprocessors ); + requests = anew( nrqueues ); + workers = aalloc( nworkers ); + + for ( i; nprocessors ) { + processors[i] = new( *cluster ); + } // for + + unsigned int reqPerWorker = nrqueues / nworkers, extras = nrqueues % nworkers; +// for ( unsigned int i = 0, start = 0, range; i < nworkers; i += 1, start += range ) { + for ( i; nworkers : start; 0u ~ @ ~ range : range; ) { + range = reqPerWorker + ( i < extras ? 1 : 0 ); + workers[i] = new( cluster, requests, start, range ); + } // for +} // ?{} + +void ?{}( Executor & ex, unsigned int nprocessors, unsigned int nworkers, bool sepClus = false ) { + ex{ nprocessors, nworkers, nworkers, sepClus }; +} +void ?{}( Executor & ex, unsigned int nprocessors, bool sepClus = false ) { + ex{ nprocessors, nprocessors, nprocessors, sepClus }; +} +void ?{}( Executor & ex ) { // special for current cluster, no processors added + ex{ 0, 5, false }; +} +void ^?{}( Executor & ex ) with(ex) { + // Add one sentinel per worker to stop them. Since in destructor, no new external work should be queued. Cannot + // combine next two loops and only have a single sentinel because workers arrive in arbitrary order, so worker1 may + // take the single sentinel while waiting for worker 0 to end. + + WRequest sentinel[nworkers]; + unsigned int reqPerWorker = nrqueues / nworkers; + for ( unsigned int i = 0, step = 0; i < nworkers; i += 1, step += reqPerWorker ) { + insert( requests[step], &sentinel[i] ); // force eventually termination + } // for + for ( i; nworkers ) { + delete( workers[i] ); + } // for + for ( i; nprocessors ) { + delete( processors[i] ); + } // for + + free( workers ); +// adelete( nrqueues, requests ); + for ( i; nrqueues ) ^?{}( requests[i] ); // FIX ME: problem with resolver + free( requests ); + free( processors ); + if ( sepClus ) { delete( cluster ); } +} // ^?{} + +void send( Executor & ex, void (* action)( void ) ) { // asynchronous call, no return value + WRequest * node = new( action ); + insert( ex.requests[tickets( ex )], node ); +} // send + + +int counter = 0; + +void work( void ) { + __atomic_add_fetch( &counter, 1, __ATOMIC_SEQ_CST ); + // fprintf( stderr, "workie\n" ); +} + +int main( int argc, char * argv[] ) { + int times = 1_000_000; + if ( argc == 2 ) times = atoi( argv[1] ); + processor p[7]; + { + Executor exector; + for ( i; times ) { + send( exector, work ); + if ( i % 100 == 0 ) yield(); + } // for + } + printf( "%d\n", counter ); +} + +// Local Variables: // +// tab-width: 4" // +// compile-command: "cfa executor.cfa" // +// End: // Index: libcfa/src/executor.cfa =================================================================== --- libcfa/src/executor.cfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ libcfa/src/executor.cfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -7,21 +7,21 @@ #include -forall( T & | $dlistable(T, T) ) { +forall( T &, TLink& = dlink(T) | embedded(T, TLink, dlink(T)) ) { monitor Buffer { // unbounded buffer - dlist( T, T ) queue; // unbounded list of work requests + dlist( T, TLink ) queue; // unbounded list of work requests condition delay; }; // Buffer - void insert( Buffer(T) & mutex buf, T * elem ) with(buf) { - dlist( T, T ) * qptr = &queue; // workaround https://cforall.uwaterloo.ca/trac/ticket/166 + void insert( Buffer(T, TLink) & mutex buf, T * elem ) with(buf) { + dlist( T, TLink ) * qptr = &queue; // workaround https://cforall.uwaterloo.ca/trac/ticket/166 insert_last( *qptr, *elem ); // insert element into buffer signal( delay ); // restart } // insert - T * remove( Buffer(T) & mutex buf ) with(buf) { - dlist( T, T ) * qptr = &queue; // workaround https://cforall.uwaterloo.ca/trac/ticket/166 - // if ( (*qptr)`is_empty ) wait( delay ); // no request to process ? => wait - if ( (*qptr)`is_empty ) return 0p; // no request to process ? => wait - return &pop_first( *qptr ); + T * remove( Buffer(T, TLink) & mutex buf ) with(buf) { + dlist( T, TLink ) * qptr = &queue; // workaround https://cforall.uwaterloo.ca/trac/ticket/166 + // if ( (*qptr)`isEmpty ) wait( delay ); // no request to process ? => wait + if ( (*qptr)`isEmpty ) return 0p; // no request to process ? => wait + return &try_pop_front( *qptr ); } // remove } // forall @@ -29,7 +29,7 @@ struct WRequest { // client request, no return void (* action)( void ); - DLISTED_MGD_IMPL_IN(WRequest) + inline dlink(WRequest); }; // WRequest -DLISTED_MGD_IMPL_OUT(WRequest) +P9_EMBEDDED(WRequest, dlink(WRequest)) void ?{}( WRequest & req ) with(req) { action = 0; } Index: sts/list/.expect/dlist-insert-remove-2.txt =================================================================== --- tests/list/.expect/dlist-insert-remove-2.txt (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ (revision ) @@ -1,1110 +1,0 @@ - -~~~~~~~~~~~~~~~~~ Headed List Tests - insert_first ~~~~~~~~~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 4-i: Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -==== fred by YOURS after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 5-i: Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 6-i. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== mary after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- - -~~~~~~~~~~~~~~~~~ Headed List Tests - insert_last ~~~~~~~~~~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 4-ii: Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -==== fred by YOURS after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 5-ii: Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 6-ii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== mary after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- - -~~~~~~~~~~~ Element ops on Headed List Tests: after, last ~~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 7-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -==== fred by YOURS after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 8-i. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 9-i. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- - -~~~~~~~~~~ Element ops on Headed List Tests: before, first ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 7-ii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -==== fred by YOURS after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 8-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 9-ii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- - -~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 13-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 14-i. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 15-i. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== mary after -1.7 -- -1.7 -- -- -- - -~~~~~~~~~~ Element removal tests on Headed List: at last ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 13-ii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 14-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 15-ii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== mary after -3.7 -- -3.7 -- -- -- - -~~~~~~~~~~ Element removal tests on Headed List: of sole ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 13-iii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by MINE after -0.7 -- -0.7 -- -- -- -==== fred by MINE after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 14-iii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS after -0.7 -- -0.7 -- -- -- -==== fred by YOURS after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 15-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== mary after -0.7 -- -0.7 -- -- -- -==== mary after -0.7 -- -0.7 -- -0.7 -- -0.7 -- - -~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 16-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 16-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 16-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== mary after -1.7 -- -1.7 -- -- -- - -~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 17-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 17-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 17-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== mary after -3.7 -- -3.7 -- -- -- - -~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 18-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Not implmented -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 18-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Not implmented -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 18-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -accessor_cases done -try_pop cases done -origin_mutation cases done Index: tests/list/.expect/dlist-insert-remove.txt =================================================================== --- tests/list/.expect/dlist-insert-remove.txt (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ tests/list/.expect/dlist-insert-remove.txt (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -1,217 +1,2 @@ -~~~~~~~~~~~~~~~~~ Headless List Tests - insert_after ~~~~~~~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 1-i: Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -==== fred by YOURS after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 2-i. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 3-i. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== mary after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- - -~~~~~~~~~~~~~~~~ Headless List Tests - insert_before ~~~~~~~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 1-ii: Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -==== fred by YOURS after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 2-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by MINE after -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== fred by YOURS after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 3-ii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -3.14 -- -3.14 -- -0.5 -- -0.5 -- -==== mary after -3.14 -0.5 -- -3.14 -- -0.5 -- -0.5 -3.14 -- ~~~~~~~~~~~~~~~~~ Headed List Tests - insert_first ~~~~~~~~~~~~~~~~~~ @@ -557,129 +342,129 @@ - -~~~~~~~~~~ Element removal tests on Headless List: mid ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 10-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -2.7 -- -2.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 11-i. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -1.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -1.7 -- -==== fred by YOURS after -2.7 -- -2.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 12-i. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~ + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 13-i. Modifying Freds on MINE +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +2.7 +3.7 +- +2.7 +- +3.7 +- +3.7 +2.7 +- +==== fred by YOURS after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +- +1.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 14-i. Modifying Freds on YOURS +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS after +2.7 +3.7 +- +2.7 +- +3.7 +- +3.7 +2.7 +- +==== fred by YOURS after +1.7 +- +1.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 15-i. Modifying Maries +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ==== mary before 1.7 @@ -696,147 +481,147 @@ - ==== mary after -1.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -1.7 -- -==== mary after -2.7 -- -2.7 -- -- -- - -~~~~~~~~~~ Element removal tests on Headless List: at first ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 10-ii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 11-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 12-ii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +2.7 +3.7 +- +2.7 +- +3.7 +- +3.7 +2.7 +- +==== mary after +1.7 +- +1.7 +- +- +- + +~~~~~~~~~~ Element removal tests on Headed List: at last ~~~~~~~~~~ + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 13-ii. Modifying Freds on MINE +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +2.7 +- +1.7 +- +2.7 +- +2.7 +1.7 +- +==== fred by YOURS after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +3.7 +- +3.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 14-ii. Modifying Freds on YOURS +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS after +1.7 +2.7 +- +1.7 +- +2.7 +- +2.7 +1.7 +- +==== fred by YOURS after +3.7 +- +3.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 15-ii. Modifying Maries +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ==== mary before 1.7 @@ -853,303 +638,269 @@ - ==== mary after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== mary after -1.7 -- -1.7 -- -- -- - -~~~~~~~~~~ Element removal tests on Headless List: at last ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 10-iii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 11-iii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 12-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +1.7 +2.7 +- +1.7 +- +2.7 +- +2.7 +1.7 +- +==== mary after +3.7 +- +3.7 +- +- +- + +~~~~~~~~~~ Element removal tests on Headed List: of sole ~~~~~~~~~~ + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 13-iii. Modifying Freds on MINE +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== fred by YOURS before +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== fred by YOURS after +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== fred by MINE after +0.7 +- +0.7 +- +- +- +==== fred by MINE after +0.7 +- +0.7 +- +0.7 +- +0.7 +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 14-iii. Modifying Freds on YOURS +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== fred by YOURS before +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== fred by YOURS after +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== fred by YOURS after +0.7 +- +0.7 +- +- +- +==== fred by YOURS after +0.7 +- +0.7 +- +0.7 +- +0.7 +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 15-iii. Modifying Maries +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== mary after -3.7 -- -3.7 -- -- -- - -~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 13-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 14-i. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 15-i. Modifying Maries +0.7 +- +0.7 +- +0.7 +- +0.7 +- +==== mary after +0.7 +- +0.7 +- +- +- +==== mary after +0.7 +- +0.7 +- +0.7 +- +0.7 +- + +~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~ + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 16-i. Modifying Freds on MINE +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +2.7 +3.7 +- +2.7 +- +3.7 +- +3.7 +2.7 +- +==== fred by YOURS after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +- +1.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 16-ii. Modifying Freds on YOURS +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS after +2.7 +3.7 +- +2.7 +- +3.7 +- +3.7 +2.7 +- +==== fred by YOURS after +1.7 +- +1.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 16-iii. Modifying Maries ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ==== mary before @@ -1185,128 +936,128 @@ - -~~~~~~~~~~ Element removal tests on Headed List: at last ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 13-ii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 14-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 15-ii. Modifying Maries +~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~ + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 17-i. Modifying Freds on MINE +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +2.7 +- +1.7 +- +2.7 +- +2.7 +1.7 +- +==== fred by YOURS after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +3.7 +- +3.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 17-ii. Modifying Freds on YOURS +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +==== fred by MINE before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS before +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by MINE after +1.7 +2.7 +3.7 +- +1.7 +- +3.7 +- +3.7 +2.7 +1.7 +- +==== fred by YOURS after +1.7 +2.7 +- +1.7 +- +2.7 +- +2.7 +1.7 +- +==== fred by YOURS after +3.7 +- +3.7 +- +- +- +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 17-iii. Modifying Maries ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ ==== mary before @@ -1342,438 +1093,18 @@ - -~~~~~~~~~~ Element removal tests on Headed List: of sole ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 13-iii. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by MINE after -0.7 -- -0.7 -- -- -- -==== fred by MINE after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 14-iii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== fred by YOURS after -0.7 -- -0.7 -- -- -- -==== fred by YOURS after -0.7 -- -0.7 -- -0.7 -- -0.7 -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 15-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -0.7 -- -0.7 -- -0.7 -- -0.7 -- -==== mary after -0.7 -- -0.7 -- -- -- -==== mary after -0.7 -- -0.7 -- -0.7 -- -0.7 -- - -~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 16-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 16-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== fred by YOURS after -1.7 -- -1.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 16-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -2.7 -3.7 -- -2.7 -- -3.7 -- -3.7 -2.7 -- -==== mary after -1.7 -- -1.7 -- -- -- - -~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~ - -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 17-i. Modifying Freds on MINE -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 17-ii. Modifying Freds on YOURS -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== fred by MINE before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by MINE after -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== fred by YOURS after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== fred by YOURS after -3.7 -- -3.7 -- -- -- -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -Test 17-iii. Modifying Maries -~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ -==== mary before -1.7 -2.7 -3.7 -- -1.7 -- -3.7 -- -3.7 -2.7 -1.7 -- -==== mary after -1.7 -2.7 -- -1.7 -- -2.7 -- -2.7 -1.7 -- -==== mary after -3.7 -- -3.7 -- -- -- +~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~ + +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 18-i. Modifying Freds on MINE +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Not implmented +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 18-ii. Modifying Freds on YOURS +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Not implmented +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +Test 18-iii. Modifying Maries +~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ +accessor_cases done +try_pop cases done +origin_mutation cases done Index: sts/list/dlist-insert-remove-2.cfa =================================================================== --- tests/list/dlist-insert-remove-2.cfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ (revision ) @@ -1,1908 +1,0 @@ -#include -#include -#include - -// Section 1: replaced by above include list.hfa - - -//////////////////////////////////////////////////////////// -// -// Section 2 -// -// Structure definitions -// -// Example of declaration-side user code -// -//////////////////////////////////////////////////////////// - -// a fred belongs to two doubly-linked lists: mine and yours -struct fred { - float adatum; - inline struct mine { inline dlink(fred); }; - inline struct yours { inline dlink(fred); }; -}; -P9_EMBEDDED(fred, fred.mine) -P9_EMBEDDED(fred, fred.yours) -P9_EMBEDDED(fred.mine, dlink(fred)) -P9_EMBEDDED(fred.yours, dlink(fred)) - - -void ?{}(fred &this, float adatum) { - (this.adatum){adatum}; -} - -// a mary belongs to just one doubly-linked list: hers -struct mary { - float anotherdatum; - inline dlink(mary); -}; - -P9_EMBEDDED(mary, dlink(mary)) - -void ?{}(mary &this, float anotherdatum) { - (this.anotherdatum){anotherdatum}; -} - -//////////////////////////////////////////////////////////// -// -// Section 3 -// -// Test helpers to traverse and print lists. -// -// These consume framework-provided accessor functions and -// do not modify their parameter lists. -// -//////////////////////////////////////////////////////////// - -void printMyFredsFwd(fred & f) { - with( DLINK_VIA( fred, fred.mine ) ) - do { - sout | f.adatum; - } while (f`moveNext); -} - -void printMyFredsRev(fred & f) { - with( DLINK_VIA( fred, fred.mine ) ) - do { - sout | f.adatum; - } while (f`movePrev); -} - - -void printMyFreddies(fred &f1, fred &f2, int isBefore) { - if (isBefore) { - sout | "==== fred by MINE before "; - } else { - sout | "==== fred by MINE after "; - } - if (&f1) { - printMyFredsFwd(f1); sout | '-'; - printMyFredsRev(f1); sout | '-'; - } else { - sout | '-'; sout | '-'; - } - if (&f2) { - printMyFredsFwd(f2); sout | '-'; - printMyFredsRev(f2); sout | '-'; - } else { - sout | '-'; sout | '-'; - } -} - -void printYourFredsFwd(fred & f) { - with( DLINK_VIA( fred, fred.yours ) ) - do { - sout | f.adatum; - } while (f`moveNext); -} - -void printYourFredsRev(fred & f) { - with( DLINK_VIA( fred, fred.yours ) ) - do { - sout | f.adatum; - } while (f`movePrev); -} - -void printYourFreddies(fred &f1, fred &f2, int isBefore) { - if (isBefore) { - sout | "==== fred by YOURS before "; - } else { - sout | "==== fred by YOURS after "; - } - if (&f1) { - printYourFredsFwd(f1); sout | '-'; - printYourFredsRev(f1); sout | '-'; - } else { - sout | '-'; sout | '-'; - } - if (&f2) { - printYourFredsFwd(f2); sout | '-'; - printYourFredsRev(f2); sout | '-'; - } else { - sout | '-'; sout | '-'; - } -} - -void printMariesFwd(mary &m) { - do { - sout | m.anotherdatum; - } while (m`moveNext); -} - -void printMariesRev(mary &m) { - do { - sout | m.anotherdatum; - } while (m`movePrev); -} - -void printMariatheotokos(mary &m1, mary &m2, int isBefore) { - if (isBefore) { - sout | "==== mary before "; - } else { - sout | "==== mary after "; - } - if (&m1) { - printMariesFwd(m1); sout | '-'; - printMariesRev(m1); sout | '-'; - } else { - sout | '-'; sout | '-'; - } - if (&m2) { - printMariesFwd(m2); sout | '-'; - printMariesRev(m2); sout | '-'; - } else { - sout | '-'; sout | '-'; - } -} - -//////////////////////////////////////////////////////////// -// -// Section 4a.i -// -// Test cases of insert_after on headless list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -// All three tests exercise the case of merging two singleton lists into (their respective -// positions in) one common list of two elements. - -// Note that the factoring of sect 4 (vs 3 and 5) keeps section 4 free of strings and IO, -// and so keeps its assembly easy to inspect. - -// Throughout all the 4s, all the print functions called from these tests print: -// - from list position #1 moving forward (a) -// - from list position #1 moving backward (b) -// - from list position #2 moving forward (c) -// - from list position #2 moving backward (d) -// The expected-output comments are in form a;b;c;d where a::=num,num,num -#if 0 -void test__insertafter_singleton_on_singleton__fred_mine () { - fred f1 = {3.14}; - fred f2 = {0.5}; - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - diref(fred, fred.mine) f1_mine = f1`from; - insert_after(f1_mine, f2); - - printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) -} - -void test__insertafter_singleton_on_singleton__fred_yours () { - fred f1 = {3.14}; - fred f2 = {0.5}; - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - diref(fred, fred.yours) f1_yours = f1`from; - insert_after(f1_yours, f2); - - printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} - -void test__insertafter_singleton_on_singleton__mary () { - mary m1 = {3.14}; - mary m2 = {0.5}; - - printMariatheotokos(m1, m2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_after(m1, m2); - - printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} - -//////////////////////////////////////////////////////////// -// -// Section 4a.ii -// -// Test cases of insert_before on headless list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__insertbefore_singleton_on_singleton__fred_mine () { - fred f1 = {3.14}; - fred f2 = {0.5}; - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - diref(fred, fred.mine) f2_mine = f2`from; - insert_before(f2_mine, f1); - - printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) -} - -void test__insertbefore_singleton_on_singleton__fred_yours () { - fred f1 = {3.14}; - fred f2 = {0.5}; - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - diref(fred, fred.yours) f2_yours = f2`from; - insert_before(f2_yours, f1); - - printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} - -void test__insertbefore_singleton_on_singleton__mary () { - mary m1 = {3.14}; - mary m2 = {0.5}; - - printMariatheotokos(m1, m2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_before(m2, m1); - - printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} -#endif -//////////////////////////////////////////////////////////// -// -// Section 4b.i -// -// Test cases of insert_first (necessarily headed list) -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -// All three tests exercise the case of creating an empty container and -// adding two items to it. -void test__insertfirst_two_on_empty__fred_mine() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.mine) lf; - - verify(validate(lf)); - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_first(lf, f2); - insert_first(lf, f1); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) -} - -void test__insertfirst_two_on_empty__fred_yours() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.yours) lf; - - verify(validate(lf)); - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_first(lf, f2); - insert_first(lf, f1); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} -void test__insertfirst_two_on_empty__mary() { - - mary m1 = {3.14}; - mary m2 = {0.5}; - - dlist(mary) lm; - - verify(validate(lm)); - printMariatheotokos(m1, m2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_first(lm, m2); - insert_first(lm, m1); - - printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - verify(validate(lm)); -} - -//////////////////////////////////////////////////////////// -// -// Section 4b.ii -// -// Test cases of insert_last (necessarily headed list) -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__insertlast_two_on_empty__fred_mine() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.mine) lf; - - verify(validate(lf)); - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_last(lf, f1); - insert_last(lf, f2); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) -} - -void test__insertlast_two_on_empty__fred_yours() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.yours) lf; - - verify(validate(lf)); - - printMyFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_last(lf, f1); - insert_last(lf, f2); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} - -void test__insertlast_two_on_empty__mary() { - - mary m1 = {3.14}; - mary m2 = {0.5}; - - dlist(mary) lm; - - verify(validate(lm)); - printMariatheotokos(m1, m2, 1); // 3.14; 3.14; 0.5; 0.5 - - insert_last(lm, m1); - insert_last(lm, m2); - - verify(validate(lm)); - printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) -} - -//////////////////////////////////////////////////////////// -// -// Section 4c.i -// -// Test cases of insert_after on headed list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__insertafter_after_last__fred_mine() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.mine) lf; - - assert( & lf`first == 0p ); - assert( & lf`last == 0p ); - - insert_first(lf, f1); - - assert( & lf`first == & f1 ); - assert( & lf`last == & f1 ); - - verify(validate(lf)); - - with ( DLINK_VIA(fred, fred.mine) ) insert_after(f1, f2); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - - assert( & lf`first == & f1 ); - assert( & lf`last == & f2 ); -} - -void test__insertafter_after_last__fred_yours() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.yours) lf; - - assert( & lf`first == 0p ); - assert( & lf`last == 0p ); - - insert_first(lf, f1); - - assert( & lf`first == & f1 ); - assert( & lf`last == & f1 ); - - verify(validate(lf)); - - with ( DLINK_VIA(fred, fred.yours) ) insert_after(f1, f2); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - - assert( & lf`first == & f1 ); - assert( & lf`last == & f2 ); -} - -void test__insertafter_after_last__mary() { - - mary m1 = {3.14}; - mary m2 = {0.5}; - - dlist(mary) lm; - - assert( & lm`first == 0p ); - assert( & lm`last == 0p ); - - insert_first(lm, m1); - - assert( & lm`first == & m1 ); - assert( & lm`last == & m1 ); - - verify(validate(lm)); - - insert_after(m1, m2); - - verify(validate(lm)); - - printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - - assert( & lm`first == & m1 ); - assert( & lm`last == & m2 ); -} - -//////////////////////////////////////////////////////////// -// -// Section 4c.ii -// -// Test cases of insert_before on headed list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__insertbefore_before_first__fred_mine() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.mine) lf; - - assert( & lf`first == 0p ); - assert( & lf`last == 0p ); - - insert_last(lf, f2); - - assert( & lf`first == & f2 ); - assert( & lf`last == & f2 ); - - verify(validate(lf)); - - with ( DLINK_VIA(fred, fred.mine) ) insert_before(f2, f1); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - - assert( & lf`first == & f1 ); - assert( & lf`last == & f2 ); -} - -void test__insertbefore_before_first__fred_yours() { - - fred f1 = {3.14}; - fred f2 = {0.5}; - - dlist(fred, fred.yours) lf; - - assert( & lf`first == 0p ); - assert( & lf`last == 0p ); - - insert_last(lf, f2); - - assert( & lf`first == & f2 ); - assert( & lf`last == & f2 ); - - verify(validate(lf)); - - with ( DLINK_VIA(fred, fred.yours) )insert_before(f2, f1); - - verify(validate(lf)); - - printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - - assert( & lf`first == & f1 ); - assert( & lf`last == & f2 ); -} - -void test__insertbefore_before_first__mary() { - - mary m1 = {3.14}; - mary m2 = {0.5}; - - dlist(mary) lm; - - assert( & lm`first == 0p ); - assert( & lm`last == 0p ); - - insert_last(lm, m2); - - assert( & lm`first == & m2 ); - assert( & lm`last == & m2 ); - - verify(validate(lm)); - - insert_before(m2, m1); - - verify(validate(lm)); - - printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - - assert( & lm`first == & m1 ); - assert( & lm`last == & m2 ); -} -#if 0 - -//////////////////////////////////////////////////////////// -// -// Section 4d.i -// -// Test cases of remove, from middle of headless list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -// These tests, in the fred cases, set up the my/your lists initially identical, -// act on one list, and expect the other unaffected. - -void test__remove_mid__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - insert_after(f1`in_mine, f2); - insert_after(f2`in_mine, f3); - - insert_after(f1`in_yours, f2); - insert_after(f2`in_yours, f3); - - printMyFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(f2`in_mine); - - printMyFreddies(f1, f3, 0); // 1.7, 3.7; 1.7; 3.7; 3.7, 1.7 (modified) - printYourFreddies(f1, f3, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f2 is now solo in mine; in yours, it was just traversed - printMyFreddies(f2, *0p, 0); // 2.7; 2.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f2.$links_mine.next.is_terminator == false); - assert(f2.$links_mine.prev.is_terminator == false); -} - -void test__remove_mid__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - insert_after(f1`in_mine, f2); - insert_after(f2`in_mine, f3); - - insert_after(f1`in_yours, f2); - insert_after(f2`in_yours, f3); - - printMyFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(f2`in_yours); - - printMyFreddies(f1, f3, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(f1, f3, 0); // 1.7, 3.7; 1.7; 3.7; 3.7, 1.7 (modified) - - // observe f2 is now solo in yours; in mine, it was just traversed - printYourFreddies(f2, *0p, 0); // 2.7; 2.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f2.$links_yours.next.is_terminator == false); - assert(f2.$links_yours.prev.is_terminator == false); -} - -void test__remove_mid__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - insert_after(m1, m2); - insert_after(m2, m3); - - printMariatheotokos(m1, m3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(m2); - - printMariatheotokos(m1, m3, 0); // 1.7, 3.7; 1.7; 3.7; 3.7, 1.7 (modified) - - // observe m2 is now solo - printMariatheotokos(m2, *0p, 0); // 2.7; 2.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(m2.$links.next.is_terminator == false); - assert(m2.$links.prev.is_terminator == false); -} - -//////////////////////////////////////////////////////////// -// -// Section 4d.ii -// -// Test cases of remove, from first position of headless list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -// TODO: validate headless semantic: remove of a neighbourless element is valid and no-op - -void test__remove_at_first__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - insert_after(f1`in_mine, f2); - insert_after(f2`in_mine, f3); - - insert_after(f1`in_yours, f2); - insert_after(f2`in_yours, f3); - - printMyFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(f1`in_mine); - - printMyFreddies(f2, f3, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - printYourFreddies(f1, f3, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f1 is now solo in mine; in yours, it was just traversed - printMyFreddies(f1, *0p, 0); // 1.7; 1.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f1.$links_mine.next.is_terminator == false); - assert(f1.$links_mine.prev.is_terminator == false); -} - -void test__remove_at_first__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - insert_after(f1`in_mine, f2); - insert_after(f2`in_mine, f3); - - insert_after(f1`in_yours, f2); - insert_after(f2`in_yours, f3); - - printMyFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(f1`in_yours); - - printMyFreddies(f1, f3, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(f2, f3, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - - // observe f1 is now solo in yours; in mine, it was just traversed - printYourFreddies(f1, *0p, 0); // 1.7; 1.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f1.$links_yours.next.is_terminator == false); - assert(f1.$links_yours.prev.is_terminator == false); -} - -void test__remove_at_first__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - insert_after(m1, m2); - insert_after(m2, m3); - - printMariatheotokos(m1, m3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(m1); - - printMariatheotokos(m2, m3, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - - // observe m2 is now solo - printMariatheotokos(m1, *0p, 0); // 1.7; 1.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(m1.$links.next.is_terminator == false); - assert(m1.$links.prev.is_terminator == false); -} - -//////////////////////////////////////////////////////////// -// -// Section 4d.iii -// -// Test cases of remove, from last position of headless list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__remove_at_last__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - insert_after(f1`in_mine, f2); - insert_after(f2`in_mine, f3); - - insert_after(f1`in_yours, f2); - insert_after(f2`in_yours, f3); - - printMyFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(f3`in_mine); - - printMyFreddies(f1, f2, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - printYourFreddies(f1, f3, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f3 is now solo in mine; in yours, it was just traversed - printMyFreddies(f3, *0p, 0); // 3.7; 3.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f3.$links_mine.next.is_terminator == false); - assert(f3.$links_mine.prev.is_terminator == false); -} - -void test__remove_at_last__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - insert_after(f1`in_mine, f2); - insert_after(f2`in_mine, f3); - - insert_after(f1`in_yours, f2); - insert_after(f2`in_yours, f3); - - printMyFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(f1, f3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(f3`in_yours); - - printMyFreddies(f1, f3, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(f1, f2, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - - // observe f3 is now solo in yours; in mine, it was just traversed - printYourFreddies(f3, *0p, 0); // 3.7; 3.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f3.$links_yours.next.is_terminator == false); - assert(f3.$links_yours.prev.is_terminator == false); -} - -void test__remove_at_last__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - insert_after(m1, m2); - insert_after(m2, m3); - - printMariatheotokos(m1, m3, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - remove(m3); - - printMariatheotokos(m1, m2, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - - // observe m3 is now solo - printMariatheotokos(m3, *0p, 0); // 3.7; 3.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(m1.$links.next.is_terminator == false); - assert(m1.$links.prev.is_terminator == false); -} - -//////////////////////////////////////////////////////////// -// -// Section 4e.i -// -// Test cases of remove, from first position of headed list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// -#endif -void test__remove_at_head__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - with( DLINK_VIA(fred, fred.mine) ) remove(f1); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - printYourFreddies(fly`first, fly`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f1 is now solo in mine; in yours, it was just traversed - printMyFreddies(f1, *0p, 0); // 1.7; 1.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(f1.$links_mine.next.is_terminator == false); - // assert(f1.$links_mine.prev.is_terminator == false); -} - - -void test__remove_at_head__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - with( DLINK_VIA(fred, fred.yours) ) remove(f1); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(fly`first, fly`last, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - - // observe f1 is now solo in yours; in mine, it was just traversed - printYourFreddies(f1, *0p, 0); // 1.7; 1.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(f1.$links_yours.next.is_terminator == false); - // assert(f1.$links_yours.prev.is_terminator == false); -} - -void test__remove_at_head__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - dlist(mary) ml; - insert_last(ml, m1); - insert_last(ml, m2); - insert_last(ml, m3); - - printMariatheotokos(ml`first, ml`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(ml)); - - remove(m1); - - verify(validate(ml)); - - printMariatheotokos(ml`first, ml`last, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - - // observe m1 is now solo - printMariatheotokos(m1, *0p, 0); // 1.7; 1.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(m1.$links.next.is_terminator == false); - // assert(m1.$links.prev.is_terminator == false); -} - -//////////////////////////////////////////////////////////// -// -// Section 4e.ii -// -// Test cases of remove, from last position of headed list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__remove_at_tail__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - with( DLINK_VIA(fred, fred.mine) ) remove(f3); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - printYourFreddies(fly`first, fly`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f3 is now solo in mine; in yours, it was just traversed - printMyFreddies(f3, *0p, 0); // 3.7; 3.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(f3.$links_mine.next.is_terminator == false); - // assert(f3.$links_mine.prev.is_terminator == false); -} - -void test__remove_at_tail__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - with( DLINK_VIA(fred, fred.yours) ) remove(f3); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(fly`first, fly`last, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - - // observe f3 is now solo in yours; in mine, it was just traversed - printYourFreddies(f3, *0p, 0); // 3.7; 3.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(f3.$links_yours.next.is_terminator == false); - // assert(f3.$links_yours.prev.is_terminator == false); -} - -void test__remove_at_tail__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - dlist(mary) ml; - insert_last(ml, m1); - insert_last(ml, m2); - insert_last(ml, m3); - - printMariatheotokos(ml`first, ml`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(ml)); - - remove(m3); - - verify(validate(ml)); - - printMariatheotokos(ml`first, ml`last, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - - // observe m3 is now solo - printMariatheotokos(m3, *0p, 0); //3.7; 3.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(m3.$links.next.is_terminator == false); - // assert(m3.$links.prev.is_terminator == false); -} - -//////////////////////////////////////////////////////////// -// -// Section 4e.iii -// -// Test cases of remove, of sole element of headed list -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__remove_of_sole__fred_mine() { - - fred f = {0.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f); - - dlist(fred, fred.yours) fly; - insert_last(fly, f); - - printMyFreddies(flm`first, flm`last, 1); // 0.7; 0.7; 0.7; 0.7 - printYourFreddies(fly`first, fly`last, 1); // 0.7; 0.7; 0.7; 0.7 - - verify(validate(fly)); - verify(validate(flm)); - - with( DLINK_VIA(fred, fred.mine) ) remove(f); - - verify(validate(fly)); - verify(validate(flm)); - - assert( & flm`first == 0p ); - assert( & flm`last == 0p ); - - printYourFreddies(fly`first, fly`last, 0); // 0.7; 0.7; 0.7; 0.7 (unmodified) - - // observe f is solo in mine (now unlisted); in yours, it was just traversed - printMyFreddies(f, *0p, 0); // 0.7; 0.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(f.$links_mine.next.is_terminator == false); - // assert(f.$links_mine.prev.is_terminator == false); - - insert_last(flm, f); - verify(validate(fly)); - verify(validate(flm)); - printMyFreddies(flm`first, flm`last, 0); // 0.7; 0.7; 0.7; 0.7 -} - -void test__remove_of_sole__fred_yours() { - - fred f = {0.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f); - - dlist(fred, fred.yours) fly; - insert_last(fly, f); - - printMyFreddies(flm`first, flm`last, 1); // 0.7; 0.7; 0.7; 0.7 - printYourFreddies(fly`first, fly`last, 1); // 0.7; 0.7; 0.7; 0.7 - - verify(validate(fly)); - verify(validate(flm)); - - with( DLINK_VIA(fred, fred.yours) ) remove(f); - - verify(validate(fly)); - verify(validate(flm)); - - assert( & fly`first == 0p ); - assert( & fly`last == 0p ); - - printYourFreddies(flm`first, flm`last, 0); // 0.7; 0.7; 0.7; 0.7 (unmodified) - - // observe f is solo in yours (now unlisted); in mine, it was just traversed - printYourFreddies(f, *0p, 0); // 0.7; 0.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(f.$links_yours.next.is_terminator == false); - // assert(f.$links_yours.prev.is_terminator == false); - - insert_last(fly, f); - verify(validate(fly)); - verify(validate(flm)); - printYourFreddies(fly`first, fly`last, 0); // 0.7; 0.7; 0.7; 0.7 -} - -void test__remove_of_sole__mary() { - - mary m = {0.7}; - - dlist(mary) ml; - insert_last(ml, m); - - printMariatheotokos(ml`first, ml`last, 1); // 0.7; 0.7; 0.7; 0.7 - - verify(validate(ml)); - - remove(m); - - verify(validate(ml)); - - assert( & ml`first == 0p ); - assert( & ml`last == 0p ); - - // observe f is solo in mine (now unlisted); in yours, it was just traversed - printMariatheotokos(m, *0p, 0); // 0.7; 0.7; ; - - // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - // assert(m.$links.next.is_terminator == false); - // assert(m.$links.prev.is_terminator == false); - - insert_last(ml, m); - verify(validate(ml)); - printMariatheotokos(ml`first, ml`last, 0); // 0.7; 0.7; 0.7; 0.7 -} - -//////////////////////////////////////////////////////////// -// -// Section 4f -// -// Test cases of pop_first, pop_last -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -// These cases assume element removal at first-last is correct - -void test__pop_first__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - fred & popped = try_pop_front(flm); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - printYourFreddies(fly`first, fly`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f1 is now solo in mine; in yours, it was just traversed - printMyFreddies(f1, *0p, 0); // 1.7; 1.7; ; - - assert( &popped == & f1 ); -} - -void test__pop_first__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - fred & popped = try_pop_front(fly); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(fly`first, fly`last, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - - // observe f1 is now solo in yours; in mine, it was just traversed - printYourFreddies(f1, *0p, 0); // 1.7; 1.7; ; - - assert( &popped == &f1 ); -} - -void test__pop_first__maries() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - dlist(mary) ml; - insert_last(ml, m1); - insert_last(ml, m2); - insert_last(ml, m3); - - printMariatheotokos(ml`first, ml`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(ml)); - - mary & popped = try_pop_front(ml); - - verify(validate(ml)); - - printMariatheotokos(ml`first, ml`last, 0); // 2.7, 3.7; 2.7; 3.7; 3.7, 2.7 (modified) - - // observe m1 is now solo - printMariatheotokos(m1, *0p, 0); // 1.7; 1.7; ; - - assert( &popped == &m1 ); -} - -void test__pop_last__fred_mine() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - fred & popped = try_pop_back(flm); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - printYourFreddies(fly`first, fly`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - - // observe f3 is now solo in mine; in yours, it was just traversed - printMyFreddies(f3, *0p, 0); // 3.7; 3.7; ; - - assert( &popped == & f3 ); -} - -void test__pop_last__fred_yours() { - - fred f1 = {1.7}; - fred f2 = {2.7}; - fred f3 = {3.7}; - - dlist(fred, fred.mine) flm; - insert_last(flm, f1); - insert_last(flm, f2); - insert_last(flm, f3); - - dlist(fred, fred.yours) fly; - insert_last(fly, f1); - insert_last(fly, f2); - insert_last(fly, f3); - - printMyFreddies(flm`first, flm`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - printYourFreddies(fly`first, fly`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(fly)); - verify(validate(flm)); - - fred & popped = try_pop_back(fly); - - verify(validate(fly)); - verify(validate(flm)); - - printMyFreddies(flm`first, flm`last, 0); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 (unmodified) - printYourFreddies(fly`first, fly`last, 0); // 1.7, 2.7; 1.7; 2.7; 2.7, 1.7 (modified) - - // observe f3 is now solo in yours; in mine, it was just traversed - printYourFreddies(f3, *0p, 0); // 3.7; 3.7; ; - - assert( &popped == & f3 ); -} - -void test__pop_last__maries() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - dlist(mary) ml; - insert_last(ml, m1); - insert_last(ml, m2); - insert_last(ml, m3); - - printMariatheotokos(ml`first, ml`last, 1); // 1.7, 2.7, 3.7; 1.7; 3.7; 3.7, 2.7, 1.7 - - verify(validate(ml)); - - mary & popped = try_pop_back(ml); - - verify(validate(ml)); - - printMariatheotokos(ml`first, ml`last, 0); // 1.7, 1.7; 1.7; 2.7; 2.7, 1.7 (modified) - - // observe m1 is now solo - printMariatheotokos(m3, *0p, 0); // 3.7; 3.7; ; - - assert( &popped == &m3 ); -} - -//////////////////////////////////////////////////////////// -// -// Section 4g -// -// Test cases of `isEmpty, `hasPrev, `hasNext, -// try_pop_front, try_pop_back, modifications via `elems -// -// Example of call-side user code -// -//////////////////////////////////////////////////////////// - -void test__accessor_cases__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - dlist(mary) ml; assert( ml`isEmpty); - - insert_last(ml, m1); assert(!ml`isEmpty); - insert_last(ml, m2); assert(!ml`isEmpty); - insert_last(ml, m3); assert(!ml`isEmpty); - - mary & m1prev = m1`prev; - mary & m1next = m1`next; - mary & m2prev = m2`prev; - mary & m2next = m2`next; - mary & m3prev = m3`prev; - mary & m3next = m3`next; - - assert (&m1prev == 0p); - assert (&m1next == &m2); - assert (&m2prev == &m1); - assert (&m2next == &m3); - assert (&m3prev == &m2); - assert (&m3next == 0p); - - assert(!m1`hasPrev); - assert( m1`hasNext); - assert( m2`hasPrev); - assert( m2`hasNext); - assert( m3`hasPrev); - assert(!m3`hasNext); - - printf("accessor_cases done\n"); -} - -void test__try_pop__mary() { - - mary m1 = {1.7}; - mary m2 = {2.7}; - mary m3 = {3.7}; - - dlist(mary) ml; - - mary &m1r = *0p; - mary &m2r = *0p; - mary &m3r = *0p; - mary &mxr = *0p; - - // queue, back to front - - assert( ml`isEmpty); - - insert_last(ml, m1); - insert_last(ml, m2); - insert_last(ml, m3); - - &m1r = & try_pop_front(ml); assert(!ml`isEmpty); - &m2r = & try_pop_front(ml); assert(!ml`isEmpty); - &m3r = & try_pop_front(ml); assert( ml`isEmpty); - &mxr = & try_pop_front(ml); assert( ml`isEmpty); - - assert( &m1r == &m1 ); - assert( &m2r == &m2 ); - assert( &m3r == &m3 ); - assert( &mxr == 0p ); - - &m1r = 0p; - &m2r = 0p; - &m3r = 0p; - - // queue, front to back - - assert( ml`isEmpty); - - insert_first(ml, m1); - insert_first(ml, m2); - insert_first(ml, m3); - - &m1r = & try_pop_back(ml); assert(!ml`isEmpty); - &m2r = & try_pop_back(ml); assert(!ml`isEmpty); - &m3r = & try_pop_back(ml); assert( ml`isEmpty); - &mxr = & try_pop_back(ml); assert( ml`isEmpty); - - assert( &m1r == &m1 ); - assert( &m2r == &m2 ); - assert( &m3r == &m3 ); - assert( &mxr == 0p ); - - &m1r = 0p; - &m2r = 0p; - &m3r = 0p; - - // stack at front - - assert( ml`isEmpty); - - insert_first(ml, m1); - insert_first(ml, m2); - insert_first(ml, m3); - - &m3r = & try_pop_front(ml); assert(!ml`isEmpty); - &m2r = & try_pop_front(ml); assert(!ml`isEmpty); - &m1r = & try_pop_front(ml); assert( ml`isEmpty); - &mxr = & try_pop_front(ml); assert( ml`isEmpty); - - assert( &m1r == &m1 ); - assert( &m2r == &m2 ); - assert( &m3r == &m3 ); - assert( &mxr == 0p ); - - &m1r = 0p; - &m2r = 0p; - &m3r = 0p; - - // stack at back - - assert( ml`isEmpty); - - insert_last(ml, m1); - insert_last(ml, m2); - insert_last(ml, m3); - - &m3r = & try_pop_back(ml); assert(!ml`isEmpty); - &m2r = & try_pop_back(ml); assert(!ml`isEmpty); - &m1r = & try_pop_back(ml); assert( ml`isEmpty); - &mxr = & try_pop_back(ml); assert( ml`isEmpty); - - assert( &m1r == &m1 ); - assert( &m2r == &m2 ); - assert( &m3r == &m3 ); - assert( &mxr == 0p ); - - &m1r = 0p; - &m2r = 0p; - &m3r = 0p; - - printf("try_pop cases done\n"); -} - -void test__origin_mutation__mary() { - - mary m1 = {1.7}; - - dlist(mary) ml; - mary & mlorigin = ml`elems; - - // insert before the origin - - insert_before( ml`elems, m1 ); - assert( ! ml`isEmpty ); - - mary & mlfirst = ml`first; - mary & mllast = ml`last; - - assert( &m1 == & mlfirst ); - assert( &m1 == & mllast ); - - // moveNext after last goes back to origin, &vv - - bool canMoveNext = mllast`moveNext; - bool canMovePrev = mlfirst`movePrev; - - assert( ! canMoveNext ); - assert( ! canMovePrev ); - - assert( &mlorigin == & mlfirst ); - assert( &mlorigin == & mllast ); - - printf("origin_mutation cases done\n"); -} - -//////////////////////////////////////////////////////////// -// -// Section 5 -// -// Simple driver with the inter-scario printing -// -//////////////////////////////////////////////////////////// - -int main() { -#if 0 - sout | "~~~~~~~~~~~~~~~~~ Headless List Tests - insert_after ~~~~~~~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 1-i: Modifying Freds on MINE "; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertafter_singleton_on_singleton__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 2-i. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertafter_singleton_on_singleton__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 3-i. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertafter_singleton_on_singleton__mary(); - - sout | ""; - sout | "~~~~~~~~~~~~~~~~ Headless List Tests - insert_before ~~~~~~~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 1-ii: Modifying Freds on MINE "; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertbefore_singleton_on_singleton__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 2-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertbefore_singleton_on_singleton__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 3-ii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertbefore_singleton_on_singleton__mary(); -#endif - sout | ""; - sout | "~~~~~~~~~~~~~~~~~ Headed List Tests - insert_first ~~~~~~~~~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 4-i: Modifying Freds on MINE "; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertfirst_two_on_empty__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 5-i: Modifying Freds on YOURS "; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertfirst_two_on_empty__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 6-i. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertfirst_two_on_empty__mary(); - - sout | ""; - sout | "~~~~~~~~~~~~~~~~~ Headed List Tests - insert_last ~~~~~~~~~~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 4-ii: Modifying Freds on MINE "; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertlast_two_on_empty__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 5-ii: Modifying Freds on YOURS "; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertlast_two_on_empty__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 6-ii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertlast_two_on_empty__mary(); - - sout | ""; - sout | "~~~~~~~~~~~ Element ops on Headed List Tests: after, last ~~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 7-i. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertafter_after_last__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 8-i. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertafter_after_last__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 9-i. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertafter_after_last__mary(); - - sout | ""; - sout | "~~~~~~~~~~ Element ops on Headed List Tests: before, first ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 7-ii. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertbefore_before_first__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 8-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertbefore_before_first__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 9-ii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__insertbefore_before_first__mary(); -#if 0 - - sout | ""; - sout | "~~~~~~~~~~ Element removal tests on Headless List: mid ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 10-i. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_mid__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 11-i. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_mid__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 12-i. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_mid__mary(); - - sout | ""; - sout | "~~~~~~~~~~ Element removal tests on Headless List: at first ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 10-ii. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_first__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 11-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_first__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 12-ii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_first__mary(); - - sout | ""; - sout | "~~~~~~~~~~ Element removal tests on Headless List: at last ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 10-iii. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_last__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 11-iii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_last__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 12-iii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_last__mary(); -#endif - sout | ""; - sout | "~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 13-i. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_head__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 14-i. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_head__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 15-i. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_head__mary(); - - sout | ""; - sout | "~~~~~~~~~~ Element removal tests on Headed List: at last ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 13-ii. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_tail__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 14-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_tail__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 15-ii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_at_tail__mary(); - - sout | ""; - sout | "~~~~~~~~~~ Element removal tests on Headed List: of sole ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 13-iii. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_of_sole__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 14-iii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_of_sole__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 15-iii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__remove_of_sole__mary(); - - sout | ""; - sout | "~~~~~~~~~~ End removal tests on Headed List: First ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 16-i. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__pop_first__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 16-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__pop_first__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 16-iii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__pop_first__maries(); - - sout | ""; - sout | "~~~~~~~~~~ End removal tests on Headed List: Last ~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 17-i. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__pop_last__fred_mine(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 17-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__pop_last__fred_yours(); - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 17-iii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - test__pop_last__maries(); - - sout | ""; - sout | "~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~"; - sout | ""; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 18-i. Modifying Freds on MINE"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Not implmented"; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 18-ii. Modifying Freds on YOURS"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Not implmented"; - - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - sout | "Test 18-iii. Modifying Maries"; - sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; - - test__accessor_cases__mary(); - test__try_pop__mary(); - test__origin_mutation__mary(); - - return 0; -} Index: tests/list/dlist-insert-remove.cfa =================================================================== --- tests/list/dlist-insert-remove.cfa (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ tests/list/dlist-insert-remove.cfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -19,10 +19,12 @@ struct fred { float adatum; - DLISTED_MGD_EXPL_IN(fred, mine) - DLISTED_MGD_EXPL_IN(fred, yours) + inline struct mine { inline dlink(fred); }; + inline struct yours { inline dlink(fred); }; }; - -DLISTED_MGD_EXPL_OUT(fred, mine) -DLISTED_MGD_EXPL_OUT(fred, yours) +P9_EMBEDDED(fred, fred.mine) +P9_EMBEDDED(fred, fred.yours) +P9_EMBEDDED(fred.mine, dlink(fred)) +P9_EMBEDDED(fred.yours, dlink(fred)) + void ?{}(fred &this, float adatum) { @@ -33,8 +35,8 @@ struct mary { float anotherdatum; - DLISTED_MGD_IMPL_IN(mary) + inline dlink(mary); }; -DLISTED_MGD_IMPL_OUT(mary) +P9_EMBEDDED(mary, dlink(mary)) void ?{}(mary &this, float anotherdatum) { @@ -53,17 +55,18 @@ //////////////////////////////////////////////////////////// -void printMyFredsFwd(fred &f) { - while (&f != 0p) { +void printMyFredsFwd(fred & f) { + with( DLINK_VIA( fred, fred.mine ) ) + do { sout | f.adatum; - &f = &f`in_mine`next; - } -} - -void printMyFredsRev(fred &f) { - while (&f != 0p) { + } while (f`moveNext); +} + +void printMyFredsRev(fred & f) { + with( DLINK_VIA( fred, fred.mine ) ) + do { sout | f.adatum; - &f = &f`in_mine`prev; - } -} + } while (f`movePrev); +} + void printMyFreddies(fred &f1, fred &f2, int isBefore) { @@ -73,22 +76,30 @@ sout | "==== fred by MINE after "; } - printMyFredsFwd(f1); sout | '-'; - printMyFredsRev(f1); sout | '-'; - printMyFredsFwd(f2); sout | '-'; - printMyFredsRev(f2); sout | '-'; -} - -void printYourFredsFwd(fred &f) { - while (&f != 0p) { + if (&f1) { + printMyFredsFwd(f1); sout | '-'; + printMyFredsRev(f1); sout | '-'; + } else { + sout | '-'; sout | '-'; + } + if (&f2) { + printMyFredsFwd(f2); sout | '-'; + printMyFredsRev(f2); sout | '-'; + } else { + sout | '-'; sout | '-'; + } +} + +void printYourFredsFwd(fred & f) { + with( DLINK_VIA( fred, fred.yours ) ) + do { sout | f.adatum; - &f = &f`in_yours`next; - } -} - -void printYourFredsRev(fred &f) { - while (&f != 0p) { + } while (f`moveNext); +} + +void printYourFredsRev(fred & f) { + with( DLINK_VIA( fred, fred.yours ) ) + do { sout | f.adatum; - &f = &f`in_yours`prev; - } + } while (f`movePrev); } @@ -99,22 +110,28 @@ sout | "==== fred by YOURS after "; } - printYourFredsFwd(f1); sout | '-'; - printYourFredsRev(f1); sout | '-'; - printYourFredsFwd(f2); sout | '-'; - printYourFredsRev(f2); sout | '-'; + if (&f1) { + printYourFredsFwd(f1); sout | '-'; + printYourFredsRev(f1); sout | '-'; + } else { + sout | '-'; sout | '-'; + } + if (&f2) { + printYourFredsFwd(f2); sout | '-'; + printYourFredsRev(f2); sout | '-'; + } else { + sout | '-'; sout | '-'; + } } void printMariesFwd(mary &m) { - while (&m != 0p) { + do { sout | m.anotherdatum; - &m = &m`next; - } + } while (m`moveNext); } void printMariesRev(mary &m) { - while (&m != 0p) { + do { sout | m.anotherdatum; - &m = &m`prev; - } + } while (m`movePrev); } @@ -125,8 +142,16 @@ sout | "==== mary after "; } - printMariesFwd(m1); sout | '-'; - printMariesRev(m1); sout | '-'; - printMariesFwd(m2); sout | '-'; - printMariesRev(m2); sout | '-'; + if (&m1) { + printMariesFwd(m1); sout | '-'; + printMariesRev(m1); sout | '-'; + } else { + sout | '-'; sout | '-'; + } + if (&m2) { + printMariesFwd(m2); sout | '-'; + printMariesRev(m2); sout | '-'; + } else { + sout | '-'; sout | '-'; + } } @@ -153,5 +178,5 @@ // - from list position #2 moving backward (d) // The expected-output comments are in form a;b;c;d where a::=num,num,num - +#if 0 void test__insertafter_singleton_on_singleton__fred_mine () { fred f1 = {3.14}; @@ -161,5 +186,6 @@ printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - insert_after(f1`in_mine, f2); + diref(fred, fred.mine) f1_mine = f1`from; + insert_after(f1_mine, f2); printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) @@ -174,5 +200,6 @@ printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - insert_after(f1`in_yours, f2); + diref(fred, fred.yours) f1_yours = f1`from; + insert_after(f1_yours, f2); printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) @@ -208,5 +235,6 @@ printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - insert_before(f2`in_mine, f1); + diref(fred, fred.mine) f2_mine = f2`from; + insert_before(f2_mine, f1); printMyFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) @@ -221,5 +249,6 @@ printYourFreddies(f1, f2, 1); // 3.14; 3.14; 0.5; 0.5 - insert_before(f2`in_yours, f1); + diref(fred, fred.yours) f2_yours = f2`from; + insert_before(f2_yours, f1); printMyFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) @@ -237,5 +266,5 @@ printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) } - +#endif //////////////////////////////////////////////////////////// // @@ -250,5 +279,4 @@ // All three tests exercise the case of creating an empty container and // adding two items to it. - void test__insertfirst_two_on_empty__fred_mine() { @@ -256,5 +284,5 @@ fred f2 = {0.5}; - dlist(fred_in_mine, fred) lf; + dlist(fred, fred.mine) lf; verify(validate(lf)); @@ -277,5 +305,5 @@ fred f2 = {0.5}; - dlist(fred_in_yours, fred) lf; + dlist(fred, fred.yours) lf; verify(validate(lf)); @@ -292,5 +320,4 @@ printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) } - void test__insertfirst_two_on_empty__mary() { @@ -298,5 +325,5 @@ mary m2 = {0.5}; - dlist(mary, mary) lm; + dlist(mary) lm; verify(validate(lm)); @@ -325,5 +352,5 @@ fred f2 = {0.5}; - dlist(fred_in_mine, fred) lf; + dlist(fred, fred.mine) lf; verify(validate(lf)); @@ -346,5 +373,5 @@ fred f2 = {0.5}; - dlist(fred_in_yours, fred) lf; + dlist(fred, fred.yours) lf; verify(validate(lf)); @@ -367,5 +394,5 @@ mary m2 = {0.5}; - dlist(mary, mary) lm; + dlist(mary) lm; verify(validate(lm)); @@ -394,17 +421,17 @@ fred f2 = {0.5}; - dlist(fred_in_mine, fred) lf; - - assert(& lf`first == 0p); - assert(& lf`last == 0p); + dlist(fred, fred.mine) lf; + + assert( & lf`first == 0p ); + assert( & lf`last == 0p ); insert_first(lf, f1); - assert(& lf`first == & f1); - assert(& lf`last == & f1); + assert( & lf`first == & f1 ); + assert( & lf`last == & f1 ); verify(validate(lf)); - insert_after(f1`in_mine, f2); + with ( DLINK_VIA(fred, fred.mine) ) insert_after(f1, f2); verify(validate(lf)); @@ -413,6 +440,6 @@ printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - assert(& lf`first == & f1); - assert(& lf`last == & f2); + assert( & lf`first == & f1 ); + assert( & lf`last == & f2 ); } @@ -422,17 +449,17 @@ fred f2 = {0.5}; - dlist(fred_in_yours, fred) lf; - - assert(& lf`first == 0p); - assert(& lf`last == 0p); + dlist(fred, fred.yours) lf; + + assert( & lf`first == 0p ); + assert( & lf`last == 0p ); insert_first(lf, f1); - assert(& lf`first == & f1); - assert(& lf`last == & f1); + assert( & lf`first == & f1 ); + assert( & lf`last == & f1 ); verify(validate(lf)); - insert_after(f1`in_yours, f2); + with ( DLINK_VIA(fred, fred.yours) ) insert_after(f1, f2); verify(validate(lf)); @@ -441,6 +468,6 @@ printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - assert(& lf`first == & f1); - assert(& lf`last == & f2); + assert( & lf`first == & f1 ); + assert( & lf`last == & f2 ); } @@ -450,13 +477,13 @@ mary m2 = {0.5}; - dlist(mary, mary) lm; - - assert(& lm`first == 0p); - assert(& lm`last == 0p); + dlist(mary) lm; + + assert( & lm`first == 0p ); + assert( & lm`last == 0p ); insert_first(lm, m1); - assert(& lm`first == & m1); - assert(& lm`last == & m1); + assert( & lm`first == & m1 ); + assert( & lm`last == & m1 ); verify(validate(lm)); @@ -468,6 +495,6 @@ printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - assert(& lm`first == & m1); - assert(& lm`last == & m2); + assert( & lm`first == & m1 ); + assert( & lm`last == & m2 ); } @@ -487,17 +514,17 @@ fred f2 = {0.5}; - dlist(fred_in_mine, fred) lf; - - assert(& lf`first == 0p); - assert(& lf`last == 0p); + dlist(fred, fred.mine) lf; + + assert( & lf`first == 0p ); + assert( & lf`last == 0p ); insert_last(lf, f2); - assert(& lf`first == & f2); - assert(& lf`last == & f2); + assert( & lf`first == & f2 ); + assert( & lf`last == & f2 ); verify(validate(lf)); - insert_before(f2`in_mine, f1); + with ( DLINK_VIA(fred, fred.mine) ) insert_before(f2, f1); verify(validate(lf)); @@ -506,6 +533,6 @@ printYourFreddies(f1, f2, 0); // 3.14; 3.14; 0.5; 0.5 (unmodified) - assert(& lf`first == & f1); - assert(& lf`last == & f2); + assert( & lf`first == & f1 ); + assert( & lf`last == & f2 ); } @@ -515,17 +542,17 @@ fred f2 = {0.5}; - dlist(fred_in_yours, fred) lf; - - assert(& lf`first == 0p); - assert(& lf`last == 0p); + dlist(fred, fred.yours) lf; + + assert( & lf`first == 0p ); + assert( & lf`last == 0p ); insert_last(lf, f2); - assert(& lf`first == & f2); - assert(& lf`last == & f2); + assert( & lf`first == & f2 ); + assert( & lf`last == & f2 ); verify(validate(lf)); - insert_before(f2`in_yours, f1); + with ( DLINK_VIA(fred, fred.yours) )insert_before(f2, f1); verify(validate(lf)); @@ -534,6 +561,6 @@ printYourFreddies(f1, f2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - assert(& lf`first == & f1); - assert(& lf`last == & f2); + assert( & lf`first == & f1 ); + assert( & lf`last == & f2 ); } @@ -543,13 +570,13 @@ mary m2 = {0.5}; - dlist(mary, mary) lm; - - assert(& lm`first == 0p); - assert(& lm`last == 0p); + dlist(mary) lm; + + assert( & lm`first == 0p ); + assert( & lm`last == 0p ); insert_last(lm, m2); - assert(& lm`first == & m2); - assert(& lm`last == & m2); + assert( & lm`first == & m2 ); + assert( & lm`last == & m2 ); verify(validate(lm)); @@ -561,7 +588,8 @@ printMariatheotokos(m1, m2, 0); // 3.14, 0.5; 3.14; 0.5; 0.5, 3.14 (modified) - assert(& lm`first == & m1); - assert(& lm`last == & m2); -} + assert( & lm`first == & m1 ); + assert( & lm`last == & m2 ); +} +#if 0 //////////////////////////////////////////////////////////// @@ -846,5 +874,5 @@ // //////////////////////////////////////////////////////////// - +#endif void test__remove_at_head__fred_mine() { @@ -853,10 +881,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -869,5 +897,5 @@ verify(validate(flm)); - remove(f1`in_mine); + with( DLINK_VIA(fred, fred.mine) ) remove(f1); verify(validate(fly)); @@ -881,7 +909,8 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f1.$links_mine.next.is_terminator == false); - assert(f1.$links_mine.prev.is_terminator == false); -} + // assert(f1.$links_mine.next.is_terminator == false); + // assert(f1.$links_mine.prev.is_terminator == false); +} + void test__remove_at_head__fred_yours() { @@ -891,10 +920,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -907,5 +936,5 @@ verify(validate(flm)); - remove(f1`in_yours); + with( DLINK_VIA(fred, fred.yours) ) remove(f1); verify(validate(fly)); @@ -919,6 +948,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f1.$links_yours.next.is_terminator == false); - assert(f1.$links_yours.prev.is_terminator == false); + // assert(f1.$links_yours.next.is_terminator == false); + // assert(f1.$links_yours.prev.is_terminator == false); } @@ -929,5 +958,5 @@ mary m3 = {3.7}; - dlist(mary, mary) ml; + dlist(mary) ml; insert_last(ml, m1); insert_last(ml, m2); @@ -948,6 +977,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(m1.$links.next.is_terminator == false); - assert(m1.$links.prev.is_terminator == false); + // assert(m1.$links.next.is_terminator == false); + // assert(m1.$links.prev.is_terminator == false); } @@ -968,10 +997,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -984,5 +1013,5 @@ verify(validate(flm)); - remove(f3`in_mine); + with( DLINK_VIA(fred, fred.mine) ) remove(f3); verify(validate(fly)); @@ -996,6 +1025,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f3.$links_mine.next.is_terminator == false); - assert(f3.$links_mine.prev.is_terminator == false); + // assert(f3.$links_mine.next.is_terminator == false); + // assert(f3.$links_mine.prev.is_terminator == false); } @@ -1006,10 +1035,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -1022,5 +1051,5 @@ verify(validate(flm)); - remove(f3`in_yours); + with( DLINK_VIA(fred, fred.yours) ) remove(f3); verify(validate(fly)); @@ -1034,6 +1063,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f3.$links_yours.next.is_terminator == false); - assert(f3.$links_yours.prev.is_terminator == false); + // assert(f3.$links_yours.next.is_terminator == false); + // assert(f3.$links_yours.prev.is_terminator == false); } @@ -1044,5 +1073,5 @@ mary m3 = {3.7}; - dlist(mary, mary) ml; + dlist(mary) ml; insert_last(ml, m1); insert_last(ml, m2); @@ -1063,6 +1092,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(m3.$links.next.is_terminator == false); - assert(m3.$links.prev.is_terminator == false); + // assert(m3.$links.next.is_terminator == false); + // assert(m3.$links.prev.is_terminator == false); } @@ -1081,8 +1110,8 @@ fred f = {0.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f); @@ -1093,11 +1122,11 @@ verify(validate(flm)); - remove(f`in_mine); - - verify(validate(fly)); - verify(validate(flm)); - - assert(& flm`first == 0p); - assert(& flm`last == 0p); + with( DLINK_VIA(fred, fred.mine) ) remove(f); + + verify(validate(fly)); + verify(validate(flm)); + + assert( & flm`first == 0p ); + assert( & flm`last == 0p ); printYourFreddies(fly`first, fly`last, 0); // 0.7; 0.7; 0.7; 0.7 (unmodified) @@ -1107,6 +1136,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f.$links_mine.next.is_terminator == false); - assert(f.$links_mine.prev.is_terminator == false); + // assert(f.$links_mine.next.is_terminator == false); + // assert(f.$links_mine.prev.is_terminator == false); insert_last(flm, f); @@ -1120,8 +1149,8 @@ fred f = {0.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f); @@ -1132,11 +1161,11 @@ verify(validate(flm)); - remove(f`in_yours); - - verify(validate(fly)); - verify(validate(flm)); - - assert(& fly`first == 0p); - assert(& fly`last == 0p); + with( DLINK_VIA(fred, fred.yours) ) remove(f); + + verify(validate(fly)); + verify(validate(flm)); + + assert( & fly`first == 0p ); + assert( & fly`last == 0p ); printYourFreddies(flm`first, flm`last, 0); // 0.7; 0.7; 0.7; 0.7 (unmodified) @@ -1146,6 +1175,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(f.$links_yours.next.is_terminator == false); - assert(f.$links_yours.prev.is_terminator == false); + // assert(f.$links_yours.next.is_terminator == false); + // assert(f.$links_yours.prev.is_terminator == false); insert_last(fly, f); @@ -1159,5 +1188,5 @@ mary m = {0.7}; - dlist(mary, mary) ml; + dlist(mary) ml; insert_last(ml, m); @@ -1170,6 +1199,6 @@ verify(validate(ml)); - assert(& ml`first == 0p); - assert(& ml`last == 0p); + assert( & ml`first == 0p ); + assert( & ml`last == 0p ); // observe f is solo in mine (now unlisted); in yours, it was just traversed @@ -1177,6 +1206,6 @@ // TODO: decide on appropriate ovservable outcome (is_listed?) and its itended semantics - assert(m.$links.next.is_terminator == false); - assert(m.$links.prev.is_terminator == false); + // assert(m.$links.next.is_terminator == false); + // assert(m.$links.prev.is_terminator == false); insert_last(ml, m); @@ -1203,10 +1232,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -1219,5 +1248,5 @@ verify(validate(flm)); - fred & popped = pop_first(flm); + fred & popped = try_pop_front(flm); verify(validate(fly)); @@ -1239,10 +1268,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -1255,5 +1284,5 @@ verify(validate(flm)); - fred & popped = pop_first(fly); + fred & popped = try_pop_front(fly); verify(validate(fly)); @@ -1275,5 +1304,5 @@ mary m3 = {3.7}; - dlist(mary, mary) ml; + dlist(mary) ml; insert_last(ml, m1); insert_last(ml, m2); @@ -1284,5 +1313,5 @@ verify(validate(ml)); - mary & popped = pop_first(ml); + mary & popped = try_pop_front(ml); verify(validate(ml)); @@ -1302,10 +1331,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -1318,5 +1347,5 @@ verify(validate(flm)); - fred & popped = pop_last(flm); + fred & popped = try_pop_back(flm); verify(validate(fly)); @@ -1338,10 +1367,10 @@ fred f3 = {3.7}; - dlist(fred_in_mine, fred) flm; + dlist(fred, fred.mine) flm; insert_last(flm, f1); insert_last(flm, f2); insert_last(flm, f3); - dlist(fred_in_yours, fred) fly; + dlist(fred, fred.yours) fly; insert_last(fly, f1); insert_last(fly, f2); @@ -1354,5 +1383,5 @@ verify(validate(flm)); - fred & popped = pop_last(fly); + fred & popped = try_pop_back(fly); verify(validate(fly)); @@ -1374,5 +1403,5 @@ mary m3 = {3.7}; - dlist(mary, mary) ml; + dlist(mary) ml; insert_last(ml, m1); insert_last(ml, m2); @@ -1383,5 +1412,5 @@ verify(validate(ml)); - mary & popped = pop_last(ml); + mary & popped = try_pop_back(ml); verify(validate(ml)); @@ -1397,4 +1426,187 @@ //////////////////////////////////////////////////////////// // +// Section 4g +// +// Test cases of `isEmpty, `hasPrev, `hasNext, +// try_pop_front, try_pop_back, modifications via `elems +// +// Example of call-side user code +// +//////////////////////////////////////////////////////////// + +void test__accessor_cases__mary() { + + mary m1 = {1.7}; + mary m2 = {2.7}; + mary m3 = {3.7}; + + dlist(mary) ml; assert( ml`isEmpty); + + insert_last(ml, m1); assert(!ml`isEmpty); + insert_last(ml, m2); assert(!ml`isEmpty); + insert_last(ml, m3); assert(!ml`isEmpty); + + mary & m1prev = m1`prev; + mary & m1next = m1`next; + mary & m2prev = m2`prev; + mary & m2next = m2`next; + mary & m3prev = m3`prev; + mary & m3next = m3`next; + + assert (&m1prev == 0p); + assert (&m1next == &m2); + assert (&m2prev == &m1); + assert (&m2next == &m3); + assert (&m3prev == &m2); + assert (&m3next == 0p); + + assert(!m1`hasPrev); + assert( m1`hasNext); + assert( m2`hasPrev); + assert( m2`hasNext); + assert( m3`hasPrev); + assert(!m3`hasNext); + + printf("accessor_cases done\n"); +} + +void test__try_pop__mary() { + + mary m1 = {1.7}; + mary m2 = {2.7}; + mary m3 = {3.7}; + + dlist(mary) ml; + + mary &m1r = *0p; + mary &m2r = *0p; + mary &m3r = *0p; + mary &mxr = *0p; + + // queue, back to front + + assert( ml`isEmpty); + + insert_last(ml, m1); + insert_last(ml, m2); + insert_last(ml, m3); + + &m1r = & try_pop_front(ml); assert(!ml`isEmpty); + &m2r = & try_pop_front(ml); assert(!ml`isEmpty); + &m3r = & try_pop_front(ml); assert( ml`isEmpty); + &mxr = & try_pop_front(ml); assert( ml`isEmpty); + + assert( &m1r == &m1 ); + assert( &m2r == &m2 ); + assert( &m3r == &m3 ); + assert( &mxr == 0p ); + + &m1r = 0p; + &m2r = 0p; + &m3r = 0p; + + // queue, front to back + + assert( ml`isEmpty); + + insert_first(ml, m1); + insert_first(ml, m2); + insert_first(ml, m3); + + &m1r = & try_pop_back(ml); assert(!ml`isEmpty); + &m2r = & try_pop_back(ml); assert(!ml`isEmpty); + &m3r = & try_pop_back(ml); assert( ml`isEmpty); + &mxr = & try_pop_back(ml); assert( ml`isEmpty); + + assert( &m1r == &m1 ); + assert( &m2r == &m2 ); + assert( &m3r == &m3 ); + assert( &mxr == 0p ); + + &m1r = 0p; + &m2r = 0p; + &m3r = 0p; + + // stack at front + + assert( ml`isEmpty); + + insert_first(ml, m1); + insert_first(ml, m2); + insert_first(ml, m3); + + &m3r = & try_pop_front(ml); assert(!ml`isEmpty); + &m2r = & try_pop_front(ml); assert(!ml`isEmpty); + &m1r = & try_pop_front(ml); assert( ml`isEmpty); + &mxr = & try_pop_front(ml); assert( ml`isEmpty); + + assert( &m1r == &m1 ); + assert( &m2r == &m2 ); + assert( &m3r == &m3 ); + assert( &mxr == 0p ); + + &m1r = 0p; + &m2r = 0p; + &m3r = 0p; + + // stack at back + + assert( ml`isEmpty); + + insert_last(ml, m1); + insert_last(ml, m2); + insert_last(ml, m3); + + &m3r = & try_pop_back(ml); assert(!ml`isEmpty); + &m2r = & try_pop_back(ml); assert(!ml`isEmpty); + &m1r = & try_pop_back(ml); assert( ml`isEmpty); + &mxr = & try_pop_back(ml); assert( ml`isEmpty); + + assert( &m1r == &m1 ); + assert( &m2r == &m2 ); + assert( &m3r == &m3 ); + assert( &mxr == 0p ); + + &m1r = 0p; + &m2r = 0p; + &m3r = 0p; + + printf("try_pop cases done\n"); +} + +void test__origin_mutation__mary() { + + mary m1 = {1.7}; + + dlist(mary) ml; + mary & mlorigin = ml`elems; + + // insert before the origin + + insert_before( ml`elems, m1 ); + assert( ! ml`isEmpty ); + + mary & mlfirst = ml`first; + mary & mllast = ml`last; + + assert( &m1 == & mlfirst ); + assert( &m1 == & mllast ); + + // moveNext after last goes back to origin, &vv + + bool canMoveNext = mllast`moveNext; + bool canMovePrev = mlfirst`movePrev; + + assert( ! canMoveNext ); + assert( ! canMovePrev ); + + assert( &mlorigin == & mlfirst ); + assert( &mlorigin == & mllast ); + + printf("origin_mutation cases done\n"); +} + +//////////////////////////////////////////////////////////// +// // Section 5 // @@ -1404,5 +1616,5 @@ int main() { - +#if 0 sout | "~~~~~~~~~~~~~~~~~ Headless List Tests - insert_after ~~~~~~~~~~~~~~~~"; sout | ""; @@ -1441,5 +1653,5 @@ sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; test__insertbefore_singleton_on_singleton__mary(); - +#endif sout | ""; sout | "~~~~~~~~~~~~~~~~~ Headed List Tests - insert_first ~~~~~~~~~~~~~~~~~~"; @@ -1517,4 +1729,5 @@ sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; test__insertbefore_before_first__mary(); +#if 0 sout | ""; @@ -1574,5 +1787,5 @@ sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; test__remove_at_last__mary(); - +#endif sout | ""; sout | "~~~~~~~~~~ Element removal tests on Headed List: at first ~~~~~~~~~~"; @@ -1670,4 +1883,26 @@ test__pop_last__maries(); + sout | ""; + sout | "~~~~~~~~~~~~~~~~~~~ Ease-of-access cases ~~~~~~~~~~~~~~~~~~"; + sout | ""; + + sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; + sout | "Test 18-i. Modifying Freds on MINE"; + sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; + sout | "Not implmented"; + + sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; + sout | "Test 18-ii. Modifying Freds on YOURS"; + sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; + sout | "Not implmented"; + + sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; + sout | "Test 18-iii. Modifying Maries"; + sout | "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"; + + test__accessor_cases__mary(); + test__try_pop__mary(); + test__origin_mutation__mary(); + return 0; } Index: tests/zombies/linked-list-perf/experiment.koad =================================================================== --- tests/zombies/linked-list-perf/experiment.koad (revision 67b421c05a280cde8747b61757656154a9f530c9) +++ tests/zombies/linked-list-perf/experiment.koad (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -49,23 +49,23 @@ #elif defined IMPL_CFA_MIKE_OLD + #include "mike-old.hfa" + struct S { + int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD + DLISTED_MGD_IMPL_IN(S) + }; + DLISTED_MGD_IMPL_OUT(S) + +#elif defined IMPL_CFA_MIKE_POC + + #include "mike-proto-list.hfa" + struct S { + int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD + inline dlink(S); + }; + P9_EMBEDDED( S, dlink(S) ) + +#elif defined IMPL_CFA_MIKE_NEW + #include - struct S { - int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD - DLISTED_MGD_IMPL_IN(S) - }; - DLISTED_MGD_IMPL_OUT(S) - -#elif defined IMPL_CFA_MIKE_POC - - #include "mike-proto-list.hfa" - struct S { - int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD - inline dlink(S); - }; - P9_EMBEDDED( S, dlink(S) ) - -#elif defined IMPL_CFA_MIKE_NEW - - #include struct S { int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD Index: tests/zombies/linked-list-perf/mike-old.hfa =================================================================== --- tests/zombies/linked-list-perf/mike-old.hfa (revision 69914cbc38918b375971f7accca59529f62f2d08) +++ tests/zombies/linked-list-perf/mike-old.hfa (revision 69914cbc38918b375971f7accca59529f62f2d08) @@ -0,0 +1,351 @@ +// +// Cforall Version 1.0.0 Copyright (C) 2020 University of Waterloo +// +// The contents of this file are covered under the licence agreement in the +// file "LICENCE" distributed with Cforall. +// +// list -- lets a user-defined stuct form intrusive linked lists +// +// Author : Michael Brooks +// Created On : Wed Apr 22 18:00:00 2020 +// Last Modified By : Michael Brooks +// Last Modified On : Wed Apr 22 18:00:00 2020 +// Update Count : 1 +// + +#pragma once + +#include + +#define __DLISTED_MGD_COMMON(ELEM, NODE, LINKS_FLD) \ +static inline ELEM& $tempcv_n2e(NODE &node) { \ + return node; \ +} \ +\ +static inline NODE& $tempcv_e2n(ELEM &node) { \ + return ( NODE & ) node; \ +} \ +\ +static inline ELEM & ?`prev(NODE &node) { \ + $dlinks(ELEM) & ls = node.LINKS_FLD; \ + $mgd_link(ELEM) * l = &ls.prev; \ + ELEM * e = l->elem; \ + return *e; \ +} \ +\ +static inline ELEM & ?`next(NODE &node) { \ + $dlinks(ELEM) & ls = node.LINKS_FLD; \ + $mgd_link(ELEM) * l = &ls.next; \ + ELEM * e = l->elem; \ + return *e; \ +} \ +\ +static inline $mgd_link(ELEM) & $prev_link(NODE &node) { \ + $dlinks(ELEM) & ls = node.LINKS_FLD; \ + $mgd_link(ELEM) * l = &ls.prev; \ + return *l; \ +} \ +\ +static inline $mgd_link(ELEM) & $next_link(NODE &node) { \ + $dlinks(ELEM) & ls = node.LINKS_FLD; \ + $mgd_link(ELEM) * l = &ls.next; \ + return *l; \ +} + +#define __DLISTED_MGD_JUSTEXPL(STRUCT, IN_THELIST, STRUCT_IN_THELIST) \ +struct STRUCT_IN_THELIST { \ + inline STRUCT; \ +}; \ +\ +void ?{}(STRUCT_IN_THELIST &) = void; \ +\ +static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \ + return (STRUCT_IN_THELIST&)this; \ +} + +#define __DLISTED_MGD_JUSTIMPL(STRUCT) + +forall( tE & ) { + struct $mgd_link { + tE *elem; + void *terminator; + _Bool is_terminator; + // will collapse to single pointer with tag bit + }; + static inline void ?{}( $mgd_link(tE) &this, tE* elem ) { + (this.elem){ elem }; + (this.terminator){ 0p }; + (this.is_terminator){ 0 }; + } + static inline void ?{}( $mgd_link(tE) &this, void * terminator ) { + (this.elem){ 0p }; + (this.terminator){ terminator }; + (this.is_terminator){ 1 }; + } + static inline void ?=?( $mgd_link(tE) &this, tE* elem ) { + this.elem = elem ; + this.terminator = 0p; + this.is_terminator = 0; + } + static inline void ?=?( $mgd_link(tE) &this, void * terminator ) { + this.elem = 0p; + this.terminator = terminator; + this.is_terminator = 1; + } + struct $dlinks { + // containing item is not listed + // iff + // links have (elem == 0p && terminator == 0p) + $mgd_link(tE) next; + $mgd_link(tE) prev; + }; + static inline void ?{}( $dlinks(tE) &this ) { + (this.next){ (tE *)0p }; + (this.prev){ (tE *)0p }; + } +} + +#define DLISTED_MGD_EXPL_IN(STRUCT, LIST_SUF) \ + $dlinks(STRUCT) $links_ ## LIST_SUF; + +#define DLISTED_MGD_EXPL_OUT(STRUCT, LIST_SUF) \ + __DLISTED_MGD_JUSTEXPL(STRUCT, in_##LIST_SUF, STRUCT ## _in_ ## LIST_SUF) \ + __DLISTED_MGD_COMMON(STRUCT, STRUCT##_in_##LIST_SUF, $links_ ## LIST_SUF) + +#define DLISTED_MGD_IMPL_IN(STRUCT) \ + $dlinks(STRUCT) $links; + +#define DLISTED_MGD_IMPL_OUT(STRUCT) \ + __DLISTED_MGD_JUSTIMPL(STRUCT) \ + __DLISTED_MGD_COMMON(STRUCT, STRUCT, $links) + +trait $dlistable(Tnode &, Telem &) { + $mgd_link(Telem) & $prev_link(Tnode &); + $mgd_link(Telem) & $next_link(Tnode &); + Telem& $tempcv_n2e(Tnode &); + Tnode& $tempcv_e2n(Telem &); + + Telem& ?`next(Tnode &); + Telem& ?`prev(Tnode &); +}; + +forall (Tnode &, Telem & | $dlistable(Tnode, Telem)) { + + // implemented as a sentinel item in an underlying cicrular list + // theList.$links.next is first + // theList.$links.prev is last + // note this allocation preserves prev-next composition as an identity + struct dlist { + $dlinks(Telem) $links; + }; + + // an empty dlist + // links refer to self, making a tight circle + static inline void ?{}( dlist(Tnode, Telem) & this ) { + $mgd_link(Telem) selfRef = (void *) &this; + ( this.$links ) { selfRef, selfRef }; + } + + static inline Telem & ?`first( dlist(Tnode, Telem) &l ) { + return * l.$links.next.elem; + } + + static inline Telem & ?`last( dlist(Tnode, Telem) &l ) { + return * l.$links.prev.elem; + } + + #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) + static bool $validate_fwd( dlist(Tnode, Telem) & this ) { + Tnode * it = & $tempcv_e2n( this`first ); + if (!it) return (& this`last == 0p); + + while( $next_link(*it).elem ) { + it = & $tempcv_e2n( * $next_link(*it).elem ); + } + + return ( it == & $tempcv_e2n( this`last ) ) && + ( $next_link(*it).is_terminator ) && + ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this ); + } + static bool $validate_rev( dlist(Tnode, Telem) & this ) { + Tnode * it = & $tempcv_e2n( this`last ); + if (!it) return (& this`first == 0p); + + while( $prev_link(*it).elem ) { + it = & $tempcv_e2n( * $prev_link(*it).elem ); + } + + return ( it == & $tempcv_e2n( this`first ) ) && + ( $prev_link(*it).is_terminator ) && + ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this ); + } + static bool validate( dlist(Tnode, Telem) & this ) { + return $validate_fwd(this) && $validate_rev(this); + } + #endif + + static inline void insert_after(Tnode &list_pos, Telem &to_insert) { + verify (&list_pos != 0p); + verify (&to_insert != 0p); + Tnode &singleton_to_insert = $tempcv_e2n(to_insert); + verify($prev_link(singleton_to_insert).elem == 0p); + verify($next_link(singleton_to_insert).elem == 0p); + $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos); + $next_link(singleton_to_insert) = $next_link(list_pos); + if ($next_link(list_pos).is_terminator) { + dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator; + $dlinks(Telem) *list_links = & list->$links; + $mgd_link(Telem) *list_last = & list_links->prev; + *list_last = &to_insert; + } else { + Telem *list_pos_next = $next_link(list_pos).elem; + if (list_pos_next) { + Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next); + $prev_link(lpn_inlist) = &to_insert; + } + } + $next_link(list_pos) = &to_insert; + } + + static inline void insert_before(Tnode &list_pos, Telem &to_insert) { + verify (&list_pos != 0p); + verify (&to_insert != 0p); + Tnode &singleton_to_insert = $tempcv_e2n(to_insert); + verify($prev_link(singleton_to_insert).elem == 0p); + verify($next_link(singleton_to_insert).elem == 0p); + $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos); + $prev_link(singleton_to_insert) = $prev_link(list_pos); + if ($prev_link(list_pos).is_terminator) { + dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator; + $dlinks(Telem) *list_links = & list->$links; + $mgd_link(Telem) *list_first = & list_links->next; + *list_first = &to_insert; + } else { + Telem *list_pos_prev = $prev_link(list_pos).elem; + if (list_pos_prev) { + Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev); + $next_link(lpp_inlist) = &to_insert; + } + } + $prev_link(list_pos) = &to_insert; + } + + static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) { + verify (&list != 0p); + verify (&to_insert != 0p); + Tnode &singleton_to_insert = $tempcv_e2n(to_insert); + verify($prev_link(singleton_to_insert).elem == 0p); + verify($next_link(singleton_to_insert).elem == 0p); + + $prev_link(singleton_to_insert) = (void*) &list; + $next_link(singleton_to_insert) = list.$links.next; + + $dlinks(Telem) *listLinks = & list.$links; + if (listLinks->next.is_terminator) { + $mgd_link(Telem) * listPrevReference = & listLinks->prev; + *listPrevReference = &to_insert; + } else { + Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem); + $prev_link(next_inlist) = &to_insert; + } + $mgd_link(Telem) * listNextReference = & listLinks->next; + *listNextReference = &to_insert; + } + + static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) { + verify (&list != 0p); + verify (&to_insert != 0p); + Tnode &singleton_to_insert = $tempcv_e2n(to_insert); + verify($next_link(singleton_to_insert).elem == 0p); + verify($prev_link(singleton_to_insert).elem == 0p); + + $next_link(singleton_to_insert) = (void*) &list; + $prev_link(singleton_to_insert) = list.$links.prev; + + $dlinks(Telem) *listLinks = & list.$links; + if (listLinks->prev.is_terminator) { + $mgd_link(Telem) * listNextReference = & listLinks->next; + *listNextReference = &to_insert; + } else { + Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem); + $next_link(prev_inlist) = &to_insert; + } + $mgd_link(Telem) * listPrevReference = & listLinks->prev; + *listPrevReference = &to_insert; + } + + static inline void remove(Tnode &list_pos) { + verify( &list_pos != 0p ); + + $mgd_link(Telem) &incoming_from_prev = *0p; + $mgd_link(Telem) &incoming_from_next = *0p; + + if ( $prev_link(list_pos).is_terminator ) { + dlist(Tnode, Telem) * tgt_before = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator; + $dlinks(Telem) * links_before = & tgt_before->$links; + &incoming_from_prev = & links_before->next; + } else if ($prev_link(list_pos).elem) { + Telem * tgt_before = $prev_link(list_pos).elem; + Tnode & list_pos_before = $tempcv_e2n(*tgt_before); + &incoming_from_prev = & $next_link(list_pos_before); + } + + if ( $next_link(list_pos).is_terminator ) { + dlist(Tnode, Telem) * tgt_after = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator; + $dlinks(Telem) * links_after = & tgt_after->$links; + &incoming_from_next = & links_after->prev; + } else if ($next_link(list_pos).elem) { + Telem * tgt_after = $next_link(list_pos).elem; + Tnode & list_pos_after = $tempcv_e2n(*tgt_after ); + &incoming_from_next = & $prev_link(list_pos_after ); + } + + if (& incoming_from_prev) { + incoming_from_prev = $next_link(list_pos); + } + if (& incoming_from_next) { + incoming_from_next = $prev_link(list_pos); + } + + $next_link(list_pos) = (Telem*) 0p; + $prev_link(list_pos) = (Telem*) 0p; + } + + static inline bool ?`is_empty(dlist(Tnode, Telem) &list) { + verify( &list != 0p ); + $dlinks(Telem) *listLinks = & list.$links; + if (listLinks->next.is_terminator) { + verify(listLinks->prev.is_terminator); + verify(listLinks->next.terminator); + verify(listLinks->prev.terminator); + return true; + } else { + verify(!listLinks->prev.is_terminator); + verify(listLinks->next.elem); + verify(listLinks->prev.elem); + return false; + } + } + + static inline Telem & pop_first(dlist(Tnode, Telem) &list) { + verify( &list != 0p ); + verify( !list`is_empty ); + $dlinks(Telem) *listLinks = & list.$links; + Telem & first = *listLinks->next.elem; + Tnode & list_pos_first = $tempcv_e2n( first ); + remove(list_pos_first); + return first; + } + + static inline Telem & pop_last(dlist(Tnode, Telem) &list) { + verify( &list != 0p ); + verify( !list`is_empty ); + $dlinks(Telem) *listLinks = & list.$links; + Telem & last = *listLinks->prev.elem; + Tnode & list_pos_last = $tempcv_e2n( last ); + remove(list_pos_last); + return last; + } + +} +