#include <assert.h>

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