git.sesse.net Git - mlt/blob - src/framework/mlt_deque.c

   1 /*
   2  * mlt_deque.c -- double ended queue
   3  * Copyright (C) 2003-2004 Ushodaya Enterprises Limited
   4  * Author: Charles Yates <charles.yates@pandora.be>
   5  *
   6  * This program is free software; you can redistribute it and/or modify
   7  * it under the terms of the GNU General Public License as published by
   8  * the Free Software Foundation; either version 2 of the License, or
   9  * (at your option) any later version.
  10  *
  11  * This program is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14  * GNU General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU General Public License
  17  * along with this program; if not, write to the Free Software Foundation,
  18  * Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
  19  */
  20
  21 // Local header files
  22 #include "mlt_deque.h"
  23
  24 // System header files
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 typedef union
  29 {
  30         void *addr;
  31         int value;
  32 }
  33 deque_entry;
  34
  35 /** Private structure.
  36 */
  37
  38 struct mlt_deque_s
  39 {
  40         deque_entry *list;
  41         int size;
  42         int count;
  43 };
  44
  45 /** Create a deque.
  46 */
  47
  48 mlt_deque mlt_deque_init( )
  49 {
  50         mlt_deque this = malloc( sizeof( struct mlt_deque_s ) );
  51         if ( this != NULL )
  52         {
  53                 this->list = NULL;
  54                 this->size = 0;
  55                 this->count = 0;
  56         }
  57         return this;
  58 }
  59
  60 /** Return the number of items in the deque.
  61 */
  62
  63 int mlt_deque_count( mlt_deque this )
  64 {
  65         return this->count;
  66 }
  67
  68 /** Allocate space on the deque.
  69 */
  70
  71 static int mlt_deque_allocate( mlt_deque this )
  72 {
  73         if ( this->count == this->size )
  74         {
  75                 this->list = realloc( this->list, sizeof( deque_entry ) * ( this->size + 20 ) );
  76                 this->size += 20;
  77         }
  78         return this->list == NULL;
  79 }
  80
  81 /** Push an item to the end.
  82 */
  83
  84 int mlt_deque_push_back( mlt_deque this, void *item )
  85 {
  86         int error = mlt_deque_allocate( this );
  87
  88         if ( error == 0 )
  89                 this->list[ this->count ++ ].addr = item;
  90
  91         return error;
  92 }
  93
  94 /** Pop an item.
  95 */
  96
  97 void *mlt_deque_pop_back( mlt_deque this )
  98 {
  99         return this->count > 0 ? this->list[ -- this->count ].addr : NULL;
 100 }
 101
 102 /** Queue an item at the start.
 103 */
 104
 105 int mlt_deque_push_front( mlt_deque this, void *item )
 106 {
 107         int error = mlt_deque_allocate( this );
 108
 109         if ( error == 0 )
 110         {
 111                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 112                 this->list[ 0 ].addr = item;
 113         }
 114
 115         return error;
 116 }
 117
 118 /** Remove an item from the start.
 119 */
 120
 121 void *mlt_deque_pop_front( mlt_deque this )
 122 {
 123         void *item = NULL;
 124
 125         if ( this->count > 0 )
 126         {
 127                 item = this->list[ 0 ].addr;
 128                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 129         }
 130
 131         return item;
 132 }
 133
 134 /** Inquire on item at back of deque but don't remove.
 135 */
 136
 137 void *mlt_deque_peek_back( mlt_deque this )
 138 {
 139         return this->count > 0 ? this->list[ this->count - 1 ].addr : NULL;
 140 }
 141
 142 /** Inquire on item at front of deque but don't remove.
 143 */
 144
 145 void *mlt_deque_peek_front( mlt_deque this )
 146 {
 147         return this->count > 0 ? this->list[ 0 ].addr : NULL;
 148 }
 149
 150 /** Push an item to the end.
 151 */
 152
 153 int mlt_deque_push_back_int( mlt_deque this, int item )
 154 {
 155         int error = mlt_deque_allocate( this );
 156
 157         if ( error == 0 )
 158                 this->list[ this->count ++ ].value = item;
 159
 160         return error;
 161 }
 162
 163 /** Pop an item.
 164 */
 165
 166 int mlt_deque_pop_back_int( mlt_deque this )
 167 {
 168         return this->count > 0 ? this->list[ -- this->count ].value : 0;
 169 }
 170
 171 /** Queue an item at the start.
 172 */
 173
 174 int mlt_deque_push_front_int( mlt_deque this, int item )
 175 {
 176         int error = mlt_deque_allocate( this );
 177
 178         if ( error == 0 )
 179         {
 180                 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( deque_entry ) );
 181                 this->list[ 0 ].value = item;
 182         }
 183
 184         return error;
 185 }
 186
 187 /** Remove an item from the start.
 188 */
 189
 190 int mlt_deque_pop_front_int( mlt_deque this )
 191 {
 192         int item = 0;
 193
 194         if ( this->count > 0 )
 195         {
 196                 item = this->list[ 0 ].value;
 197                 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( deque_entry ) );
 198         }
 199
 200         return item;
 201 }
 202
 203 /** Inquire on item at back of deque but don't remove.
 204 */
 205
 206 int mlt_deque_peek_back_int( mlt_deque this )
 207 {
 208         return this->count > 0 ? this->list[ this->count - 1 ].value : 0;
 209 }
 210
 211 /** Inquire on item at front of deque but don't remove.
 212 */
 213
 214 int mlt_deque_peek_front_int( mlt_deque this )
 215 {
 216         return this->count > 0 ? this->list[ 0 ].value : 0;
 217 }
 218
 219 /** Close the queue.
 220 */
 221
 222 void mlt_deque_close( mlt_deque this )
 223 {
 224         free( this->list );
 225         free( this );
 226 }
 227