Index: libcfa/src/containers/list.hfa
===================================================================
--- libcfa/src/containers/list.hfa	(revision 1268ad8ea58487a8428bbedb6801b68c2ddd7c85)
+++ libcfa/src/containers/list.hfa	(revision 1268ad8ea58487a8428bbedb6801b68c2ddd7c85)
@@ -0,0 +1,274 @@
+//
+// 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; \
+} \
+\
+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
+	};
+	inline void ?{}( $mgd_link(tE) &this, tE* elem ) {
+		(this.elem){ elem };
+		(this.terminator){ 0p };
+		(this.is_terminator){ 0 };
+	}
+	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); } )
+	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;
+	};
+	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 &);
+};
+
+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
+	void ?{}( dlist(Tnode, Telem) & this ) {
+		$mgd_link(Telem) selfRef = (void *) &this;
+		( this.$links ) { selfRef, selfRef };
+	}
+
+	Telem & ?`first( dlist(Tnode, Telem) &l ) {
+		return * l.$links.next.elem;
+	}
+
+	Telem & ?`last( dlist(Tnode, Telem) &l ) {
+		return * l.$links.prev.elem;
+	}
+
+	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).elem;
+		if ($next_link(list_pos).is_terminator) {
+			dlist(Tnode, Telem) *list = $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).elem;
+		if ($prev_link(list_pos).is_terminator) {
+			dlist(Tnode, Telem) *list = $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 = $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 = $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;
+	}
+}
+