Main Page   Modules   Alphabetical List   Data Structures   File List   Data Fields   Globals   Related Pages  

queue.c

Go to the documentation of this file.
00001 /*!     \file kernel/queue.c
00002  *      \brief Circular queues operators.
00003  *      \author Andrea Righi <drizzt@inwind.it>
00004  *      \date Last update:\n
00005  *              2003-12-08 Andrea Righi:
00006  *                      Added find_queue()
00007  *      \note Copyright (&copy;) 2003 Andrea Righi
00008  *
00009  *      \n We assume that elemets' value is univocal in the queue.
00010  */
00011 
00012 #include <const.h>
00013 
00014 #include <arch/mem.h>
00015 
00016 #include <kernel/kmalloc.h>
00017 #include <kernel/kernel.h>
00018 
00019 #include <kernel/queue.h>
00020 
00021 //! \brief Get the number of elements presents in the queue.
00022 //! \param q The queue pointer.
00023 //! \return The number of elements in the queue.
00024 //! \exception NULL The queue is empty or not allocated.
00025 int count_queue(queue_t **q)
00026 {
00027         queue_t *temp;
00028         int count;
00029 
00030         if (q==NULL) return(NULL);
00031         if (*q==NULL) return(0);
00032 
00033         temp = *q; count = 0;
00034         do
00035         {
00036                 temp = temp->next;
00037                 count++;
00038         }
00039         while (temp != *q);
00040 
00041         return(count);
00042 }
00043 
00044 //! \brief Get the first element in the queue and update the pointer.
00045 //! \param q The queue pointer.
00046 //! \return The next element in the queue.
00047 //! \exception NULL The queue is empty or not allocated.
00048 void *pick_queue(queue_t **q)
00049 {
00050         void *__ret;
00051 
00052         if (q==NULL) return(NULL);
00053         if (*q==NULL) return(NULL);
00054 
00055         __ret = (*q)->value;
00056 
00057         *q=(*q)->next;
00058 
00059         return( __ret );
00060 }
00061 
00062 //! \brief Add an element to a circular queue.
00063 //! \param q The queue pointer.
00064 //! \param v The value of the element.
00065 /** \bug
00066  *      An "out of virtual memory" error can occur
00067  *      while the new element is added to the queue.
00068  */
00069 void add_queue(queue_t **q, void *v)
00070 {
00071         queue_t *p;
00072 
00073         p = (queue_t *)kmalloc(sizeof(queue_t));
00074         if (p == NULL) error("Out of virtual memory!!!");
00075 
00076         p->value = v;
00077 
00078         if (*q==NULL)
00079         {
00080                 p->next = p;
00081                 *q=p;
00082         }
00083         else
00084         {
00085                 p->next = (*q)->next;
00086                 (*q)->next = p;
00087         }
00088 }
00089 
00090 //! \brief Remove an element from a circular queue.
00091 //! \param q The queue pointer.
00092 //! \param v The value of the element to remove.
00093 //! \note
00094 //!     We assume that the value of the elements are univocal
00095 //!     in the queue.
00096 //!     Otherwise this routine removes the first occurrence.
00097 int rem_queue(queue_t **q, void *v)
00098 {
00099         queue_t *t, *t2;
00100 
00101         if (q==NULL) return(FALSE);
00102         if (*q==NULL) return(FALSE);
00103 
00104         // Search for the element 'v' //
00105         t = *q;
00106         do
00107         {
00108                 t2 = t;
00109                 t = t->next;
00110 
00111                 if (t->value == v)
00112                 {
00113                         // Element found! //
00114                         t2->next = t->next;
00115 
00116                         if (t == *q)
00117                         {
00118                                 // Deleting current element //
00119                                 if (t == t->next)
00120                                         *q = NULL;
00121                                 else
00122                                         *q = (*q)->next;
00123                         };
00124                         kfree(t);
00125                         return(TRUE);
00126                 }
00127         } while (t != *q);
00128         return(FALSE);
00129 }
00130 
00131 //! \brief Find an element into a circular queue.
00132 //! \param q The queue pointer.
00133 //! \param v The value of the element to find.
00134 //! \return
00135 //!     \li The element if found;
00136 //!     \li #NULL if the element is not present.
00137 //! \note
00138 //!     We assume that the value of the elements are univocal
00139 //!     in the queue.
00140 //!     Otherwise this routine finds the first occurrence.
00141 void *find_queue(queue_t **q, void *v)
00142 {
00143         queue_t *t;
00144 
00145         if (q==NULL) return(FALSE);
00146         if (*q==NULL) return(FALSE);
00147 
00148         // Search for the element 'v'                                   //
00149         t = *q;
00150         do
00151         {
00152                 if (t->value == v)
00153                 {
00154                         // Element found!                               //
00155                         return( t->value );
00156                 }
00157                 t = t->next;
00158         } while (t != *q);
00159         // Element not found!                                           //
00160         return( NULL );
00161 }

Generated on Fri Feb 20 15:32:16 2004 for Minirighi by doxygen1.2.18