/*
 * Copyright (C) 2007 Fabio Checconi <fabio@gandalf.sssup.it>,
 *		      Paolo Valente <paolo.valente@unimore.it>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License version 2 as
 * published by the Free Software Foundation.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
 */
 
#ifndef _WFQ_H
#define _WFQ_H

#include <string.h>

#include <linux/rbtree.h>
#include <linux/types.h>
#include <asm/div64.h>

typedef u64 wfq_timestamp_t;
typedef unsigned long wfq_weight_t;
typedef unsigned long wfq_service_t;

/**
 * struct wfq_queue - queue handled by a WF2Q+ scheduler
 * @active:		tree of active entities.
 * @idle:		tree of idle entities.
 * @active_entity:	entity being served.
 * @first_idle:		leftmost entity in the idle tree.
 * @last_idle:		rightmost entity in the idle tree.
 * @nr_entities:	total number of entities.
 * @vtime:		virtual time.
 * @weight_sum:		sum of the weights of the entities.
 * @get_entity:		get method for entity refcounting.
 * @put_entity:		put method for entity refcounting.
 */
struct wfq_queue {
	struct rb_root active;
	struct rb_root idle;

	struct wfq_entity *active_entity;
	struct wfq_entity *first_idle;
	struct wfq_entity *last_idle;
	int nr_entities;

	wfq_timestamp_t vtime;

	wfq_weight_t weight_sum;

	void (*get_entity)(struct wfq_entity *entity);
	struct wfq_entity *(*put_entity)(struct wfq_entity *entity);
};

/**
 * struct wfq_entity - entity managed by a WF2Q+ scheduler
 * @finish:		finish time.
 * @start:		start time.
 * @tree:		root of tree the activity is enqueued on.
 * @node:		link into the tree.
 * @min_start:		min start time in the subtree rooted at this entity.
 * @weight:		weight of the entity.
 * @size:		amount of service requested by the activity.
 * @queue:		if not %NULL, the contained queue.
 *
 * @queue is used for hierarchical scheduling.
 */
struct wfq_entity {
	wfq_timestamp_t finish;
	wfq_timestamp_t start;

	struct rb_root *tree;
	struct rb_node node;

	wfq_timestamp_t min_start;

	wfq_weight_t weight;
	wfq_service_t size;

	struct wfq_queue *queue;
};

/**
 * wfq_enqueue - enqueue an entity in a queue
 * @queue:		the queue.
 * @entity:		the entity.
 * @service:		the amount of service requested.
 */
void wfq_enqueue(struct wfq_queue *queue, struct wfq_entity *entity,
		 wfq_service_t service);

/**
 * wfq_dequeue - dequeue an entity
 * @queue:		the queue.
 * @entity:		the entity.
 *
 * The entity is dequeued and its finish time is decreased according to
 * the entity size, be careful to update the service it received.
 */
void wfq_dequeue(struct wfq_queue *queue, struct wfq_entity *entity);

/**
 * wfq_next - select the next entity to be served
 * @queue:		the queue.
 *
 * Returns the selected entity, NULL if @qp is empty.
 */
struct wfq_entity *wfq_next(struct wfq_queue *queue);

/**
 * wfq_update_size - try to resize an entity
 * @queue:		the queue.
 * @entity:		the entity.
 * @service:		the new amount of service.
 *
 * Try to update the @entity timestamps according to the new amount
 * of service it requires.  Cannot be called for the entity being served.
 */
void wfq_update_size(struct wfq_queue *queue, struct wfq_entity *entity,
		     wfq_service_t service);

/**
 * wfq_served - update the scheduler status after service
 * @queue:		the queue.
 * @served:		the amount of service.
 */
void wfq_served(struct wfq_queue *queue, wfq_service_t served);

/**
 * wfq_service_left - return the amount of service left to an entity
 * @entity:		the entity.
 */
static inline wfq_service_t wfq_service_left(struct wfq_entity *entity)
{
	return entity->size;
}

/**
 * wfq_entity_get - get a reference to an entity
 * @queue:		the queue containing the entity.
 * @entity:		the entity to reference.
 *
 * The reference counter is not atomic, so the caller has to take care
 * of concurrency issues.
 */
static inline void wfq_entity_get(struct wfq_queue *queue,
				  struct wfq_entity *entity)
{
	if (queue->get_entity != NULL)
		queue->get_entity(entity);
}

/**
 * wfq_entity_put - put a reference to an entity, and release it if necessary
 * @queue:		the queue containing the entity.
 * @entity:		the entity to release.
 *
 * Return the value returned by queue->put_entity(entity), @entity
 * if @queue has no @put_entity member.
 */
static inline struct wfq_entity *wfq_entity_put(struct wfq_queue *queue,
						struct wfq_entity *entity)
{
	if (queue->put_entity !=  NULL)
		return queue->put_entity(entity);

	return entity;
}

/**
 * wfq_init_queue - initialize a queue
 * @queue:		the queue to initialize.
 */
static inline void wfq_init_queue(struct wfq_queue *queue)
{
	memset(queue, 0, sizeof(*queue));
	queue->active = RB_ROOT;
	queue->idle = RB_ROOT;
}

#endif