queue.c

/*************************************************************************
*                                                                        *
*   Modulo per la gestione di code generiche                             *
*                                                                        *
*   realizzato dal Gruppo 17 di Lab2 Anno Accademico 1995/96             *
*                                                                        *
*   Lorenzo     Claudio       Valerio    Riccardo    Emiliano            *
*   Coronati    Lanconelli    Paolini    Solmi       Trentini            *
*                                                                        *
**************************************************************************/

/*
 * Invariante:
 *
 * Sia E1, E2, ..., En la sequenza degli eventi di chiamata:
 * E := { insertQueue(tp, x), ins1Queue(tp, x),
 *        x = removeQueue(tp), x = outQueue(tp, x) }
 *
 * Per ogni i, j tale che Ei := insertQueue(tp, x)
 *                        Ej := y = removeQueue(tp)  con i < j
 * se |{Ek; 0 < k < i; Ek := insertQueue(tp, *)}| +
 *    |{Ek; 0 < k < j; Ek := ins1Queue(tp, *)}| =
 *    |{Ek; 0 < k < j; Ek := * = removeQueue(tp); * != NULL}| +
 *    |{Ek; 0 < k < i; Ek := * = outQueue(tp, *); * != NULL}| +
 *    |{Ek; i < k < j; Ek := z = outQueue(tp, z);
 *      (esiste El; 0 < l < j; El := ins1Queue(tp, z))}|
 *  e (per ogni Ek; i < k < j; Ek := * = removeQueue(tp) => * != x)
 *  e (per ogni Ek; i < k < j; Ek := * = outQueue(tp, *) => * != x)
 * => x = y
 *
 * e per ogni i, j tale che Ei := ins1Queue(tp, x)
 *                          Ej := y = removeQueue(tp)  con i < j
 * se |{Ek; i < k < j; Ek := ins1Queue(tp, *)}| =
 *    |{Ek; i < k < j; Ek := * = removeQueue(tp); * != NULL}| +
 *    |{Ek; i < k < j; Ek := z = outQueue(tp, z);
 *      (esiste El; i < l < j; El := ins1Queue(tp, z))}|
 *  e (per ogni Ek; i < k < j; Ek := * = removeQueue(tp) => * != x)
 *  e (per ogni Ek; i < k < j; Ek := * = outQueue(tp, *) => * != x)
 * => x = y
 *
 * e per ogni i, j tale che Ei := insertQueue(tp, x)
 *                          Ej := y = outQueue(tp, x)  con i < j
 * se (per ogni Ek; i < k < j; Ek := * = removeQueue(tp) => * != x)
 *  e (per ogni Ek; i < k < j; Ek := * = outQueue(tp, *) => * != x)
 * => x = y
 *
 * e per ogni i, j tale che Ei := ins1Queue(tp, x)
 *                          Ej := y = outQueue(tp, x)  con i < j
 * se (per ogni Ek; i < k < j; Ek := * = removeQueue(tp) => * != x)
 *  e (per ogni Ek; i < k < j; Ek := * = outQueue(tp, *) => * != x)
 * => x = y
*/

#include "../h/const.h"

typedef struct elem_t
{
    struct elem_t *next;
} elem_t;

/* -----------------------------------------------------------------------
 * Funzioni per la gestione di una free-list, realizzata come una
 * lista concatenata semplice
*/

/*
 * Costruisce la free-list sull'array di elementi passato.
 * Restituisce un puntatore alla free-list.
 * sizeof(array) = noelem * elsize
 * noelem >= 1
 * elsize = sizeof(tipo_elemento_passato)
*/
elem_t *
initQueue(array, noelem, elsize)
elem_t *array;
register int noelem, elsize;
{
    register elem_t *p = array;

    while (--noelem)
        p = p->next = (elem_t *) ((char *) p + elsize);
    p->next = NULL;

    return array;
}

/*
 * Alloca un elemento prelevandolo dalla free-list.
 * Restituisce NULL nel caso la free-list sia vuota
*/
elem_t *
AllocQueue(fp)
register elem_t **fp;
{
    register elem_t *retp = *fp;

    if (retp != NULL)
        *fp = (*fp)->next;

    return retp;
}

/*
 * Dealloca un elemento riponendolo nella free-list
*/
freeQueue(p, fp)
elem_t *p, **fp;
{
    p->next = *fp;
    *fp = p;
}

/* ----------------------------------------------------------------------
 * Funzioni di gestione di code generiche; la coda e` gestita come una
 * lista circolare il cui ultimo elemento e` memorizzato in un puntatore.
 * Nel caso di lista vuota tale puntatore sara` NULL
*/

/*
 * Inserisce in coda
*/
insertQueue(tp, p)
register elem_t **tp, *p;
{
    if (*tp == NULL)
        *tp = p->next = p;
    else
    {
        p->next = (*tp)->next;
        *tp = (*tp)->next = p;
    }
}

/*
 * Inserisce in testa
*/
ins1Queue(tp, p)
register elem_t **tp, *p;
{
    if (*tp == NULL)
        *tp = p->next = p;
    else
    {
        p->next = (*tp)->next;
        (*tp)->next = p;
    }
}

/*
 * Rimuove il primo elemento della coda
*/
elem_t *
removeQueue(tp)
register elem_t **tp;
{
    register elem_t *retp = NULL;

    if (*tp != NULL)
    {
        /*
         * controllo che ci sia piu` di 1 nodo in lista, in caso
         * contrario mettera` il puntatore a NULL (lista vuota)
         */
        if ((retp = (*tp)->next) == *tp)
            *tp = NULL;
        else
            (*tp)->next = retp->next;
    }
    return retp;
}

/*
 * Rimuove un elemento dato dalla coda; se l'elemento cercato
 * non esiste, viene restituito NULL
*/
elem_t *
outQueue(tp, p)
elem_t **tp, *p;
{
    register elem_t *prevp = *tp;

    if (prevp == NULL)
        return NULL;
    else
    {
        /*
         * Se la coda non e' vuota, la scandisce alla ricerca
         * dell'elemento p
         */
        while (prevp->next != p && prevp->next != *tp)
            prevp = prevp->next;

        if (prevp->next == p)
        {
            /* Gestione ultimo elemento della coda */
            if (prevp == prevp->next)
                *tp = NULL;
            else
            {
                /*
                 * Se l'elemento ricercato coincide con
                 * l'ultimo elemento della coda, aggiorna il
                 * puntatore tp
                 */
                if (p == *tp)
                    *tp = prevp;
                prevp->next = p->next;
            }
            return p;
        } else
            return NULL;
    }
}

/*
 * Restituisce il puntatore al primo elemento della coda
*/
elem_t *
headQueue(tp)
elem_t *tp;
{
    return (tp == NULL) ? (elem_t *) NULL : tp->next;
}