Changeset 9c47a47


Ignore:
Timestamp:
Dec 28, 2017, 9:56:28 PM (7 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
ADT, aaron-thesis, arm-eh, ast-experimental, cleanup-dtors, deferred_resn, demangler, enum, forall-pointer-decay, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, pthread-emulation, qualifiedEnum, resolv-new, with_gc
Children:
853451b
Parents:
e672372
Message:

extend stdlib bsearch

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed

  • src/libcfa/stdlib

    re672372 r9c47a47  
    1010// Created On       : Thu Jan 28 17:12:35 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Dec 23 18:21:42 2017
    13 // Update Count     : 267
     12// Last Modified On : Thu Dec 28 18:43:12 2017
     13// Update Count     : 277
    1414//
    1515
    … …  
    185185//---------------------------------------
    186186
    187 forall( otype T | { int ?<?( T, T ); } )
    188 T * bsearch( T key, const T * arr, size_t dim );
    189 
    190 forall( otype T | { int ?<?( T, T ); } )
    191 unsigned int bsearch( T key, const T * arr, size_t dim );
    192 
    193 
    194 forall( otype T | { int ?<?( T, T ); } )
    195 void qsort( const T * arr, size_t dim );
     187forall( otype E | { int ?<?( E, E ); } )
     188E * bsearch( E key, const E * arr, size_t dim );
     189
     190forall( otype E | { int ?<?( E, E ); } )
     191unsigned int bsearch( E key, const E * arr, size_t dim );
     192
     193forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
     194E * bsearch( K key, const E * arr, size_t dim );
     195
     196forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
     197unsigned int bsearch( K key, const E * arr, size_t dim );
     198
     199forall( otype E | { int ?<?( E, E ); } )
     200void qsort( E * arr, size_t dim );
    196201
    197202//---------------------------------------

  • src/libcfa/stdlib.c

    re672372 r9c47a47  
    1010// Created On       : Thu Jan 28 17:10:29 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sun Dec 24 13:00:15 2017
    13 // Update Count     : 344
     12// Last Modified On : Thu Dec 28 18:43:16 2017
     13// Update Count     : 378
    1414//
    1515
    … …  
    128128//---------------------------------------
    129129
    130 forall( otype T | { int ?<?( T, T ); } )
    131 T * bsearch( T key, const T * arr, size_t dim ) {
    132         int comp( const void * t1, const void * t2 ) { return *(T *)t1 < *(T *)t2 ? -1 : *(T *)t2 < *(T *)t1 ? 1 : 0; }
    133         return (T *)bsearch( &key, arr, dim, sizeof(T), comp );
     130forall( otype E | { int ?<?( E, E ); } )
     131E * bsearch( E key, const E * arr, size_t dim ) {
     132        int comp( const void * t1, const void * t2 ) { return *(E *)t1 < *(E *)t2 ? -1 : *(E *)t2 < *(E *)t1 ? 1 : 0; }
     133        return (E *)bsearch( &key, arr, dim, sizeof(E), comp );
    134134} // bsearch
    135135
    136 forall( otype T | { int ?<?( T, T ); } )
    137 unsigned int bsearch( T key, const T * arr, size_t dim ) {
    138         T * result = bsearch( key, arr, dim );
    139         return result ? result - arr : dim;                                     // pointer subtraction includes sizeof(T)
     136forall( otype E | { int ?<?( E, E ); } )
     137unsigned int bsearch( E key, const E * arr, size_t dim ) {
     138        E * result = bsearch( key, arr, dim );
     139        return result ? result - arr : dim;                                     // pointer subtraction includes sizeof(E)
    140140} // bsearch
    141141
    142 forall( otype T | { int ?<?( T, T ); } )
    143 void qsort( const T * arr, size_t dim ) {
    144         int comp( const void * t1, const void * t2 ) { return *(T *)t1 < *(T *)t2 ? -1 : *(T *)t2 < *(T *)t1 ? 1 : 0; }
    145         qsort( arr, dim, sizeof(T), comp );
     142forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
     143E * bsearch( K key, const E * arr, size_t dim ) {
     144        int comp( const void * t1, const void * t2 ) { return *(K *)t1 < getKey( *(E *)t2 ) ? -1 : getKey( *(E *)t2 ) < *(K *)t1 ? 1 : 0; }
     145        return (E *)bsearch( &key, arr, dim, sizeof(E), comp );
     146} // bsearch
     147
     148forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
     149unsigned int bsearch( K key, const E * arr, size_t dim ) {
     150        E * result = bsearch( key, arr, dim );
     151        return result ? result - arr : dim;                                     // pointer subtraction includes sizeof(E)
     152} // bsearch
     153
     154forall( otype E | { int ?<?( E, E ); } )
     155void qsort( E * arr, size_t dim ) {
     156        int comp( const void * t1, const void * t2 ) { return *(E *)t1 < *(E *)t2 ? -1 : *(E *)t2 < *(E *)t1 ? 1 : 0; }
     157        qsort( arr, dim, sizeof(E), comp );
    146158} // qsort
    147159

  • src/tests/.expect/searchsort.txt

    re672372 r9c47a47  
    22
    331, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    4 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    5 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    6 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
     410:10, 9:9, 8:8, 7:7, 6:6, 5:5, 4:4, 3:3, 2:2, 1:1,
     510:10, 9:9, 8:8, 7:7, 6:6, 5:5, 4:4, 3:3, 2:2, 1:1,
     610:10, 9:9, 8:8, 7:7, 6:6, 5:5, 4:4, 3:3, 2:2, 1:1,
    77
    881, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    9910, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    10 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    11 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,
     1010:10, 9:9, 8:8, 7:7, 6:6, 5:5, 4:4, 3:3, 2:2, 1:1,
     1110:10, 9:9, 8:8, 7:7, 6:6, 5:5, 4:4, 3:3, 2:2, 1:1,
    1212
    131310.5, 9.5, 8.5, 7.5, 6.5, 5.5, 4.5, 3.5, 2.5, 1.5,
    14141.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 10.5,
    15 10.5, 9.5, 8.5, 7.5, 6.5, 5.5, 4.5, 3.5, 2.5, 1.5,
    16 10.5, 9.5, 8.5, 7.5, 6.5, 5.5, 4.5, 3.5, 2.5, 1.5,
     1510.5:10.5, 9.5:9.5, 8.5:8.5, 7.5:7.5, 6.5:6.5, 5.5:5.5, 4.5:4.5, 3.5:3.5, 2.5:2.5, 1.5:1.5,
     1610.5:10.5, 9.5:9.5, 8.5:8.5, 7.5:7.5, 6.5:6.5, 5.5:5.5, 4.5:4.5, 3.5:3.5, 2.5:2.5, 1.5:1.5,
    1717
    181810 11, 9 10, 8 9, 7 8, 6 7, 5 6, 4 5, 3 4, 2 3, 1 2,
    19191 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 10, 10 11,
    20 10 11, 9 10, 8 9, 7 8, 6 7, 5 6, 4 5, 3 4, 2 3, 1 2,
    21 10 11, 9 10, 8 9, 7 8, 6 7, 5 6, 4 5, 3 4, 2 3, 1 2,
     2010 11:10 11, 9 10:9 10, 8 9:8 9, 7 8:7 8, 6 7:6 7, 5 6:5 6, 4 5:4 5, 3 4:3 4, 2 3:2 3, 1 2:1 2,
     2110 11:10 11, 9 10:9 10, 8 9:8 9, 7 8:7 8, 6 7:6 7, 5 6:5 6, 4 5:4 5, 3 4:3 4, 2 3:2 3, 1 2:1 2,
    2222
     231 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 10, 10 11,
     2411:10 11, 10:9 10, 9:8 9, 8:7 8, 7:6 7, 6:5 6, 5:4 5, 4:3 4, 3:2 3, 2:1 2,
     2511:10 11, 10:9 10, 9:8 9, 8:7 8, 7:6 7, 6:5 6, 5:4 5, 4:3 4, 3:2 3, 2:1 2,
     26

  • src/tests/searchsort.c

    re672372 r9c47a47  
    1010// Created On       : Thu Feb  4 18:17:50 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Dec  7 09:14:06 2017
    13 // Update Count     : 77
     12// Last Modified On : Thu Dec 28 18:48:10 2017
     13// Update Count     : 99
    1414//
    1515
    … …  
    3838        for ( unsigned int i = 0; i < size; i += 1 ) {          // C version
    3939                int key = size - i;
    40                 int *v = bsearch( &key, iarr, size, sizeof( iarr[0] ), comp );
    41                 sout | *v | ", ";
     40                int * v = bsearch( &key, iarr, size, sizeof( iarr[0] ), comp );
     41                sout | key | ':' | *v | ", ";
    4242        } // for
    4343        sout | endl;
     44
    4445        for ( unsigned int i = 0; i < size; i += 1 ) {
    45                 int *v = bsearch( size - i, iarr, size );
    46                 sout | *v | ", ";
     46                int * v = bsearch( size - i, iarr, size );
     47                sout | size - i | ':' | *v | ", ";
    4748        } // for
    4849        sout | endl;
    4950        for ( unsigned int i = 0; i < size; i += 1 ) {
    5051                unsigned int posn = bsearch( size - i, iarr, size );
    51                 sout | iarr[posn] | ", ";
     52                sout | size - i | ':' | iarr[posn] | ", ";
    5253        } // for
    5354        sout | endl | endl;
    … …  
    6768                sout | endl;
    6869                for ( unsigned int i = 0; i < size; i += 1 ) {
    69                         int *v = bsearch( size - i, iarr, size );
    70                         sout | *v | ", ";
     70                        int * v = bsearch( size - i, iarr, size );
     71                        sout | size - i | ':' | *v | ", ";
    7172                } // for
    7273                sout | endl;
    7374                for ( unsigned int i = 0; i < size; i += 1 ) {
    7475                        unsigned int posn = bsearch( size - i, iarr, size );
    75                         sout | iarr[posn] | ", ";
     76                        sout | size - i | ':' | iarr[posn] | ", ";
    7677                } // for
    7778        }
    … …  
    9091        sout | endl;
    9192        for ( unsigned int i = 0; i < size; i += 1 ) {
    92                 double *v = bsearch( size - i + 0.5, darr, size );
    93                 sout | *v | ", ";
     93                double * v = bsearch( size - i + 0.5, darr, size );
     94                sout | size - i + 0.5 | ':' | *v | ", ";
    9495        } // for
    9596        sout | endl;
    9697        for ( unsigned int i = 0; i < size; i += 1 ) {
    9798                unsigned int posn = bsearch( size - i + 0.5, darr, size );
    98                 sout | darr[posn] | ", ";
     99                sout | size - i + 0.5 | ':' | darr[posn] | ", ";
    99100        } // for
    100101        sout | endl | endl;
    … …  
    116117        for ( unsigned int i = 0; i < size; i += 1 ) {
    117118                S temp = { size - i, size - i + 1 };
    118                 S *v = bsearch( temp, sarr, size );
    119                 sout | *v | ", ";
     119                S * v = bsearch( temp, sarr, size );
     120                sout | temp | ':' | *v | ", ";
    120121        } // for
    121122        sout | endl;
    … …  
    123124                S temp = { size - i, size - i + 1 };
    124125                unsigned int posn = bsearch( temp, sarr, size );
    125                 sout | sarr[posn] | ", ";
     126                sout | temp | ':' | sarr[posn] | ", ";
    126127        } // for
    127128        sout | endl | endl;
     129        {
     130                unsigned int getKey( S & s ) { return s.j; }
     131                for ( unsigned int i = 0; i < size; i += 1 ) {
     132                        sout | sarr[i] | ", ";
     133                } // for
     134                sout | endl;
     135                for ( unsigned int i = 0; i < size; i += 1 ) {
     136                        S * v = bsearch( size - i + 1, sarr, size );
     137                        sout | size - i + 1 | ':' | *v | ", ";
     138                } // for
     139                sout | endl;
     140                for ( unsigned int i = 0; i < size; i += 1 ) {
     141                        unsigned int posn = bsearch( size - i + 1, sarr, size );
     142                        sout | size - i + 1 | ':' | sarr[posn] | ", ";
     143                } // for
     144                sout | endl | endl;
     145        }
    128146} // main
    129147
Note: See TracChangeset for help on using the changeset viewer.