research.m1stereo.tv/gitweb/ - melted/blob - src/framework/mlt_deque.c

   1 /**
   2  * \file mlt_deque.c
   3  * \brief double ended queue
   4  *
   5  * Copyright (C) 2003-2008 Ushodaya Enterprises Limited
   6  * \author Charles Yates <charles.yates@pandora.be>
   7  *
   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.
  12  *
  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.
  17  *
  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
  21  */
  22
  23 // Local header files
  24 #include "mlt_deque.h"
  25
  26 // System header files
  27 #include <stdlib.h>
  28 #include <string.h>
  29
  30 /** \brief Deque entry class
  31  *
  32  */
  33
  34 typedef union
  35 {
  36         void *addr;
  37         int value;
  38         double floating;
  39 }
  40 deque_entry;
  41
  42 /** \brief Double-Ended Queue (deque) class
  43  *
  44  * The double-ended queue is a very versatile data structure. MLT uses it as
  45  * list, stack, and circular queue.
  46  */
  47
  48 struct mlt_deque_s
  49 {
  50         deque_entry *list;
  51         int size;
  52         int count;
  53 };
  54
  55 /** Create a deque.
  56  *
  57  * \public \memberof mlt_deque_s
  58  * \return a new deque
  59  */
  60
  61 mlt_deque mlt_deque_init( )
  62 {
  63         mlt_deque this = malloc( sizeof( struct mlt_deque_s ) );
  64         if ( this != NULL )
  65         {
  66                 this->list = NULL;
  67                 this->size = 0;
  68                 this->count = 0;
  69         }
  70         return this;
  71 }
  72
  73 /** Return the number of items in the deque.
  74  *
  75  * \public \memberof mlt_deque_s
  76  * \param this a deque
  77  * \return the number of items
  78  */
  79
  80 int mlt_deque_count( mlt_deque this )
  81 {
  82         return this->count;
  83 }
  84
  85 /** Allocate space on the deque.
  86  *
  87  * \private \memberof mlt_deque_s
  88  * \param this a deque
  89  * \return true if there was an error
  90  */
  91
  92 static int mlt_deque_allocate( mlt_deque this )
  93 {
  94         if ( this->count == this->size )
  95         {
  96                 this->list = realloc( this->list, sizeof( deque_entry ) * ( this->size + 20 ) );
  97                 this->size += 20;
  98         }
  99         return this->list == NULL;
 100 }
 101
 102 /** Push an item to the end.
 103  *
 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
 108  */
 109
 110 int mlt_deque_push_back( mlt_deque this, void *item )
 111 {
 112         int error = mlt_deque_allocate( this );
 113
 114         if ( error == 0 )
 115                 this->list[ this->count ++ ].addr = item;
 116
 117         return error;
 118 }
 119
 120 /** Pop an item.
 121  *
 122  * \public \memberof mlt_deque_s
 123  * \param this a pointer
 124  * \return an opaque pointer
 125  */
 126
 127 void *mlt_deque_pop_back( mlt_deque this )
 128 {
 129         return this->count > 0 ? this->list[ -- this->count ].addr : NULL;
 130 }
 131
 132 /** Queue an item at the start.
 133  *
 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
 138  */
 139
 140 int mlt_deque_push_front( mlt_deque this, void *item )
 141 {
 142         int error = mlt_deque_allocate( this );
 143
 144         if ( error == 0 )
 145         {
 146                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 147                 this->list[ 0 ].addr = item;
 148         }
 149
 150         return error;
 151 }
 152
 153 /** Remove an item from the start.
 154  *
 155  * \public \memberof mlt_deque_s
 156  * \param this a pointer
 157  * \return an opaque pointer
 158  */
 159
 160 void *mlt_deque_pop_front( mlt_deque this )
 161 {
 162         void *item = NULL;
 163
 164         if ( this->count > 0 )
 165         {
 166                 item = this->list[ 0 ].addr;
 167                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 168         }
 169
 170         return item;
 171 }
 172
 173 /** Inquire on item at back of deque but don't remove.
 174  *
 175  * \public \memberof mlt_deque_s
 176  * \param this a deque
 177  * \return an opaque pointer
 178  */
 179
 180 void *mlt_deque_peek_back( mlt_deque this )
 181 {
 182         return this->count > 0 ? this->list[ this->count - 1 ].addr : NULL;
 183 }
 184
 185 /** Inquire on item at front of deque but don't remove.
 186  *
 187  * \public \memberof mlt_deque_s
 188  * \param this a deque
 189  * \return an opaque pointer
 190  */
 191
 192 void *mlt_deque_peek_front( mlt_deque this )
 193 {
 194         return this->count > 0 ? this->list[ 0 ].addr : NULL;
 195 }
 196
 197 /** Push an integer to the end.
 198  *
 199  * \public \memberof mlt_deque_s
 200  * \param this a deque
 201  * \param item an integer
 202  * \return true if there was an error
 203  */
 204
 205 int mlt_deque_push_back_int( mlt_deque this, int item )
 206 {
 207         int error = mlt_deque_allocate( this );
 208
 209         if ( error == 0 )
 210                 this->list[ this->count ++ ].value = item;
 211
 212         return error;
 213 }
 214
 215 /** Pop an integer.
 216  *
 217  * \public \memberof mlt_deque_s
 218  * \param this a deque
 219  * \return an integer
 220  */
 221
 222 int mlt_deque_pop_back_int( mlt_deque this )
 223 {
 224         return this->count > 0 ? this->list[ -- this->count ].value : 0;
 225 }
 226
 227 /** Queue an integer at the start.
 228  *
 229  * \public \memberof mlt_deque_s
 230  * \param this a deque
 231  * \param item an integer
 232  * \return true if there was an error
 233  */
 234
 235 int mlt_deque_push_front_int( mlt_deque this, int item )
 236 {
 237         int error = mlt_deque_allocate( this );
 238
 239         if ( error == 0 )
 240         {
 241                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 242                 this->list[ 0 ].value = item;
 243         }
 244
 245         return error;
 246 }
 247
 248 /** Remove an integer from the start.
 249  *
 250  * \public \memberof mlt_deque_s
 251  * \param this a deque
 252  * \return an integer
 253  */
 254
 255 int mlt_deque_pop_front_int( mlt_deque this )
 256 {
 257         int item = 0;
 258
 259         if ( this->count > 0 )
 260         {
 261                 item = this->list[ 0 ].value;
 262                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 263         }
 264
 265         return item;
 266 }
 267
 268 /** Inquire on an integer at back of deque but don't remove.
 269  *
 270  * \public \memberof mlt_deque_s
 271  * \param this a deque
 272  * \return an integer
 273  */
 274
 275 int mlt_deque_peek_back_int( mlt_deque this )
 276 {
 277         return this->count > 0 ? this->list[ this->count - 1 ].value : 0;
 278 }
 279
 280 /** Inquire on an integer at front of deque but don't remove.
 281  *
 282  * \public \memberof mlt_deque_s
 283  * \param this a deque
 284  * \return an integer
 285  */
 286
 287 int mlt_deque_peek_front_int( mlt_deque this )
 288 {
 289         return this->count > 0 ? this->list[ 0 ].value : 0;
 290 }
 291
 292 /** Push a double float to the end.
 293  *
 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
 298  */
 299
 300 int mlt_deque_push_back_double( mlt_deque this, double item )
 301 {
 302         int error = mlt_deque_allocate( this );
 303
 304         if ( error == 0 )
 305                 this->list[ this->count ++ ].floating = item;
 306
 307         return error;
 308 }
 309
 310 /** Pop a double float.
 311  *
 312  * \public \memberof mlt_deque_s
 313  * \param this a deque
 314  * \return a double float
 315  */
 316
 317 double mlt_deque_pop_back_double( mlt_deque this )
 318 {
 319         return this->count > 0 ? this->list[ -- this->count ].floating : 0;
 320 }
 321
 322 /** Queue a double float at the start.
 323  *
 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
 328  */
 329
 330 int mlt_deque_push_front_double( mlt_deque this, double item )
 331 {
 332         int error = mlt_deque_allocate( this );
 333
 334         if ( error == 0 )
 335         {
 336                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 337                 this->list[ 0 ].floating = item;
 338         }
 339
 340         return error;
 341 }
 342
 343 /** Remove a double float from the start.
 344  *
 345  * \public \memberof mlt_deque_s
 346  * \param this a deque
 347  * \return a double float
 348  */
 349
 350 double mlt_deque_pop_front_double( mlt_deque this )
 351 {
 352         double item = 0;
 353
 354         if ( this->count > 0 )
 355         {
 356                 item = this->list[ 0 ].floating;
 357                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 358         }
 359
 360         return item;
 361 }
 362
 363 /** Inquire on a double float at back of deque but don't remove.
 364  *
 365  * \public \memberof mlt_deque_s
 366  * \param this a deque
 367  * \return a double float
 368  */
 369
 370 double mlt_deque_peek_back_double( mlt_deque this )
 371 {
 372         return this->count > 0 ? this->list[ this->count - 1 ].floating : 0;
 373 }
 374
 375 /** Inquire on a double float at front of deque but don't remove.
 376  *
 377  * \public \memberof mlt_deque_s
 378  * \param this a deque
 379  * \return a double float
 380  */
 381
 382 double mlt_deque_peek_front_double( mlt_deque this )
 383 {
 384         return this->count > 0 ? this->list[ 0 ].floating : 0;
 385 }
 386
 387 /** Destroy the queue.
 388  *
 389  * \public \memberof mlt_deque_s
 390  * \param this a deque
 391  */
 392
 393 void mlt_deque_close( mlt_deque this )
 394 {
 395         free( this->list );
 396         free( this );
 397 }