3 * \brief double ended queue
5 * Copyright (C) 2003-2008 Ushodaya Enterprises Limited
6 * \author Charles Yates <charles.yates@pandora.be>
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.
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.
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., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
24 #include "mlt_deque.h"
26 // System header files
30 /** \brief Deque entry class
42 /** \brief Double-Ended Queue (deque) class
44 * The double-ended queue is a very versatile data structure. MLT uses it as
45 * list, stack, and circular queue.
57 * \public \memberof mlt_deque_s
61 mlt_deque mlt_deque_init( )
63 mlt_deque this = malloc( sizeof( struct mlt_deque_s ) );
73 /** Return the number of items in the deque.
75 * \public \memberof mlt_deque_s
77 * \return the number of items
80 int mlt_deque_count( mlt_deque this )
85 /** Allocate space on the deque.
87 * \private \memberof mlt_deque_s
89 * \return true if there was an error
92 static int mlt_deque_allocate( mlt_deque this )
94 if ( this->count == this->size )
96 this->list = realloc( this->list, sizeof( deque_entry ) * ( this->size + 20 ) );
99 return this->list == NULL;
102 /** Push an item to the end.
104 * \public \memberof mlt_deque_s
105 * \param this a deque
106 * \param item an opaque pointer
107 * \return true if there was an error
110 int mlt_deque_push_back( mlt_deque this, void *item )
112 int error = mlt_deque_allocate( this );
115 this->list[ this->count ++ ].addr = item;
122 * \public \memberof mlt_deque_s
123 * \param this a pointer
124 * \return an opaque pointer
127 void *mlt_deque_pop_back( mlt_deque this )
129 return this->count > 0 ? this->list[ -- this->count ].addr : NULL;
132 /** Queue an item at the start.
134 * \public \memberof mlt_deque_s
135 * \param this a deque
136 * \param item an opaque pointer
137 * \return true if there was an error
140 int mlt_deque_push_front( mlt_deque this, void *item )
142 int error = mlt_deque_allocate( this );
146 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
147 this->list[ 0 ].addr = item;
153 /** Remove an item from the start.
155 * \public \memberof mlt_deque_s
156 * \param this a pointer
157 * \return an opaque pointer
160 void *mlt_deque_pop_front( mlt_deque this )
164 if ( this->count > 0 )
166 item = this->list[ 0 ].addr;
167 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
173 /** Inquire on item at back of deque but don't remove.
175 * \public \memberof mlt_deque_s
176 * \param this a deque
177 * \return an opaque pointer
180 void *mlt_deque_peek_back( mlt_deque this )
182 return this->count > 0 ? this->list[ this->count - 1 ].addr : NULL;
185 /** Inquire on item at front of deque but don't remove.
187 * \public \memberof mlt_deque_s
188 * \param this a deque
189 * \return an opaque pointer
192 void *mlt_deque_peek_front( mlt_deque this )
194 return this->count > 0 ? this->list[ 0 ].addr : NULL;
197 /** Push an integer to the end.
199 * \public \memberof mlt_deque_s
200 * \param this a deque
201 * \param item an integer
202 * \return true if there was an error
205 int mlt_deque_push_back_int( mlt_deque this, int item )
207 int error = mlt_deque_allocate( this );
210 this->list[ this->count ++ ].value = item;
217 * \public \memberof mlt_deque_s
218 * \param this a deque
222 int mlt_deque_pop_back_int( mlt_deque this )
224 return this->count > 0 ? this->list[ -- this->count ].value : 0;
227 /** Queue an integer at the start.
229 * \public \memberof mlt_deque_s
230 * \param this a deque
231 * \param item an integer
232 * \return true if there was an error
235 int mlt_deque_push_front_int( mlt_deque this, int item )
237 int error = mlt_deque_allocate( this );
241 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
242 this->list[ 0 ].value = item;
248 /** Remove an integer from the start.
250 * \public \memberof mlt_deque_s
251 * \param this a deque
255 int mlt_deque_pop_front_int( mlt_deque this )
259 if ( this->count > 0 )
261 item = this->list[ 0 ].value;
262 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
268 /** Inquire on an integer at back of deque but don't remove.
270 * \public \memberof mlt_deque_s
271 * \param this a deque
275 int mlt_deque_peek_back_int( mlt_deque this )
277 return this->count > 0 ? this->list[ this->count - 1 ].value : 0;
280 /** Inquire on an integer at front of deque but don't remove.
282 * \public \memberof mlt_deque_s
283 * \param this a deque
287 int mlt_deque_peek_front_int( mlt_deque this )
289 return this->count > 0 ? this->list[ 0 ].value : 0;
292 /** Push a double float to the end.
294 * \public \memberof mlt_deque_s
295 * \param this a deque
296 * \param item a double float
297 * \return true if there was an error
300 int mlt_deque_push_back_double( mlt_deque this, double item )
302 int error = mlt_deque_allocate( this );
305 this->list[ this->count ++ ].floating = item;
310 /** Pop a double float.
312 * \public \memberof mlt_deque_s
313 * \param this a deque
314 * \return a double float
317 double mlt_deque_pop_back_double( mlt_deque this )
319 return this->count > 0 ? this->list[ -- this->count ].floating : 0;
322 /** Queue a double float at the start.
324 * \public \memberof mlt_deque_s
325 * \param this a deque
326 * \param item a double float
327 * \return true if there was an error
330 int mlt_deque_push_front_double( mlt_deque this, double item )
332 int error = mlt_deque_allocate( this );
336 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
337 this->list[ 0 ].floating = item;
343 /** Remove a double float from the start.
345 * \public \memberof mlt_deque_s
346 * \param this a deque
347 * \return a double float
350 double mlt_deque_pop_front_double( mlt_deque this )
354 if ( this->count > 0 )
356 item = this->list[ 0 ].floating;
357 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
363 /** Inquire on a double float at back of deque but don't remove.
365 * \public \memberof mlt_deque_s
366 * \param this a deque
367 * \return a double float
370 double mlt_deque_peek_back_double( mlt_deque this )
372 return this->count > 0 ? this->list[ this->count - 1 ].floating : 0;
375 /** Inquire on a double float at front of deque but don't remove.
377 * \public \memberof mlt_deque_s
378 * \param this a deque
379 * \return a double float
382 double mlt_deque_peek_front_double( mlt_deque this )
384 return this->count > 0 ? this->list[ 0 ].floating : 0;
387 /** Destroy the queue.
389 * \public \memberof mlt_deque_s
390 * \param this a deque
393 void mlt_deque_close( mlt_deque this )