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
25 typedef struct QueueEntry QueueEntry;
26
27 struct QueueEntry {
28 void *value;
29 QueueEntry *prev;
30 QueueEntry *next;
31 };
32
33 struct Queue {
34 QueueEntry *head;
35 QueueEntry *tail;
36 size_t length;
37 };
38
create_entry(void * val)39 static inline QueueEntry *create_entry(void *val)
40 {
41 QueueEntry *entry = av_malloc(sizeof(*entry));
42 if (entry)
43 entry->value = val;
44 return entry;
45 }
46
ff_queue_create(void)47 Queue* ff_queue_create(void)
48 {
49 Queue *q = av_malloc(sizeof(*q));
50 if (!q)
51 return NULL;
52
53 q->head = create_entry(q);
54 q->tail = create_entry(q);
55
56 if (!q->head || !q->tail) {
57 av_freep(&q->head);
58 av_freep(&q->tail);
59 av_freep(&q);
60 return NULL;
61 }
62
63 q->head->next = q->tail;
64 q->tail->prev = q->head;
65 q->head->prev = NULL;
66 q->tail->next = NULL;
67 q->length = 0;
68
69 return q;
70 }
71
ff_queue_destroy(Queue * q)72 void ff_queue_destroy(Queue *q)
73 {
74 QueueEntry *entry;
75 if (!q)
76 return;
77
78 entry = q->head;
79 while (entry != NULL) {
80 QueueEntry *temp = entry;
81 entry = entry->next;
82 av_freep(&temp);
83 }
84
85 av_freep(&q);
86 }
87
ff_queue_size(Queue * q)88 size_t ff_queue_size(Queue *q)
89 {
90 return q ? q->length : 0;
91 }
92
ff_queue_peek_front(Queue * q)93 void *ff_queue_peek_front(Queue *q)
94 {
95 if (!q || q->length == 0)
96 return NULL;
97
98 return q->head->next->value;
99 }
100
ff_queue_peek_back(Queue * q)101 void *ff_queue_peek_back(Queue *q)
102 {
103 if (!q || q->length == 0)
104 return NULL;
105
106 return q->tail->prev->value;
107 }
108
ff_queue_push_front(Queue * q,void * v)109 int ff_queue_push_front(Queue *q, void *v)
110 {
111 QueueEntry *new_entry;
112 QueueEntry *original_next;
113 if (!q)
114 return 0;
115
116 new_entry = create_entry(v);
117 if (!new_entry)
118 return -1;
119 original_next = q->head->next;
120
121 q->head->next = new_entry;
122 original_next->prev = new_entry;
123 new_entry->prev = q->head;
124 new_entry->next = original_next;
125 q->length++;
126
127 return q->length;
128 }
129
ff_queue_push_back(Queue * q,void * v)130 int ff_queue_push_back(Queue *q, void *v)
131 {
132 QueueEntry *new_entry;
133 QueueEntry *original_prev;
134 if (!q)
135 return 0;
136
137 new_entry = create_entry(v);
138 if (!new_entry)
139 return -1;
140 original_prev = q->tail->prev;
141
142 q->tail->prev = new_entry;
143 original_prev->next = new_entry;
144 new_entry->next = q->tail;
145 new_entry->prev = original_prev;
146 q->length++;
147
148 return q->length;
149 }
150
ff_queue_pop_front(Queue * q)151 void *ff_queue_pop_front(Queue *q)
152 {
153 QueueEntry *front;
154 QueueEntry *new_head_next;
155 void *ret;
156
157 if (!q || q->length == 0)
158 return NULL;
159
160 front = q->head->next;
161 new_head_next = front->next;
162 ret = front->value;
163
164 q->head->next = new_head_next;
165 new_head_next->prev = q->head;
166
167 av_freep(&front);
168 q->length--;
169 return ret;
170 }
171
ff_queue_pop_back(Queue * q)172 void *ff_queue_pop_back(Queue *q)
173 {
174 QueueEntry *back;
175 QueueEntry *new_tail_prev;
176 void *ret;
177
178 if (!q || q->length == 0)
179 return NULL;
180
181 back = q->tail->prev;
182 new_tail_prev = back->prev;
183 ret = back->value;
184
185 q->tail->prev = new_tail_prev;
186 new_tail_prev->next = q->tail;
187
188 av_freep(&back);
189 q->length--;
190 return ret;
191 }
192