Index: libcfa/src/collections/list2.hfa =================================================================== --- libcfa/src/collections/list2.hfa (revision 1b4e5a84173be2ec1a815d98741f2ac6fb809dd5) +++ libcfa/src/collections/list2.hfa (revision 1b4e5a84173be2ec1a815d98741f2ac6fb809dd5) @@ -0,0 +1,599 @@ +// A revision of . +// Supports headless (and headed) lists. +// It's basically all good, and should become the official libcfa one, except: +// - perf tests compare this one ("thesis's work") to libcfa ("old, before supporting headless") +// - in libcfa, some uses of list.hfa make assumptions about list's private representation, which need fixing + + + + +// +// 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 : Peter A. Buhr +// Last Modified On : Thu Feb 2 11:32:26 2023 +// Update Count : 2 +// + +#pragma once + +#include + +forall( Decorator &, T & ) +struct tytagref { + inline T &; +}; + +forall( tOuter &, tMid &, tInner & ) +trait embedded { + 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; } + + +// +// P9_EMBEDDED: Use on every case of plan-9 inheritance, to make "implements embedded" be a closure of plan-9 inheritance. +// +// struct foo { +// int a, b, c; +// inline (bar); +// }; +// P9_EMBEDDED( foo, bar ) +// + +// usual version, for structs that are top-level declarations +#define P9_EMBEDDED( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) P9_EMBEDDED_BDY_( immedBase ) + +// special version, for structs that are declared in functions +#define P9_EMBEDDED_INFUNC( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, ) P9_EMBEDDED_BDY_( immedBase ) + +// forward declarations of both the above; generally not needed +// may help you control where the P9_EMBEEDED cruft goes, in case "right after the stuct" isn't where you want it +#define P9_EMBEDDED_FWD( derived, immedBase ) P9_EMBEDDED_DECL_( derived, immedBase, static ) ; +#define P9_EMBEDDED_FWD_INFUNC( derived, immedBase ) auto P9_EMBEDDED_DECL_( derived, immedBase, ) ; + +// private helpers +#define P9_EMBEDDED_DECL_( derived, immedBase, STORAGE ) \ + forall( Tbase &, TdiscardPath & | { tytagref( TdiscardPath, Tbase ) ?`inner( immedBase & ); } ) \ + STORAGE inline tytagref(immedBase, Tbase) ?`inner( derived & this ) + +#define P9_EMBEDDED_BDY_( immedBase ) { \ + 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 advance as the first step, and uses the return +// of advance 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. + +#ifdef __EXPERIMENTAL_DISABLE_OTAG__ // Perf experimention alt mode + + // With origin tagging disabled, iteration never reports "no more elements." + // In this mode, the list API is buggy. + // This mode is used to quantify the cost of the normal tagging scheme. + + #define ORIGIN_TAG_ENABL(p) (p) + #define ORIGIN_TAG_CLEAR(p) (p) + #define ORIGIN_TAG_QUERY(p) 0 + #define ORIGIN_TAG_ASGN(p, v) (p) + #define ORIGIN_TAG_EITHER(p, v) (p) + #define ORIGIN_TAG_NEQ(v1, v2) 0 + +#else // Normal + + #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_ENABL(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_ASGN(p, v) ( \ + verify( ! ORIGIN_TAG_QUERY(p) && "p had no tagbit" ), \ + ORIGIN_TAG_EITHER((p), (v)) \ + ) + + #define ORIGIN_TAG_EITHER(p, v) ( \ + verify( ! ORIGIN_TAG_CLEAR(v) && "v is a pure tagbit" ), \ + ( (p) | (v) ) \ + ) + + #define ORIGIN_TAG_NEQ(v1, v2) ( \ + verify( ! ORIGIN_TAG_CLEAR(v1) && "v1 is a pure tagbit" ), \ + verify( ! ORIGIN_TAG_CLEAR(v2) && "v2 is a pure tagbit" ), \ + ( (v1) ^ (v2) ) \ + ) + +#endif + + + + + + +#ifdef __EXPERIMENTAL_LOOSE_SINGLES__ // Perf experimention alt mode + + // In loose-singles mode, the ability to answer an "is listed" query is disabled, as is "to insert an element, + // it must not be listed already" checking. The user must know separately whether an element is listed. + // Other than inserting it, any list-api action on an unlisted element is undefined. Notably, list iteration + // starting from an unlisted element is not defined to respond "no more elements," and may instead continue + // iterating from a formerly occupied list position. This mode matches LQ usage. + + #define NOLOOSE(...) + #define LOOSEONLY(...) __VA_ARGS__ + +#else // Normal + + #define NOLOOSE(...) __VA_ARGS__ + #define LOOSEONLY(...) + +#endif + + + + + + + + +// struct workaround0_t {}; + +forall( tE & ) { + + struct dlink; + + // do not use; presence of the field declaration unblocks ability to define dlink (#304) + struct __dlink_selfref_workaround_t { + dlink(tE) *ref_notSelfRef; + }; + + struct dlink { + dlink(tE) *next; // TODO: rename with $ + dlink(tE) *prev; + }; + + static inline void ?{}( dlink(tE) & this ) { + NOLOOSE( + dlink(tE) * toSelf = & this; + size_t toSelfNum = (size_t) toSelf; + size_t toSelfNumTagged = ORIGIN_TAG_ENABL( toSelfNum ); + dlink(tE) * toSelfPtrTagged = (dlink(tE) *) toSelfNumTagged; + toSelf = toSelfPtrTagged; + (this.next){ toSelf }; + (this.prev){ toSelf }; + ) + } + + // You can "copy" a dlink. But the result won't be linked. + // Lets you copy what you inline the dlink into. + static inline void ?{}( dlink(tE) & this, dlink(tE) ) { + this{}; + } + + forall( tLinks & = dlink(tE) | embedded(tE, tLinks, dlink(tE)) ) { + struct dlist { + inline 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_ENABL( origin_addr ); + return (tE *)preResult; + } + + static inline void ?{}( dlist(tE, tLinks) & this ) { + NOLOOSE( + ( (dlink(tE) &) this ){}; + ) + LOOSEONLY( + dlink(tE) * listOrigin = (dlink(tE) *) $get_list_origin_addr( this ); + dlink( tE ) & thisl = this; + (thisl.prev) = listOrigin; + (thisl.next) = listOrigin; + ) + } + } +} + + +forall( tE &, tLinks & | embedded( tE, tLinks, dlink(tE) ) ) { + + static inline void insert_after(tE & list_pos, tE &to_insert) { + size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert after the origin is fine + tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos); + verify (&list_pos_real != 0p); + + verify (&to_insert != 0p); + NOLOOSE( + verify(! ORIGIN_TAG_QUERY((size_t) & to_insert)); + ) + dlink(tE) & linkToInsert = to_insert`inner; + NOLOOSE( + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev)); + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next)); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert); + ) + dlink(tE) & list_pos_links = list_pos_real`inner; + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t)(& list_pos_links); + size_t to_insert_prev_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag); + dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num; + linkToInsert.prev = to_insert_prev; + linkToInsert.next = list_pos_links.next; + dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next ); + size_t afterLinks_prev_tag = ORIGIN_TAG_QUERY((size_t)afterLinks.prev); + size_t linkToInsert_num = (size_t)(& linkToInsert); + size_t afterLinks_prev_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, afterLinks_prev_tag)); + afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num); + list_pos_links.next = &linkToInsert; + asm( "" : : : "memory" ); + } + + static inline void insert_before(tE & list_pos, tE &to_insert) { + size_t list_pos_tag = ORIGIN_TAG_QUERY((size_t) & list_pos); // a request to insert before the origin is fine + tE & list_pos_real = * (tE *) ORIGIN_TAG_CLEAR((size_t) & list_pos); + verify (&list_pos_real != 0p); + + verify (&to_insert != 0p); + NOLOOSE( + verify(! ORIGIN_TAG_QUERY((size_t) & to_insert)); + ) + dlink(tE) & linkToInsert = to_insert`inner; + NOLOOSE( + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev)); + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next)); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert); + ) + dlink(tE) & list_pos_links = list_pos_real`inner; + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t)(& list_pos_links); + size_t to_insert_next_num = ORIGIN_TAG_ASGN(list_pos_links_num, list_pos_tag); + dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num; + linkToInsert.next = to_insert_next; + linkToInsert.prev = list_pos_links.prev; + dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev ); + size_t beforeLinks_next_tag = ORIGIN_TAG_QUERY((size_t)beforeLinks.next); + size_t linkToInsert_num = (size_t)(& linkToInsert); + size_t beforeLinks_next_num = ORIGIN_TAG_ASGN(linkToInsert_num, ORIGIN_TAG_NEQ(list_pos_tag, beforeLinks_next_tag)); + beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num); + list_pos_links.prev = &linkToInsert; + asm( "" : : : "memory" ); + } + + static inline tE & remove(tE & list_pos) { + verify( ! ORIGIN_TAG_QUERY((size_t) & list_pos) ); + verify (&list_pos != 0p); + + dlink(tE) & list_pos_links = list_pos`inner; + dlink(tE) & before_raw = * list_pos_links.prev; + dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + size_t before_links_next_tag = ORIGIN_TAG_QUERY( (size_t) (before_links.next) ); + + dlink(tE) & after_raw = * list_pos_links.next; + dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + size_t after_links_prev_tag = ORIGIN_TAG_QUERY( (size_t) (after_links.prev) ); + + size_t before_links_next_rslt = ORIGIN_TAG_EITHER( ((size_t) & after_raw), before_links_next_tag ); + size_t after_links_prev_rslt = ORIGIN_TAG_EITHER( ((size_t) & before_raw), after_links_prev_tag ); + before_links.next = (dlink(tE) *) before_links_next_rslt; + after_links.prev = (dlink(tE) *) after_links_prev_rslt; + + NOLOOSE( + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t) &list_pos_links; + size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num ); + list_pos_links.next = list_pos_links.prev = (dlink(tE)*) list_pos_links_tagged_num; + asm( "" : : : "memory" ); + ) + return list_pos; + } + + static inline tE & downcast$( tytagref( tLinks, dlink(tE) ) ref ) { + dlink(tE) & lnk = ref; + dlink(tE) & link_from_null = ( * (tE *) 0p )`inner; + ptrdiff_t link_offset = (ptrdiff_t) & link_from_null; + size_t elm_addr = ((size_t) & lnk) - link_offset; + return * (tE*) elm_addr; + } + + static inline tE & first( dlist(tE, tLinks) & lst ) { + verify (&lst != 0p); + dlink(tE) * firstLnk = lst.next; + if (ORIGIN_TAG_QUERY((size_t)firstLnk)) return * 0p; + tytagref( tLinks, dlink(tE) ) firstLnkTagged = {*firstLnk}; + return downcast$( firstLnkTagged ); + } + static inline tE & last ( dlist(tE, tLinks) & lst ) { + verify (&lst != 0p); + dlink(tE) * lastLnk = lst.prev; + if (ORIGIN_TAG_QUERY((size_t)lastLnk)) return * 0p; + tytagref( tLinks, dlink(tE) ) lastLnkTagged = {*lastLnk}; + return downcast$( lastLnkTagged ); + } + + static inline bool isEmpty( dlist(tE, tLinks) & lst ) { + verify (&lst != 0p); + if ( & first(lst) == 0p || & last(lst) == 0p ) { + verify( & last(lst) == 0p && & last(lst) == 0p ); + return true; + } + return false; + } + + static inline bool isListed( tE & e ) { + NOLOOSE( + verify (&e != 0p); + verify(! ORIGIN_TAG_QUERY( (size_t) & e )); + dlink(tE) & e_links = e`inner; + dlink(tE) * lprev = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.prev); + dlink(tE) * lnext = (dlink(tE)*) ORIGIN_TAG_CLEAR((size_t) e_links.next); + return ( lprev != &e_links ) || ( lnext != &e_links ); + ) + LOOSEONLY( + verify(false && "isListed is undefined"); + return true; + ) + } + + static inline tE & iter( dlist(tE, tLinks) & lst ) { + tE * origin = $get_list_origin_addr( lst ); + return *origin; + } + + + // todo: resolve the pun: + // tag as in proxy (tytagref) + // tag as in bit manipulation on a funny pointer + + static inline bool advance( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + verify (& oldReferent != 0p); + dlink(tE) * tgt = oldReferent`inner.next; + size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt); + dlink(tE) * nextl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt); + tytagref( tLinks, dlink(tE) ) nextLnkTagged = { * nextl }; + tE & nexte = downcast$( nextLnkTagged ); + size_t next_te_num = (size_t) & nexte; + size_t new_ref_inner_num = ORIGIN_TAG_ASGN(next_te_num, tgt_tags); + tE * new_ref_inner = (tE *) new_ref_inner_num; + &ref_inner = new_ref_inner; + return ! tgt_tags; + } + + static inline bool recede( tE && refx ) { + tE && ref_inner = refx; + tE & oldReferent = * (tE*) ORIGIN_TAG_CLEAR( (size_t) & ref_inner ); + verify (& oldReferent != 0p); + dlink(tE) * tgt = oldReferent`inner.prev; + size_t tgt_tags = ORIGIN_TAG_QUERY( (size_t)tgt); + dlink(tE) * prevl = (dlink(tE) *)ORIGIN_TAG_CLEAR((size_t)tgt); + tytagref( tLinks, dlink(tE) ) prevLnkTagged = { * prevl }; + tE & preve = downcast$( prevLnkTagged ); + size_t prev_te_num = (size_t) & preve; + size_t new_ref_inner_num = ORIGIN_TAG_ASGN(prev_te_num, tgt_tags); + tE * new_ref_inner = (tE *) new_ref_inner_num; + &ref_inner = new_ref_inner; + return ! tgt_tags; + } + + bool isFirst( tE & node ) { + // Probable bug copied from master + // should be `! recede(node)` + // correct: "is first iff cannot recede" + // used backward in test suite too, probably victim of a grep rename + return recede( node ); + } + + bool isLast( tE & node ) { + // ditto, vice versa + return advance( node ); + } + + static inline tE & next( tE & e ) { + if( advance(e) ) return e; + return * 0p; + } + + static inline tE & prev( tE & e ) { + if( recede(e) ) return e; + return * 0p; + } + + // Next 4 headed operations: + // Manual inline of the equivalent headless operation, manually simplified. + // Applies knowledge of tag pattern around head (unknown to optimizer) to reduce runtime tag operations. + + static inline void insert_first( dlist(tE, tLinks) &lst, tE & e ) { + dlink(tE) & linkToInsert = e`inner; + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev)); + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next)); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert); + dlink(tE) & list_pos_links = lst; + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t)(& list_pos_links); + size_t to_insert_prev_num = ORIGIN_TAG_ENABL(list_pos_links_num); + dlink(tE) * to_insert_prev = (dlink(tE)*)to_insert_prev_num; + linkToInsert.prev = to_insert_prev; + linkToInsert.next = list_pos_links.next; + dlink(tE) & afterLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.next ); + size_t linkToInsert_num = (size_t)(& linkToInsert); + size_t afterLinks_prev_num = linkToInsert_num; + afterLinks.prev = (dlink(tE)*)(afterLinks_prev_num); + list_pos_links.next = &linkToInsert; + asm( "" : : : "memory" ); + } + + static inline void insert_last( dlist(tE, tLinks) &lst, tE & e ) { + // insert_before(iter(lst), e); + dlink(tE) & linkToInsert = e`inner; + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.next)); + verify(ORIGIN_TAG_QUERY((size_t)linkToInsert.prev)); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.next) == (size_t)&linkToInsert); + verify(ORIGIN_TAG_CLEAR((size_t)linkToInsert.prev) == (size_t)&linkToInsert); + dlink(tE) & list_pos_links = lst; + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t)(& list_pos_links); + size_t to_insert_next_num = ORIGIN_TAG_ENABL(list_pos_links_num); + dlink(tE) * to_insert_next = (dlink(tE)*)to_insert_next_num; + linkToInsert.next = to_insert_next; + linkToInsert.prev = list_pos_links.prev; + dlink(tE) & beforeLinks = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) list_pos_links.prev ); + size_t linkToInsert_num = (size_t)(& linkToInsert); + size_t beforeLinks_next_num = linkToInsert_num; + beforeLinks.next = (dlink(tE)*)(beforeLinks_next_num); + list_pos_links.prev = &linkToInsert; + asm( "" : : : "memory" ); + } + + static inline tE & remove_first( dlist(tE, tLinks) &lst ) { + verify (&lst != 0p); + dlink(tE) & list_links = lst; + verify (! ORIGIN_TAG_QUERY( (size_t) (list_links.next) ) ); + + dlink(tE) & fst_links = * list_links.next; + + dlink(tE) & after_raw = * fst_links.next; + dlink(tE) & after_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & after_raw ); + verify( ! ORIGIN_TAG_QUERY( (size_t) (after_links.prev) ) ); + + size_t before_links_next_rslt = ((size_t) & after_raw); + size_t after_links_prev_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links ); + list_links.next = (dlink(tE) *) before_links_next_rslt; + after_links.prev = (dlink(tE) *) after_links_prev_rslt; + + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t) &fst_links; + size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num ); + fst_links.next = fst_links.prev = (dlink(tE)*) list_pos_links_tagged_num; + asm( "" : : : "memory" ); + + tytagref( tLinks, dlink(tE) ) lpLnkTagged = {fst_links}; + return downcast$( lpLnkTagged ); + } + + static inline tE & remove_last( dlist(tE, tLinks) &lst ) { + verify (&lst != 0p); + dlink(tE) & list_links = lst; + verify (! ORIGIN_TAG_QUERY( (size_t) (list_links.prev) ) ); + + dlink(tE) & last_links = * list_links.prev; + + dlink(tE) & before_raw = * last_links.prev; + dlink(tE) & before_links = * (dlink(tE) *) ORIGIN_TAG_CLEAR( (size_t) & before_raw ); + verify( ! ORIGIN_TAG_QUERY( (size_t) (before_links.next) ) ); + + size_t after_links_prev_rslt = ((size_t) & before_raw); + size_t before_links_next_rslt = ORIGIN_TAG_ENABL( (size_t) & list_links ); + list_links.prev = (dlink(tE) *) after_links_prev_rslt; + before_links.next = (dlink(tE) *) before_links_next_rslt; + + asm( "" : : : "memory" ); + size_t list_pos_links_num = (size_t) &last_links; + size_t list_pos_links_tagged_num = ORIGIN_TAG_ENABL( list_pos_links_num ); + last_links.prev = last_links.next = (dlink(tE)*) list_pos_links_tagged_num; + asm( "" : : : "memory" ); + + tytagref( tLinks, dlink(tE) ) lpLnkTagged = {last_links}; + return downcast$( lpLnkTagged ); + } + + static inline tE & try_pop_first( dlist(tE, tLinks) &lst ) { + tE & first_inlist = first(lst); + tE & first_item = first_inlist; + if (&first_item) remove(first_inlist); // TODO: should it use pop_front? + return first_item; + } + + static inline tE & try_pop_last( dlist(tE, tLinks) &lst ) { + tE & last_inlist = last(lst); + tE & last_item = last_inlist; + if (&last_item) remove(last_inlist); // TODO: should it use pop_back? + return last_item; + } + + + #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__)) + static bool $validate_fwd( dlist(tE, tLinks) & this ) { + tE & lagElem = *0p; + + while ( tE & it = iter(this); advance(it) ) { + if (& lagElem == 0p && &it != & first(this) ) return false; + & lagElem = & it; + } + + if (& lagElem != & last(this)) return false; + + // TODO: verify that it is back at iter(this); + return true; + } + static bool $validate_rev( dlist(tE, tLinks) & this ) { + tE & lagElem = *0p; + + while ( tE & it = iter(this); recede(it) ) { + if (& lagElem == 0p && &it != & last(this) ) return false; + & lagElem = & it; + } + + if (& lagElem != & first(this)) return false; + + // TODO: verify that it is back at iter(this); + return true; + } + static inline bool validate( dlist(tE, tLinks) & this ) { + bool reportsHavingFirst = ((& first(this)) == 0p); + bool reportsHavingLast = ((& last(this)) == 0p); + if ( reportsHavingFirst != reportsHavingLast ) return false; + + return $validate_fwd(this) && $validate_rev(this); + } + #endif + +} +