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