Blame |
Last modification |
View Log
| RSS feed
/*
* Project: S.Ha.R.K.
*
* Coordinators:
* Giorgio Buttazzo <giorgio@sssup.it>
* Paolo Gai <pj@gandalf.sssup.it>
*
* Authors :
* Paolo Gai <pj@gandalf.sssup.it>
* (see the web pages for full authors list)
*
* ReTiS Lab (Scuola Superiore S.Anna - Pisa - Italy)
*
* http://www.sssup.it
* http://retis.sssup.it
* http://shark.sssup.it
*/
/**
------------
CVS : $Id: qqueue.c,v 1.1.1.1 2002-03-29 14:12:52 pj Exp $
File: $File$
Revision: $Revision: 1.1.1.1 $
Last update: $Date: 2002-03-29 14:12:52 $
------------
This file contains the system queues function management
The functions use the general process descriptor table entries,
particularly the next & prev to mantain the queues order;
the insertion is based on the field priority, inserted in generic process
descriptor to simplify the implementation of many schedulers (like EDF,
RM, DM, etc.)
There are 2 queue types:
QUEUE -> a simple queue with only head.
QQUEUE -> a queue that manage the head and the tail of the queue
... and 2 queue function sets, beginning with q_ if related to the type
QUEUE, qq_ if related to the other type.
The queue insertion is made by the following functions:
q_insert, qq_insert -> insertion based on the priority field.
q_timespec_insert, qq_timespec_insert -> same as above but use
the timespec_priority field
q_insertfirst, qq_insertfirst -> insert in the first position of the queue
**/
/*
* Copyright (C) 2000 Paolo Gai
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* 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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*
*/
#include <kernel/const.h>
#include <sys/types.h>
#include <kernel/var.h>
/*
*
* QQUEUE Functions
*
*/
/*+ This function initialize a QQUEUE +*/
void qq_init(QQUEUE *que)
{
que->first = NIL;
que->last = NIL;
}
/*+
This function insert the task with PID p in the queue que.
The insertion is made respecting the priority field.
(the first item in the queue have the less priority)
+*/
void qq_insert(PID i, QQUEUE *que)
{
DWORD prio;
PID p,q;
p = NIL;
q = que->first;
prio = proc_table[i].priority;
while ((q != NIL) && (prio >= proc_table[q].priority)) {
p = q;
q = proc_table[q].next;
}
if (p != NIL)
proc_table[p].next = i;
else
que->first = i;
if (q != NIL)
proc_table[q].prev = i;
else
que->last = i;
proc_table[i].next = q;
proc_table[i].prev = p;
}
/*+
This function insert the task with PID p in the queue que.
The insertion is made respecting the timespec priority field.
(the first item in the queue have the less priority)
+*/
void qq_timespec_insert(PID i, QQUEUE *que)
{
struct timespec prio;
PID p,q;
p = NIL;
q = que->first;
TIMESPEC_ASSIGN(&prio, &proc_table[i].timespec_priority);
while ((q != NIL) &&
!TIMESPEC_A_LT_B(&prio, &proc_table[q].timespec_priority)) {
p = q;
q = proc_table[q].next;
}
if (p != NIL)
proc_table[p].next = i;
else
que->first = i;
if (q != NIL)
proc_table[q].prev = i;
else
que->last = i;
proc_table[i].next = q;
proc_table[i].prev = p;
}
/*+
This function extract the task i from the queue que.
It not check if the task i is REALLY IN the queue que...
so make attention!!!
+*/
void qq_extract(PID i, QQUEUE *que)
{
PID p,q;
p = proc_table[i].prev;
q = proc_table[i].next;
if (p != NIL)
proc_table[p].next = proc_table[i].next;
else
que->first = q;
if (q != NIL)
proc_table[q].prev = proc_table[i].prev;
else
que->last = p;
}
/*+
This function returns the first task in the queue que, or NIL if the
queue is empty... (it extracts the task from the queue...)
+*/
PID qq_getfirst(QQUEUE *q)
{
PID p = q->first;
if (p == NIL) return(NIL);
q->first = proc_table[q->first].next;
if (q->first != NIL)
proc_table[q->first].prev = NIL;
else
q->last = NIL;
return(p);
}
/*+
This function insert the task with PID p in the first position
of the queue que redardless of the priority field
+*/
void qq_insertfirst(PID p, QQUEUE *que)
{
if (que->first != NIL) {
proc_table[p].next = que->first;
proc_table[que->first].prev = p;
}
else {
que->last = p;
proc_table[p].next = NIL;
}
proc_table[p].prev = NIL;
que->first = p;
}
/*+
This function insert the task with PID p in the last position
of the queue que redardless of the priority field
+*/
void qq_insertlast(PID p, QQUEUE *que)
{
if (que->last != NIL) {
proc_table[p].prev = que->last;
proc_table[que->last].next = p;
}
else {
que->first = p;
proc_table[p].prev = NIL;
}
proc_table[p].next = NIL;
que->last = p;
}
/*+
This function returns the first task in the queue que, without removing it
+*/
PID qq_queryfirst(QQUEUE *q)
{
return q->first;
}
/*+
This function returns the last task in the queue que, without removing it
+*/
PID qq_querylast(QQUEUE *q)
{
return q->last;
}