Debian Codegraph @

src/deque.c

raw
1 /*
2 * deque.c -- double ended queue
3 * Copyright (C) 2003-2004 Ushodaya Enterprises Limited
4 * Author: Charles Yates <[email protected]>
5 * Copied from mlt: http://www.sf.net/projects/mlt
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2.1 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21
22 #include "deque.h"
23
24 #include <stdlib.h>
25 #include <string.h>
26
27 /** Private structure.
28 */
29
30 struct iec61883_deque
31 {
32 void **list;
33 int size;
34 int count;
35 };
36
37 /** Create a deque.
38 */
39
40 iec61883_deque_t iec61883_deque_init( )
41 {
42 iec61883_deque_t this = malloc( sizeof( struct iec61883_deque ) );
43 if ( this != NULL )
44 {
45 this->list = NULL;
46 this->size = 0;
47 this->count = 0;
48 }
49 return this;
50 }
51
52 /** Return the number of items in the deque.
53 */
54
55 int iec61883_deque_size( iec61883_deque_t this )
56 {
57 return this->count;
58 }
59
60 /** Allocate space on the deque.
61 */
62
63 static int iec61883_deque_allocate( iec61883_deque_t this )
64 {
65 if ( this->count == this->size )
66 {
67 this->list = realloc( this->list, sizeof( void * ) * ( this->size + 20 ) );
68 this->size += 20;
69 }
70 return this->list == NULL;
71 }
72
73 /** Push an item to the end.
74 */
75
76 int iec61883_deque_push_back( iec61883_deque_t this, void *item )
77 {
78 int error = iec61883_deque_allocate( this );
79
80 if ( error == 0 )
81 this->list[ this->count ++ ] = item;
82
83 return error;
84 }
85
86 /** Pop an item.
87 */
88
89 void *iec61883_deque_pop_back( iec61883_deque_t this )
90 {
91 return this->count > 0 ? this->list[ -- this->count ] : NULL;
92 }
93
94 /** Queue an item at the start.
95 */
96
97 int iec61883_deque_push_front( iec61883_deque_t this, void *item )
98 {
99 int error = iec61883_deque_allocate( this );
100
101 if ( error == 0 )
102 {
103 memmove( &this->list[ 1 ], this->list, ( this->count ++ ) * sizeof( void * ) );
104 this->list[ 0 ] = item;
105 }
106
107 return error;
108 }
109
110 /** Remove an item from the start.
111 */
112
113 void *iec61883_deque_pop_front( iec61883_deque_t this )
114 {
115 void *item = NULL;
116
117 if ( this->count > 0 )
118 {
119 item = this->list[ 0 ];
120 memmove( this->list, &this->list[ 1 ], ( -- this->count ) * sizeof( void * ) );
121 }
122
123 return item;
124 }
125
126 /** Get the item at back of deque but don't remove.
127 */
128
129 void *iec61883_deque_back( iec61883_deque_t this )
130 {
131 return this->count > 0 ? this->list[ this->count - 1 ] : NULL;
132 }
133
134 /** Get the item at front of deque but don't remove.
135 */
136
137 void *iec61883_deque_front( iec61883_deque_t this )
138 {
139 return this->count > 0 ? this->list[ 0 ] : NULL;
140 }
141
142 /** Close the queue.
143 */
144
145 void iec61883_deque_close( iec61883_deque_t this )
146 {
147 free( this->list );
148 free( this );
149 }