---

queue.c

Go to the documentation of this file.

/*!     \file kernel/queue.c
 *      \brief Circular queues operators.
 *      \author Andrea Righi <drizzt@inwind.it>
 *      \date Last update:\n
 *              2003-12-08 Andrea Righi:
 *                      Added find_queue()
 *      \note Copyright (&copy;) 2003 Andrea Righi
 *
 *      \n We assume that elemets' value is univocal in the queue.
 */

#include <const.h>

#include <arch/mem.h>

#include <kernel/kmalloc.h>
#include <kernel/kernel.h>

#include <kernel/queue.h>

//! \brief Get the number of elements presents in the queue.
//! \param q The queue pointer.
//! \return The number of elements in the queue.
//! \exception NULL The queue is empty or not allocated.
int count_queue(queue_t **q)
{
        queue_t *temp;
        int count;

        if (q==NULL) return(NULL);
        if (*q==NULL) return(0);

        temp = *q; count = 0;
        do
        {
                temp = temp->next;
                count++;
        }
        while (temp != *q);

        return(count);
}

//! \brief Get the first element in the queue and update the pointer.
//! \param q The queue pointer.
//! \return The next element in the queue.
//! \exception NULL The queue is empty or not allocated.
void *pick_queue(queue_t **q)
{
        void *__ret;

        if (q==NULL) return(NULL);
        if (*q==NULL) return(NULL);

        __ret = (*q)->value;

        *q=(*q)->next;

        return( __ret );
}

//! \brief Add an element to a circular queue.
//! \param q The queue pointer.
//! \param v The value of the element.
/** \bug
 *      An "out of virtual memory" error can occur
 *      while the new element is added to the queue.
 */
void add_queue(queue_t **q, void *v)
{
        queue_t *p;

        p = (queue_t *)kmalloc(sizeof(queue_t));
        if (p == NULL) error("Out of virtual memory!!!");

        p->value = v;

        if (*q==NULL)
        {
                p->next = p;
                *q=p;
        }
        else
        {
                p->next = (*q)->next;
                (*q)->next = p;
        }
}

//! \brief Remove an element from a circular queue.
//! \param q The queue pointer.
//! \param v The value of the element to remove.
//! \note
//!     We assume that the value of the elements are univocal
//!     in the queue.
//!     Otherwise this routine removes the first occurrence.
int rem_queue(queue_t **q, void *v)
{
        queue_t *t, *t2;

        if (q==NULL) return(FALSE);
        if (*q==NULL) return(FALSE);

        // Search for the element 'v' //
        t = *q;
        do
        {
                t2 = t;
                t = t->next;

                if (t->value == v)
                {
                        // Element found! //
                        t2->next = t->next;

                        if (t == *q)
                        {
                                // Deleting current element //
                                if (t == t->next)
                                        *q = NULL;
                                else
                                        *q = (*q)->next;
                        };
                        kfree(t);
                        return(TRUE);
                }
        } while (t != *q);
        return(FALSE);
}

//! \brief Find an element into a circular queue.
//! \param q The queue pointer.
//! \param v The value of the element to find.
//! \return
//!     \li The element if found;
//!     \li #NULL if the element is not present.
//! \note
//!     We assume that the value of the elements are univocal
//!     in the queue.
//!     Otherwise this routine finds the first occurrence.
void *find_queue(queue_t **q, void *v)
{
        queue_t *t;

        if (q==NULL) return(FALSE);
        if (*q==NULL) return(FALSE);

        // Search for the element 'v'                                   //
        t = *q;
        do
        {
                if (t->value == v)
                {
                        // Element found!                               //
                        return( t->value );
                }
                t = t->next;
        } while (t != *q);
        // Element not found!                                           //
        return( NULL );
}

---