28dfd7f689a769f463ac1c561fee1bc4784416e2
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 )