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 self = malloc( sizeof( struct mlt_deque_s ) );
  65         if ( self != NULL )
  66         {
  67                 self->list = NULL;
  68                 self->size = 0;
  69                 self->count = 0;
  70         }
  71         return self;
  72 }
  73
  74 /** Return the number of items in the deque.
  75  *
  76  * \public \memberof mlt_deque_s
  77  * \param self a deque
  78  * \return the number of items
  79  */
  80
  81 int mlt_deque_count( mlt_deque self )
  82 {
  83         return self->count;
  84 }
  85
  86 /** Allocate space on the deque.
  87  *
  88  * \private \memberof mlt_deque_s
  89  * \param self a deque
  90  * \return true if there was an error
  91  */
  92
  93 static int mlt_deque_allocate( mlt_deque self )
  94 {
  95         if ( self->count == self->size )
  96         {
  97                 self->list = realloc( self->list, sizeof( deque_entry ) * ( self->size + 20 ) );
  98                 self->size += 20;
  99         }
 100         return self->list == NULL;
 101 }
 102
 103 /** Push an item to the end.
 104  *
 105  * \public \memberof mlt_deque_s
 106  * \param self 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 self, void *item )
 112 {
 113         int error = mlt_deque_allocate( self );
 114
 115         if ( error == 0 )
 116                 self->list[ self->count ++ ].addr = item;
 117
 118         return error;
 119 }
 120
 121 /** Pop an item.
 122  *
 123  * \public \memberof mlt_deque_s
 124  * \param self a pointer
 125  * \return an opaque pointer
 126  */
 127
 128 void *mlt_deque_pop_back( mlt_deque self )
 129 {
 130         return self->count > 0 ? self->list[ -- self->count ].addr : NULL;
 131 }
 132
 133 /** Queue an item at the start.
 134  *
 135  * \public \memberof mlt_deque_s
 136  * \param self 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 self, void *item )
 142 {
 143         int error = mlt_deque_allocate( self );
 144
 145         if ( error == 0 )
 146         {
 147                 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
 148                 self->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 self a pointer
 158  * \return an opaque pointer
 159  */
 160
 161 void *mlt_deque_pop_front( mlt_deque self )
 162 {
 163         void *item = NULL;
 164
 165         if ( self->count > 0 )
 166         {
 167                 item = self->list[ 0 ].addr;
 168                 memmove( self->list, &self->list[ 1 ], ( -- self->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 self a deque
 178  * \return an opaque pointer
 179  */
 180
 181 void *mlt_deque_peek_back( mlt_deque self )
 182 {
 183         return self->count > 0 ? self->list[ self->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 self a deque
 190  * \return an opaque pointer
 191  */
 192
 193 void *mlt_deque_peek_front( mlt_deque self )
 194 {
 195         return self->count > 0 ? self->list[ 0 ].addr : NULL;
 196 }
 197
 198 /** Inquire on item in deque but don't remove.
 199  *
 200  * \public \memberof mlt_deque_s
 201  * \param self a deque
 202  * \param index the position in the deque
 203  * \return an opaque pointer
 204  */
 205
 206 void *mlt_deque_peek( mlt_deque self, int index )
 207 {
 208         return self->count > index ? self->list[ index ].addr : NULL;
 209 }
 210
 211 /** Insert an item in a sorted fashion.
 212  *
 213  * Optimized for the equivalent of \p mlt_deque_push_back.
 214  *
 215  * \public \memberof mlt_deque_s
 216  * \param self a deque
 217  * \param item an opaque pointer
 218  * \param cmp a function pointer to the comparison function
 219  * \return true if there was an error
 220  */
 221
 222 int mlt_deque_insert( mlt_deque self, void *item, mlt_deque_compare cmp )
 223 {
 224         int error = mlt_deque_allocate( self );
 225
 226         if ( error == 0 )
 227         {
 228                 int n = self->count + 1;
 229                 while ( --n )
 230                         if ( cmp( item, self->list[ n - 1 ].addr ) >= 0 )
 231                                 break;
 232                 memmove( &self->list[ n + 1 ], &self->list[ n ], ( self->count - n ) * sizeof( deque_entry ) );
 233                 self->list[ n ].addr = item;
 234                 self->count++;
 235         }
 236         return error;
 237 }
 238
 239 /** Push an integer to the end.
 240  *
 241  * \public \memberof mlt_deque_s
 242  * \param self a deque
 243  * \param item an integer
 244  * \return true if there was an error
 245  */
 246
 247 int mlt_deque_push_back_int( mlt_deque self, int item )
 248 {
 249         int error = mlt_deque_allocate( self );
 250
 251         if ( error == 0 )
 252                 self->list[ self->count ++ ].value = item;
 253
 254         return error;
 255 }
 256
 257 /** Pop an integer.
 258  *
 259  * \public \memberof mlt_deque_s
 260  * \param self a deque
 261  * \return an integer
 262  */
 263
 264 int mlt_deque_pop_back_int( mlt_deque self )
 265 {
 266         return self->count > 0 ? self->list[ -- self->count ].value : 0;
 267 }
 268
 269 /** Queue an integer at the start.
 270  *
 271  * \public \memberof mlt_deque_s
 272  * \param self a deque
 273  * \param item an integer
 274  * \return true if there was an error
 275  */
 276
 277 int mlt_deque_push_front_int( mlt_deque self, int item )
 278 {
 279         int error = mlt_deque_allocate( self );
 280
 281         if ( error == 0 )
 282         {
 283                 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
 284                 self->list[ 0 ].value = item;
 285         }
 286
 287         return error;
 288 }
 289
 290 /** Remove an integer from the start.
 291  *
 292  * \public \memberof mlt_deque_s
 293  * \param self a deque
 294  * \return an integer
 295  */
 296
 297 int mlt_deque_pop_front_int( mlt_deque self )
 298 {
 299         int item = 0;
 300
 301         if ( self->count > 0 )
 302         {
 303                 item = self->list[ 0 ].value;
 304                 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
 305         }
 306
 307         return item;
 308 }
 309
 310 /** Inquire on an integer at back of deque but don't remove.
 311  *
 312  * \public \memberof mlt_deque_s
 313  * \param self a deque
 314  * \return an integer
 315  */
 316
 317 int mlt_deque_peek_back_int( mlt_deque self )
 318 {
 319         return self->count > 0 ? self->list[ self->count - 1 ].value : 0;
 320 }
 321
 322 /** Inquire on an integer at front of deque but don't remove.
 323  *
 324  * \public \memberof mlt_deque_s
 325  * \param self a deque
 326  * \return an integer
 327  */
 328
 329 int mlt_deque_peek_front_int( mlt_deque self )
 330 {
 331         return self->count > 0 ? self->list[ 0 ].value : 0;
 332 }
 333
 334 /** Push a double float to the end.
 335  *
 336  * \public \memberof mlt_deque_s
 337  * \param self a deque
 338  * \param item a double float
 339  * \return true if there was an error
 340  */
 341
 342 int mlt_deque_push_back_double( mlt_deque self, double item )
 343 {
 344         int error = mlt_deque_allocate( self );
 345
 346         if ( error == 0 )
 347                 self->list[ self->count ++ ].floating = item;
 348
 349         return error;
 350 }
 351
 352 /** Pop a double float.
 353  *
 354  * \public \memberof mlt_deque_s
 355  * \param self a deque
 356  * \return a double float
 357  */
 358
 359 double mlt_deque_pop_back_double( mlt_deque self )
 360 {
 361         return self->count > 0 ? self->list[ -- self->count ].floating : 0;
 362 }
 363
 364 /** Queue a double float at the start.
 365  *
 366  * \public \memberof mlt_deque_s
 367  * \param self a deque
 368  * \param item a double float
 369  * \return true if there was an error
 370  */
 371
 372 int mlt_deque_push_front_double( mlt_deque self, double item )
 373 {
 374         int error = mlt_deque_allocate( self );
 375
 376         if ( error == 0 )
 377         {
 378                 memmove( &self->list[ 1 ], self->list, ( self->count ++ ) * sizeof( deque_entry ) );
 379                 self->list[ 0 ].floating = item;
 380         }
 381
 382         return error;
 383 }
 384
 385 /** Remove a double float from the start.
 386  *
 387  * \public \memberof mlt_deque_s
 388  * \param self a deque
 389  * \return a double float
 390  */
 391
 392 double mlt_deque_pop_front_double( mlt_deque self )
 393 {
 394         double item = 0;
 395
 396         if ( self->count > 0 )
 397         {
 398                 item = self->list[ 0 ].floating;
 399                 memmove( self->list, &self->list[ 1 ], ( -- self->count ) * sizeof( deque_entry ) );
 400         }
 401
 402         return item;
 403 }
 404
 405 /** Inquire on a double float at back of deque but don't remove.
 406  *
 407  * \public \memberof mlt_deque_s
 408  * \param self a deque
 409  * \return a double float
 410  */
 411
 412 double mlt_deque_peek_back_double( mlt_deque self )
 413 {
 414         return self->count > 0 ? self->list[ self->count - 1 ].floating : 0;
 415 }
 416
 417 /** Inquire on a double float at front of deque but don't remove.
 418  *
 419  * \public \memberof mlt_deque_s
 420  * \param self a deque
 421  * \return a double float
 422  */
 423
 424 double mlt_deque_peek_front_double( mlt_deque self )
 425 {
 426         return self->count > 0 ? self->list[ 0 ].floating : 0;
 427 }
 428
 429 /** Destroy the queue.
 430  *
 431  * \public \memberof mlt_deque_s
 432  * \param self a deque
 433  */
 434
 435 void mlt_deque_close( mlt_deque self )
 436 {
 437         free( self->list );
 438         free( self );
 439 }