From 86cb5f26029b3357727b88fee3fa7dd799a8d6c8 Mon Sep 17 00:00:00 2001 From: Anthony LaTorre Date: Tue, 6 Sep 2011 17:18:14 -0400 Subject: geometry on the GPU is now a struct created in the GPUGeometry class. coding style for cuda code is now compliant with python PEP 7 -- Style Guide for C Code. --- src/sorting.h | 134 +++++++++++++++++++++++++++++----------------------------- 1 file changed, 68 insertions(+), 66 deletions(-) (limited to 'src/sorting.h') diff --git a/src/sorting.h b/src/sorting.h index ec16bbe..03eabc6 100644 --- a/src/sorting.h +++ b/src/sorting.h @@ -1,103 +1,105 @@ template -__device__ void swap(T &a, T &b) +__device__ void +swap(T &a, T &b) { - T tmp = a; - a = b; - b = tmp; + T tmp = a; + a = b; + b = tmp; } template -__device__ void reverse(int n, T *a) +__device__ void +reverse(int n, T *a) { - for (int i=0; i < n/2; i++) - swap(a[i],a[n-1-i]); + for (int i=0; i < n/2; i++) + swap(a[i],a[n-1-i]); } template -__device__ void piksrt(int n, T *arr) +__device__ void +piksrt(int n, T *arr) { - int i,j; - T a; + int i,j; + T a; - for (j=1; j < n; j++) - { - a = arr[j]; - i = j-1; - while (i >= 0 && arr[i] > a) - { - arr[i+1] = arr[i]; - i--; - } - arr[i+1] = a; + for (j=1; j < n; j++) { + a = arr[j]; + i = j-1; + while (i >= 0 && arr[i] > a) { + arr[i+1] = arr[i]; + i--; } + arr[i+1] = a; + } } template -__device__ void piksrt2(int n, T *arr, U *brr) +__device__ void +piksrt2(int n, T *arr, U *brr) { - int i,j; - T a; - U b; + int i,j; + T a; + U b; - for (j=1; j < n; j++) - { - a = arr[j]; - b = brr[j]; - i = j-1; - while (i >= 0 && arr[i] > a) - { - arr[i+1] = arr[i]; - brr[i+1] = brr[i]; - i--; - } - arr[i+1] = a; - brr[i+1] = b; + for (j=1; j < n; j++) { + a = arr[j]; + b = brr[j]; + i = j-1; + while (i >= 0 && arr[i] > a) { + arr[i+1] = arr[i]; + brr[i+1] = brr[i]; + i--; } + arr[i+1] = a; + brr[i+1] = b; + } } template -__device__ unsigned long searchsorted(unsigned long n, T *arr, const T &x) +__device__ unsigned long +searchsorted(unsigned long n, T *arr, const T &x) { - unsigned long ju,jm,jl; - int ascnd; + unsigned long ju,jm,jl; + int ascnd; - jl = 0; - ju = n; + jl = 0; + ju = n; - ascnd = (arr[n-1] > arr[0]); + ascnd = (arr[n-1] > arr[0]); - while (ju-jl > 1) - { - jm = (ju+jl) >> 1; + while (ju-jl > 1) { + jm = (ju+jl) >> 1; - if (x >= arr[jm] == ascnd) - jl = jm; - else - ju = jm; - } - - if (x <= arr[0]) - return 0; - else if (x == arr[n-1]) - return n-1; + if (x >= arr[jm] == ascnd) + jl = jm; else - return ju; + ju = jm; + } + + if (x <= arr[0]) + return 0; + else if (x == arr[n-1]) + return n-1; + else + return ju; } template -__device__ void insert(unsigned long n, T *arr, unsigned long i, const T &x) +__device__ void +insert(unsigned long n, T *arr, unsigned long i, const T &x) { - unsigned long j; - for (j=n-1; j > i; j--) - arr[j] = arr[j-1]; - arr[i] = x; + unsigned long j; + for (j=n-1; j > i; j--) + arr[j] = arr[j-1]; + arr[i] = x; } template -__device__ void add_sorted(unsigned long n, T *arr, const T &x) +__device__ void +add_sorted(unsigned long n, T *arr, const T &x) { - unsigned long i = searchsorted(n, arr, x); + unsigned long i = searchsorted(n, arr, x); - if (i < n) - insert(n, arr, i, x); + if (i < n) + insert(n, arr, i, x); } -- cgit From c0d055366c18b2f3a71435c7c07ce0afe126f85e Mon Sep 17 00:00:00 2001 From: Anthony LaTorre Date: Tue, 6 Sep 2011 23:57:18 -0400 Subject: fix devious assumption in searchsorted that if searching a length one array it assumed the array was meant to be in descending order; it now assumes ascending order and this assumption is documented. --- src/sorting.h | 8 ++++++-- 1 file changed, 6 insertions(+), 2 deletions(-) (limited to 'src/sorting.h') diff --git a/src/sorting.h b/src/sorting.h index 03eabc6..9fd52fe 100644 --- a/src/sorting.h +++ b/src/sorting.h @@ -55,6 +55,10 @@ piksrt2(int n, T *arr, U *brr) } } +/* Returns the index in `arr` where `x` should be inserted in order to + maintain order. If `n` equals one, return the index such that, when + `x` is inserted, `arr` will be in ascending order. +*/ template __device__ unsigned long searchsorted(unsigned long n, T *arr, const T &x) @@ -65,12 +69,12 @@ searchsorted(unsigned long n, T *arr, const T &x) jl = 0; ju = n; - ascnd = (arr[n-1] > arr[0]); + ascnd = (arr[n-1] >= arr[0]); while (ju-jl > 1) { jm = (ju+jl) >> 1; - if (x >= arr[jm] == ascnd) + if ((x > arr[jm]) == ascnd) jl = jm; else ju = jm; -- cgit From c7c161179a0a26dc9b4e3acdbc61a48803fa00e7 Mon Sep 17 00:00:00 2001 From: Anthony LaTorre Date: Wed, 7 Sep 2011 11:46:23 -0400 Subject: fix bug in searchsorted() so that it properly searches a descending array. --- src/sorting.h | 4 +--- 1 file changed, 1 insertion(+), 3 deletions(-) (limited to 'src/sorting.h') diff --git a/src/sorting.h b/src/sorting.h index 9fd52fe..2bf1a5a 100644 --- a/src/sorting.h +++ b/src/sorting.h @@ -80,10 +80,8 @@ searchsorted(unsigned long n, T *arr, const T &x) ju = jm; } - if (x <= arr[0]) + if ((x <= arr[0]) == ascnd) return 0; - else if (x == arr[n-1]) - return n-1; else return ju; } -- cgit