Changeset 707446a


Ignore:
Timestamp:
Apr 1, 2017, 7:14:11 PM (5 years ago)
Author:
Peter A. Buhr <pabuhr@…>
Branches:
aaron-thesis, arm-eh, cleanup-dtors, deferred_resn, demangler, jacob/cs343-translation, jenkins-sandbox, master, new-ast, new-ast-unique-expr, new-env, no_list, persistent-indexer, resolv-new, with_gc
Children:
06cf47f
Parents:
24c18ea
Message:

add alternate bsearch returning posn of key

Location:
src
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • src/libcfa/stdlib

    r24c18ea r707446a  
    1010// Created On       : Thu Jan 28 17:12:35 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Mar  4 22:03:54 2017
    13 // Update Count     : 102
     12// Last Modified On : Sat Apr  1 17:35:24 2017
     13// Update Count     : 104
    1414//
    1515
     
    8484forall( otype T | { int ?<?( T, T ); } )
    8585T * bsearch( T key, const T * arr, size_t dimension );
     86forall( otype T | { int ?<?( T, T ); } )
     87unsigned int bsearch( T key, const T * arr, size_t dimension );
    8688
    8789forall( otype T | { int ?<?( T, T ); } )
  • src/libcfa/stdlib.c

    r24c18ea r707446a  
    1010// Created On       : Thu Jan 28 17:10:29 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Sat Mar  4 22:02:22 2017
    13 // Update Count     : 172
     12// Last Modified On : Sat Apr  1 18:31:26 2017
     13// Update Count     : 181
    1414//
    1515
     
    228228
    229229forall( otype T | { int ?<?( T, T ); } )
     230unsigned int bsearch( T key, const T * arr, size_t dimension ) {
     231        int comp( const void * t1, const void * t2 ) { return *(T *)t1 < *(T *)t2 ? -1 : *(T *)t2 < *(T *)t1 ? 1 : 0; }
     232        T *result = (T *)bsearch( &key, arr, dimension, sizeof(T), comp );
     233        return result ? result - arr : dimension;                       // pointer subtraction includes sizeof(T)
     234} // bsearch
     235
     236forall( otype T | { int ?<?( T, T ); } )
    230237void qsort( const T * arr, size_t dimension ) {
    231238        int comp( const void * t1, const void * t2 ) { return *(T *)t1 < *(T *)t2 ? -1 : *(T *)t2 < *(T *)t1 ? 1 : 0; }
  • src/tests/.expect/searchsort.txt

    r24c18ea r707446a  
    221, 2, 3, 4, 5, 6, 7, 8, 9, 10,
    3310, 9, 8, 7, 6, 5, 4, 3, 2, 1,
     410, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    45
    561, 2, 3, 4, 5, 6, 7, 8, 9, 10,
     710, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    6810, 9, 8, 7, 6, 5, 4, 3, 2, 1,
    7910, 9, 8, 7, 6, 5, 4, 3, 2, 1,
     
    10121.5, 2.5, 3.5, 4.5, 5.5, 6.5, 7.5, 8.5, 9.5, 10.5,
    111310.5, 9.5, 8.5, 7.5, 6.5, 5.5, 4.5, 3.5, 2.5, 1.5,
     1410.5, 9.5, 8.5, 7.5, 6.5, 5.5, 4.5, 3.5, 2.5, 1.5,
    1215
    131610 11, 9 10, 8 9, 7 8, 6 7, 5 6, 4 5, 3 4, 2 3, 1 2,
    14171 2, 2 3, 3 4, 4 5, 5 6, 6 7, 7 8, 8 9, 9 10, 10 11,
    151810 11, 9 10, 8 9, 7 8, 6 7, 5 6, 4 5, 3 4, 2 3, 1 2,
     1910 11, 9 10, 8 9, 7 8, 6 7, 5 6, 4 5, 3 4, 2 3, 1 2,
    1620
  • src/tests/searchsort.c

    r24c18ea r707446a  
    1010// Created On       : Thu Feb  4 18:17:50 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Tue Jul  5 18:06:07 2016
    13 // Update Count     : 56
     12// Last Modified On : Sat Apr  1 19:10:12 2017
     13// Update Count     : 62
    1414//
    1515
     
    3535                sout | *v | ", ";
    3636        } // for
     37        sout | endl;
     38        for ( unsigned int i = 0; i < size; i += 1 ) {
     39                unsigned int posn = bsearch( size - i, iarr, size );
     40                sout | iarr[posn] | ", ";
     41        } // for
    3742        sout | endl | endl;
    3843
     
    5459                        sout | *v | ", ";
    5560                } // for
     61                sout | endl;
     62                for ( unsigned int i = 0; i < size; i += 1 ) {
     63                        unsigned int posn = bsearch( size - i, iarr, size );
     64                        sout | iarr[posn] | ", ";
     65                } // for
    5666        }
    5767        sout | endl | endl;
     
    7181                double *v = bsearch( size - i + 0.5, darr, size );
    7282                sout | *v | ", ";
     83        } // for
     84        sout | endl;
     85        for ( unsigned int i = 0; i < size; i += 1 ) {
     86                unsigned int posn = bsearch( size - i + 0.5, darr, size );
     87                sout | darr[posn] | ", ";
    7388        } // for
    7489        sout | endl | endl;
     
    93108                sout | *v | ", ";
    94109        } // for
     110        sout | endl;
     111        for ( unsigned int i = 0; i < size; i += 1 ) {
     112                S temp = { size - i, size - i + 1 };
     113                unsigned int posn = bsearch( temp, sarr, size );
     114                sout | sarr[posn] | ", ";
     115        } // for
    95116        sout | endl | endl;
    96117} // main
Note: See TracChangeset for help on using the changeset viewer.