source: libcfa/src/containers/list2.hfa @ 1680072

//
// 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 <assert.h>

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


// The origin is the position encountered at the start of iteration,
// signifying, "need to advance to the first element," and at the end
// of iteration, signifying, "no more elements."  Normal comsumption of
// an iterator runs ?`moveNext as the first step, and uses the return
// of ?`moveNext as a guard, before dereferencing the iterator.  So
// normal consumption of an iterator does not dereference an iterator
// in origin position.  The value of a pointer (underlying a refence)
// that is exposed publicly as an iteraor, and also a pointer stored
// internally in a link field, is tagged, to indicate "is the origin"
// (internally, is the list-head sentinel node), or untagged, to indicate
// "is a regular node."  Intent is to help a user who dereferences an
// iterator in origin position (which would be an API-use error on their
// part), by failing fast.

#if defined( __x86_64 )
    // Preferred case: tag in the most-significant bit.  Dereference
    // has been shown to segfault consistently.  Maintenance should
    // list more architectures as "ok" here, to let them use the
    // preferred case, when valid.
    #define ORIGIN_TAG_BITNO ( 8 * sizeof( size_t ) - 1 )
#else
    // Fallback case: tag in the least-significant bit.  Dereference
    // will often give an alignment error, but may not, e.g. if
    // accessing a char-typed member.  32-bit x86 uses the most-
    // significant bit for real room on the heap.
    #define ORIGIN_TAG_BITNO 0
#endif
#define ORIGIN_TAG_MASK (((size_t)1) << ORIGIN_TAG_BITNO)

#define ORIGIN_TAG_SET(p)   ((p) |  ORIGIN_TAG_MASK)
#define ORIGIN_TAG_CLEAR(p) ((p) & ~ORIGIN_TAG_MASK)
#define ORIGIN_TAG_QUERY(p) ((p) &  ORIGIN_TAG_MASK)


forall( tE & ) {

    struct dlink{
        tE *next;
        tE *prev;
    };

    static inline void ?{}( dlink(tE) & this ) {
        this.next = 0p;
        this.prev = 0p;
    }

    forall( tLinks & = 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 = &target;
        // }
    }

}


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 );
        asm( "" : : : "memory" );
        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;
        asm( "" : : : "memory" );
        }

        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 );
        asm( "" : : : "memory" );
        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;
        asm( "" : : : "memory" );
        }

        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;
        asm( "" : : : "memory" );
        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;
    }

}