]> git.sesse.net Git - vlc/blob - test/native/algo.c
Removes trailing spaces. Removes tabs.
[vlc] / test / native / algo.c
1 /*****************************************************************************
2  * algo.c : Algorithms test
3  *****************************************************************************
4  * Copyright (C) 2006 VideoLAN
5  * $Id: i18n.c 16157 2006-07-29 13:32:12Z zorglub $
6  *
7  * This program is free software; you can redistribute it and/or modify
8  * it under the terms of the GNU General Public License as published by
9  * the Free Software Foundation; either version 2 of the License, or
10  * (at your option) any later version.
11  *
12  * This program 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
15  * GNU General Public License for more details.
16  *
17  * You should have received a copy of the GNU General Public License
18  * along with this program; if not, write to the Free Software
19  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301, USA.
20  *****************************************************************************/
21
22 #include "../pyunit.h"
23 #include <vlc/vlc.h>
24
25 /**********************************************************************
26  * Arrays
27  *********************************************************************/
28
29 TYPEDEF_ARRAY(long,long_array_t);
30
31 PyObject *arrays_test( PyObject *self, PyObject *args )
32 {
33     mtime_t one, two;
34     int number = 1000000;
35     int number2 = 50000; /* For slow with memmove */
36     printf("\n");
37     {
38         int i_items = 0;
39         int *p_items = NULL;
40         int i;
41         one = mdate();
42         for( i = 0 ; i<number;i++) {
43             INSERT_ELEM(p_items,i_items, i_items, i+50);
44         }
45         two = mdate();
46         printf( " Std array %i items appended in "I64Fi" µs\n", number,
47                 (two-one) );
48         for( i = number-1 ; i>=0; i--) {
49             REMOVE_ELEM( p_items, i_items, i );
50         }
51         one = mdate();
52         printf( " Std array %i items removed in  "I64Fi" µs\n", number,
53                 (one-two) );
54
55         for( i = 0 ; i<number2;i++) {
56             int pos = i_items == 0  ? 0 : rand() % i_items;
57             INSERT_ELEM(p_items, i_items, pos, pos + 50);
58         }
59         two = mdate();
60         printf( " Std array %i items inserted in  "I64Fi" µs\n", number2,
61                 (two-one) );
62     }
63     {
64         DECL_ARRAY(int) int_array;
65         int i = 0;
66         ARRAY_INIT(int_array);
67         ASSERT(int_array.i_size == 0, "" );
68         ASSERT(int_array.i_alloc == 0, "" );
69         ASSERT(int_array.p_elems == 0, "" );
70
71         ARRAY_APPEND(int_array, 42 );
72         ASSERT(int_array.i_size == 1, "" );
73         ASSERT(int_array.i_alloc > 1, "" );
74         ASSERT(int_array.p_elems[0] == 42, "" );
75         ARRAY_REMOVE(int_array,0);
76         ASSERT(int_array.i_size == 0, "" );
77
78         one = mdate();
79         for( i = 0 ; i<number;i++) {
80             ARRAY_APPEND(int_array, i+50);
81         }
82         two = mdate();
83         printf( " New array %i items appended in "I64Fi" µs\n", number,
84                 (two-one) );
85         ASSERT(int_array.p_elems[1242] == 1292 , "");
86         for( i = number-1 ; i>=0; i--) {
87             ARRAY_REMOVE(int_array,i);
88         }
89         one = mdate();
90         printf( " New array %i items removed in  "I64Fi" µs\n", number,
91                 (one-two) );
92
93         /* Now random inserts */
94         for( i = 0 ; i<number2;i++) {
95             int pos = int_array.i_size == 0  ? 0 : rand() % int_array.i_size;
96             ARRAY_INSERT(int_array, pos+50, pos);
97         }
98         two = mdate();
99         printf( " New array %i items inserted in  "I64Fi" µs\n", number2,
100                 (two-one) );
101     }
102     {
103         long_array_t larray;
104         ARRAY_INIT(larray);
105     }
106     Py_INCREF( Py_None);
107     return Py_None;
108 }
109
110 /**********************************************************************
111  * Binary search
112  *********************************************************************/
113
114 PyObject *bsearch_direct_test( PyObject *self, PyObject *args )
115 {
116 #define DIRCHECK( size, initial, checked, expected ) { \
117     int array[size] = initial; \
118     int answer = -1;  \
119     BSEARCH( array, size, , int, checked, answer ); \
120     ASSERT( answer == expected , "" ); }
121
122 #define ORDERED10 {0,1,2,3,4,5,6,7,8,9}
123     DIRCHECK( 10, ORDERED10, 0, 0 );
124     DIRCHECK( 10, ORDERED10, 1, 1 );
125     DIRCHECK( 10, ORDERED10, 2, 2 );
126     DIRCHECK( 10, ORDERED10, 3, 3 );
127     DIRCHECK( 10, ORDERED10, 4, 4 );
128     DIRCHECK( 10, ORDERED10, 5, 5 );
129     DIRCHECK( 10, ORDERED10, 6, 6 );
130     DIRCHECK( 10, ORDERED10, 7, 7 );
131     DIRCHECK( 10, ORDERED10, 8, 8 );
132     DIRCHECK( 10, ORDERED10, 9,9 );
133
134     DIRCHECK( 10, ORDERED10, 10, -1 );
135     DIRCHECK( 10, ORDERED10, -1, -1 );
136
137     /* TODO: tests on unordered arrays, odd number of elements, 1 element, 2 */
138
139     Py_INCREF( Py_None);
140     return Py_None;
141 }
142
143 struct bsearch_tester
144 {
145     int key; int value;
146 };
147
148 /* Lighter test, we just check correct member access, all the real testing
149  * has been made already */
150 PyObject *bsearch_member_test( PyObject *self, PyObject *args )
151 {
152     struct bsearch_tester array[] =
153     {
154         { 0, 12 }, { 1, 22 } , { 2, 33 } , { 3, 68 } , { 4, 56 }
155     };
156 #define MEMBCHECK( checked, expected ) { \
157     int answer = -1;  \
158     BSEARCH( array, 5, .key , int, checked, answer ); \
159     ASSERT( answer == expected , "" ); }
160
161     MEMBCHECK( 0, 0 ) ;
162     MEMBCHECK( 1, 1 );
163     MEMBCHECK( 2, 2 );
164     MEMBCHECK( 3, 3 );
165     MEMBCHECK( 4, 4 );
166     MEMBCHECK( 5, -1 );
167
168     Py_INCREF( Py_None);
169     return Py_None;
170 }
171
172 /**********************************************************************
173  * Dictionnary
174  *********************************************************************/
175 DICT_TYPE( test, int );
176
177 static void DumpDict( dict_test_t *p_dict )
178 {
179     int i = 0;
180     fprintf( stderr, "**** Begin Dump ****\n" );
181     for( i = 0 ; i < p_dict->i_entries; i++ )
182     {
183         fprintf( stderr, "Entry %i - hash %lli int %i string %s data %i\n",
184                         i, p_dict->p_entries[i].i_hash,
185                         p_dict->p_entries[i].i_int,
186                         p_dict->p_entries[i].psz_string,
187                         p_dict->p_entries[i].data );
188     }
189     fprintf( stderr, "**** End Dump ****\n" );
190 }
191
192 PyObject *dict_test( PyObject *self, PyObject *args )
193 {
194     int i42 = 42,i40 = 40,i12 = 12, i0 = 0, i00 = 0;
195     int answer;
196
197     printf("\n");
198
199     dict_test_t *p_dict;
200     DICT_NEW( p_dict );
201     ASSERT( p_dict->i_entries == 0, "" );
202     ASSERT( p_dict->p_entries == NULL, "" );
203
204     DICT_INSERT( p_dict, 0, NULL, i42 );
205     ASSERT( p_dict->i_entries == 1, "" );
206     ASSERT( p_dict->p_entries[0].data == i42, "" );
207
208     DICT_INSERT( p_dict, 1, "42", i42 );
209     ASSERT( p_dict->i_entries == 2, "" );
210
211     DICT_LOOKUP( p_dict, 1, "42", answer );
212     DICT_GET( p_dict, 1, "42", answer );
213     ASSERT( answer == i42, "" );
214     DICT_LOOKUP( p_dict, 0, "42", answer ); ASSERT( answer == -1, "" );
215     DICT_LOOKUP( p_dict, 1, " 42", answer ); ASSERT( answer == -1, "" );
216
217     DICT_INSERT( p_dict, 1, "12", i12 );
218     DICT_GET( p_dict, 1, "12", answer ) ; ASSERT( answer == i12, "" );
219
220     DICT_INSERT( p_dict, 3, "40", i40 );
221     DICT_GET( p_dict, 1, "42", answer ); ASSERT( answer == i42, "" );
222     DICT_GET( p_dict, 3, "40", answer ); ASSERT( answer == i40, "" );
223     DICT_GET( p_dict, 1, "12", answer ); ASSERT( answer == i12, "" );
224
225     DICT_INSERT( p_dict, 12, "zero-1", i0 );
226     DICT_INSERT( p_dict, 5, "zero-0", i00 );
227     DICT_GET( p_dict, 12, "zero-1", answer ); ASSERT( answer == i0, "" );
228     DICT_GET( p_dict, 5, "zero-0", answer ); ASSERT( answer == i00, "" );
229     answer = -1;
230     DICT_GET( p_dict, 12, "zero-0", answer ); ASSERT( answer == -1, "" );
231     DICT_GET( p_dict, 1, "12", answer ); ASSERT( answer == i12, "" );
232
233     DICT_INSERT( p_dict, 0, "zero", 17 );
234     DICT_GET( p_dict, 1, "12", answer ); ASSERT( answer == i12, "" );
235     DICT_GET( p_dict, 12, "zero-1", answer ); ASSERT( answer == i0, "" );
236     DICT_GET( p_dict, 0, "zero", answer ); ASSERT( answer == 17, "" );
237
238     DICT_INSERT( p_dict, 0, "12", i12 );
239     DICT_INSERT( p_dict, 0, "thisisaverylongstringwith12", i12 );
240     answer = -1;
241     DICT_GET( p_dict, 0, "thisisaverylongstringwith12", answer );
242     ASSERT( answer == i12, "" );
243     answer = -1;
244     DICT_GET( p_dict, 0, "thisisaverylongstringwith13", answer );
245     ASSERT( answer == -1, "" );
246
247     DICT_CLEAR( p_dict );
248
249     Py_INCREF( Py_None);
250     return Py_None;
251 }