root / branches / autonomous_recharging / code / projects / libwireless / lib / queue.c @ 767
History | View | Annotate | Download (2.38 KB)
1 | 17 | bcoltin | #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 | } |