Index: src/libcfa/bits/algorithms.h =================================================================== --- src/libcfa/bits/algorithms.h (revision 2c1830a6adc6b436fec2a3d329890adb4740944d) +++ src/libcfa/bits/algorithms.h (revision 2c1830a6adc6b436fec2a3d329890adb4740944d) @@ -0,0 +1,191 @@ +// +// 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.h -- 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 ); } ) static inline void __libcfa_small_sort2( T * arr ); +forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort3( T * arr ); +forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort4( T * arr ); +forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort5( T * arr ); +forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sort6( T * arr ); +forall( otype T | { int ??( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim ); + +forall( otype 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 ); } ) +static inline void __libcfa_small_sort2( T * arr ) { + SWAP(0, 1); +} + +forall( otype 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 ); } ) +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 ); } ) +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 ); } ) +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 ); } ) +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( otype 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( (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 Index: src/libcfa/concurrency/monitor.c =================================================================== --- src/libcfa/concurrency/monitor.c (revision 6a5be52db68460f917313bc7fb311cfb03b0f0c1) +++ src/libcfa/concurrency/monitor.c (revision 2c1830a6adc6b436fec2a3d329890adb4740944d) @@ -21,4 +21,6 @@ #include "kernel_private.h" +#include "bits/algorithms.h" + //----------------------------------------------------------------------------- // Forward declarations @@ -291,5 +293,5 @@ // Sort monitors based on address -> TODO use a sort specialized for small numbers - qsort(this.m, count); + __libcfa_small_sort(this.m, count); // Save previous thread context @@ -492,4 +494,6 @@ set_owner( monitors, count, signallee ); + LIB_DEBUG_PRINT_BUFFER_DECL( "Kernel : signal_block condition %p (s: %p)\n", this, signallee ); + //Everything is ready to go to sleep BlockInternal( locks, count, &signallee, 1 ); @@ -498,4 +502,6 @@ // WE WOKE UP + + LIB_DEBUG_PRINT_BUFFER_LOCAL( "Kernel : signal_block returned\n" ); //We are back, restore the masks and recursions @@ -869,5 +875,5 @@ short size = 0; for( int i = 0; i < mask.size; i++ ) { - qsort( mask.clauses[i].list, mask.clauses[i].size ); + __libcfa_small_sort( mask.clauses[i].list, mask.clauses[i].size ); for( int j = 0; j < mask.clauses[i].size; j++) { insert_unique( storage, size, mask.clauses[i].list[j] ); @@ -875,5 +881,5 @@ } // TODO insertion sort instead of this - qsort( storage, size ); + __libcfa_small_sort( storage, size ); return size; }