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