source: src/libcfa/bits/algorithms.h@ 59a0bde

ADT aaron-thesis arm-eh ast-experimental cleanup-dtors deferred_resn demangler enum forall-pointer-decay jacob/cs343-translation jenkins-sandbox new-ast new-ast-unique-expr new-env no_list persistent-indexer pthread-emulation qualifiedEnum resolv-new with_gc
Last change on this file since 59a0bde was e1e8408, checked in by Thierry Delisle <tdelisle@…>, 8 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.