Commit | Line | Data |
---|---|---|
3719602c PC |
1 | /* Copyright (C) 2010-2020 The RetroArch team |
2 | * | |
3 | * --------------------------------------------------------------------------------------- | |
4 | * The following license statement only applies to this file (generic_queue.c). | |
5 | * --------------------------------------------------------------------------------------- | |
6 | * | |
7 | * Permission is hereby granted, free of charge, | |
8 | * to any person obtaining a copy of this software and associated documentation files (the "Software"), | |
9 | * to deal in the Software without restriction, including without limitation the rights to | |
10 | * use, copy, modify, merge, publish, distribute, sublicense, and/or sell copies of the Software, | |
11 | * and to permit persons to whom the Software is furnished to do so, subject to the following conditions: | |
12 | * | |
13 | * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software. | |
14 | * | |
15 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, | |
16 | * INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
17 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. | |
18 | * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, | |
19 | * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
20 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE. | |
21 | */ | |
22 | ||
23 | #include <boolean.h> | |
24 | #include <stddef.h> | |
25 | #include <stdlib.h> | |
26 | ||
27 | #include <queues/generic_queue.h> | |
28 | ||
29 | struct generic_queue_item_t | |
30 | { | |
31 | void *value; | |
32 | struct generic_queue_item_t *previous; | |
33 | struct generic_queue_item_t *next; | |
34 | }; | |
35 | ||
36 | struct generic_queue | |
37 | { | |
38 | struct generic_queue_item_t *first_item; | |
39 | struct generic_queue_item_t *last_item; | |
40 | size_t length; | |
41 | }; | |
42 | ||
43 | struct generic_queue_iterator | |
44 | { | |
45 | generic_queue_t *queue; | |
46 | struct generic_queue_item_t *item; | |
47 | bool forward; | |
48 | }; | |
49 | ||
50 | generic_queue_t *generic_queue_new(void) | |
51 | { | |
52 | return (generic_queue_t *)calloc(1, sizeof(generic_queue_t)); | |
53 | } | |
54 | ||
55 | void generic_queue_free(generic_queue_t *queue, void (*free_value)(void *value)) | |
56 | { | |
57 | struct generic_queue_item_t *next_item; | |
58 | ||
59 | if (!queue) | |
60 | return; | |
61 | ||
62 | while (queue->first_item) | |
63 | { | |
64 | if (free_value) | |
65 | free_value(queue->first_item->value); | |
66 | ||
67 | next_item = queue->first_item->next; | |
68 | free(queue->first_item); | |
69 | queue->first_item = next_item; | |
70 | } | |
71 | ||
72 | free(queue); | |
73 | } | |
74 | ||
75 | void generic_queue_push(generic_queue_t *queue, void *value) | |
76 | { | |
77 | struct generic_queue_item_t *new_item; | |
78 | ||
79 | new_item = (struct generic_queue_item_t *)calloc(1, sizeof(struct generic_queue_item_t)); | |
80 | new_item->value = value; | |
81 | new_item->previous = queue->last_item; | |
82 | new_item->next = NULL; | |
83 | ||
84 | queue->last_item = new_item; | |
85 | queue->length++; | |
86 | ||
87 | if (!queue->first_item) | |
88 | queue->first_item = new_item; | |
89 | else | |
90 | new_item->previous->next = new_item; | |
91 | } | |
92 | ||
93 | void *generic_queue_pop(generic_queue_t *queue) | |
94 | { | |
95 | void *value; | |
96 | struct generic_queue_item_t *item; | |
97 | ||
98 | if (!queue || !queue->last_item) | |
99 | return NULL; | |
100 | ||
101 | item = queue->last_item; | |
102 | queue->last_item = queue->last_item->previous; | |
103 | queue->length--; | |
104 | ||
105 | if (queue->length == 0) | |
106 | queue->first_item = NULL; | |
107 | ||
108 | value = item->value; | |
109 | free(item); | |
110 | ||
111 | return value; | |
112 | } | |
113 | ||
114 | void *generic_queue_peek(generic_queue_t *queue) | |
115 | { | |
116 | if (!queue || !queue->last_item) | |
117 | return NULL; | |
118 | ||
119 | return queue->last_item->value; | |
120 | } | |
121 | ||
122 | void *generic_queue_peek_first(generic_queue_t *queue) | |
123 | { | |
124 | if (!queue || !queue->first_item) | |
125 | return NULL; | |
126 | ||
127 | return queue->first_item->value; | |
128 | } | |
129 | ||
130 | void generic_queue_shift(generic_queue_t *queue, void *value) | |
131 | { | |
132 | struct generic_queue_item_t *new_item; | |
133 | ||
134 | if (!queue) | |
135 | return; | |
136 | ||
137 | new_item = (struct generic_queue_item_t *)calloc(1, sizeof(struct generic_queue_item_t)); | |
138 | new_item->value = value; | |
139 | new_item->previous = NULL; | |
140 | new_item->next = queue->first_item; | |
141 | ||
142 | queue->first_item = new_item; | |
143 | queue->length++; | |
144 | ||
145 | if (!queue->last_item) | |
146 | queue->last_item = new_item; | |
147 | else | |
148 | new_item->next->previous = new_item; | |
149 | } | |
150 | ||
151 | void *generic_queue_unshift(generic_queue_t *queue) | |
152 | { | |
153 | void *value; | |
154 | struct generic_queue_item_t *item; | |
155 | ||
156 | if (!queue || !queue->first_item) | |
157 | return NULL; | |
158 | ||
159 | item = queue->first_item; | |
160 | queue->first_item = queue->first_item->next; | |
161 | queue->length--; | |
162 | ||
163 | if (queue->length == 0) | |
164 | queue->last_item = NULL; | |
165 | ||
166 | value = item->value; | |
167 | free(item); | |
168 | ||
169 | return value; | |
170 | } | |
171 | ||
172 | size_t generic_queue_length(generic_queue_t *queue) | |
173 | { | |
174 | if (queue) | |
175 | return queue->length; | |
176 | ||
177 | return 0; | |
178 | } | |
179 | ||
180 | void *generic_queue_remove(generic_queue_t *queue, void *value) | |
181 | { | |
182 | struct generic_queue_item_t *item; | |
183 | ||
184 | if (!queue) | |
185 | return NULL; | |
186 | ||
187 | for (item = queue->first_item; item; item = item->next) | |
188 | { | |
189 | if (item->value == value) | |
190 | { | |
191 | if (item->previous) | |
192 | item->previous->next = item->next; | |
193 | else | |
194 | queue->first_item = item->next; | |
195 | ||
196 | if (item->next) | |
197 | item->next->previous = item->previous; | |
198 | else | |
199 | queue->last_item = item->previous; | |
200 | ||
201 | free(item); | |
202 | queue->length--; | |
203 | ||
204 | return value; | |
205 | } | |
206 | } | |
207 | ||
208 | return NULL; | |
209 | } | |
210 | ||
211 | generic_queue_iterator_t *generic_queue_iterator(generic_queue_t *queue, bool forward) | |
212 | { | |
213 | if (queue && queue->first_item) | |
214 | { | |
215 | generic_queue_iterator_t *iterator; | |
216 | ||
217 | iterator = (generic_queue_iterator_t *)malloc(sizeof(generic_queue_iterator_t)); | |
218 | iterator->queue = queue; | |
219 | iterator->item = forward ? queue->first_item : queue->last_item; | |
220 | iterator->forward = forward; | |
221 | ||
222 | return iterator; | |
223 | } | |
224 | ||
225 | return NULL; | |
226 | } | |
227 | ||
228 | generic_queue_iterator_t *generic_queue_iterator_next(generic_queue_iterator_t *iterator) | |
229 | { | |
230 | if (iterator) | |
231 | { | |
232 | struct generic_queue_item_t *item; | |
233 | ||
234 | item = iterator->forward ? iterator->item->next : iterator->item->previous; | |
235 | if (item) | |
236 | { | |
237 | iterator->item = item; | |
238 | return iterator; | |
239 | } else | |
240 | { | |
241 | free(iterator); | |
242 | return NULL; | |
243 | } | |
244 | } | |
245 | ||
246 | return NULL; | |
247 | } | |
248 | ||
249 | void *generic_queue_iterator_value(generic_queue_iterator_t *iterator) | |
250 | { | |
251 | if (iterator) | |
252 | return iterator->item->value; | |
253 | ||
254 | return NULL; | |
255 | } | |
256 | ||
257 | generic_queue_iterator_t *generic_queue_iterator_remove(generic_queue_iterator_t *iterator) | |
258 | { | |
259 | struct generic_queue_item_t *item; | |
260 | ||
261 | if (!iterator) | |
262 | return NULL; | |
263 | ||
264 | item = iterator->forward ? iterator->queue->first_item : iterator->queue->last_item; | |
265 | while (item) | |
266 | { | |
267 | if (iterator->item == item) | |
268 | { | |
269 | if (iterator->queue->first_item == item) | |
270 | iterator->queue->first_item = item->next; | |
271 | else | |
272 | item->previous->next = item->next; | |
273 | ||
274 | if (iterator->queue->last_item == item) | |
275 | iterator->queue->last_item = item->previous; | |
276 | else | |
277 | item->next->previous = item->previous; | |
278 | ||
279 | iterator->queue->length--; | |
280 | ||
281 | iterator->item = iterator->forward ? item->next : item->previous; | |
282 | free(item); | |
283 | if (iterator->item) | |
284 | { | |
285 | return iterator; | |
286 | } else | |
287 | { | |
288 | free(iterator); | |
289 | return NULL; | |
290 | } | |
291 | } | |
292 | ||
293 | item = iterator->forward ? item->next : item->previous; | |
294 | } | |
295 | ||
296 | return iterator; | |
297 | } | |
298 | ||
299 | void generic_queue_iterator_free(generic_queue_iterator_t *iterator) | |
300 | { | |
301 | if (iterator) | |
302 | free(iterator); | |
303 | } |