source: src/libcfa/bits/algorithms.h @ 4ab3d68e

ADTaaron-thesisarm-ehast-experimentalcleanup-dtorsdeferred_resndemanglerenumforall-pointer-decayjacob/cs343-translationjenkins-sandboxnew-astnew-ast-unique-exprnew-envno_listpersistent-indexerpthread-emulationqualifiedEnumresolv-newwith_gc
Last change on this file since 4ab3d68e was e1e8408, checked in by Thierry Delisle <tdelisle@…>, 7 years ago

Updated concurrency tests with bounded rand48
  • Property mode set to 100644
File size: 4.8 KB
Line 
1//
2// Cforall Version 1.0.0 Copyright (C) 2016 University of Waterloo
3//
4// The contents of this file are covered under the licence agreement in the
5// file "LICENCE" distributed with Cforall.
6//
7// bits/algorithms.h -- Builtins for exception handling.
8//
9// Author           : Thierry Delisle
10// Created On       : Mon Oct 30 13:37:34 2017
11// Last Modified By : --
12// Last Modified On : --
13// Update Count     : 0
14//
15
16#pragma once
17
18#ifdef SAFE_SORT
19forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort2( T * arr );
20forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort3( T * arr );
21forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort4( T * arr );
22forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort5( T * arr );
23forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sort6( T * arr );
24forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } ) static inline void __libcfa_small_sortN( T * arr, size_t dim );
25
26forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
27static inline void __libcfa_small_sort( T * arr, size_t dim ) {
28        switch( dim ) {
29                case 1 : return;
30                case 2 : __libcfa_small_sort2( arr ); return;
31                case 3 : __libcfa_small_sort3( arr ); return;
32                case 4 : __libcfa_small_sort4( arr ); return;
33                case 5 : __libcfa_small_sort5( arr ); return;
34                case 6 : __libcfa_small_sort6( arr ); return;
35                default: __libcfa_small_sortN( arr, dim ); return;
36        }
37}
38
39#define min(x, y) (y > x ? x : y)
40#define max(x, y) (y > x ? y : x)
41#define SWAP(x,y) { T a = min(arr[x], arr[y]); T b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;}
42
43forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
44static inline void __libcfa_small_sort2( T * arr ) {
45        SWAP(0, 1);
46}
47
48forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
49static inline void __libcfa_small_sort3( T * arr ) {
50        SWAP(1, 2);
51        SWAP(0, 2);
52        SWAP(0, 1);
53}
54
55forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
56static inline void __libcfa_small_sort4( T * arr ) {
57        SWAP(0, 1);
58        SWAP(2, 3);
59        SWAP(0, 2);
60        SWAP(1, 3);
61        SWAP(1, 2);
62}
63
64forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
65static inline void __libcfa_small_sort5( T * arr ) {
66        SWAP(0, 1);
67        SWAP(3, 4);
68        SWAP(2, 4);
69        SWAP(2, 3);
70        SWAP(0, 3);
71        SWAP(0, 2);
72        SWAP(1, 4);
73        SWAP(1, 3);
74        SWAP(1, 2);
75}
76
77forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
78static inline void __libcfa_small_sort6( T * arr ) {
79        SWAP(1, 2);
80        SWAP(4, 5);
81        SWAP(0, 2);
82        SWAP(3, 5);
83        SWAP(0, 1);
84        SWAP(3, 4);
85        SWAP(1, 4);
86        SWAP(0, 3);
87        SWAP(2, 5);
88        SWAP(1, 3);
89        SWAP(2, 4);
90        SWAP(2, 3);
91}
92
93forall( otype T | {  int ?<?( T, T ); int ?>?( T, T ); } )
94static inline void __libcfa_small_sortN( T * arr, size_t dim ) {
95        int i, j;
96        for (i = 1; i < dim; i++) {
97                T tmp = arr[i];
98                for (j = i; j >= 1 && tmp < arr[j-1]; j--) {
99                        arr[j] = arr[j-1];
100                }
101                arr[j] = tmp;
102        }
103}
104
105#else
106
107static inline void __libcfa_small_sort2( void* * arr );
108static inline void __libcfa_small_sort3( void* * arr );
109static inline void __libcfa_small_sort4( void* * arr );
110static inline void __libcfa_small_sort5( void* * arr );
111static inline void __libcfa_small_sort6( void* * arr );
112static inline void __libcfa_small_sortN( void* * arr, size_t dim );
113
114forall( dtype T )
115static inline void __libcfa_small_sort( T* * arr, size_t dim ) {
116        switch( dim ) {
117                case 1 : return;
118                case 2 : __libcfa_small_sort2( (void **) arr ); return;
119                case 3 : __libcfa_small_sort3( (void **) arr ); return;
120                case 4 : __libcfa_small_sort4( (void **) arr ); return;
121                case 5 : __libcfa_small_sort5( (void **) arr ); return;
122                case 6 : __libcfa_small_sort6( (void **) arr ); return;
123                default: __libcfa_small_sortN( (void **) arr, dim ); return;
124        }
125}
126
127#define min(x, y) (y > x ? x : y)
128#define max(x, y) (y > x ? y : x)
129#define SWAP(x,y) { void* a = min(arr[x], arr[y]); void* b = max(arr[x], arr[y]); arr[x] = a; arr[y] = b;}
130
131static inline void __libcfa_small_sort2( void* * arr ) {
132        SWAP(0, 1);
133}
134
135static inline void __libcfa_small_sort3( void* * arr ) {
136        SWAP(1, 2);
137        SWAP(0, 2);
138        SWAP(0, 1);
139}
140
141static inline void __libcfa_small_sort4( void* * arr ) {
142        SWAP(0, 1);
143        SWAP(2, 3);
144        SWAP(0, 2);
145        SWAP(1, 3);
146        SWAP(1, 2);
147}
148
149static inline void __libcfa_small_sort5( void* * arr ) {
150        SWAP(0, 1);
151        SWAP(3, 4);
152        SWAP(2, 4);
153        SWAP(2, 3);
154        SWAP(0, 3);
155        SWAP(0, 2);
156        SWAP(1, 4);
157        SWAP(1, 3);
158        SWAP(1, 2);
159}
160
161static inline void __libcfa_small_sort6( void* * arr ) {
162        SWAP(1, 2);
163        SWAP(4, 5);
164        SWAP(0, 2);
165        SWAP(3, 5);
166        SWAP(0, 1);
167        SWAP(3, 4);
168        SWAP(1, 4);
169        SWAP(0, 3);
170        SWAP(2, 5);
171        SWAP(1, 3);
172        SWAP(2, 4);
173        SWAP(2, 3);
174}
175
176static inline void __libcfa_small_sortN( void* * arr, size_t dim ) {
177        int i, j;
178        for (i = 1; i < dim; i++) {
179                void* tmp = arr[i];
180                for (j = i; j >= 1 && tmp < arr[j-1]; j--) {
181                        arr[j] = arr[j-1];
182                }
183                arr[j] = tmp;
184        }
185}
186
187#endif
188
189#undef SWAP
190#undef min
191#undef max
Note: See TracBrowser for help on using the repository browser.