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