/*
 * Copyright 2013 Haiku, Inc. All rights reserved.
 * Distributed under the terms of the MIT License.
 *
 * Authors:
 *		Paweł Dziepak, pdziepak@quarnos.org
 */
#ifndef RUN_QUEUE_H
#define RUN_QUEUE_H


#include <util/Heap.h>

#include "scheduler_profiler.h"


template<typename Element>
struct RunQueueLink {
					RunQueueLink();

	unsigned int	fPriority;
	Element*		fPrevious;
	Element*		fNext;
};

template<typename Element>
class RunQueueLinkImpl {
public:
	inline	RunQueueLink<Element>*	GetRunQueueLink();

private:
			RunQueueLink<Element>	fRunQueueLink;
};

template<typename Element>
class RunQueueStandardGetLink {
private:
	typedef RunQueueLink<Element> Link;

public:
	inline	Link*		operator()(Element* element) const;
};

template<typename Element, RunQueueLink<Element> Element::*LinkMember>
class RunQueueMemberGetLink {
private:
	typedef RunQueueLink<Element> Link;

public:
	inline	Link*		operator()(Element* element) const;
};

#define RUN_QUEUE_TEMPLATE_LIST	\
	template<typename Element, unsigned int MaxPriority, typename GetLink>
#define RUN_QUEUE_CLASS_NAME	RunQueue<Element, MaxPriority, GetLink>

template<typename Element, unsigned int MaxPriority,
	typename GetLink = RunQueueStandardGetLink<Element> >
class RunQueue {
public:
	class ConstIterator {
	public:
								ConstIterator();
								ConstIterator(const RunQueue<Element,
										MaxPriority, GetLink>* list);

		inline	ConstIterator&	operator=(const ConstIterator& other);

				bool			HasNext() const;
				Element*		Next();

				void			Rewind();

	private:
		inline	void			_FindNextPriority();

				const RUN_QUEUE_CLASS_NAME*	fList;
				unsigned int	fPriority;
				Element*		fNext;

		static	GetLink			sGetLink;
	};

						RunQueue();

	inline	status_t	GetInitStatus();

	inline	Element*	PeekMaximum() const;

	inline	void		PushFront(Element* element, unsigned int priority);
	inline	void		PushBack(Element* elementt, unsigned int priority);

	inline	void		Remove(Element* element);

	inline	Element*	GetHead(unsigned int priority) const;

	inline	ConstIterator	GetConstIterator() const;

private:
	struct PriorityEntry : public HeapLinkImpl<PriorityEntry, unsigned int>
	{
	};

	typedef Heap<PriorityEntry, unsigned int, HeapGreaterCompare<unsigned int> >
		PriorityHeap;

			status_t	fInitStatus;

			PriorityEntry	fPriorityEntries[MaxPriority + 1];
			PriorityHeap	fPriorityHeap;

			Element*	fHeads[MaxPriority + 1];
			Element*	fTails[MaxPriority + 1];

	static	GetLink		sGetLink;
};


template<typename Element>
RunQueueLink<Element>::RunQueueLink()
	:
	fPrevious(NULL),
	fNext(NULL)
{
}


template<typename Element>
RunQueueLink<Element>*
RunQueueLinkImpl<Element>::GetRunQueueLink()
{
	return &fRunQueueLink;
}


template<typename Element>
RunQueueLink<Element>*
RunQueueStandardGetLink<Element>::operator()(Element* element) const
{
	return element->GetRunQueueLink();
}


template<typename Element, RunQueueLink<Element> Element::*LinkMember>
RunQueueLink<Element>*
RunQueueMemberGetLink<Element, LinkMember>::operator()(Element* element) const
{
	return &(element->*LinkMember);
}


RUN_QUEUE_TEMPLATE_LIST
RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator()
	:
	fList(NULL)
{
}


RUN_QUEUE_TEMPLATE_LIST
RUN_QUEUE_CLASS_NAME::ConstIterator::ConstIterator(const RunQueue<Element,
		MaxPriority, GetLink>* list)
	:
	fList(list)
{
	Rewind();
}


RUN_QUEUE_TEMPLATE_LIST
typename RUN_QUEUE_CLASS_NAME::ConstIterator&
RUN_QUEUE_CLASS_NAME::ConstIterator::operator=(const ConstIterator& other)
{
	fList = other.fList;
	fPriority = other.fPriority;
	fNext = other.fNext;

	return *this;
}


RUN_QUEUE_TEMPLATE_LIST
bool
RUN_QUEUE_CLASS_NAME::ConstIterator::HasNext() const
{
	return fNext != NULL;
}


RUN_QUEUE_TEMPLATE_LIST
Element*
RUN_QUEUE_CLASS_NAME::ConstIterator::Next()
{
	ASSERT(HasNext());

	Element* current = fNext;
	RunQueueLink<Element>* link = sGetLink(fNext);

	fNext = link->fNext;
	if (fNext == NULL)
		_FindNextPriority();

	return current;
}


RUN_QUEUE_TEMPLATE_LIST
void
RUN_QUEUE_CLASS_NAME::ConstIterator::Rewind()
{
	ASSERT(fList != NULL);

	fPriority = MaxPriority;
	fNext = fList->GetHead(fPriority);
	if (fNext == NULL)
		_FindNextPriority();
}


RUN_QUEUE_TEMPLATE_LIST
void
RUN_QUEUE_CLASS_NAME::ConstIterator::_FindNextPriority()
{
	ASSERT(fList != NULL);

	while (fPriority-- > 0) {
		fNext = fList->GetHead(fPriority);
		if (fNext != NULL)
			break;
	}
}


RUN_QUEUE_TEMPLATE_LIST
RUN_QUEUE_CLASS_NAME::RunQueue()
	:
	fInitStatus(B_OK),
	fPriorityHeap(MaxPriority + 1)
{
	memset(fHeads, 0, sizeof(fHeads));
	memset(fTails, 0, sizeof(fTails));
}


RUN_QUEUE_TEMPLATE_LIST
status_t
RUN_QUEUE_CLASS_NAME::GetInitStatus()
{
	return fInitStatus;
}


RUN_QUEUE_TEMPLATE_LIST
Element*
RUN_QUEUE_CLASS_NAME::PeekMaximum() const
{
	SCHEDULER_ENTER_FUNCTION();

	PriorityEntry* maxPriority = fPriorityHeap.PeekRoot();
	if (maxPriority == NULL)
		return NULL;
	unsigned int priority = PriorityHeap::GetKey(maxPriority);

	ASSERT(priority <= MaxPriority);
	ASSERT(fHeads[priority] != NULL);

	Element* element = fHeads[priority];

	ASSERT(sGetLink(element)->fPriority == priority);
	ASSERT(fTails[priority] != NULL);
	ASSERT(sGetLink(element)->fPrevious == NULL);

	return element;
}


RUN_QUEUE_TEMPLATE_LIST
void
RUN_QUEUE_CLASS_NAME::PushFront(Element* element,
	unsigned int priority)
{
	SCHEDULER_ENTER_FUNCTION();

	ASSERT(priority <= MaxPriority);

	RunQueueLink<Element>* elementLink = sGetLink(element);

	ASSERT(elementLink->fPrevious == NULL);
	ASSERT(elementLink->fNext == NULL);

	ASSERT((fHeads[priority] == NULL && fTails[priority] == NULL)
		|| (fHeads[priority] != NULL && fTails[priority] != NULL));

	elementLink->fPriority = priority;
	elementLink->fNext = fHeads[priority];
	if (fHeads[priority] != NULL)
		sGetLink(fHeads[priority])->fPrevious = element;
	else {
		fTails[priority] = element;
		fPriorityHeap.Insert(&fPriorityEntries[priority], priority);
	}
	fHeads[priority] = element;
}


RUN_QUEUE_TEMPLATE_LIST
void
RUN_QUEUE_CLASS_NAME::PushBack(Element* element,
	unsigned int priority)
{
	SCHEDULER_ENTER_FUNCTION();

	ASSERT(priority <= MaxPriority);

	RunQueueLink<Element>* elementLink = sGetLink(element);

	ASSERT(elementLink->fPrevious == NULL);
	ASSERT(elementLink->fNext == NULL);

	ASSERT((fHeads[priority] == NULL && fTails[priority] == NULL)
		|| (fHeads[priority] != NULL && fTails[priority] != NULL));

	elementLink->fPriority = priority;
	elementLink->fPrevious = fTails[priority];
	if (fTails[priority] != NULL)
		sGetLink(fTails[priority])->fNext = element;
	else {
		fHeads[priority] = element;
		fPriorityHeap.Insert(&fPriorityEntries[priority], priority);
	}
	fTails[priority] = element;
}


RUN_QUEUE_TEMPLATE_LIST
void
RUN_QUEUE_CLASS_NAME::Remove(Element* element)
{
	SCHEDULER_ENTER_FUNCTION();

	RunQueueLink<Element>* elementLink = sGetLink(element);
	unsigned int priority = elementLink->fPriority;

	ASSERT(elementLink->fPrevious != NULL || fHeads[priority] == element);
	ASSERT(elementLink->fNext != NULL || fTails[priority] == element);

	if (elementLink->fPrevious != NULL)
		sGetLink(elementLink->fPrevious)->fNext = elementLink->fNext;
	else
		fHeads[priority] = elementLink->fNext;
	if (elementLink->fNext != NULL)
		sGetLink(elementLink->fNext)->fPrevious = elementLink->fPrevious;
	else
		fTails[priority] = elementLink->fPrevious;

	ASSERT((fHeads[priority] == NULL && fTails[priority] == NULL)
		|| (fHeads[priority] != NULL && fTails[priority] != NULL));

	if (fHeads[priority] == NULL) {
		fPriorityHeap.ModifyKey(&fPriorityEntries[priority], MaxPriority + 1);
		ASSERT(fPriorityHeap.PeekRoot() == &fPriorityEntries[priority]);
		fPriorityHeap.RemoveRoot();
	}

	elementLink->fPrevious = NULL;
	elementLink->fNext = NULL;
}


RUN_QUEUE_TEMPLATE_LIST
Element*
RUN_QUEUE_CLASS_NAME::GetHead(unsigned int priority) const
{
	SCHEDULER_ENTER_FUNCTION();

	ASSERT(priority <= MaxPriority);
	return fHeads[priority];
}


RUN_QUEUE_TEMPLATE_LIST
typename RUN_QUEUE_CLASS_NAME::ConstIterator
RUN_QUEUE_CLASS_NAME::GetConstIterator() const
{
	return ConstIterator(this);
}


RUN_QUEUE_TEMPLATE_LIST
GetLink RUN_QUEUE_CLASS_NAME::sGetLink;

RUN_QUEUE_TEMPLATE_LIST
GetLink RUN_QUEUE_CLASS_NAME::ConstIterator::sGetLink;


#endif	// RUN_QUEUE_H