/*
    Copyright 2000 (c) by Reto Gaehler, Toni Kaufmann,
    Swiss Federal Institute of Technology,
    Computer Engineering and Networks Laboratory.

    TOPSY -- A Teachable Operating System.
             Implementation of a tiny and simple
             micro kernel for teaching purposes.

    For further information, please visit http://www.tik.ee.ethz.ch/~topsy

    This software is provided under the terms of the GNU General Public 
    Licence. A full copy of the GNU GPL is provided in the file COPYING 
    found in the development root of Topsy.
*/
/*	
    File:                  $Source: /usr/drwho/vault/cvs/topsy/Topsy/Net/TCP/GPQueue.c,v $
    Author(s):             
    Affiliation:           ETH Zuerich, TIK
    Version:               $Revision: 1.2 $
    Creation Date:         
    Last Date of Change:   $Date: 2000/04/03 17:45:30 $      by: $Author: gfa $


    $Log: GPQueue.c,v $
    Revision 1.2  2000/04/03 17:45:30  gfa
    *** empty log message ***

    Revision 1.1  2000/03/31 17:50:37  gfa
    Merged with /Net from several term projects

*/
#include "GPQueue.h"

//**************************************************************************************************
//	GPQueue globals
//**************************************************************************************************
static	int	qinit = FALSE;
static	qinfo Q[MAXNQ];

//**************************************************************************************************
//	pqEnq
//	inserts an element
//**************************************************************************************************
int pqEnq(int q, void *elt, int key)
{
	qinfoptr	qp;
	int			i, j, left;

	if (q < 0 || q >= MAXNQ)
		return GPQ_FAILED;
	if (!Q[q].q_valid || Q[q].q_count >= Q[q].q_max)
		return GPQ_FAILED;

	qp = &Q[q];

	semWait(&qp->q_mutex);

	/* start at tail and move towards head, as long as key is greater */

	/* this shouldn't happen, but... */
	if (qp->q_count < 0)
		qp->q_count = 0;
	i = qp->q_count-1;

	while(i >= 0 && key > qp->q_key[i])
		--i;
	/* i can be -1 (new head) -- it still works */

	for (j = qp->q_count-1; j > i; --j) {
		qp->q_key[j+1] = qp->q_key[j];
		qp->q_elt[j+1] = qp->q_elt[j];
	}
	qp->q_key[i+1] = key;
	qp->q_elt[i+1] = elt;
	qp->q_count++;
	left = qp->q_max - qp->q_count;
	semSignal(&qp->q_mutex);
	
	return left;
}
//**************************************************************************************************
//	pqDeq
//	removes and returns an element
//**************************************************************************************************
void* pqDeq(int q)
{
	qinfoptr	qp;
	char		*elt;
	int			i;

	if (q < 0 || q >= MAXNQ)
		return NULL;
	if (!Q[q].q_valid || Q[q].q_count <= 0)
		return NULL;

	qp = &Q[q];

	semWait(&qp->q_mutex);

	elt = qp->q_elt[0];

	for (i=1; i<qp->q_count; ++i) {
		qp->q_elt[i-1] = qp->q_elt[i];
		qp->q_key[i-1] = qp->q_key[i];
	}
	qp->q_count--;
	semSignal(&qp->q_mutex);
	return(elt);
}
//**************************************************************************************************
//	pqHeadq
//	returns the first element without removing
//**************************************************************************************************
void* pqHeadq(int q)
{
	qinfoptr	qp;
	char		*elt;

	if (q < 0 || q >= MAXNQ)
		return NULL;
	if (!Q[q].q_valid || Q[q].q_count == 0)
		return NULL;

	qp = &Q[q];

	semWait(&qp->q_mutex);

	elt = qp->q_elt[0];
	semSignal(&qp->q_mutex);

	return(elt);
}
//**************************************************************************************************
//	pqSeeq
//	peek at queue elements in order, without removing them
//	return the elements until all out; then return NULL and reset q_seen
//**************************************************************************************************
void* pqSeeq(int q)
{
	qinfoptr	qp;
	char		*elt;

	if (q < 0 || q >= MAXNQ)
		return NULL;
	if (!Q[q].q_valid || Q[q].q_count == 0)
		return NULL;

	qp = &Q[q];

	semWait(&qp->q_mutex);

	qp->q_seen++;
	if (qp->q_seen >= qp->q_count) {
		qp->q_seen = -1;
		semSignal(&qp->q_mutex);
		return NULL;
	}

	elt = qp->q_elt[qp->q_seen];
	semSignal(&qp->q_mutex);

	return(elt);
}
//**************************************************************************************************
//	pqNewq
//	allocate a new queue, return the queue's index
//**************************************************************************************************
int pqNewq(unsigned size)
{
	qinfoptr	qp;
	int 		i;

	if (!qinit)
		pqInitq();
	for (i=0; i<MAXNQ; ++i) {
		if (!Q[i].q_valid)
			break;
	}
	if (i == MAXNQ)
		return GPQ_FAILED;
	qp = &Q[i];
	qp->q_valid = TRUE;
	qp->q_max = size;
	qp->q_count = 0;
	qp->q_seen = -1;
	semInit(&qp->q_mutex,1);
	if (vmAlloc((Address *)&qp->q_elt,sizeof(char *) * size)==VM_ALLOCFAILED)
		return GPQ_FAILED;
	if (vmAlloc((Address *)&qp->q_key,sizeof(int) * size)==VM_ALLOCFAILED)
		return GPQ_FAILED;
	return i;
}
//**************************************************************************************************
//	pqFreeq
//	deallocate a queue
//**************************************************************************************************
int pqFreeq(int q)
{
	qinfoptr	qp;

	if (q < 0 || q >= MAXNQ)
		return GPQ_FAILED;
	if (!Q[q].q_valid || Q[q].q_count != 0)		/* user frees elts */
		return GPQ_FAILED;

	qp = &Q[q];
	/* free resources */
	vmFree((Address)qp->q_key);
	vmFree((Address)qp->q_elt);
	qp->q_valid = FALSE;
	return GPQ_OK;
}
//**************************************************************************************************
//	pqLenq
//	returns number of elements in queue
//**************************************************************************************************
int pqLenq(int q)
{
	if (q < 0 || q >= MAXNQ || !Q[q].q_valid)
		return GPQ_FAILED;
	return Q[q].q_count;
}
//**************************************************************************************************
//	pqInitq
//	initialize the queue
//**************************************************************************************************
int pqInitq()
{
	int i;

	for (i=0; i<MAXNQ; ++i)
		Q[i].q_valid = FALSE;
	qinit = TRUE;
	
	return GPQ_OK;
}