git.sesse.net Git - mlt/blob - 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 /** Insert an item in a sorted fashion.
 199  *
 200  * Optimized for the equivalent of \p mlt_deque_push_back.
 201  *
 202  * \public \memberof mlt_deque_s
 203  * \param this a deque
 204  * \param item an opaque pointer
 205  * \param cmp a function pointer to the comparison function
 206  * \return true if there was an error
 207  */
 208
 209 int mlt_deque_insert( mlt_deque this, void *item, mlt_deque_compare cmp )
 210 {
 211         int error = mlt_deque_allocate( this );
 212
 213         if ( error == 0 )
 214         {
 215                 int n = this->count + 1;
 216                 while ( --n )
 217                         if ( cmp( item, this->list[ n - 1 ].addr ) >= 0 )
 218                                 break;
 219                 memmove( &this->list[ n + 1 ], &this->list[ n ], ( this->count - n ) * sizeof( deque_entry ) );
 220                 this->list[ n ].addr = item;
 221                 this->count++;
 222         }
 223         return error;
 224 }
 225
 226 /** Push an integer to the end.
 227  *
 228  * \public \memberof mlt_deque_s
 229  * \param this a deque
 230  * \param item an integer
 231  * \return true if there was an error
 232  */
 233
 234 int mlt_deque_push_back_int( mlt_deque this, int item )
 235 {
 236         int error = mlt_deque_allocate( this );
 237
 238         if ( error == 0 )
 239                 this->list[ this->count ++ ].value = item;
 240
 241         return error;
 242 }
 243
 244 /** Pop an integer.
 245  *
 246  * \public \memberof mlt_deque_s
 247  * \param this a deque
 248  * \return an integer
 249  */
 250
 251 int mlt_deque_pop_back_int( mlt_deque this )
 252 {
 253         return this->count > 0 ? this->list[ -- this->count ].value : 0;
 254 }
 255
 256 /** Queue an integer at the start.
 257  *
 258  * \public \memberof mlt_deque_s
 259  * \param this a deque
 260  * \param item an integer
 261  * \return true if there was an error
 262  */
 263
 264 int mlt_deque_push_front_int( mlt_deque this, int item )
 265 {
 266         int error = mlt_deque_allocate( this );
 267
 268         if ( error == 0 )
 269         {
 270                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 271                 this->list[ 0 ].value = item;
 272         }
 273
 274         return error;
 275 }
 276
 277 /** Remove an integer from the start.
 278  *
 279  * \public \memberof mlt_deque_s
 280  * \param this a deque
 281  * \return an integer
 282  */
 283
 284 int mlt_deque_pop_front_int( mlt_deque this )
 285 {
 286         int item = 0;
 287
 288         if ( this->count > 0 )
 289         {
 290                 item = this->list[ 0 ].value;
 291                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 292         }
 293
 294         return item;
 295 }
 296
 297 /** Inquire on an integer at back of deque but don't remove.
 298  *
 299  * \public \memberof mlt_deque_s
 300  * \param this a deque
 301  * \return an integer
 302  */
 303
 304 int mlt_deque_peek_back_int( mlt_deque this )
 305 {
 306         return this->count > 0 ? this->list[ this->count - 1 ].value : 0;
 307 }
 308
 309 /** Inquire on an integer at front of deque but don't remove.
 310  *
 311  * \public \memberof mlt_deque_s
 312  * \param this a deque
 313  * \return an integer
 314  */
 315
 316 int mlt_deque_peek_front_int( mlt_deque this )
 317 {
 318         return this->count > 0 ? this->list[ 0 ].value : 0;
 319 }
 320
 321 /** Push a double float to the end.
 322  *
 323  * \public \memberof mlt_deque_s
 324  * \param this a deque
 325  * \param item a double float
 326  * \return true if there was an error
 327  */
 328
 329 int mlt_deque_push_back_double( mlt_deque this, double item )
 330 {
 331         int error = mlt_deque_allocate( this );
 332
 333         if ( error == 0 )
 334                 this->list[ this->count ++ ].floating = item;
 335
 336         return error;
 337 }
 338
 339 /** Pop a double float.
 340  *
 341  * \public \memberof mlt_deque_s
 342  * \param this a deque
 343  * \return a double float
 344  */
 345
 346 double mlt_deque_pop_back_double( mlt_deque this )
 347 {
 348         return this->count > 0 ? this->list[ -- this->count ].floating : 0;
 349 }
 350
 351 /** Queue a double float at the start.
 352  *
 353  * \public \memberof mlt_deque_s
 354  * \param this a deque
 355  * \param item a double float
 356  * \return true if there was an error
 357  */
 358
 359 int mlt_deque_push_front_double( mlt_deque this, double item )
 360 {
 361         int error = mlt_deque_allocate( this );
 362
 363         if ( error == 0 )
 364         {
 365                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 366                 this->list[ 0 ].floating = item;
 367         }
 368
 369         return error;
 370 }
 371
 372 /** Remove a double float from the start.
 373  *
 374  * \public \memberof mlt_deque_s
 375  * \param this a deque
 376  * \return a double float
 377  */
 378
 379 double mlt_deque_pop_front_double( mlt_deque this )
 380 {
 381         double item = 0;
 382
 383         if ( this->count > 0 )
 384         {
 385                 item = this->list[ 0 ].floating;
 386                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 387         }
 388
 389         return item;
 390 }
 391
 392 /** Inquire on a double float at back of deque but don't remove.
 393  *
 394  * \public \memberof mlt_deque_s
 395  * \param this a deque
 396  * \return a double float
 397  */
 398
 399 double mlt_deque_peek_back_double( mlt_deque this )
 400 {
 401         return this->count > 0 ? this->list[ this->count - 1 ].floating : 0;
 402 }
 403
 404 /** Inquire on a double float at front of deque but don't remove.
 405  *
 406  * \public \memberof mlt_deque_s
 407  * \param this a deque
 408  * \return a double float
 409  */
 410
 411 double mlt_deque_peek_front_double( mlt_deque this )
 412 {
 413         return this->count > 0 ? this->list[ 0 ].floating : 0;
 414 }
 415
 416 /** Destroy the queue.
 417  *
 418  * \public \memberof mlt_deque_s
 419  * \param this a deque
 420  */
 421
 422 void mlt_deque_close( mlt_deque this )
 423 {
 424         free( this->list );
 425         free( this );
 426 }