1 /* Copyright (C) 2010-2020 The RetroArch team
3 * ---------------------------------------------------------------------------------------
4 * The following license statement only applies to this file (generic_queue.c).
5 * ---------------------------------------------------------------------------------------
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:
13 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
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.
27 #include <queues/generic_queue.h>
29 struct generic_queue_item_t
32 struct generic_queue_item_t *previous;
33 struct generic_queue_item_t *next;
38 struct generic_queue_item_t *first_item;
39 struct generic_queue_item_t *last_item;
43 struct generic_queue_iterator
45 generic_queue_t *queue;
46 struct generic_queue_item_t *item;
50 generic_queue_t *generic_queue_new(void)
52 return (generic_queue_t *)calloc(1, sizeof(generic_queue_t));
55 void generic_queue_free(generic_queue_t *queue, void (*free_value)(void *value))
57 struct generic_queue_item_t *next_item;
62 while (queue->first_item)
65 free_value(queue->first_item->value);
67 next_item = queue->first_item->next;
68 free(queue->first_item);
69 queue->first_item = next_item;
75 void generic_queue_push(generic_queue_t *queue, void *value)
77 struct generic_queue_item_t *new_item;
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;
84 queue->last_item = new_item;
87 if (!queue->first_item)
88 queue->first_item = new_item;
90 new_item->previous->next = new_item;
93 void *generic_queue_pop(generic_queue_t *queue)
96 struct generic_queue_item_t *item;
98 if (!queue || !queue->last_item)
101 item = queue->last_item;
102 queue->last_item = queue->last_item->previous;
105 if (queue->length == 0)
106 queue->first_item = NULL;
114 void *generic_queue_peek(generic_queue_t *queue)
116 if (!queue || !queue->last_item)
119 return queue->last_item->value;
122 void *generic_queue_peek_first(generic_queue_t *queue)
124 if (!queue || !queue->first_item)
127 return queue->first_item->value;
130 void generic_queue_shift(generic_queue_t *queue, void *value)
132 struct generic_queue_item_t *new_item;
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;
142 queue->first_item = new_item;
145 if (!queue->last_item)
146 queue->last_item = new_item;
148 new_item->next->previous = new_item;
151 void *generic_queue_unshift(generic_queue_t *queue)
154 struct generic_queue_item_t *item;
156 if (!queue || !queue->first_item)
159 item = queue->first_item;
160 queue->first_item = queue->first_item->next;
163 if (queue->length == 0)
164 queue->last_item = NULL;
172 size_t generic_queue_length(generic_queue_t *queue)
175 return queue->length;
180 void *generic_queue_remove(generic_queue_t *queue, void *value)
182 struct generic_queue_item_t *item;
187 for (item = queue->first_item; item; item = item->next)
189 if (item->value == value)
192 item->previous->next = item->next;
194 queue->first_item = item->next;
197 item->next->previous = item->previous;
199 queue->last_item = item->previous;
211 generic_queue_iterator_t *generic_queue_iterator(generic_queue_t *queue, bool forward)
213 if (queue && queue->first_item)
215 generic_queue_iterator_t *iterator;
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;
228 generic_queue_iterator_t *generic_queue_iterator_next(generic_queue_iterator_t *iterator)
232 struct generic_queue_item_t *item;
234 item = iterator->forward ? iterator->item->next : iterator->item->previous;
237 iterator->item = item;
249 void *generic_queue_iterator_value(generic_queue_iterator_t *iterator)
252 return iterator->item->value;
257 generic_queue_iterator_t *generic_queue_iterator_remove(generic_queue_iterator_t *iterator)
259 struct generic_queue_item_t *item;
264 item = iterator->forward ? iterator->queue->first_item : iterator->queue->last_item;
267 if (iterator->item == item)
269 if (iterator->queue->first_item == item)
270 iterator->queue->first_item = item->next;
272 item->previous->next = item->next;
274 if (iterator->queue->last_item == item)
275 iterator->queue->last_item = item->previous;
277 item->next->previous = item->previous;
279 iterator->queue->length--;
281 iterator->item = iterator->forward ? item->next : item->previous;
293 item = iterator->forward ? item->next : item->previous;
299 void generic_queue_iterator_free(generic_queue_iterator_t *iterator)