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