git.sesse.net Git - vlc/blob - 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 static void DumpDict( dict_t *p_dict )
 176 {
 177     int i = 0;
 178     fprintf( stderr, "**** Begin Dump ****\n" );
 179     for( i = 0 ; i < p_dict->i_entries; i++ )
 180     {
 181         fprintf( stderr, "Entry %i - hash %lli int %i string %s data %p\n",
 182                         i, p_dict->p_entries[i].i_hash,
 183                         p_dict->p_entries[i].i_int,
 184                         p_dict->p_entries[i].psz_string,
 185                         p_dict->p_entries[i].p_data );
 186     }
 187     fprintf( stderr, "**** End Dump ****\n" );
 188 }
 189
 190 PyObject *dict_test( PyObject *self, PyObject *args )
 191 {
 192     int i42 = 42,i40 = 40,i12 = 12, i0 = 0, i00 = 0;
 193
 194     dict_t *p_dict = vlc_DictNew();
 195     ASSERT( p_dict->i_entries == 0, "" );
 196     ASSERT( p_dict->p_entries == NULL, "" );
 197
 198     vlc_DictInsert( p_dict, 0, NULL, (void*)(&i42) );
 199     ASSERT( p_dict->i_entries == 1, "" );
 200     ASSERT( p_dict->p_entries[0].p_data == (void*)(&i42), "" );
 201
 202     vlc_DictInsert( p_dict, 1, "42", (void*)(&i42) );
 203     ASSERT( p_dict->i_entries == 2, "" );
 204     ASSERT( vlc_DictGet( p_dict, 1, "42" ) == (void*)(&i42), "" );
 205     ASSERT( vlc_DictGet( p_dict, 0, "42" ) == NULL , "");
 206     ASSERT( vlc_DictGet( p_dict, 1, " 42" ) == NULL , "");
 207
 208     vlc_DictInsert( p_dict, 1, "12", (void*)(&i12) );
 209     ASSERT( vlc_DictGet( p_dict, 1, "12") == (void*)(&i12), "" );
 210
 211     vlc_DictInsert( p_dict, 3, "40", (void*)(&i40) );
 212     ASSERT( vlc_DictGet( p_dict, 3, "40") == (void*)(&i40), "" );
 213     ASSERT( vlc_DictGet( p_dict, 1, "12") == (void*)(&i12), "" );
 214     ASSERT( vlc_DictGet( p_dict, 1, "42") == (void*)(&i42), "" );
 215
 216     vlc_DictInsert( p_dict, 12, "zero-1", (void*)(&i0) );
 217     vlc_DictInsert( p_dict, 5, "zero-0", (void*)(&i00) );
 218     ASSERT( vlc_DictGet( p_dict, 12, "zero-1") == (void*)(&i0), "" );
 219     ASSERT( vlc_DictGet( p_dict, 5, "zero-0") == (void*)(&i00), "" );
 220     ASSERT( vlc_DictGet( p_dict, 12, "zero-0") == NULL, "" );
 221
 222     vlc_DictInsert( p_dict, 0, "12", (void*)(&i12) );
 223     vlc_DictInsert( p_dict, 0, "thisisaverylongstringwith12", (void*)(&i12) );
 224     ASSERT( vlc_DictGet( p_dict, 0, "thisisaverylongstringwith12" ) ==
 225                     (void*)(&i12),"" );
 226     ASSERT( vlc_DictGet( p_dict, 0, "thisisaverylongstringwith13" ) == NULL,"");
 227
 228     vlc_DictClear( p_dict );
 229
 230     Py_INCREF( Py_None);
 231     return Py_None;
 232 }