3 * \brief double ended queue
6 * Copyright (C) 2003-2009 Ushodaya Enterprises Limited
7 * \author Charles Yates <charles.yates@pandora.be>
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.
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.
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
25 #include "mlt_deque.h"
27 // System header files
31 /** \brief Deque entry class
43 /** \brief Double-Ended Queue (deque) class
45 * The double-ended queue is a very versatile data structure. MLT uses it as
46 * list, stack, and circular queue.
58 * \public \memberof mlt_deque_s
62 mlt_deque mlt_deque_init( )
64 mlt_deque self = calloc( 1, sizeof( struct mlt_deque_s ) );
68 /** Return the number of items in the deque.
70 * \public \memberof mlt_deque_s
72 * \return the number of items
75 int mlt_deque_count( mlt_deque self )
83 /** Allocate space on the deque.
85 * \private \memberof mlt_deque_s
87 * \return true if there was an error
90 static int mlt_deque_allocate( mlt_deque self )
92 if ( self->count == self->size )
94 self->list = realloc( self->list, sizeof( deque_entry ) * ( self->size + 20 ) );
97 return self->list == NULL;
100 /** Push an item to the end.
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
108 int mlt_deque_push_back( mlt_deque self, void *item )
110 int error = mlt_deque_allocate( self );
113 self->list[ self->count ++ ].addr = item;
120 * \public \memberof mlt_deque_s
121 * \param self a pointer
122 * \return an opaque pointer
125 void *mlt_deque_pop_back( mlt_deque self )
127 return self->count > 0 ? self->list[ -- self->count ].addr : NULL;
130 /** Queue an item at the start.
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
138 int mlt_deque_push_front( mlt_deque self, void *item )
140 int error = mlt_deque_allocate( self );
144 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
145 self->list[ 0 ].addr = item;
151 /** Remove an item from the start.
153 * \public \memberof mlt_deque_s
154 * \param self a pointer
155 * \return an opaque pointer
158 void *mlt_deque_pop_front( mlt_deque self )
162 if ( self->count > 0 )
164 item = self->list[ 0 ].addr;
165 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
171 /** Inquire on item at back of deque but don't remove.
173 * \public \memberof mlt_deque_s
174 * \param self a deque
175 * \return an opaque pointer
178 void *mlt_deque_peek_back( mlt_deque self )
180 return self->count > 0 ? self->list[ self->count - 1 ].addr : NULL;
183 /** Inquire on item at front of deque but don't remove.
185 * \public \memberof mlt_deque_s
186 * \param self a deque
187 * \return an opaque pointer
190 void *mlt_deque_peek_front( mlt_deque self )
192 return self->count > 0 ? self->list[ 0 ].addr : NULL;
195 /** Inquire on item in deque but don't remove.
197 * \public \memberof mlt_deque_s
198 * \param self a deque
199 * \param index the position in the deque
200 * \return an opaque pointer
203 void *mlt_deque_peek( mlt_deque self, int index )
205 return self->count > index ? self->list[ index ].addr : NULL;
208 /** Insert an item in a sorted fashion.
210 * Optimized for the equivalent of \p mlt_deque_push_back.
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
219 int mlt_deque_insert( mlt_deque self, void *item, mlt_deque_compare cmp )
221 int error = mlt_deque_allocate( self );
225 int n = self->count + 1;
227 if ( cmp( item, self->list[ n - 1 ].addr ) >= 0 )
229 memmove( &self->list[ n + 1 ], &self->list[ n ], ( self->count - n ) * sizeof( deque_entry ) );
230 self->list[ n ].addr = item;
236 /** Push an integer to the end.
238 * \public \memberof mlt_deque_s
239 * \param self a deque
240 * \param item an integer
241 * \return true if there was an error
244 int mlt_deque_push_back_int( mlt_deque self, int item )
246 int error = mlt_deque_allocate( self );
249 self->list[ self->count ++ ].value = item;
256 * \public \memberof mlt_deque_s
257 * \param self a deque
261 int mlt_deque_pop_back_int( mlt_deque self )
263 return self->count > 0 ? self->list[ -- self->count ].value : 0;
266 /** Queue an integer at the start.
268 * \public \memberof mlt_deque_s
269 * \param self a deque
270 * \param item an integer
271 * \return true if there was an error
274 int mlt_deque_push_front_int( mlt_deque self, int item )
276 int error = mlt_deque_allocate( self );
280 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
281 self->list[ 0 ].value = item;
287 /** Remove an integer from the start.
289 * \public \memberof mlt_deque_s
290 * \param self a deque
294 int mlt_deque_pop_front_int( mlt_deque self )
298 if ( self->count > 0 )
300 item = self->list[ 0 ].value;
301 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
307 /** Inquire on an integer at back of deque but don't remove.
309 * \public \memberof mlt_deque_s
310 * \param self a deque
314 int mlt_deque_peek_back_int( mlt_deque self )
316 return self->count > 0 ? self->list[ self->count - 1 ].value : 0;
319 /** Inquire on an integer at front of deque but don't remove.
321 * \public \memberof mlt_deque_s
322 * \param self a deque
326 int mlt_deque_peek_front_int( mlt_deque self )
328 return self->count > 0 ? self->list[ 0 ].value : 0;
331 /** Push a double float to the end.
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
339 int mlt_deque_push_back_double( mlt_deque self, double item )
341 int error = mlt_deque_allocate( self );
344 self->list[ self->count ++ ].floating = item;
349 /** Pop a double float.
351 * \public \memberof mlt_deque_s
352 * \param self a deque
353 * \return a double float
356 double mlt_deque_pop_back_double( mlt_deque self )
358 return self->count > 0 ? self->list[ -- self->count ].floating : 0;
361 /** Queue a double float at the start.
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
369 int mlt_deque_push_front_double( mlt_deque self, double item )
371 int error = mlt_deque_allocate( self );
375 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
376 self->list[ 0 ].floating = item;
382 /** Remove a double float from the start.
384 * \public \memberof mlt_deque_s
385 * \param self a deque
386 * \return a double float
389 double mlt_deque_pop_front_double( mlt_deque self )
393 if ( self->count > 0 )
395 item = self->list[ 0 ].floating;
396 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
402 /** Inquire on a double float at back of deque but don't remove.
404 * \public \memberof mlt_deque_s
405 * \param self a deque
406 * \return a double float
409 double mlt_deque_peek_back_double( mlt_deque self )
411 return self->count > 0 ? self->list[ self->count - 1 ].floating : 0;
414 /** Inquire on a double float at front of deque but don't remove.
416 * \public \memberof mlt_deque_s
417 * \param self a deque
418 * \return a double float
421 double mlt_deque_peek_front_double( mlt_deque self )
423 return self->count > 0 ? self->list[ 0 ].floating : 0;
426 /** Destroy the queue.
428 * \public \memberof mlt_deque_s
429 * \param self a deque
432 void mlt_deque_close( mlt_deque self )