diff options
author | David Monniaux <david.monniaux@univ-grenoble-alpes.fr> | 2020-03-03 08:17:40 +0100 |
---|---|---|
committer | David Monniaux <david.monniaux@univ-grenoble-alpes.fr> | 2020-03-03 08:17:40 +0100 |
commit | 1ab7b51c30e1b10ac45b0bd64cefdc01da0f7f68 (patch) | |
tree | 210ffc156c83f04fb0c61a40b4f9037d7ba8a7e1 /test/mppa/sort/merge.c | |
parent | 222c9047d61961db9c6b19fed5ca49829223fd33 (diff) | |
parent | 12be46d59a2483a10d77fa8ee67f7e0ca1bd702f (diff) | |
download | compcert-kvx-1ab7b51c30e1b10ac45b0bd64cefdc01da0f7f68.tar.gz compcert-kvx-1ab7b51c30e1b10ac45b0bd64cefdc01da0f7f68.zip |
Merge branch 'mppa-cse2' of gricad-gitlab.univ-grenoble-alpes.fr:sixcy/CompCert into mppa-work
Diffstat (limited to 'test/mppa/sort/merge.c')
-rw-r--r-- | test/mppa/sort/merge.c | 92 |
1 files changed, 92 insertions, 0 deletions
diff --git a/test/mppa/sort/merge.c b/test/mppa/sort/merge.c new file mode 100644 index 00000000..99f8ba85 --- /dev/null +++ b/test/mppa/sort/merge.c @@ -0,0 +1,92 @@ +#include "../prng/prng.h" +#include "../prng/types.h" + +//https://en.wikipedia.org/wiki/Merge_sort + +#ifdef __UNIT_TEST_MERGE__ +#define SIZE 100 +#else +#include "test.h" +#endif + +int min(int a, int b){ + return (a < b)?a:b; +} + +void BottomUpMerge(const uint64_t *A, int iLeft, int iRight, int iEnd, uint64_t *B) +{ + int i = iLeft, j = iRight, k; + for (k = iLeft; k < iEnd; k++) { + if (i < iRight && (j >= iEnd || A[i] <= A[j])) { + B[k] = A[i]; + i = i + 1; + } else { + B[k] = A[j]; + j = j + 1; + } + } +} + +void CopyArray(uint64_t *to, const uint64_t *from) +{ + const int n = SIZE; + int i; + + for(i = 0; i < n; i++) + to[i] = from[i]; +} + +void BottomUpMergeSort(uint64_t *A, uint64_t *B) +{ + const int n = SIZE; + int width, i; + + for (width = 1; width < n; width = 2 * width) + { + for (i = 0; i < n; i = i + 2 * width) + { + BottomUpMerge(A, i, min(i+width, n), min(i+2*width, n), B); + } + CopyArray(A, B); + } +} + +int merge_sort(uint64_t *res, const uint64_t *T){ + int i; + + if (SIZE <= 0) + return -1; + + uint64_t B[SIZE]; + uint64_t *A = res; + for (i = 0 ; i < SIZE ; i++) + A[i] = T[i]; + + BottomUpMergeSort(A, B); + + return 0; +} + +#ifdef __UNIT_TEST_MERGE__ +int main(void){ + uint64_t T[SIZE]; + uint64_t res[SIZE]; + int i; + srand(42); + + for (i = 0 ; i < SIZE ; i++) + T[i] = randlong(); + + /* Sorting the table */ + if (merge_sort(res, T) < 0) return -1; + + /* Computing max(T) */ + uint64_t max = T[0]; + for (i = 1 ; i < SIZE ; i++) + if (T[i] > max) + max = T[i]; + + /* We should have: max(T) == res[SIZE] */ + return !(max == res[SIZE-1]); +} +#endif // __UNIT_TEST_MERGE__ |