root / branches / charging_station / code / projects / recharging / charging_station / queue.c @ 85
History | View | Annotate | Download (2.38 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 |
q->head = NULL;
|
28 |
q->size = 0;
|
29 |
return q;
|
30 |
} |
31 |
|
32 |
/**
|
33 |
* Destroys a queue, freeing memory.
|
34 |
*
|
35 |
* @param q the queue to destroy
|
36 |
**/
|
37 |
void queue_destroy(Queue* q)
|
38 |
{ |
39 |
Node* t = q->head; |
40 |
while (t != NULL) |
41 |
{ |
42 |
Node* t2 = t->next; |
43 |
free(t); |
44 |
t = t2; |
45 |
} |
46 |
free(q); |
47 |
} |
48 |
|
49 |
/**
|
50 |
* Add an element to a queue.
|
51 |
*
|
52 |
* @param q the queue to add an element to
|
53 |
* @param item the item to add to the queue
|
54 |
**/
|
55 |
void queue_add(Queue* q, void* item) |
56 |
{ |
57 |
Node* n = (Node*)malloc(sizeof(Node));
|
58 |
n->val = item; |
59 |
n->next = NULL;
|
60 |
|
61 |
if (q->head == NULL) |
62 |
{ |
63 |
q->head = n; |
64 |
q->tail = n; |
65 |
} |
66 |
else
|
67 |
{ |
68 |
q->tail->next = n; |
69 |
q->tail = n; |
70 |
} |
71 |
|
72 |
q->size++; |
73 |
} |
74 |
|
75 |
/**
|
76 |
* Remove an element from the front of a queue.
|
77 |
*
|
78 |
* @param q the queue to remove the element from
|
79 |
*
|
80 |
* @return the element which was removed
|
81 |
**/
|
82 |
void* queue_remove(Queue* q)
|
83 |
{ |
84 |
Node* first = q->head; |
85 |
if (first == NULL) |
86 |
{ |
87 |
WL_DEBUG_PRINT("Attempting to remove item \
|
88 |
from empty queue.\r\n");
|
89 |
WL_DEBUG_PRINT_INT(queue_size(q)); |
90 |
} |
91 |
void* ret = first->val;
|
92 |
q->head = first->next; |
93 |
if (q->tail == first)
|
94 |
q->tail = NULL;
|
95 |
free(first); |
96 |
q->size--; |
97 |
return ret;
|
98 |
} |
99 |
|
100 |
/**
|
101 |
* Remove all instances of a given element from a queue.
|
102 |
*
|
103 |
* @param q the queue to remove the elements from
|
104 |
* @param item the element to remove all instances of
|
105 |
**/
|
106 |
void queue_remove_all(Queue* q, void* item) |
107 |
{ |
108 |
Node* curr = q->head; |
109 |
Node* prev = NULL;
|
110 |
|
111 |
while (curr != NULL) |
112 |
{ |
113 |
Node* next = curr->next; |
114 |
if (curr->val == item)
|
115 |
{ |
116 |
if (q->head == curr)
|
117 |
q->head = next; |
118 |
if (q->tail == curr)
|
119 |
q->tail = prev; |
120 |
if (prev != NULL) |
121 |
prev->next = next; |
122 |
free(curr); |
123 |
q->size--; |
124 |
} |
125 |
else
|
126 |
prev = curr; |
127 |
curr = next; |
128 |
} |
129 |
} |
130 |
|
131 |
/**
|
132 |
* Get the number of elements in the queue.
|
133 |
*
|
134 |
* @param q the queue to get the size of
|
135 |
* @return the size of the queue
|
136 |
**/
|
137 |
int queue_size(Queue* q)
|
138 |
{ |
139 |
return q->size;
|
140 |
} |
141 |
|
142 |
/**
|
143 |
* Check if the queue is empty.
|
144 |
*
|
145 |
* @param q the queue to check
|
146 |
* @return nonzero if the queue is empty, 0 otherwise
|
147 |
**/
|
148 |
int queue_is_empty(Queue* q)
|
149 |
{ |
150 |
return q->size == 0; |
151 |
} |
152 |
|