//
// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// bits/containers.h -- Intrusive generic containers.h
//
// Author           : Thierry Delisle
// Created On       : Tue Oct 31 16:38:50 2017
// Last Modified By : --
// Last Modified On : --
// Update Count     : 0

#pragma once

#include <stddef.h>

#include "libhdr.h"

//-----------------------------------------------------------------------------
// Node Base
//-----------------------------------------------------------------------------

#ifdef __CFORALL__
	trait is_node(dtype T) {
		T*& get_next( T& );
	};
#endif

//-----------------------------------------------------------------------------
// Stack
//-----------------------------------------------------------------------------
#ifdef __CFORALL__
	forall(dtype TYPE | is_node(TYPE))
	#define T TYPE
#else
	#define T void
#endif
struct __stack {
	T * top;
};

#ifdef __CFORALL__
#define __stack_t(T) __stack(T)
#else
#define __stack_t(T) struct __stack
#endif

#ifdef __CFORALL__
	forall(dtype T | is_node(T))
	void ?{}( __stack(T) & this ) {
		this.top = NULL;
	}

	forall(dtype T | is_node(T) | sized(T))
	void push( __stack(T) & this, T * val ) {
		verify( !get_next( *val ) );
		get_next( *val ) = this.top;
		this.top = val;
	}

	forall(dtype T | is_node(T) | sized(T))
	T * pop( __stack(T) & this ) {
		T * top = this.top;
		if( top ) {
			this.top = get_next( *top );
			get_next( *top ) = NULL;
		}
		return top;
	}
#endif

//-----------------------------------------------------------------------------
// Queue
//-----------------------------------------------------------------------------
#ifdef __CFORALL__
	forall(dtype T | is_node(T))
	#define T TYPE
#else
	#define T void
#endif
struct __queue {
	T * head;
	T ** tail;
};

#ifdef __CFORALL__
	forall(dtype T | is_node(T))
	void ?{}( __queue(T) & this ) {
		this.head = NULL;
		this.tail = &this.head;
	}

	forall(dtype T | is_node(T) | sized(T))
	void append( __queue(T) & this, T * val ) {
		verify(this.tail != NULL);
		*this.tail = val;
		this.tail = &get_next( *val );
	}

	forall(dtype T | is_node(T) | sized(T))
	T * pop_head( __queue(T) & this ) {
		T * head = this.head;
		if( head ) {
			this.head = get_next( *head );
			if( !get_next( *head ) ) {
				this.tail = &this.head;
			}
			get_next( *head ) = NULL;
		}
		return head;
	}

	forall(dtype T | is_node(T) | sized(T))
	T * remove( __queue(T) & this, T ** it ) {
		T * val = *it;
		verify( val );

		(*it) = get_next( *val );

		if( this.tail == &get_next( *val ) ) {
			this.tail = it;
		}

		get_next( *val ) = NULL;

		verify( (this.head == NULL) == (&this.head == this.tail) );
		verify( *this.tail == NULL );
		return val;
	}
#endif