1 /*
2 * Copyright (c) 2020
3 *
4 * This file is part of FFmpeg.
5 *
6 * FFmpeg is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Lesser General Public
8 * License as published by the Free Software Foundation; either
9 * version 2.1 of the License, or (at your option) any later version.
10 *
11 * FFmpeg is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 * Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with FFmpeg; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 #include <stdio.h>
22 #include "queue.h"
23 #include "libavutil/mem.h"
24 #include "libavutil/avassert.h"
25
26 typedef struct QueueEntry QueueEntry;
27
28 struct QueueEntry {
29 void *value;
30 QueueEntry *prev;
31 QueueEntry *next;
32 };
33
34 struct Queue {
35 QueueEntry *head;
36 QueueEntry *tail;
37 size_t length;
38 };
39
create_entry(void * val)40 static inline QueueEntry *create_entry(void *val)
41 {
42 QueueEntry *entry = av_malloc(sizeof(*entry));
43 if (entry)
44 entry->value = val;
45 return entry;
46 }
47
ff_queue_create(void)48 Queue* ff_queue_create(void)
49 {
50 Queue *q = av_malloc(sizeof(*q));
51 if (!q)
52 return NULL;
53
54 q->head = create_entry(q);
55 q->tail = create_entry(q);
56
57 if (!q->head || !q->tail) {
58 av_freep(&q->head);
59 av_freep(&q->tail);
60 av_freep(&q);
61 return NULL;
62 }
63
64 q->head->next = q->tail;
65 q->tail->prev = q->head;
66 q->head->prev = NULL;
67 q->tail->next = NULL;
68 q->length = 0;
69
70 return q;
71 }
72
ff_queue_destroy(Queue * q)73 void ff_queue_destroy(Queue *q)
74 {
75 QueueEntry *entry;
76 if (!q)
77 return;
78
79 entry = q->head;
80 while (entry != NULL) {
81 QueueEntry *temp = entry;
82 entry = entry->next;
83 av_freep(&temp);
84 }
85
86 av_freep(&q);
87 }
88
ff_queue_size(Queue * q)89 size_t ff_queue_size(Queue *q)
90 {
91 return q ? q->length : 0;
92 }
93
ff_queue_peek_front(Queue * q)94 void *ff_queue_peek_front(Queue *q)
95 {
96 if (!q || q->length == 0)
97 return NULL;
98
99 return q->head->next->value;
100 }
101
ff_queue_peek_back(Queue * q)102 void *ff_queue_peek_back(Queue *q)
103 {
104 if (!q || q->length == 0)
105 return NULL;
106
107 return q->tail->prev->value;
108 }
109
ff_queue_push_front(Queue * q,void * v)110 int ff_queue_push_front(Queue *q, void *v)
111 {
112 QueueEntry *new_entry;
113 QueueEntry *original_next;
114 if (!q)
115 return 0;
116
117 new_entry = create_entry(v);
118 if (!new_entry)
119 return -1;
120 original_next = q->head->next;
121
122 q->head->next = new_entry;
123 original_next->prev = new_entry;
124 new_entry->prev = q->head;
125 new_entry->next = original_next;
126 q->length++;
127
128 return q->length;
129 }
130
ff_queue_push_back(Queue * q,void * v)131 int ff_queue_push_back(Queue *q, void *v)
132 {
133 QueueEntry *new_entry;
134 QueueEntry *original_prev;
135 if (!q)
136 return 0;
137
138 new_entry = create_entry(v);
139 if (!new_entry)
140 return -1;
141 original_prev = q->tail->prev;
142
143 q->tail->prev = new_entry;
144 original_prev->next = new_entry;
145 new_entry->next = q->tail;
146 new_entry->prev = original_prev;
147 q->length++;
148
149 return q->length;
150 }
151
ff_queue_pop_front(Queue * q)152 void *ff_queue_pop_front(Queue *q)
153 {
154 QueueEntry *front;
155 QueueEntry *new_head_next;
156 void *ret;
157
158 if (!q || q->length == 0)
159 return NULL;
160
161 front = q->head->next;
162 new_head_next = front->next;
163 ret = front->value;
164
165 q->head->next = new_head_next;
166 new_head_next->prev = q->head;
167
168 av_freep(&front);
169 q->length--;
170 return ret;
171 }
172
ff_queue_pop_back(Queue * q)173 void *ff_queue_pop_back(Queue *q)
174 {
175 QueueEntry *back;
176 QueueEntry *new_tail_prev;
177 void *ret;
178
179 if (!q || q->length == 0)
180 return NULL;
181
182 back = q->tail->prev;
183 new_tail_prev = back->prev;
184 ret = back->value;
185
186 q->tail->prev = new_tail_prev;
187 new_tail_prev->next = q->tail;
188
189 av_freep(&back);
190 q->length--;
191 return ret;
192 }
193