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 this = malloc( sizeof( struct mlt_deque_s ) );
74 /** Return the number of items in the deque.
76 * \public \memberof mlt_deque_s
78 * \return the number of items
81 int mlt_deque_count( mlt_deque this )
86 /** Allocate space on the deque.
88 * \private \memberof mlt_deque_s
90 * \return true if there was an error
93 static int mlt_deque_allocate( mlt_deque this )
95 if ( this->count == this->size )
97 this->list = realloc( this->list, sizeof( deque_entry ) * ( this->size + 20 ) );
100 return this->list == NULL;
103 /** Push an item to the end.
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
111 int mlt_deque_push_back( mlt_deque this, void *item )
113 int error = mlt_deque_allocate( this );
116 this->list[ this->count ++ ].addr = item;
123 * \public \memberof mlt_deque_s
124 * \param this a pointer
125 * \return an opaque pointer
128 void *mlt_deque_pop_back( mlt_deque this )
130 return this->count > 0 ? this->list[ -- this->count ].addr : NULL;
133 /** Queue an item at the start.
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
141 int mlt_deque_push_front( mlt_deque this, void *item )
143 int error = mlt_deque_allocate( this );
147 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
148 this->list[ 0 ].addr = item;
154 /** Remove an item from the start.
156 * \public \memberof mlt_deque_s
157 * \param this a pointer
158 * \return an opaque pointer
161 void *mlt_deque_pop_front( mlt_deque this )
165 if ( this->count > 0 )
167 item = this->list[ 0 ].addr;
168 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
174 /** Inquire on item at back of deque but don't remove.
176 * \public \memberof mlt_deque_s
177 * \param this a deque
178 * \return an opaque pointer
181 void *mlt_deque_peek_back( mlt_deque this )
183 return this->count > 0 ? this->list[ this->count - 1 ].addr : NULL;
186 /** Inquire on item at front of deque but don't remove.
188 * \public \memberof mlt_deque_s
189 * \param this a deque
190 * \return an opaque pointer
193 void *mlt_deque_peek_front( mlt_deque this )
195 return this->count > 0 ? this->list[ 0 ].addr : NULL;
198 /** Push an integer to the end.
200 * \public \memberof mlt_deque_s
201 * \param this a deque
202 * \param item an integer
203 * \return true if there was an error
206 int mlt_deque_push_back_int( mlt_deque this, int item )
208 int error = mlt_deque_allocate( this );
211 this->list[ this->count ++ ].value = item;
218 * \public \memberof mlt_deque_s
219 * \param this a deque
223 int mlt_deque_pop_back_int( mlt_deque this )
225 return this->count > 0 ? this->list[ -- this->count ].value : 0;
228 /** Queue an integer at the start.
230 * \public \memberof mlt_deque_s
231 * \param this a deque
232 * \param item an integer
233 * \return true if there was an error
236 int mlt_deque_push_front_int( mlt_deque this, int item )
238 int error = mlt_deque_allocate( this );
242 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
243 this->list[ 0 ].value = item;
249 /** Remove an integer from the start.
251 * \public \memberof mlt_deque_s
252 * \param this a deque
256 int mlt_deque_pop_front_int( mlt_deque this )
260 if ( this->count > 0 )
262 item = this->list[ 0 ].value;
263 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
269 /** Inquire on an integer at back of deque but don't remove.
271 * \public \memberof mlt_deque_s
272 * \param this a deque
276 int mlt_deque_peek_back_int( mlt_deque this )
278 return this->count > 0 ? this->list[ this->count - 1 ].value : 0;
281 /** Inquire on an integer at front of deque but don't remove.
283 * \public \memberof mlt_deque_s
284 * \param this a deque
288 int mlt_deque_peek_front_int( mlt_deque this )
290 return this->count > 0 ? this->list[ 0 ].value : 0;
293 /** Push a double float to the end.
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
301 int mlt_deque_push_back_double( mlt_deque this, double item )
303 int error = mlt_deque_allocate( this );
306 this->list[ this->count ++ ].floating = item;
311 /** Pop a double float.
313 * \public \memberof mlt_deque_s
314 * \param this a deque
315 * \return a double float
318 double mlt_deque_pop_back_double( mlt_deque this )
320 return this->count > 0 ? this->list[ -- this->count ].floating : 0;
323 /** Queue a double float at the start.
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
331 int mlt_deque_push_front_double( mlt_deque this, double item )
333 int error = mlt_deque_allocate( this );
337 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
338 this->list[ 0 ].floating = item;
344 /** Remove a double float from the start.
346 * \public \memberof mlt_deque_s
347 * \param this a deque
348 * \return a double float
351 double mlt_deque_pop_front_double( mlt_deque this )
355 if ( this->count > 0 )
357 item = this->list[ 0 ].floating;
358 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
364 /** Inquire on a double float at back of deque but don't remove.
366 * \public \memberof mlt_deque_s
367 * \param this a deque
368 * \return a double float
371 double mlt_deque_peek_back_double( mlt_deque this )
373 return this->count > 0 ? this->list[ this->count - 1 ].floating : 0;
376 /** Inquire on a double float at front of deque but don't remove.
378 * \public \memberof mlt_deque_s
379 * \param this a deque
380 * \return a double float
383 double mlt_deque_peek_front_double( mlt_deque this )
385 return this->count > 0 ? this->list[ 0 ].floating : 0;
388 /** Destroy the queue.
390 * \public \memberof mlt_deque_s
391 * \param this a deque
394 void mlt_deque_close( mlt_deque this )