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: 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;

}