test/native/algo.c

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