FFmpeg
queue.c
Go to the documentation of this file.
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;
32 };
33 
34 struct Queue {
37  size_t length;
38 };
39 
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 
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 
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 
89 size_t ff_queue_size(Queue *q)
90 {
91  return q ? q->length : 0;
92 }
93 
95 {
96  if (!q || q->length == 0)
97  return NULL;
98 
99  return q->head->next->value;
100 }
101 
103 {
104  if (!q || q->length == 0)
105  return NULL;
106 
107  return q->tail->prev->value;
108 }
109 
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 
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 
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 
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 }
ff_queue_push_front
int ff_queue_push_front(Queue *q, void *v)
Add data to the head of the queue.
Definition: queue.c:110
ff_queue_pop_front
void * ff_queue_pop_front(Queue *q)
Remove and free first element from the Queue.
Definition: queue.c:152
ff_queue_size
size_t ff_queue_size(Queue *q)
Return the length of the Queue.
Definition: queue.c:89
QueueEntry::next
QueueEntry * next
Definition: queue.c:31
av_malloc
#define av_malloc(s)
Definition: tableprint_vlc.h:31
ff_queue_peek_back
void * ff_queue_peek_back(Queue *q)
Return a pointer to the data at the tail of the queue.
Definition: queue.c:102
ff_queue_create
Queue * ff_queue_create(void)
Create a Queue instance.
Definition: queue.c:48
val
static double val(void *priv, double ch)
Definition: aeval.c:76
Queue
Linear double-ended data structure.
Definition: queue.c:34
ff_queue_push_back
int ff_queue_push_back(Queue *q, void *v)
Add data to the tail of the queue.
Definition: queue.c:131
avassert.h
QueueEntry
Definition: queue.c:28
ff_queue_pop_back
void * ff_queue_pop_back(Queue *q)
Remove and free last element from the Queue.
Definition: queue.c:173
ff_queue_destroy
void ff_queue_destroy(Queue *q)
Destroy the Queue instance.
Definition: queue.c:73
NULL
#define NULL
Definition: coverity.c:32
Queue::tail
QueueEntry * tail
Definition: queue.c:36
queue.h
ret
ret
Definition: filter_design.txt:187
Queue::length
size_t length
Definition: queue.c:37
temp
else temp
Definition: vf_mcdeint.c:259
ff_queue_peek_front
void * ff_queue_peek_front(Queue *q)
Return a pointer to the data at the head of the queue.
Definition: queue.c:94
mem.h
create_entry
static QueueEntry * create_entry(void *val)
Definition: queue.c:40
av_freep
#define av_freep(p)
Definition: tableprint_vlc.h:35
Queue::head
QueueEntry * head
Definition: queue.c:35
QueueEntry::prev
QueueEntry * prev
Definition: queue.c:30
QueueEntry::value
void * value
Definition: queue.c:29