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