1 /**
2 * \file mlt_deque.c
3 * \brief double ended queue
4 * \see mlt_deque_s
5 *
6 * Copyright (C) 2003-2019 Meltytech, LLC
7 *
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
12 *
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
17 *
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21 */
22
23 // Local header files
24 #include "mlt_deque.h"
25
26 // System header files
27 #include <stdlib.h>
28 #include <string.h>
29 #include <stdatomic.h>
30
31 /** \brief Deque entry class
32 *
33 */
34
35 typedef union
36 {
37 void *addr;
38 int value;
39 double floating;
40 }
41 deque_entry;
42
43 /** \brief Double-Ended Queue (deque) class
44 *
45 * The double-ended queue is a very versatile data structure. MLT uses it as
46 * list, stack, and circular queue.
47 */
48
49 struct mlt_deque_s
50 {
51 deque_entry *list;
52 int size;
53 atomic_int count;
54 };
55
56 /** Create a deque.
57 *
58 * \public \memberof mlt_deque_s
59 * \return a new deque
60 */
61
mlt_deque_init()62 mlt_deque mlt_deque_init( )
63 {
64 mlt_deque self = calloc( 1, sizeof( struct mlt_deque_s ) );
65 return self;
66 }
67
68 /** Return the number of items in the deque.
69 *
70 * \public \memberof mlt_deque_s
71 * \param self a deque
72 * \return the number of items
73 */
74
mlt_deque_count(mlt_deque self)75 int mlt_deque_count( mlt_deque self )
76 {
77 if ( self )
78 return self->count;
79 else
80 return 0;
81 }
82
83 /** Allocate space on the deque.
84 *
85 * \private \memberof mlt_deque_s
86 * \param self a deque
87 * \return true if there was an error
88 */
89
mlt_deque_allocate(mlt_deque self)90 static int mlt_deque_allocate( mlt_deque self )
91 {
92 if ( self->count == self->size )
93 {
94 self->list = realloc( self->list, sizeof( deque_entry ) * ( self->size + 20 ) );
95 self->size += 20;
96 }
97 return self->list == NULL;
98 }
99
100 /** Push an item to the end.
101 *
102 * \public \memberof mlt_deque_s
103 * \param self a deque
104 * \param item an opaque pointer
105 * \return true if there was an error
106 */
107
mlt_deque_push_back(mlt_deque self,void * item)108 int mlt_deque_push_back( mlt_deque self, void *item )
109 {
110 int error = mlt_deque_allocate( self );
111
112 if ( error == 0 )
113 self->list[ self->count ++ ].addr = item;
114
115 return error;
116 }
117
118 /** Pop an item.
119 *
120 * \public \memberof mlt_deque_s
121 * \param self a pointer
122 * \return an opaque pointer
123 */
124
mlt_deque_pop_back(mlt_deque self)125 void *mlt_deque_pop_back( mlt_deque self )
126 {
127 return self->count > 0 ? self->list[ -- self->count ].addr : NULL;
128 }
129
130 /** Queue an item at the start.
131 *
132 * \public \memberof mlt_deque_s
133 * \param self a deque
134 * \param item an opaque pointer
135 * \return true if there was an error
136 */
137
mlt_deque_push_front(mlt_deque self,void * item)138 int mlt_deque_push_front( mlt_deque self, void *item )
139 {
140 int error = mlt_deque_allocate( self );
141
142 if ( error == 0 )
143 {
144 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
145 self->list[ 0 ].addr = item;
146 }
147
148 return error;
149 }
150
151 /** Remove an item from the start.
152 *
153 * \public \memberof mlt_deque_s
154 * \param self a pointer
155 * \return an opaque pointer
156 */
157
mlt_deque_pop_front(mlt_deque self)158 void *mlt_deque_pop_front( mlt_deque self )
159 {
160 void *item = NULL;
161
162 if ( self->count > 0 )
163 {
164 item = self->list[ 0 ].addr;
165 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
166 }
167
168 return item;
169 }
170
171 /** Inquire on item at back of deque but don't remove.
172 *
173 * \public \memberof mlt_deque_s
174 * \param self a deque
175 * \return an opaque pointer
176 */
177
mlt_deque_peek_back(mlt_deque self)178 void *mlt_deque_peek_back( mlt_deque self )
179 {
180 return self->count > 0 ? self->list[ self->count - 1 ].addr : NULL;
181 }
182
183 /** Inquire on item at front of deque but don't remove.
184 *
185 * \public \memberof mlt_deque_s
186 * \param self a deque
187 * \return an opaque pointer
188 */
189
mlt_deque_peek_front(mlt_deque self)190 void *mlt_deque_peek_front( mlt_deque self )
191 {
192 return self->count > 0 ? self->list[ 0 ].addr : NULL;
193 }
194
195 /** Inquire on item in deque but don't remove.
196 *
197 * \public \memberof mlt_deque_s
198 * \param self a deque
199 * \param index the position in the deque
200 * \return an opaque pointer
201 */
202
mlt_deque_peek(mlt_deque self,int index)203 void *mlt_deque_peek( mlt_deque self, int index )
204 {
205 return self->count > index ? self->list[ index ].addr : NULL;
206 }
207
208 /** Insert an item in a sorted fashion.
209 *
210 * Optimized for the equivalent of \p mlt_deque_push_back.
211 *
212 * \public \memberof mlt_deque_s
213 * \param self a deque
214 * \param item an opaque pointer
215 * \param cmp a function pointer to the comparison function
216 * \return true if there was an error
217 */
218
mlt_deque_insert(mlt_deque self,void * item,mlt_deque_compare cmp)219 int mlt_deque_insert( mlt_deque self, void *item, mlt_deque_compare cmp )
220 {
221 int error = mlt_deque_allocate( self );
222
223 if ( error == 0 )
224 {
225 int n = self->count + 1;
226 while ( --n )
227 if ( cmp( item, self->list[ n - 1 ].addr ) >= 0 )
228 break;
229 memmove( &self->list[ n + 1 ], &self->list[ n ], ( self->count - n ) * sizeof( deque_entry ) );
230 self->list[ n ].addr = item;
231 self->count++;
232 }
233 return error;
234 }
235
236 /** Push an integer to the end.
237 *
238 * \public \memberof mlt_deque_s
239 * \param self a deque
240 * \param item an integer
241 * \return true if there was an error
242 */
243
mlt_deque_push_back_int(mlt_deque self,int item)244 int mlt_deque_push_back_int( mlt_deque self, int item )
245 {
246 int error = mlt_deque_allocate( self );
247
248 if ( error == 0 )
249 self->list[ self->count ++ ].value = item;
250
251 return error;
252 }
253
254 /** Pop an integer.
255 *
256 * \public \memberof mlt_deque_s
257 * \param self a deque
258 * \return an integer
259 */
260
mlt_deque_pop_back_int(mlt_deque self)261 int mlt_deque_pop_back_int( mlt_deque self )
262 {
263 return self->count > 0 ? self->list[ -- self->count ].value : 0;
264 }
265
266 /** Queue an integer at the start.
267 *
268 * \public \memberof mlt_deque_s
269 * \param self a deque
270 * \param item an integer
271 * \return true if there was an error
272 */
273
mlt_deque_push_front_int(mlt_deque self,int item)274 int mlt_deque_push_front_int( mlt_deque self, int item )
275 {
276 int error = mlt_deque_allocate( self );
277
278 if ( error == 0 )
279 {
280 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
281 self->list[ 0 ].value = item;
282 }
283
284 return error;
285 }
286
287 /** Remove an integer from the start.
288 *
289 * \public \memberof mlt_deque_s
290 * \param self a deque
291 * \return an integer
292 */
293
mlt_deque_pop_front_int(mlt_deque self)294 int mlt_deque_pop_front_int( mlt_deque self )
295 {
296 int item = 0;
297
298 if ( self->count > 0 )
299 {
300 item = self->list[ 0 ].value;
301 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
302 }
303
304 return item;
305 }
306
307 /** Inquire on an integer at back of deque but don't remove.
308 *
309 * \public \memberof mlt_deque_s
310 * \param self a deque
311 * \return an integer
312 */
313
mlt_deque_peek_back_int(mlt_deque self)314 int mlt_deque_peek_back_int( mlt_deque self )
315 {
316 return self->count > 0 ? self->list[ self->count - 1 ].value : 0;
317 }
318
319 /** Inquire on an integer at front of deque but don't remove.
320 *
321 * \public \memberof mlt_deque_s
322 * \param self a deque
323 * \return an integer
324 */
325
mlt_deque_peek_front_int(mlt_deque self)326 int mlt_deque_peek_front_int( mlt_deque self )
327 {
328 return self->count > 0 ? self->list[ 0 ].value : 0;
329 }
330
331 /** Push a double float to the end.
332 *
333 * \public \memberof mlt_deque_s
334 * \param self a deque
335 * \param item a double float
336 * \return true if there was an error
337 */
338
mlt_deque_push_back_double(mlt_deque self,double item)339 int mlt_deque_push_back_double( mlt_deque self, double item )
340 {
341 int error = mlt_deque_allocate( self );
342
343 if ( error == 0 )
344 self->list[ self->count ++ ].floating = item;
345
346 return error;
347 }
348
349 /** Pop a double float.
350 *
351 * \public \memberof mlt_deque_s
352 * \param self a deque
353 * \return a double float
354 */
355
mlt_deque_pop_back_double(mlt_deque self)356 double mlt_deque_pop_back_double( mlt_deque self )
357 {
358 return self->count > 0 ? self->list[ -- self->count ].floating : 0;
359 }
360
361 /** Queue a double float at the start.
362 *
363 * \public \memberof mlt_deque_s
364 * \param self a deque
365 * \param item a double float
366 * \return true if there was an error
367 */
368
mlt_deque_push_front_double(mlt_deque self,double item)369 int mlt_deque_push_front_double( mlt_deque self, double item )
370 {
371 int error = mlt_deque_allocate( self );
372
373 if ( error == 0 )
374 {
375 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
376 self->list[ 0 ].floating = item;
377 }
378
379 return error;
380 }
381
382 /** Remove a double float from the start.
383 *
384 * \public \memberof mlt_deque_s
385 * \param self a deque
386 * \return a double float
387 */
388
mlt_deque_pop_front_double(mlt_deque self)389 double mlt_deque_pop_front_double( mlt_deque self )
390 {
391 double item = 0;
392
393 if ( self->count > 0 )
394 {
395 item = self->list[ 0 ].floating;
396 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
397 }
398
399 return item;
400 }
401
402 /** Inquire on a double float at back of deque but don't remove.
403 *
404 * \public \memberof mlt_deque_s
405 * \param self a deque
406 * \return a double float
407 */
408
mlt_deque_peek_back_double(mlt_deque self)409 double mlt_deque_peek_back_double( mlt_deque self )
410 {
411 return self->count > 0 ? self->list[ self->count - 1 ].floating : 0;
412 }
413
414 /** Inquire on a double float at front of deque but don't remove.
415 *
416 * \public \memberof mlt_deque_s
417 * \param self a deque
418 * \return a double float
419 */
420
mlt_deque_peek_front_double(mlt_deque self)421 double mlt_deque_peek_front_double( mlt_deque self )
422 {
423 return self->count > 0 ? self->list[ 0 ].floating : 0;
424 }
425
426 /** Destroy the queue.
427 *
428 * \public \memberof mlt_deque_s
429 * \param self a deque
430 */
431
mlt_deque_close(mlt_deque self)432 void mlt_deque_close( mlt_deque self )
433 {
434 free( self->list );
435 free( self );
436 }
437