#pragma once

#define __CFA_NO_SCHED_STATS__

// Intrusives lanes which are used by the relaxed ready queue
struct __attribute__((aligned(128))) __intrusive_lane_t {

	// anchor for the head and the tail of the queue
	__attribute__((aligned(128))) struct __sentinel_t {
		// Link lists fields
		// instrusive link field for threads
		// must be exactly as in $thread
		__thread_desc_link link;
	} before, after;

	// spin lock protecting the queue
	volatile bool lock;

	// Optional statistic counters
	#if !defined(__CFA_NO_SCHED_STATS__)
		struct __attribute__((aligned(64))) {
			// difference between number of push and pops
			ssize_t diff;

			// total number of pushes and pops
			size_t  push;
			size_t  pop ;
		} stat;
	#endif
};

void  ?{}(__intrusive_lane_t & this);
void ^?{}(__intrusive_lane_t & this);

// Get the head pointer (one before the first element) from the anchor
static inline $thread * head(const __intrusive_lane_t & this) {
	$thread * rhead = ($thread *)(
		(uintptr_t)( &this.before ) - offsetof( $thread, link )
	);
	/* paranoid */ verify(rhead);
	return rhead;
}

// Get the tail pointer (one after the last element) from the anchor
static inline $thread * tail(const __intrusive_lane_t & this) {
	$thread * rtail = ($thread *)(
		(uintptr_t)( &this.after ) - offsetof( $thread, link )
	);
	/* paranoid */ verify(rtail);
	return rtail;
}

// Ctor
void ?{}( __intrusive_lane_t & this ) {
	this.lock = false;

	this.before.link.prev = 0p;
	this.before.link.next = tail(this);
	this.before.link.ts   = 0;

	this.after .link.prev = head(this);
	this.after .link.next = 0p;
	this.after .link.ts   = 0;

	#if !defined(__CFA_NO_SCHED_STATS__)
		this.stat.diff = 0;
		this.stat.push = 0;
		this.stat.pop  = 0;
	#endif

	// We add a boat-load of assertions here because the anchor code is very fragile
	/* paranoid */ verify(((uintptr_t)( head(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.before));
	/* paranoid */ verify(((uintptr_t)( tail(this) ) + offsetof( $thread, link )) == (uintptr_t)(&this.after ));
	/* paranoid */ verify(head(this)->link.prev == 0p );
	/* paranoid */ verify(head(this)->link.next == tail(this) );
	/* paranoid */ verify(tail(this)->link.next == 0p );
	/* paranoid */ verify(tail(this)->link.prev == head(this) );
	/* paranoid */ verify(&head(this)->link.prev == &this.before.link.prev );
	/* paranoid */ verify(&head(this)->link.next == &this.before.link.next );
	/* paranoid */ verify(&tail(this)->link.prev == &this.after .link.prev );
	/* paranoid */ verify(&tail(this)->link.next == &this.after .link.next );
	/* paranoid */ verify(__alignof__(__intrusive_lane_t) == 128);
	/* paranoid */ verify(__alignof__(this) == 128);
	/* paranoid */ verifyf(((intptr_t)(&this) % 128) == 0, "Expected address to be aligned %p %% 128 == %zd", &this, ((intptr_t)(&this) % 128));
}

// Dtor is trivial
void ^?{}( __intrusive_lane_t & this ) {
	// Make sure the list is empty
	/* paranoid */ verify(head(this)->link.prev == 0p );
	/* paranoid */ verify(head(this)->link.next == tail(this) );
	/* paranoid */ verify(tail(this)->link.next == 0p );
	/* paranoid */ verify(tail(this)->link.prev == head(this) );
}

// Push a thread onto this lane
// returns true of lane was empty before push, false otherwise
bool push(__intrusive_lane_t & this, $thread * node) {
	#if defined(__CFA_WITH_VERIFY__)
		/* paranoid */ verify(this.lock);
		/* paranoid */ verify(node->link.ts != 0);
		/* paranoid */ verify(node->link.next == 0p);
		/* paranoid */ verify(node->link.prev == 0p);
		/* paranoid */ verify(tail(this)->link.next == 0p);
		/* paranoid */ verify(head(this)->link.prev == 0p);

		if(this.before.link.ts == 0l) {
			/* paranoid */ verify(tail(this)->link.prev == head(this));
			/* paranoid */ verify(head(this)->link.next == tail(this));
		} else {
			/* paranoid */ verify(tail(this)->link.prev != head(this));
			/* paranoid */ verify(head(this)->link.next != tail(this));
		}
	#endif

	// Get the relevant nodes locally
	$thread * tail = tail(this);
	$thread * prev = tail->link.prev;

	// Do the push
	node->link.next = tail;
	node->link.prev = prev;
	prev->link.next = node;
	tail->link.prev = node;

	// Update stats
	#if !defined(__CFA_NO_SCHED_STATS__)
		this.stat.diff++;
		this.stat.push++;
	#endif

	verify(node->link.next == tail(this));

	// Check if the queue used to be empty
	if(this.before.link.ts == 0l) {
		this.before.link.ts = node->link.ts;
		/* paranoid */ verify(node->link.prev == head(this));
		return true;
	}
	return false;
}

// Pop a thread from this lane (must be non-empty)
// returns popped
// returns true of lane was empty before push, false otherwise
$thread * pop(__intrusive_lane_t & this) {
	/* paranoid */ verify(this.lock);
	/* paranoid */ verify(this.before.link.ts != 0ul);

	// Get anchors locally
	$thread * head = head(this);
	$thread * tail = tail(this);

	// Get the relevant nodes locally
	$thread * node = head->link.next;
	$thread * next = node->link.next;

	/* paranoid */ verify(node != tail);
	/* paranoid */ verify(node);

	// Do the pop
	head->link.next = next;
	next->link.prev = head;
	node->link.next = 0p;
	node->link.prev = 0p;

	// Update head time stamp
	this.before.link.ts = next->link.ts;

	// Update stats
	#ifndef __CFA_NO_SCHED_STATS__
		this.stat.diff--;
		this.stat.pop ++;
	#endif

	// Check if we emptied list and return accordingly
	/* paranoid */ verify(tail(this)->link.next == 0p);
	/* paranoid */ verify(head(this)->link.prev == 0p);
	if(next == tail) {
		/* paranoid */ verify(this.before.link.ts == 0);
		/* paranoid */ verify(tail(this)->link.prev == head(this));
		/* paranoid */ verify(head(this)->link.next == tail(this));
		return node;
	}
	else {
		/* paranoid */ verify(next->link.ts != 0);
		/* paranoid */ verify(tail(this)->link.prev != head(this));
		/* paranoid */ verify(head(this)->link.next != tail(this));
		/* paranoid */ verify(this.before.link.ts != 0);
		return node;
	}
}

// Check whether or not list is empty
static inline bool is_empty(__intrusive_lane_t & this) {
	// Cannot verify here since it may not be locked
	return this.before.link.ts == 0;
}

// Return the timestamp
static inline unsigned long long ts(__intrusive_lane_t & this) {
	// Cannot verify here since it may not be locked
	return this.before.link.ts;
}