source: libcfa/src/bits/algorithm.hfa @ 97c3159

//
// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
//
// The contents of this file are covered under the licence agreement in the
// file "LICENCE" distributed with Cforall.
//
// bits/algorithms.hfa -- Builtins for exception handling.
//
// Author           : Thierry Delisle
// Created On       : Mon Oct 30 13:37:34 2017
// Last Modified By : --
// Last Modified On : --
// Update Count     : 0
//

#pragma once

#ifdef SAFE_SORT
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr );
forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim );

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort( T * arr, size_t dim ) {
        switch( dim ) {
                case 1 : return;
                case 2 : __libcfa_small_sort2( arr ); return;
                case 3 : __libcfa_small_sort3( arr ); return;
                case 4 : __libcfa_small_sort4( arr ); return;
                case 5 : __libcfa_small_sort5( arr ); return;
                case 6 : __libcfa_small_sort6( arr ); return;
                default: __libcfa_small_sortN( arr, dim ); return;
        }
}

#define min(x, y) (y > x ? x : y)
#define max(x, y) (y > x ? y : x)
#define SWAP(x,y) { T a = min(arr[x], arr[y]); T b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort2( T * arr ) {
        SWAP(0, 1);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort3( T * arr ) {
        SWAP(1, 2);
        SWAP(0, 2);
        SWAP(0, 1);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort4( T * arr ) {
        SWAP(0, 1);
        SWAP(2, 3);
        SWAP(0, 2);
        SWAP(1, 3);
        SWAP(1, 2);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort5( T * arr ) {
        SWAP(0, 1);
        SWAP(3, 4);
        SWAP(2, 4);
        SWAP(2, 3);
        SWAP(0, 3);
        SWAP(0, 2);
        SWAP(1, 4);
        SWAP(1, 3);
        SWAP(1, 2);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sort6( T * arr ) {
        SWAP(1, 2);
        SWAP(4, 5);
        SWAP(0, 2);
        SWAP(3, 5);
        SWAP(0, 1);
        SWAP(3, 4);
        SWAP(1, 4);
        SWAP(0, 3);
        SWAP(2, 5);
        SWAP(1, 3);
        SWAP(2, 4);
        SWAP(2, 3);
}

forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
static inline void __libcfa_small_sortN( T * arr, size_t dim ) {
        int i, j;
        for (i = 1; i < dim; i++) {
                T tmp = arr[i];
                for (j = i; j >= 1 && tmp < arr[j-1]; j--) {
                        arr[j] = arr[j-1];
                }
                arr[j] = tmp;
        }
}

#else

static inline void __libcfa_small_sort2( void* * arr );
static inline void __libcfa_small_sort3( void* * arr );
static inline void __libcfa_small_sort4( void* * arr );
static inline void __libcfa_small_sort5( void* * arr );
static inline void __libcfa_small_sort6( void* * arr );
static inline void __libcfa_small_sortN( void* * arr, size_t dim );

forall( dtype T )
static inline void __libcfa_small_sort( T* * arr, size_t dim ) {
        switch( dim ) {
                case 1 : return;
                case 2 : __libcfa_small_sort2( (void **) arr ); return;
                case 3 : __libcfa_small_sort3( (void **) arr ); return;
                case 4 : __libcfa_small_sort4( (void **) arr ); return;
                case 5 : __libcfa_small_sort5( (void **) arr ); return;
                case 6 : __libcfa_small_sort6( (void **) arr ); return;
                default: __libcfa_small_sortN( (void **) arr, dim ); return;
        }
}

#define min(x, y) (y > x ? x : y)
#define max(x, y) (y > x ? y : x)
#define SWAP(x,y) { void* a = min(arr[x], arr[y]); void* b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;}

static inline void __libcfa_small_sort2( void* * arr ) {
        SWAP(0, 1);
}

static inline void __libcfa_small_sort3( void* * arr ) {
        SWAP(1, 2);
        SWAP(0, 2);
        SWAP(0, 1);
}

static inline void __libcfa_small_sort4( void* * arr ) {
        SWAP(0, 1);
        SWAP(2, 3);
        SWAP(0, 2);
        SWAP(1, 3);
        SWAP(1, 2);
}

static inline void __libcfa_small_sort5( void* * arr ) {
        SWAP(0, 1);
        SWAP(3, 4);
        SWAP(2, 4);
        SWAP(2, 3);
        SWAP(0, 3);
        SWAP(0, 2);
        SWAP(1, 4);
        SWAP(1, 3);
        SWAP(1, 2);
}

static inline void __libcfa_small_sort6( void* * arr ) {
        SWAP(1, 2);
        SWAP(4, 5);
        SWAP(0, 2);
        SWAP(3, 5);
        SWAP(0, 1);
        SWAP(3, 4);
        SWAP(1, 4);
        SWAP(0, 3);
        SWAP(2, 5);
        SWAP(1, 3);
        SWAP(2, 4);
        SWAP(2, 3);
}

static inline void __libcfa_small_sortN( void* * arr, size_t dim ) {
        int i, j;
        for (i = 1; i < dim; i++) {
                void* tmp = arr[i];
                for (j = i; j >= 1 && tmp < arr[j-1]; j--) {
                        arr[j] = arr[j-1];
                }
                arr[j] = tmp;
        }
}

#endif

#undef SWAP
#undef min
#undef max