source: libcfa/src/containers/list.hfa @ b81fd95

//
// 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
//

#include <assert.h>

#define __DLISTED_MGD_COMMON(ELEM, NODE, LINKS_FLD) \
static inline ELEM& $tempcv_n2e(NODE &node) { \
        return node; \
} \
\
static inline NODE& $tempcv_e2n(ELEM &node) { \
        return ( NODE & ) node; \
} \
\
static inline ELEM & ?`prev(NODE &node) { \
    $dlinks(ELEM) & ls = node.LINKS_FLD; \
        $mgd_link(ELEM) * l = &ls.prev; \
        ELEM * e = l->elem; \
        return *e; \
} \
\
static inline ELEM & ?`next(NODE &node) { \
    $dlinks(ELEM) & ls = node.LINKS_FLD; \
        $mgd_link(ELEM) * l = &ls.next; \
        ELEM * e = l->elem; \
        return *e; \
} \
\
static inline $mgd_link(ELEM) & $prev_link(NODE &node) { \
    $dlinks(ELEM) & ls = node.LINKS_FLD; \
        $mgd_link(ELEM) * l = &ls.prev; \
        return *l; \
} \
\
static inline $mgd_link(ELEM) & $next_link(NODE &node) { \
    $dlinks(ELEM) & ls = node.LINKS_FLD; \
        $mgd_link(ELEM) * l = &ls.next; \
        return *l; \
}

#define __DLISTED_MGD_JUSTEXPL(STRUCT, IN_THELIST, STRUCT_IN_THELIST) \
struct STRUCT_IN_THELIST { \
        inline STRUCT; \
}; \
\
void ?{}(STRUCT_IN_THELIST &) = void; \
\
static inline STRUCT_IN_THELIST& ?`IN_THELIST(STRUCT &this) { \
        return (STRUCT_IN_THELIST&)this; \
}

#define __DLISTED_MGD_JUSTIMPL(STRUCT)

forall( dtype tE ) {
        struct $mgd_link {
                tE *elem;
                void *terminator;
                _Bool is_terminator;
                // will collapse to single pointer with tag bit
        };
        static inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
                (this.elem){ elem };
                (this.terminator){ 0p };
                (this.is_terminator){ 0 };
        }
        static inline void ?{}( $mgd_link(tE) &this, void * terminator ) {
                (this.elem){ 0p };
                (this.terminator){ terminator };
                (this.is_terminator){ 1 };
        }
        forall ( otype tInit | { void ?{}( $mgd_link(tE) &, tInit); } )
        static inline void ?=?( $mgd_link(tE) &this, tInit i ) {
                ^?{}( this );
                ?{}( this, i );
        }
        struct $dlinks {
                // containing item is not listed
                // iff
                // links have (elem == 0p && terminator == 0p)
                $mgd_link(tE) next;
                $mgd_link(tE) prev;
        };
        static inline void ?{}( $dlinks(tE) &this ) {
                (this.next){ (tE *)0p };
                (this.prev){ (tE *)0p };
        }
}

#define DLISTED_MGD_EXPL_IN(STRUCT, LIST_SUF) \
  $dlinks(STRUCT) $links_ ## LIST_SUF;

#define DLISTED_MGD_EXPL_OUT(STRUCT, LIST_SUF) \
  __DLISTED_MGD_JUSTEXPL(STRUCT, in_##LIST_SUF, STRUCT ## _in_ ## LIST_SUF) \
  __DLISTED_MGD_COMMON(STRUCT, STRUCT##_in_##LIST_SUF,  $links_ ## LIST_SUF)

#define DLISTED_MGD_IMPL_IN(STRUCT) \
  $dlinks(STRUCT) $links;

#define DLISTED_MGD_IMPL_OUT(STRUCT) \
  __DLISTED_MGD_JUSTIMPL(STRUCT) \
  __DLISTED_MGD_COMMON(STRUCT, STRUCT, $links)

trait $dlistable(dtype Tnode, dtype Telem) {
        $mgd_link(Telem) & $prev_link(Tnode &);
        $mgd_link(Telem) & $next_link(Tnode &);
        Telem& $tempcv_n2e(Tnode &);
        Tnode& $tempcv_e2n(Telem &);

        Telem& ?`next(Tnode &);
        Telem& ?`prev(Tnode &);
};

forall (dtype Tnode, dtype Telem | $dlistable(Tnode, Telem)) {

        // implemented as a sentinel item in an underlying cicrular list
        // theList.$links.next is first
        // theList.$links.prev is last
        // note this allocation preserves prev-next composition as an identity
        struct dlist {
                $dlinks(Telem) $links;
        };

        // an empty dlist
        // links refer to self, making a tight circle
        static inline void ?{}( dlist(Tnode, Telem) & this ) {
                $mgd_link(Telem) selfRef = (void *) &this;
                ( this.$links ) { selfRef, selfRef };
        }

        static inline Telem & ?`first( dlist(Tnode, Telem) &l ) {
                return * l.$links.next.elem;
        }

        static inline Telem & ?`last( dlist(Tnode, Telem) &l ) {
                return * l.$links.prev.elem;
        }

        #if !defined(NDEBUG) && (defined(__CFA_DEBUG__) || defined(__CFA_VERIFY__))
        static bool $validate_fwd( dlist(Tnode, Telem) & this ) {
                Tnode * it = & $tempcv_e2n( this`first );
                if (!it) return (& this`last == 0p);

                while( $next_link(*it).elem ) {
                        it = & $tempcv_e2n( * $next_link(*it).elem );
                }

                return ( it == & $tempcv_e2n( this`last ) ) &&
                           ( $next_link(*it).is_terminator ) &&
                           ( ((dlist(Tnode, Telem)*)$next_link(*it).terminator) == &this );
        }
        static bool $validate_rev( dlist(Tnode, Telem) & this ) {
                Tnode * it = & $tempcv_e2n( this`last );
                if (!it) return (& this`first == 0p);

                while( $prev_link(*it).elem ) {
                        it = & $tempcv_e2n( * $prev_link(*it).elem );
                }

                return ( it == & $tempcv_e2n( this`first ) ) &&
                           ( $prev_link(*it).is_terminator ) &&
                           ( ((dlist(Tnode, Telem)*)$prev_link(*it).terminator) == &this );
        }
        static bool validate( dlist(Tnode, Telem) & this ) {
                return $validate_fwd(this) && $validate_rev(this);
        }
        #endif

        static inline void insert_after(Tnode &list_pos, Telem &to_insert) {
                assert (&list_pos != 0p);
                assert (&to_insert != 0p);
                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
                assert($prev_link(singleton_to_insert).elem == 0p);
                assert($next_link(singleton_to_insert).elem == 0p);
                $prev_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
                $next_link(singleton_to_insert) = $next_link(list_pos);
                if ($next_link(list_pos).is_terminator) {
                        dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
                        $dlinks(Telem) *list_links = & list->$links;
                        $mgd_link(Telem) *list_last = & list_links->prev;
                        *list_last = &to_insert;
                } else {
                        Telem *list_pos_next = $next_link(list_pos).elem;
                        if (list_pos_next) {
                                Tnode & lpn_inlist = $tempcv_e2n(*list_pos_next);
                                $prev_link(lpn_inlist) = &to_insert;
                        }
                }
                $next_link(list_pos) = &to_insert;
        }

        static inline void insert_before(Tnode &list_pos, Telem &to_insert) {
                assert (&list_pos != 0p);
                assert (&to_insert != 0p);
                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
                assert($prev_link(singleton_to_insert).elem == 0p);
                assert($next_link(singleton_to_insert).elem == 0p);
                $next_link(singleton_to_insert) = & $tempcv_n2e(list_pos);
                $prev_link(singleton_to_insert) = $prev_link(list_pos);
                if ($prev_link(list_pos).is_terminator) {
                        dlist(Tnode, Telem) *list = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
                        $dlinks(Telem) *list_links = & list->$links;
                        $mgd_link(Telem) *list_first = & list_links->next;
                        *list_first = &to_insert;
                } else {
                        Telem *list_pos_prev = $prev_link(list_pos).elem;
                        if (list_pos_prev) {
                                Tnode & lpp_inlist = $tempcv_e2n(*list_pos_prev);
                                $next_link(lpp_inlist) = &to_insert;
                        }
                }
                $prev_link(list_pos) = &to_insert;
        }

    static inline void insert_first(dlist(Tnode, Telem) &list, Telem &to_insert) {
                assert (&list != 0p);
                assert (&to_insert != 0p);
                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
                assert($prev_link(singleton_to_insert).elem == 0p);
                assert($next_link(singleton_to_insert).elem == 0p);

                $prev_link(singleton_to_insert) = (void*) &list;
                $next_link(singleton_to_insert) = list.$links.next;

                $dlinks(Telem) *listLinks = & list.$links;
                if (listLinks->next.is_terminator) {
                        $mgd_link(Telem) * listPrevReference = & listLinks->prev;
                        *listPrevReference = &to_insert;
                } else {
                        Tnode & next_inlist = $tempcv_e2n(*list.$links.next.elem);
                        $prev_link(next_inlist) = &to_insert;
                }
                $mgd_link(Telem) * listNextReference = & listLinks->next;
                *listNextReference = &to_insert;
        }

    static inline void insert_last(dlist(Tnode, Telem) &list, Telem &to_insert) {
                assert (&list != 0p);
                assert (&to_insert != 0p);
                Tnode &singleton_to_insert = $tempcv_e2n(to_insert);
                assert($next_link(singleton_to_insert).elem == 0p);
                assert($prev_link(singleton_to_insert).elem == 0p);

                $next_link(singleton_to_insert) = (void*) &list;
                $prev_link(singleton_to_insert) = list.$links.prev;

                $dlinks(Telem) *listLinks = & list.$links;
                if (listLinks->prev.is_terminator) {
                        $mgd_link(Telem) * listNextReference = & listLinks->next;
                        *listNextReference = &to_insert;
                } else {
                        Tnode & prev_inlist = $tempcv_e2n(*list.$links.prev.elem);
                        $next_link(prev_inlist) = &to_insert;
                }
                $mgd_link(Telem) * listPrevReference = & listLinks->prev;
                *listPrevReference = &to_insert;
        }

    static inline void remove(Tnode &list_pos) {
                assert( &list_pos != 0p );

                $mgd_link(Telem) &incoming_from_prev = *0p;
                $mgd_link(Telem) &incoming_from_next = *0p;

                if ( $prev_link(list_pos).is_terminator ) {
                        dlist(Tnode, Telem) * tgt_before = ( dlist(Tnode, Telem) * ) $prev_link(list_pos).terminator;
                        $dlinks(Telem) * links_before = & tgt_before->$links;
                        &incoming_from_prev = & links_before->next;
                } else if ($prev_link(list_pos).elem) {
                        Telem * tgt_before = $prev_link(list_pos).elem;
                        Tnode & list_pos_before = $tempcv_e2n(*tgt_before);
                        &incoming_from_prev = & $next_link(list_pos_before);
                }

                if ( $next_link(list_pos).is_terminator ) {
                        dlist(Tnode, Telem) * tgt_after = ( dlist(Tnode, Telem) * ) $next_link(list_pos).terminator;
                        $dlinks(Telem) * links_after = & tgt_after->$links;
                        &incoming_from_next = & links_after->prev;
                } else if ($next_link(list_pos).elem) {
                        Telem * tgt_after  = $next_link(list_pos).elem;
                        Tnode & list_pos_after  = $tempcv_e2n(*tgt_after );
                        &incoming_from_next = & $prev_link(list_pos_after );
                }

                if (& incoming_from_prev) {
                        incoming_from_prev = $next_link(list_pos);
                }
                if (& incoming_from_next) {
                        incoming_from_next = $prev_link(list_pos);
                }

                $next_link(list_pos) = (Telem*) 0p;
                $prev_link(list_pos) = (Telem*) 0p;
        }

        static inline bool ?`is_empty(dlist(Tnode, Telem) &list) {
                assert( &list != 0p );
                $dlinks(Telem) *listLinks = & list.$links;
                if (listLinks->next.is_terminator) {
                        assert(listLinks->prev.is_terminator);
                        assert(listLinks->next.terminator);
                        assert(listLinks->prev.terminator);
                        return true;
                } else {
                        assert(!listLinks->prev.is_terminator);
                        assert(listLinks->next.elem);
                        assert(listLinks->prev.elem);
                        return false;
                }
        }

        static inline Telem & pop_first(dlist(Tnode, Telem) &list) {
                assert( &list != 0p );
                assert( !list`is_empty );
                $dlinks(Telem) *listLinks = & list.$links;
                Telem & first = *listLinks->next.elem;
                Tnode & list_pos_first  = $tempcv_e2n( first );
                remove(list_pos_first);
                return first;
        }

        static inline Telem & pop_last(dlist(Tnode, Telem) &list) {
                assert( &list != 0p );
                assert( !list`is_empty );
                $dlinks(Telem) *listLinks = & list.$links;
                Telem & last = *listLinks->prev.elem;
                Tnode & list_pos_last  = $tempcv_e2n( last );
                remove(list_pos_last);
                return last;
        }

}