/*
 * 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