Changeset 93cdd5c


Ignore:
Timestamp:
Jan 2, 2018, 8:34:33 AM (6 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:
490d9972, f3458a8
Parents:
853451b
Message:

add lower/upper bound bsearch, and update bsearch and its test

Location:
src
Files:
3 edited

Legend:

Unmodified
Added
Removed

  • src/libcfa/stdlib

    r853451b r93cdd5c  
    1010// Created On       : Thu Jan 28 17:12:35 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Dec 28 18:43:12 2017
    13 // Update Count     : 277
     12// Last Modified On : Mon Jan  1 17:35:43 2018
     13// Update Count     : 291
    1414//
    1515
    … …  
    186186
    187187forall( otype E | { int ?<?( E, E ); } )
    188 E * bsearch( E key, const E * arr, size_t dim );
    189 
    190 forall( otype E | { int ?<?( E, E ); } )
    191 unsigned int bsearch( E key, const E * arr, size_t dim );
    192 
    193 forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
    194 E * bsearch( K key, const E * arr, size_t dim );
    195 
    196 forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
    197 unsigned int bsearch( K key, const E * arr, size_t dim );
    198 
    199 forall( otype E | { int ?<?( E, E ); } )
    200 void qsort( E * arr, size_t dim );
     188E * bsearch( E key, const E * vals, size_t dim );
     189
     190forall( otype E | { int ?<?( E, E ); } )
     191size_t bsearch( E key, const E * vals, size_t dim );
     192
     193forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     194E * bsearch( K key, const E * vals, size_t dim );
     195
     196forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     197size_t bsearch( K key, const E * vals, size_t dim );
     198
     199
     200forall( otype E | { int ?<?( E, E ); } )
     201E * bsearchl( E key, const E * vals, size_t dim );
     202
     203forall( otype E | { int ?<?( E, E ); } )
     204size_t bsearchl( E key, const E * vals, size_t dim );
     205
     206forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     207E * bsearchl( K key, const E * vals, size_t dim );
     208
     209forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     210size_t bsearchl( K key, const E * vals, size_t dim );
     211
     212
     213forall( otype E | { int ?<?( E, E ); } )
     214E * bsearchu( E key, const E * vals, size_t dim );
     215
     216forall( otype E | { int ?<?( E, E ); } )
     217size_t bsearchu( E key, const E * vals, size_t dim );
     218
     219forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     220E * bsearchu( K key, const E * vals, size_t dim );
     221
     222forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     223size_t bsearchu( K key, const E * vals, size_t dim );
     224
     225
     226forall( otype E | { int ?<?( E, E ); } )
     227void qsort( E * vals, size_t dim );
    201228
    202229//---------------------------------------

  • src/libcfa/stdlib.c

    r853451b r93cdd5c  
    1010// Created On       : Thu Jan 28 17:10:29 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Dec 28 18:43:16 2017
    13 // Update Count     : 378
     12// Last Modified On : Mon Jan  1 19:03:16 2018
     13// Update Count     : 437
    1414//
    1515
    … …  
    129129
    130130forall( otype E | { int ?<?( E, E ); } )
    131 E * 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 );
    134 } // bsearch
    135 
    136 forall( otype E | { int ?<?( E, E ); } )
    137 unsigned 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)
    140 } // bsearch
    141 
    142 forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
    143 E * 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 
    148 forall( otype K, otype E | { int ?<?( K, K ); K getKey( E & ); } )
    149 unsigned 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 
    154 forall( otype E | { int ?<?( E, E ); } )
    155 void 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 );
     131E * bsearch( E key, const E * vals, size_t dim ) {
     132        int cmp( const void * t1, const void * t2 ) {
     133                return *(E *)t1 < *(E *)t2 ? -1 : *(E *)t2 < *(E *)t1 ? 1 : 0;
     134        } // cmp
     135        return (E *)bsearch( &key, vals, dim, sizeof(E), cmp );
     136} // bsearch
     137
     138forall( otype E | { int ?<?( E, E ); } )
     139size_t bsearch( E key, const E * vals, size_t dim ) {
     140        E * result = bsearch( key, vals, dim );
     141        return result ? result - vals : dim;                            // pointer subtraction includes sizeof(E)
     142} // bsearch
     143
     144forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     145E * bsearch( K key, const E * vals, size_t dim ) {
     146        int cmp( const void * t1, const void * t2 ) {
     147                return *(K *)t1 < getKey( *(E *)t2 ) ? -1 : getKey( *(E *)t2 ) < *(K *)t1 ? 1 : 0;
     148        } // cmp
     149        return (E *)bsearch( &key, vals, dim, sizeof(E), cmp );
     150} // bsearch
     151
     152forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     153size_t bsearch( K key, const E * vals, size_t dim ) {
     154        E * result = bsearch( key, vals, dim );
     155        return result ? result - vals : dim;                            // pointer subtraction includes sizeof(E)
     156} // bsearch
     157
     158
     159forall( otype E | { int ?<?( E, E ); } )
     160size_t bsearchl( E key, const E * vals, size_t dim ) {
     161        size_t l = 0, m, h = dim;
     162        while ( l < h ) {
     163                m = (l + h) / 2;
     164                if ( (E &)(vals[m]) < key ) {                                   // cast away const
     165                        l = m + 1;
     166                } else {
     167                        h = m;
     168                } // if
     169        } // while
     170        return l;
     171} // bsearchl
     172
     173forall( otype E | { int ?<?( E, E ); } )
     174E * bsearchl( E key, const E * vals, size_t dim ) {
     175        size_t posn = bsearchl( key, vals, dim );
     176        return (E *)(&vals[posn]);                                                      // cast away const
     177} // bsearchl
     178
     179forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     180size_t bsearchl( K key, const E * vals, size_t dim ) {
     181        size_t l = 0, m, h = dim;
     182        while ( l < h ) {
     183                m = (l + h) / 2;
     184                if ( getKey( vals[m] ) < key ) {
     185                        l = m + 1;
     186                } else {
     187                        h = m;
     188                } // if
     189        } // while
     190        return l;
     191} // bsearchl
     192
     193forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     194E * bsearchl( K key, const E * vals, size_t dim ) {
     195        size_t posn = bsearchl( key, vals, dim );
     196        return (E *)(&vals[posn]);                                                      // cast away const
     197} // bsearchl
     198
     199
     200forall( otype E | { int ?<?( E, E ); } )
     201size_t bsearchu( E key, const E * vals, size_t dim ) {
     202        size_t l = 0, m, h = dim;
     203        while ( l < h ) {
     204                m = (l + h) / 2;
     205                if ( ! ( key < (E &)(vals[m]) ) ) {                             // cast away const
     206                        l = m + 1;
     207                } else {
     208                        h = m;
     209                } // if
     210        } // while
     211        return l;
     212} // bsearchu
     213
     214forall( otype E | { int ?<?( E, E ); } )
     215E * bsearchu( E key, const E * vals, size_t dim ) {
     216        size_t posn = bsearchu( key, vals, dim );
     217        return (E *)(&vals[posn]);
     218} // bsearchu
     219
     220forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     221size_t bsearchu( K key, const E * vals, size_t dim ) {
     222        size_t l = 0, m, h = dim;
     223        while ( l < h ) {
     224                m = (l + h) / 2;
     225                if ( ! ( key < getKey( vals[m] ) ) ) {
     226                        l = m + 1;
     227                } else {
     228                        h = m;
     229                } // if
     230        } // while
     231        return l;
     232} // bsearchu
     233
     234forall( otype K, otype E | { int ?<?( K, K ); K getKey( const E & ); } )
     235E * bsearchu( K key, const E * vals, size_t dim ) {
     236        size_t posn = bsearchu( key, vals, dim );
     237        return (E *)(&vals[posn]);
     238} // bsearchu
     239
     240
     241forall( otype E | { int ?<?( E, E ); } )
     242void qsort( E * vals, size_t dim ) {
     243        int cmp( const void * t1, const void * t2 ) {
     244                return *(E *)t1 < *(E *)t2 ? -1 : *(E *)t2 < *(E *)t1 ? 1 : 0;
     245        } // cmp
     246        qsort( vals, dim, sizeof(E), cmp );
    158247} // qsort
    159248

  • src/tests/searchsort.c

    r853451b r93cdd5c  
    1010// Created On       : Thu Feb  4 18:17:50 2016
    1111// Last Modified By : Peter A. Buhr
    12 // Last Modified On : Thu Dec 28 18:48:10 2017
    13 // Update Count     : 99
     12// Last Modified On : Tue Jan  2 08:01:17 2018
     13// Update Count     : 100
    1414//
    1515
    … …  
    128128        sout | endl | endl;
    129129        {
    130                 unsigned int getKey( S & s ) { return s.j; }
     130                unsigned int getKey( const S & s ) { return s.j; }
    131131                for ( unsigned int i = 0; i < size; i += 1 ) {
    132132                        sout | sarr[i] | ", ";
Note: See TracChangeset for help on using the changeset viewer.