Index: libcfa/src/Makefile.am =================================================================== --- libcfa/src/Makefile.am (revision 4026d1be509b38f63b3b5012c65fc745d897add0) +++ libcfa/src/Makefile.am (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -59,4 +59,5 @@ concurrency/iofwd.hfa \ containers/list.hfa \ + containers/list2.hfa \ containers/queueLockFree.hfa \ containers/stackLockFree.hfa \ Index: libcfa/src/concurrency/ready_queue.cfa =================================================================== --- libcfa/src/concurrency/ready_queue.cfa (revision 4026d1be509b38f63b3b5012c65fc745d897add0) +++ libcfa/src/concurrency/ready_queue.cfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -398,13 +398,13 @@ if(proc->rdq.target == -1u) { - proc->rdq.target = __tls_rand() % lanes.count; - unsigned it1 = proc->rdq.itr; - unsigned it2 = proc->rdq.itr + 1; - unsigned idx1 = proc->rdq.id + (it1 % READYQ_SHARD_FACTOR); - unsigned idx2 = proc->rdq.id + (it2 % READYQ_SHARD_FACTOR); + _Static_assert(READYQ_SHARD_FACTOR == 2); + unsigned idx1 = proc->rdq.id + 0; + unsigned idx2 = proc->rdq.id + 1; unsigned long long tsc1 = ts(lanes.data[idx1]); unsigned long long tsc2 = ts(lanes.data[idx2]); - proc->rdq.cutoff = min(tsc1, tsc2); - if(proc->rdq.cutoff == 0) proc->rdq.cutoff = -1ull; + proc->rdq.target = __tls_rand() % lanes.count; + + // WARNING: std::min is polymorphic and therefore causes 500% slowdown instead of the expected 2% + proc->rdq.cutoff = tsc1 < tsc2 ? tsc1 : tsc2; } else { @@ -418,5 +418,5 @@ for(READYQ_SHARD_FACTOR) { - unsigned i = proc->rdq.id + (--proc->rdq.itr % READYQ_SHARD_FACTOR); + unsigned i = proc->rdq.id + (proc->rdq.itr++ % READYQ_SHARD_FACTOR); if($thread * t = try_pop(cltr, i __STATS(, __tls_stats()->ready.pop.local))) return t; } @@ -469,5 +469,6 @@ // Actually pop the list struct $thread * thrd; - thrd = pop(lane); + unsigned long long tsv; + [thrd, tsv] = pop(lane); /* paranoid */ verify(thrd); @@ -481,5 +482,5 @@ #if defined(USE_WORK_STEALING) - lanes.tscs[w].tv = thrd->link.ts; + lanes.tscs[w].tv = tsv; #endif @@ -663,5 +664,6 @@ while(!is_empty(lanes.data[idx])) { struct $thread * thrd; - thrd = pop(lanes.data[idx]); + unsigned long long _; + [thrd, _] = pop(lanes.data[idx]); push(cltr, thrd); Index: libcfa/src/concurrency/ready_subqueue.hfa =================================================================== --- libcfa/src/concurrency/ready_subqueue.hfa (revision 4026d1be509b38f63b3b5012c65fc745d897add0) +++ libcfa/src/concurrency/ready_subqueue.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -53,5 +53,5 @@ // Push a thread onto this lane // returns true of lane was empty before push, false otherwise -void push( __intrusive_lane_t & this, $thread * node ) { +static inline void push( __intrusive_lane_t & this, $thread * node ) { /* paranoid */ verify( node->link.next == 0p ); /* paranoid */ verify( node->link.ts == 0 ); @@ -77,9 +77,10 @@ // returns popped // returns true of lane was empty before push, false otherwise -$thread * pop( __intrusive_lane_t & this ) { +static inline [* $thread, unsigned long long] pop( __intrusive_lane_t & this ) { /* paranoid */ verify( this.anchor.next != 0p ); /* paranoid */ verify( this.anchor.ts != 0 ); // Get the relevant nodes locally + unsigned long long ts = this.anchor.ts; $thread * node = this.anchor.next; this.anchor.next = node->link.next; @@ -94,5 +95,5 @@ /* paranoid */ verify( node->link.next == 0p ); /* paranoid */ verify( node->link.ts == 0 ); - return node; + return [node, ts]; } Index: libcfa/src/containers/list2.hfa =================================================================== --- libcfa/src/containers/list2.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ libcfa/src/containers/list2.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,305 @@ +// +// 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( T & ) struct tag {}; +#define ttag(T) ((tag(T)){}) +#define ztag(n) ttag(Z(n)) + +extern "C" { + void * memset ( void * ptr, int value, size_t num ); +} + +trait embedded( tOuter &, tInner & ) { + tInner & ?`inner( tOuter & ); +}; + +// embedded is reflexive +forall( tX & ) +static inline tX & ?`inner( tX & this ) { return this; } + +// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance +#define P9_EMBEDDED( tOuter, tInner ) \ + static inline tInner & ?`inner( tOuter & this ) { return this; } + + + + +#define ORIGIN_TAG_BITNO 63 +#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) + +// #define ORIGIN_TAG_SET(p) (p) +// #define ORIGIN_TAG_CLEAR(p) (p) +// #define ORIGIN_TAG_QUERY(p) (0) + + +forall( tE & ) { + + struct dlink{ + tE *next; + tE *prev; + }; + + static inline void ?{}( dlink(tE) & this ) { + this.next = 0p; + this.prev = 0p; + } + + forall( tLinks & = tE ) { + + struct dlist { + inline dlink(tE); + }; + + struct diref { + inline tE &; + }; + } + + forall( tLinks & = tE | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) { + static inline tE * $get_list_origin_addr( dlist(tE, tLinks) & lst ) { + dlink(tE) & link_from_null = ( * (tE *) 0p )`inner`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 } ; + } + + // redundant + // void ?{}( diref(tE, tLinks) & this, tE & target ) { + // tE && ref = this; + // &ref = ⌖ + // } + } + +} + + +forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) { + + static inline void insert_after(diref(tE, tLinks) list_pos, tE &to_insert) { + verify (&list_pos != 0p); + verify (&to_insert != 0p); + dlink(tE) & linkToInsert = to_insert`inner`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 ); + tE & after_raw = * (list_pos_elem`inner`inner).next; + tE & after_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + linkToInsert.prev = & list_pos_raw; + linkToInsert.next = & after_raw; + (after_elem`inner`inner).prev = &to_insert; + (list_pos_elem`inner`inner).next = &to_insert; + } + + static inline void insert_before(diref(tE, tLinks) list_pos, tE &to_insert) { + verify (&list_pos != 0p); + verify (&to_insert != 0p); + dlink(tE) & linkToInsert = to_insert`inner`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 ); + tE & before_raw = * (list_pos_elem`inner`inner).prev; + tE & before_elem = * (tE *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + linkToInsert.next = & list_pos_raw; + linkToInsert.prev = & before_raw; + (before_elem`inner`inner).next = &to_insert; + (list_pos_elem`inner`inner).prev = &to_insert; + } + + static inline void doRemove( + dlink(tE) & this_links, dlink(tE) & before_links, dlink(tE) & after_links, + tE & before_target, tE & after_target ) { + + before_links.next = &after_target; + after_links.prev = &before_target; + + asm( "" : : : "memory" ); + + this_links.prev = 0p; + this_links.next = 0p; + } + + static inline tE & remove(diref(tE, tLinks) 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`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`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`inner; + + doRemove(list_pos_links, before_links, after_links, before_raw, after_raw); + + return list_pos_elem; + } +/* + static inline tE & remove(diref(tE, tLinks) 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`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`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`inner; + before_links.next = &after_raw; + after_links.prev = &before_raw; +asm( "" : : : "memory" ); + list_pos_links.prev = 0p; + list_pos_links.next = 0p; + return list_pos_elem; + } +*/ + static inline diref(tE, tLinks) ?`first( dlist(tE, tLinks) &lst ) { + tE * firstPtr = lst.next; + if (ORIGIN_TAG_QUERY((size_t)firstPtr)) firstPtr = 0p; + diref(tE, tLinks) ret = { *firstPtr }; + return ret; + } + static inline diref(tE, tLinks) ?`last ( dlist(tE, tLinks) &lst ) { + tE * lastPtr = lst.prev; + if (ORIGIN_TAG_QUERY((size_t)lastPtr)) lastPtr = 0p; + diref(tE, tLinks) ret = { *lastPtr }; + return ret; + } + + static inline int ?!=?( const diref(tE, tLinks) & list_pos, zero_t ) { + tE & list_pos_elem = list_pos; + if (ORIGIN_TAG_QUERY((size_t) & list_pos_elem)) return 0; + return & list_pos_elem != 0p; + } + + static inline int DUMB_COMPARE( diref(tE, tLinks) list_pos, tE * elem ) { + tE & signifiedLhs = list_pos; + return &signifiedLhs == elem; + } + + static inline diref(tE, tLinks) ?`from( tE & elem ) { + diref(tE, tLinks) ret = { elem }; + return ret; + } + + static inline diref(tE, tLinks) ?`elems( dlist(tE, tLinks) & lst ) { + tE * origin = $get_list_origin_addr( lst ); + diref(tE, tLinks) ret = { *origin }; + return ret; + } + + static inline bool ?`moveNext( diref(tE, tLinks) & refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + &ref_inner = oldReferent`inner`inner.next; + return &ref_inner != 0p && + ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + + static inline bool ?`movePrev( diref(tE, tLinks) & refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + &ref_inner = oldReferent`inner`inner.prev; + return &ref_inner != 0p && + ! ORIGIN_TAG_QUERY( (size_t) & ref_inner ); + } + + 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); + } + + + #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 ( diref(tE, tLinks) 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 ( diref(tE, tLinks) 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 + +} + +forall( tE & | embedded( tE, dlink(tE) ) ) { + static inline void insert_after(tE & list_pos, tE &to_insert ) { + diref(tE, tE) list_pos_ref = list_pos`from; + insert_after( list_pos_ref, to_insert ); + } + static inline void insert_before(tE & list_pos, tE &to_insert ) { + diref(tE, tE) list_pos_ref = list_pos`from; + insert_before( list_pos_ref, to_insert ); + } + static inline tE & remove(tE & list_pos ) { + diref(tE, tE) list_pos_ref = list_pos`from; + return remove( list_pos_ref ); + } + static inline bool ?`moveNext( tE && ref ) { + diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref; + return ref_dird`moveNext; + } + static inline bool ?`movePrev( tE && ref ) { + diref(tE, tE) & ref_dird = (diref(tE, tE) &) & ref; + return ref_dird`movePrev; + } + +} Index: tests/array-container/array-md-sbscr-cases.cfa =================================================================== --- tests/array-container/array-md-sbscr-cases.cfa (revision 4026d1be509b38f63b3b5012c65fc745d897add0) +++ tests/array-container/array-md-sbscr-cases.cfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -108,8 +108,10 @@ // order wxzy: wx*z, y - + #if 0 + // not working on 32-bit assert(( wxyz[[iw , ix , all , iz ]][iy ] == valExpected )); assert(( wxyz[[iw , ix , all , iz-1]][iy ] != valExpected )); assert(( wxyz[[iw , ix , all , iz ]][iy-1] != valExpected )); + #endif } Index: tests/list/.expect/dlist-insert-remove-2.txt =================================================================== --- tests/list/.expect/dlist-insert-remove-2.txt (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ tests/list/.expect/dlist-insert-remove-2.txt (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,1093 @@ + +~~~~~~~~~~~~~~~~~ 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 +- +- +- Index: tests/list/dlist-insert-remove-2.cfa =================================================================== --- tests/list/dlist-insert-remove-2.cfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ tests/list/dlist-insert-remove-2.cfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,1711 @@ +#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(diref(fred, fred.mine) f) { + do { + sout | f.adatum; + } while (f`moveNext); +} + +void printMyFredsRev(diref(fred, fred.mine) f) { + 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`from); sout | '-'; + printMyFredsRev(f1`from); sout | '-'; + } else { + sout | '-'; sout | '-'; + } + if (&f2) { + printMyFredsFwd(f2`from); sout | '-'; + printMyFredsRev(f2`from); sout | '-'; + } else { + sout | '-'; sout | '-'; + } +} + +void printYourFredsFwd(diref(fred, fred.yours) f) { + do { + sout | f.adatum; + } while (f`moveNext); +} + +void printYourFredsRev(diref(fred, fred.yours) f) { + 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`from); sout | '-'; + printYourFredsRev(f1`from); sout | '-'; + } else { + sout | '-'; sout | '-'; + } + if (&f2) { + printYourFredsFwd(f2`from); sout | '-'; + printYourFredsRev(f2`from); 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, 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, 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); + assert(! lf`last); + + insert_first(lf, f1); + + assert(DUMB_COMPARE(lf`first, & f1)); + assert(DUMB_COMPARE(lf`last , & f1)); + + verify(validate(lf)); + + diref(fred, fred.mine) f1_mine = f1`from; + insert_after(f1_mine, 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(DUMB_COMPARE(lf`first, & f1)); + assert(DUMB_COMPARE(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); + assert(! lf`last); + + insert_first(lf, f1); + + assert(DUMB_COMPARE(lf`first, & f1)); + assert(DUMB_COMPARE(lf`last , & f1)); + + verify(validate(lf)); + + diref(fred, fred.yours) f1_yours = f1`from; + insert_after(f1_yours, 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(DUMB_COMPARE(lf`first, & f1)); + assert(DUMB_COMPARE(lf`last , & f2)); +} + +void test__insertafter_after_last__mary() { + + mary m1 = {3.14}; + mary m2 = {0.5}; + + dlist(mary, mary) lm; + + assert(! lm`first); + assert(! lm`last); + + insert_first(lm, m1); + + assert(DUMB_COMPARE(lm`first, & m1)); + assert(DUMB_COMPARE(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(DUMB_COMPARE(lm`first, & m1)); + assert(DUMB_COMPARE(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); + assert(! lf`last); + + insert_last(lf, f2); + + assert(DUMB_COMPARE(lf`first, & f2)); + assert(DUMB_COMPARE(lf`last , & f2)); + + verify(validate(lf)); + + diref(fred, fred.mine) f2_mine = f2`from; + insert_before(f2_mine, 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(DUMB_COMPARE(lf`first, & f1)); + assert(DUMB_COMPARE(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); + assert(! lf`last); + + insert_last(lf, f2); + + assert(DUMB_COMPARE(lf`first, & f2)); + assert(DUMB_COMPARE(lf`last , & f2)); + + verify(validate(lf)); + + diref(fred, fred.yours) f2_yours = f2`from; + insert_before(f2_yours, 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(DUMB_COMPARE(lf`first, & f1)); + assert(DUMB_COMPARE(lf`last , & f2)); +} + +void test__insertbefore_before_first__mary() { + + mary m1 = {3.14}; + mary m2 = {0.5}; + + dlist(mary, mary) lm; + + assert(! lm`first); + assert(! lm`last); + + insert_last(lm, m2); + + assert(DUMB_COMPARE(lm`first, & m2)); + assert(DUMB_COMPARE(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(DUMB_COMPARE(lm`first, & m1)); + assert(DUMB_COMPARE(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)); + + diref(fred, fred.mine) f1_mine = f1`from; + remove(f1_mine); + + 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)); + + diref(fred, fred.yours) f1_yours = f1`from; + remove(f1_yours); + + 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, 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)); + + diref(fred, fred.mine) f3_mine = f3`from; + remove(f3_mine); + + 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)); + + diref(fred, fred.yours) f3_yours = f3`from; + remove(f3_yours); + + 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, 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)); + + diref(fred, fred.mine) f_mine = f`from; + remove(f_mine); + + verify(validate(fly)); + verify(validate(flm)); + + assert(! flm`first); + assert(! flm`last); + + 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)); + + diref(fred, fred.yours) f_yours = f`from; + remove(f_yours); + + verify(validate(fly)); + verify(validate(flm)); + + assert(! fly`first); + assert(! fly`last); + + 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, 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); + assert(! ml`last); + + // 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 = remove(flm`first); + + 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 = remove(fly`first); + + 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, 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 = remove(ml`first); + + 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 = remove(flm`last); + + 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 = remove(fly`last); + + 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, 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 = remove(ml`last); + + 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 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(); + + return 0; +} Index: tests/zombies/linked-list-perf/experiment.cpp =================================================================== --- tests/zombies/linked-list-perf/experiment.cpp (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ tests/zombies/linked-list-perf/experiment.cpp (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,1 @@ +experiment.koad Index: tests/zombies/linked-list-perf/experiment.koad =================================================================== --- tests/zombies/linked-list-perf/experiment.koad (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ tests/zombies/linked-list-perf/experiment.koad (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,203 @@ +/* + +$cfa is the result of building this configuration: +../cfa-cc/configure --with-target-hosts=host:nodebug CXX=g++- + +~/u++ is my own download of uC++ 7.0.0 + +$cfa -xc experiment.koad -DIMPL_CFA_MIKE_OLD -o perfexp-cfa-mike-old -nodebug -O2 +$cfa -xc experiment.koad -DIMPL_CFA_MIKE_NEW -o perfexp-cfa-mike-new -nodebug -O2 +$cfa -xc experiment.koad -DIMPL_CFA_MIKE_POC -o perfexp-cfa-mike-poc -nodebug -O2 +$cfa -xc experiment.koad -DIMPL_CFA_COLBY -o perfexp-cfa-colby -nodebug -O2 +$cfa -xc experiment.koad -DIMPL_CFA_THIERRY_SUB -o perfexp-cfa-thierry-sub -nodebug -O2 +g++ -xc++ experiment.koad -DIMPL_STL -DNDEBUG -o perfexp-stlgpp -O2 +~/u++/u++-7.0.0/bin/u++ experiment.cpp -DIMPL_UPP -DNDEBUG -o perfexp-uppupp -O2 + + O2 O2-ltd O3-ltd +perfexp-cfa-mike-old 2.50 2.55 +perfexp-cfa-mike-new 2.18 2.15 +perfexp-cfa-mike-poc 1.74 1.71 +perfexp-cfa-colby 2.90 2.84 3.09 +perfexp-cfa-thierry-sub 1.85 +perfexp-stlgpp 4.57 4.72 +perfexp-uppupp 2.09 1.94 1.91 + +O2-ltd is + -fno-tree-pre -fno-gcse + (An earlier draft of mike-new didn't work without disabling those optimizations; we probably don't care about that anymore.) + +*/ + +#include +#include + +#if defined IMPL_STL + + #include + struct S { + volatile int f[64]; + }; + +#elif defined IMPL_UPP + + #include + #include + struct S : public uSeqable { + volatile int f[64]; + }; + +#elif defined IMPL_CFA_MIKE_OLD + + #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 + inline dlink(S); + }; + P9_EMBEDDED( S, dlink(S) ) + +#elif defined IMPL_CFA_COLBY + + #include + struct S { + inline Seqable; + int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD + }; + static inline S *& Back( S * n ) { + return (S *)Back( (Seqable *)n ); + } + static inline S *& Next( S * n ) { + return (S *)Next( (Colable *)n ); + } + +#elif defined IMPL_CFA_THIERRY_SUB + + #include "thierry-subqueue-old-rip.hfa" + typedef $thread S; + + +#else + #error bad impl +#endif + + +#define Repeat( op ) for ( volatile unsigned int i = 0; i < NoOfNodes; i += 1 ) { op; } + +int main() { + enum { NoOfNodes = 1000, Times = 100000 }; // Times supposed to be 100000 + S s[NoOfNodes]; + clock_t start, end; + const char * impl = 0; + + #define STATS + #define REPORT do { \ + double elapsed = ((double) (end - start)) / CLOCKS_PER_SEC; \ + printf("%s %f sec\n", impl, elapsed); \ + STATS \ + } while(0); + + #if defined IMPL_STL + do { + std::list lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( lst.push_back( &s[i] ) ); + Repeat( lst.pop_front() ); + } + end = clock(); + impl = "STL list, pointer"; + REPORT + } while (0); + #elif defined IMPL_UPP + do { + uSequence lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( lst.addTail( &s[i] ) ); + Repeat( lst.dropHead() ); + } + end = clock(); + impl = "u++ intrusive list"; + REPORT + } while (0); + #elif defined IMPL_CFA_MIKE_OLD + do { + dlist(S, S) lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( insert_last( lst, s[i] ) ); + Repeat( remove( lst`first ) ); + } + end = clock(); + impl = "cfa mike-old intrusive list"; + REPORT + } while (0); + #elif defined IMPL_CFA_MIKE_POC + do { + dlist(S) lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( insert_last( lst, s[i] ) ); + Repeat( remove_first( lst ) ); + } + end = clock(); + impl = "cfa mike-poc intrusive list"; + REPORT + } while (0); + #elif defined IMPL_CFA_MIKE_NEW + do { + dlist(S) lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( insert_last( lst, s[i] ) ); + Repeat( remove( lst`first ) ); + } + end = clock(); + impl = "cfa mike-new intrusive list"; + REPORT + } while (0); + #elif defined IMPL_CFA_COLBY + do { + Sequence(S) lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( addHead( lst, s[i] ) ); + Repeat( dropTail( lst ) ); + } + end = clock(); + impl = "cfa colby intrusive list"; + REPORT + } while (0); + + #elif defined IMPL_CFA_THIERRY_SUB + do { + __intrusive_lane_t lst; + start = clock(); + for ( volatile unsigned int t = 0; t < Times; t += 1 ) { + Repeat( push( lst, &s[i] ) ); + Repeat( pop( lst ) ); + } + end = clock(); + impl = "cfa thierry subqueue intrusive list"; + REPORT + } while (0); + + #endif +} Index: tests/zombies/linked-list-perf/mike-proto-list.hfa =================================================================== --- tests/zombies/linked-list-perf/mike-proto-list.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ tests/zombies/linked-list-perf/mike-proto-list.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,75 @@ +#include + +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{ + tE *first; + tE *last; + }; + + static inline void ?{}( dlist(tE, tLinks) & this ) { + this.first = 0p; + this.last = 0p; + } + } +} + +trait embedded( tOuter &, tInner & ) { + tInner & ?`inner( tOuter & ); +}; + +// embedded is reflexive +forall( tX & ) +static inline tX & ?`inner( tX & this ) { return this; } + +// use this on every case of plan-9 inheritance, to make embedded a closure of plan-9 inheritance +#define P9_EMBEDDED( tOuter, tInner ) \ + static inline tInner & ?`inner( tOuter & this ) { return this; } + + +forall( tE &, tLinks & | embedded( tE, tLinks ) | embedded( tLinks, dlink(tE) ) ) { + static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { + if (lst.last) { + verify(lst.first); + dlink(tE) & oldLastLinks = (*lst.last)`inner`inner; + verify(oldLastLinks.next == 0p); + oldLastLinks.next = & e; + } else { + verify(!lst.first); + lst.first = &e; + } + dlink(tE) & newLastLinks = e`inner`inner; + verify(newLastLinks.prev == 0p); + verify(newLastLinks.next == 0p); + newLastLinks.prev = lst.last; + lst.last = &e; + } + static inline void remove_first( dlist(tE, tLinks) &lst ) { + verify(lst.first && lst.last); + dlink(tE) & oldFirstLinks = (*lst.first)`inner`inner; + verify(oldFirstLinks.prev == 0p); + if( lst.last != lst.first) { + verify(oldFirstLinks.next != 0p); + tE & newFirst = * oldFirstLinks.next; + dlink(tE) & newFirstLinks = (newFirst)`inner`inner; + oldFirstLinks.next = 0p; + newFirstLinks.prev = 0p; + lst.first = & newFirst; + } else { + verify(oldFirstLinks.next == 0p); + lst.last = 0p; + lst.first = 0p; + } + } +} Index: tests/zombies/linked-list-perf/thierry-subqueue-old-rip.hfa =================================================================== --- tests/zombies/linked-list-perf/thierry-subqueue-old-rip.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) +++ tests/zombies/linked-list-perf/thierry-subqueue-old-rip.hfa (revision b9376fec526ce62b12725b7b07e3779426f1d735) @@ -0,0 +1,255 @@ +#include +#include +struct $thread; +struct __thread_desc_link { + struct $thread * next; + struct $thread * prev; + volatile unsigned long long ts; + int preferred; +}; +struct $thread { + int f[64]; // FIXME: make "is volatile" consistent; given bug #TBD + struct __thread_desc_link link; +}; + +// Intrusives lanes which are used by the relaxed ready queue +struct __attribute__((aligned(128))) __intrusive_lane_t { + + #if defined(USE_MPSC) + mpsc_queue($thread) queue; + __attribute__((aligned(128))) + #else + // anchor for the head and the tail of the queue + __attribute__((aligned(128))) struct __sentinel_t { + // Link lists fields + // instrusive link field for threads + // must be exactly as in $thread + __thread_desc_link link; + } before, after; + #endif + + // spin lock protecting the queue + volatile bool lock; + + // Optional statistic counters + #if !defined(__CFA_NO_SCHED_STATS__) + struct __attribute__((aligned(64))) { + // difference between number of push and pops + ssize_t diff; + + // total number of pushes and pops + size_t push; + size_t pop ; + } stat; + #endif +}; + +void ?{}(__intrusive_lane_t & this); +void ^?{}(__intrusive_lane_t & this); + +// Get the head pointer (one before the first element) from the anchor +static inline $thread * head(const __intrusive_lane_t & this) { + #if defined(USE_MPSC) + return this.queue.head; + #else + $thread * rhead = ($thread *)( + (uintptr_t)( &this.before ) - offsetof( $thread, link ) + ); + /* paranoid */ verify(rhead); + return rhead; + #endif +} + +// Get the tail pointer (one after the last element) from the anchor +static inline $thread * tail(const __intrusive_lane_t & this) { + #if defined(USE_MPSC) + return this.queue.tail; + #else + $thread * rtail = ($thread *)( + (uintptr_t)( &this.after ) - offsetof( $thread, link ) + ); + /* paranoid */ verify(rtail); + return rtail; + #endif +} + +// Ctor +void ?{}( __intrusive_lane_t & this ) { + this.lock = false; + + #if !defined(USE_MPSC) + this.before.link.prev = 0p; + this.before.link.next = tail(this); + this.before.link.ts = 0; + + this.after .link.prev = head(this); + this.after .link.next = 0p; + this.after .link.ts = 0; + + #if !defined(__CFA_NO_SCHED_STATS__) + this.stat.diff = 0; + this.stat.push = 0; + this.stat.pop = 0; + #endif + + // We add a boat-load of assertions here because the anchor code is very fragile + /* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before)); + /* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after )); + /* paranoid */ verify(head(this)->link.prev == 0p ); + /* paranoid */ verify(head(this)->link.next == tail(this) ); + /* paranoid */ verify(tail(this)->link.next == 0p ); + /* paranoid */ verify(tail(this)->link.prev == head(this) ); + /* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev ); + /* paranoid */ verify(&head(this)->link.next == &this.before.link.next ); + /* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev ); + /* paranoid */ verify(&tail(this)->link.next == &this.after .link.next ); + /* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128); + /* paranoid */ verify(__alignof__(this) == 128); + /* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128)); + #endif +} + +// Dtor is trivial +void ^?{}( __intrusive_lane_t & this ) { + #if !defined(USE_MPSC) + // Make sure the list is empty + /* paranoid */ verify(head(this)->link.prev == 0p ); + /* paranoid */ verify(head(this)->link.next == tail(this) ); + /* paranoid */ verify(tail(this)->link.next == 0p ); + /* paranoid */ verify(tail(this)->link.prev == head(this) ); + #endif +} + +// Push a thread onto this lane +// returns true of lane was empty before push, false otherwise +bool push(__intrusive_lane_t & this, $thread * node) { + #if defined(USE_MPSC) + inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) { + return this->link.next; + } + push(this.queue, node); + #else + #if defined(__CFA_WITH_VERIFY__) + /* paranoid */ verify(this.lock); + /* paranoid */ verify(node->link.ts != 0); + /* paranoid */ verify(node->link.next == 0p); + /* paranoid */ verify(node->link.prev == 0p); + /* paranoid */ verify(tail(this)->link.next == 0p); + /* paranoid */ verify(head(this)->link.prev == 0p); + + if(this.before.link.ts == 0l) { + /* paranoid */ verify(tail(this)->link.prev == head(this)); + /* paranoid */ verify(head(this)->link.next == tail(this)); + } else { + /* paranoid */ verify(tail(this)->link.prev != head(this)); + /* paranoid */ verify(head(this)->link.next != tail(this)); + } + #endif + + // Get the relevant nodes locally + $thread * tail = tail(this); + $thread * prev = tail->link.prev; + + // Do the push + node->link.next = tail; + node->link.prev = prev; + prev->link.next = node; + tail->link.prev = node; + + // Update stats + #if !defined(__CFA_NO_SCHED_STATS__) + this.stat.diff++; + this.stat.push++; + #endif + + verify(node->link.next == tail(this)); + + // Check if the queue used to be empty + if(this.before.link.ts == 0l) { + this.before.link.ts = node->link.ts; + /* paranoid */ verify(node->link.prev == head(this)); + return true; + } + return false; + #endif +} + +// Pop a thread from this lane (must be non-empty) +// returns popped +// returns true of lane was empty before push, false otherwise +$thread * pop(__intrusive_lane_t & this) { + /* paranoid */ verify(this.lock); + #if defined(USE_MPSC) + inline $thread * volatile & ?`next ( $thread * this ) __attribute__((const)) { + return this->link.next; + } + return pop(this.queue); + #else + /* paranoid */ verify(this.before.link.ts != 0ul); + + // Get anchors locally + $thread * head = head(this); + $thread * tail = tail(this); + + // Get the relevant nodes locally + $thread * node = head->link.next; + $thread * next = node->link.next; + + /* paranoid */ verify(node != tail); + /* paranoid */ verify(node); + + // Do the pop + head->link.next = next; + next->link.prev = head; + node->link.next = 0p; + node->link.prev = 0p; + + // Update head time stamp + this.before.link.ts = next->link.ts; + + // Update stats + #ifndef __CFA_NO_SCHED_STATS__ + this.stat.diff--; + this.stat.pop ++; + #endif + + // Check if we emptied list and return accordingly + /* paranoid */ verify(tail(this)->link.next == 0p); + /* paranoid */ verify(head(this)->link.prev == 0p); + if(next == tail) { + /* paranoid */ verify(this.before.link.ts == 0); + /* paranoid */ verify(tail(this)->link.prev == head(this)); + /* paranoid */ verify(head(this)->link.next == tail(this)); + return node; + } + else { + /* paranoid */ verify(next->link.ts != 0); + /* paranoid */ verify(tail(this)->link.prev != head(this)); + /* paranoid */ verify(head(this)->link.next != tail(this)); + /* paranoid */ verify(this.before.link.ts != 0); + return node; + } + #endif +} + +// Check whether or not list is empty +static inline bool is_empty(__intrusive_lane_t & this) { + #if defined(USE_MPSC) + return this.queue.head == 0p; + #else + // Cannot verify here since it may not be locked + return this.before.link.ts == 0; + #endif +} + +// Return the timestamp +static inline unsigned long long ts(__intrusive_lane_t & this) { + #if defined(USE_MPSC) + $thread * tl = this.queue.head; + if(!tl) return -1ull; + return tl->link.ts; + #else + // Cannot verify here since it may not be locked + return this.before.link.ts; + #endif +}