/*
 * Copyright (C) 1998 by the Board of Trustees
 *    of Leland Stanford Junior University.
 * Copyright (C) 1998 Digital Equipment Corporation
 *
 * This file is part of the SimOS distribution.
 * See LICENSE file for terms of the license.
 *
 */

#ifndef _WHEEL_H_
#define _WHEEL_H_

/* to manage the time wheel */

#include "protos.h"
#include "task.h"

/* WHEEL_SIZE must be a power of two */
#define WHEEL_SIZE 32768
#define WHEEL_MASK (WHEEL_SIZE-1)

/* use only the fields we need and pad the size until it is a power of 2 */
typedef struct wheel_ask {
    struct task *next;
    struct task *prev;
    aint_time_t time;
    int priority;
} wheel_task_t, *wheel_task_ptr;

extern wheel_task_ptr wheel;
extern wheel_task_ptr current_ptr;
extern wheel_task_ptr end_ptr;
extern aint_time_t start_time;
extern aint_time_t end_time;
extern task_ptr future_q;

extern void wheel_init ();
extern int wheel_empty ();
extern int task_cleanup ();

/* Define macros */
#define INLINE_TASK_EXTRACT(pnew) pnew = task_extract()
#define INLINE_TASK_INSERT(pnew) task_insert(pnew)
task_ptr task_pull_from_future ();

#ifdef __GNUC__
static inline
#else
#  pragma inline(task_extract)
static
#endif
task_ptr 
task_extract ()
{
    task_ptr pnew;

    /* search the time wheel first */
    pnew = current_ptr->next;
    if (pnew != (task_ptr) current_ptr) {
	INLINE_REMOVE (pnew);
	return pnew;
    }
    else {

	task_ptr tptr, next;

	while (1) {

	    /*
	     * Search the queues until we get to the end. Since we put a
             * dummy item  in the last (unused) queue, we don't need to
             * check for overflow of the * current_ptr in each iteration
	     */

	    do {
		current_ptr++;
		pnew = current_ptr->next;
	    } while (pnew == (task_ptr) current_ptr);

	    /* if we found a tsk, remove it and return */
	    if (current_ptr != end_ptr) {
		INLINE_REMOVE (pnew);
		return (pnew);
	    }

	    /* Wrap around processing */
	    current_ptr = &wheel[0];
	    end_time += WHEEL_SIZE;
	    start_time += WHEEL_SIZE;
	    pnew = future_q->next;
	    if (pnew == future_q)
		return NULL;

	    for (; pnew != future_q; pnew = next) {
		int diff = pnew->time - start_time;
		next = pnew->next;

		if (diff < WHEEL_SIZE) {
		    /* insert in priority order */
		    for (tptr = wheel[diff].prev;
			 tptr->priority < pnew->priority;
			 tptr = tptr->prev);

		    INLINE_REMOVE (pnew);
		    INLINE_INSERT_AFTER (tptr, pnew);
		}
	    }

	    pnew = current_ptr->next;
	    if (pnew != (task_ptr) current_ptr) {
		INLINE_REMOVE (pnew);
		return pnew;
	    }
	}
    }
}

#ifdef __GNUC__
static inline
#else
#pragma inline(task_insert)
static
#endif
void
task_insert (task_ptr ptask)
{
    int index;
    task_ptr tptr;

    /* printf("task_insert: time is %d\n", (int) ptask->time); */
    index = ptask->time - start_time;

    if (index < WHEEL_SIZE) {
	/*
	 * insert in priority order
	 */
	for (tptr = wheel[index].prev;
	     tptr->priority < ptask->priority;
	     tptr = tptr->prev) {
	    /*
	     * Empty statement
	     */
	}
	INLINE_INSERT_AFTER (tptr, ptask);
    }
    else {
	INLINE_ENQUEUE (future_q, ptask);
    }
}

#endif /* _WHEEL_H_ */