root / branches / autonomous_recharging / code / projects / autonomous_recharging / charging_station / queue.c @ 213
History | View | Annotate | Download (2.46 KB)
1 |
#include "queue.h" |
---|---|
2 |
#include <wl_defs.h> |
3 |
|
4 |
#include <stdlib.h> |
5 |
#include <stdio.h> |
6 |
|
7 |
/**
|
8 |
* @struct node_def
|
9 |
* A node in the queue.
|
10 |
**/
|
11 |
typedef struct node_def |
12 |
{ |
13 |
/** The item at this point in the queue. **/
|
14 |
void* val;
|
15 |
/** The next node in the queue. **/
|
16 |
struct node_def* next;
|
17 |
} Node; |
18 |
|
19 |
/**
|
20 |
* Create a queue.
|
21 |
*
|
22 |
* @return the newly created queue.
|
23 |
**/
|
24 |
Queue* queue_create() |
25 |
{ |
26 |
Queue* q = (Queue*)malloc(sizeof(Queue));
|
27 |
|
28 |
if (q == NULL) |
29 |
{ |
30 |
WL_DEBUG_PRINT("Out of memory.\r\n");
|
31 |
return NULL; |
32 |
} |
33 |
|
34 |
q->head = NULL;
|
35 |
q->size = 0;
|
36 |
return q;
|
37 |
} |
38 |
|
39 |
/**
|
40 |
* Destroys a queue, freeing memory.
|
41 |
*
|
42 |
* @param q the queue to destroy
|
43 |
**/
|
44 |
void queue_destroy(Queue* q)
|
45 |
{ |
46 |
Node* t = q->head; |
47 |
while (t != NULL) |
48 |
{ |
49 |
Node* t2 = t->next; |
50 |
free(t); |
51 |
t = t2; |
52 |
} |
53 |
free(q); |
54 |
} |
55 |
|
56 |
/**
|
57 |
* Add an element to a queue.
|
58 |
*
|
59 |
* @param q the queue to add an element to
|
60 |
* @param item the item to add to the queue
|
61 |
**/
|
62 |
void queue_add(Queue* q, void* item) |
63 |
{ |
64 |
Node* n = (Node*)malloc(sizeof(Node));
|
65 |
n->val = item; |
66 |
n->next = NULL;
|
67 |
|
68 |
if (q->head == NULL) |
69 |
{ |
70 |
q->head = n; |
71 |
q->tail = n; |
72 |
} |
73 |
else
|
74 |
{ |
75 |
q->tail->next = n; |
76 |
q->tail = n; |
77 |
} |
78 |
|
79 |
q->size++; |
80 |
} |
81 |
|
82 |
/**
|
83 |
* Remove an element from the front of a queue.
|
84 |
*
|
85 |
* @param q the queue to remove the element from
|
86 |
*
|
87 |
* @return the element which was removed
|
88 |
**/
|
89 |
void* queue_remove(Queue* q)
|
90 |
{ |
91 |
Node* first = q->head; |
92 |
if (first == NULL) |
93 |
{ |
94 |
WL_DEBUG_PRINT("Attempting to remove item \
|
95 |
from empty queue.\r\n");
|
96 |
WL_DEBUG_PRINT_INT(queue_size(q)); |
97 |
} |
98 |
void* ret = first->val;
|
99 |
q->head = first->next; |
100 |
if (q->tail == first)
|
101 |
q->tail = NULL;
|
102 |
free(first); |
103 |
q->size--; |
104 |
return ret;
|
105 |
} |
106 |
|
107 |
/**
|
108 |
* Remove all instances of a given element from a queue.
|
109 |
*
|
110 |
* @param q the queue to remove the elements from
|
111 |
* @param item the element to remove all instances of
|
112 |
**/
|
113 |
void queue_remove_all(Queue* q, void* item) |
114 |
{ |
115 |
Node* curr = q->head; |
116 |
Node* prev = NULL;
|
117 |
|
118 |
while (curr != NULL) |
119 |
{ |
120 |
Node* next = curr->next; |
121 |
if (curr->val == item)
|
122 |
{ |
123 |
if (q->head == curr)
|
124 |
q->head = next; |
125 |
if (q->tail == curr)
|
126 |
q->tail = prev; |
127 |
if (prev != NULL) |
128 |
prev->next = next; |
129 |
free(curr); |
130 |
q->size--; |
131 |
} |
132 |
else
|
133 |
prev = curr; |
134 |
curr = next; |
135 |
} |
136 |
} |
137 |
|
138 |
/**
|
139 |
* Get the number of elements in the queue.
|
140 |
*
|
141 |
* @param q the queue to get the size of
|
142 |
* @return the size of the queue
|
143 |
**/
|
144 |
int queue_size(Queue* q)
|
145 |
{ |
146 |
return q->size;
|
147 |
} |
148 |
|
149 |
/**
|
150 |
* Check if the queue is empty.
|
151 |
*
|
152 |
* @param q the queue to check
|
153 |
* @return nonzero if the queue is empty, 0 otherwise
|
154 |
**/
|
155 |
int queue_is_empty(Queue* q)
|
156 |
{ |
157 |
return q->size == 0; |
158 |
} |
159 |
|