Subversion Repositories shark

/*
 * 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: queue.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>

/*
 *
 * QUEUE Functions
 *
 */

/*+
  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 q_insert(PID i, QUEUE *que)
{
    DWORD prio;
    PID p,q;

    p = NIL;
    q = *que;
    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 = i;

    if (q != NIL) proc_table[q].prev = 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 q_timespec_insert(PID i, QUEUE *que)
{
    struct timespec prio;
    PID p,q;

    p = NIL;
    q = *que;

    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 = i;

    if (q != NIL) proc_table[q].prev = 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 q_extract(PID i, QUEUE *que)
{
    PID p,q;

    p = proc_table[i].prev;
    q = proc_table[i].next;

    if (p == NIL) *que = q;
    else proc_table[p].next = proc_table[i].next;

    if (q != NIL) proc_table[q].prev = proc_table[i].prev;
}

/*+
  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 q_getfirst(QUEUE *que)
{
    QUEUE q = *que;
    if (*que == NIL) return(NIL);
    *que = proc_table[q].next;
    if (*que != NIL) proc_table[*que].prev = NIL;
    return(q);
}

/*+
  This function insert the task with PID p in the first position
  of the queue que redardless of the priority field
+*/

void q_insertfirst(PID i, QUEUE *que)
{
    if (*que != NIL) proc_table[*que].prev = i;
    proc_table[i].next = *que;
    proc_table[i].prev = NIL;
    *que = i;
}