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

queue.c File Reference

Circular queues operators. More...

#include <const.h>
#include <arch/mem.h>
#include <kernel/kmalloc.h>
#include <kernel/kernel.h>
#include <kernel/queue.h>

Go to the source code of this file.

Functions

int count_queue (queue_t **q)
 Get the number of elements presents in the queue.
Parameters:
q  The queue pointer.
Returns:
The number of elements in the queue.
Exceptions:
NULL  The queue is empty or not allocated.


void * pick_queue (queue_t **q)
 Get the first element in the queue and update the pointer.
Parameters:
q  The queue pointer.
Returns:
The next element in the queue.
Exceptions:
NULL  The queue is empty or not allocated.


void add_queue (queue_t **q, void *v)
 Add an element to a circular queue.
Parameters:
q  The queue pointer.
v  The value of the element.


int rem_queue (queue_t **q, void *v)
 Remove an element from a circular queue.
Parameters:
q  The queue pointer.
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.


void * find_queue (queue_t **q, void *v)
 Find an element into a circular queue.
Parameters:
q  The queue pointer.
v  The value of the element to find.
Returns:
  • The element if found;
  • 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.



Detailed Description

Circular queues operators.

Author:
Andrea Righi <drizzt@inwind.it>
Date:
Last update:
2003-12-08 Andrea Righi: Added find_queue()
Note:
Copyright (©) 2003 Andrea Righi

We assume that elemets' value is univocal in the queue.

Definition in file queue.c.


Function Documentation

void add_queue queue_t **    q,
void *    v
 

Add an element to a circular queue.

Parameters:
q  The queue pointer.
v  The value of the element.

Bug:
An "out of virtual memory" error can occur while the new element is added to the queue.

Definition at line 69 of file queue.c.

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 }

int count_queue queue_t **    q
 

Get the number of elements presents in the queue.

Parameters:
q  The queue pointer.
Returns:
The number of elements in the queue.
Exceptions:
NULL  The queue is empty or not allocated.

Definition at line 25 of file queue.c.

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 }

void* find_queue queue_t **    q,
void *    v
 

Find an element into a circular queue.

Parameters:
q  The queue pointer.
v  The value of the element to find.
Returns:
  • The element if found;
  • 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.

Definition at line 141 of file queue.c.

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 }

void* pick_queue queue_t **    q
 

Get the first element in the queue and update the pointer.

Parameters:
q  The queue pointer.
Returns:
The next element in the queue.
Exceptions:
NULL  The queue is empty or not allocated.

Definition at line 48 of file queue.c.

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 }

int rem_queue queue_t **    q,
void *    v
 

Remove an element from a circular queue.

Parameters:
q  The queue pointer.
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.

Definition at line 97 of file queue.c.

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 }


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