[Guile-commits] 04/08: Fix sort, sort! for arrays with nonzero lower bound
lloda pushed a commit to branch wip-lloda in repository guile. commit f36ad82aefd9a5b9cfd7e15aea2eeabe75664f8a Author: Daniel Llorens Date: Mon Feb 13 12:58:34 2017 +0100 Fix sort, sort! for arrays with nonzero lower bound * module/ice-9/arrays.scm (array-copy): New function, export. * module/Makefile.am: Install (ice-9 arrays). * doc/ref/api-data.texi: Add documentation for (ice-9 arrays). * libguile/quicksort.i.c: Use signed bounds throughout. * libguile/sort.c (scm_restricted_vector_sort_x): Fix error calls. Fix calls to quicksort. * test-suite/tests/sort.test: Actually test that the sorted results match the original data. Test cases for non-zero base index arrays for sort, sort!, and stable-sort!. --- doc/ref/api-data.texi | 32 +++--- libguile/quicksort.i.c | 48 +++ libguile/sort.c| 68 - module/Makefile.am | 1 + module/ice-9/arrays.scm| 50 +-- test-suite/tests/sort.test | 149 - 6 files changed, 208 insertions(+), 140 deletions(-) diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi index 05b7083..ac743ea 100644 --- a/doc/ref/api-data.texi +++ b/doc/ref/api-data.texi @@ -7498,10 +7498,6 @@ same type, and have corresponding elements which are either @code{equal?} (@pxref{Equality}) in that all arguments must be arrays. @end deffn -@c FIXME: array-map! accepts no source arrays at all, and in that -@c case makes calls "(proc)". Is that meant to be a documented -@c feature? -@c @c FIXME: array-for-each doesn't say what happens if the sources have @c different index ranges. The code currently iterates over the @c indices of the first and expects the others to cover those. That @@ -7509,14 +7505,15 @@ same type, and have corresponding elements which are either @c documented feature? @deffn {Scheme Procedure} array-map! dst proc src @dots{} -@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN +@deffnx {Scheme Procedure} array-map-in-order! dst proc src @dots{} @deffnx {C Function} scm_array_map_x (dst, proc, srclist) -Set each element of the @var{dst} array to values obtained from calls -to @var{proc}. The value returned is unspecified. +Set each element of the @var{dst} array to values obtained from calls to +@var{proc}. The list of @var{src} arguments may be empty. The value +returned is unspecified. -Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})}, -where each @var{elem} is from the corresponding @var{src} array, at -the @var{dst} index. @code{array-map-in-order!} makes the calls in +Each call is @code{(@var{proc} @var{elem} @dots{})}, where each +@var{elem} is from the corresponding @var{src} array, at the +@var{dst} index. @code{array-map-in-order!} makes the calls in row-major order, @code{array-map!} makes them in an unspecified order. The @var{src} arrays must have the same number of dimensions as @@ -7568,6 +7565,21 @@ $\left(\matrix{% @end example @end deffn +An additional array function is available in the module +@code{(ice-9 arrays)}. It can be used with: + +@example +(use-modules (ice-9 arrays)) +@end example + +@deffn {Scheme Procedure} array-copy src +Return a new array with the same elements, type and shape as +@var{src}. However, the array increments may not be the same as those of +@var{src}. In the current implementation, the returned array will be in +row-major order, but that might change in the future. Use +@code{array-copy!} on an array of known order if that is a concern. +@end deffn + @node Shared Arrays @subsubsection Shared Arrays diff --git a/libguile/quicksort.i.c b/libguile/quicksort.i.c index cf1742e..5982672 100644 --- a/libguile/quicksort.i.c +++ b/libguile/quicksort.i.c @@ -27,7 +27,7 @@ reduces the probability of selecting a bad pivot value and eliminates certain extraneous comparisons. - 3. Only quicksorts NR_ELEMS / MAX_THRESH partitions, leaving insertion sort + 3. Only quicksorts (UBND-LBND+1) / MAX_THRESH partitions, leaving insertion sort to order the MAX_THRESH items within each partition. This is a big win, since insertion sort is faster for small, mostly sorted array segments. @@ -54,33 +54,29 @@ #defineSTACK_NOT_EMPTY (stack < top) static void -NAME (VEC_PARAM size_t nr_elems, INC_PARAM SCM less) +NAME (VEC_PARAM ssize_t lbnd, ssize_t ubnd, INC_PARAM SCM less) { /* Stack node declarations used to store unfulfilled partition obligations. */ typedef struct { -size_t lo; -size_t hi; +ssize_t lo; +ssize_t hi; } stack_node; static const char s_buggy_less[] = "buggy less predicate used when sorting"; - if (nr_elems == 0) -/* Avoid lossage with unsigned arithmetic below. */ -return; - - if (nr_elems > MAX_THRESH) + if (ubnd-lbnd+1 > MAX_THRESH) { - size_t lo = 0; - size_t hi = nr_elems-1; +
[Guile-commits] 04/08: Fix sort, sort! for arrays with nonzero lower bound
lloda pushed a commit to branch wip-exception-truncate in repository guile. commit b049717b31e4bfefd29d2b96970efc0c63d1bfbb Author: Daniel Llorens Date: Mon Feb 13 12:58:34 2017 +0100 Fix sort, sort! for arrays with nonzero lower bound * module/ice-9/arrays.scm (array-copy, typed-array-copy): New functions. Export. * module/Makefile.am: Install (ice-9 arrays). * doc/ref/api-data.texi: Add documentation for (ice-9 arrays). * libguile/quicksort.i.c: Use signed bounds throughout. * libguile/sort.c (scm_restricted_vector_sort_x): Fix error calls. Fix calls to quicksort. * test-suite/tests/sort.test: Actually test that the sorted results match the original data. Test cases for non-zero base index arrays for sort, sort!, and stable-sort!. --- doc/ref/api-data.texi | 38 + libguile/quicksort.i.c | 48 libguile/sort.c| 43 ++- module/Makefile.am | 1 + module/ice-9/arrays.scm| 53 +++--- test-suite/tests/sort.test | 133 - 6 files changed, 194 insertions(+), 122 deletions(-) diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi index f5c8798..bb4b9f7 100644 --- a/doc/ref/api-data.texi +++ b/doc/ref/api-data.texi @@ -7495,10 +7495,6 @@ same type, and have corresponding elements which are either @code{equal?} (@pxref{Equality}) in that all arguments must be arrays. @end deffn -@c FIXME: array-map! accepts no source arrays at all, and in that -@c case makes calls "(proc)". Is that meant to be a documented -@c feature? -@c @c FIXME: array-for-each doesn't say what happens if the sources have @c different index ranges. The code currently iterates over the @c indices of the first and expects the others to cover those. That @@ -7506,14 +7502,15 @@ same type, and have corresponding elements which are either @c documented feature? @deffn {Scheme Procedure} array-map! dst proc src @dots{} -@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN +@deffnx {Scheme Procedure} array-map-in-order! dst proc src @dots{} @deffnx {C Function} scm_array_map_x (dst, proc, srclist) -Set each element of the @var{dst} array to values obtained from calls -to @var{proc}. The value returned is unspecified. +Set each element of the @var{dst} array to values obtained from calls to +@var{proc}. The list of @var{src} arguments may be empty. The value +returned is unspecified. -Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})}, -where each @var{elem} is from the corresponding @var{src} array, at -the @var{dst} index. @code{array-map-in-order!} makes the calls in +Each call is @code{(@var{proc} @var{elem} @dots{})}, where each +@var{elem} is from the corresponding @var{src} array, at the +@var{dst} index. @code{array-map-in-order!} makes the calls in row-major order, @code{array-map!} makes them in an unspecified order. The @var{src} arrays must have the same number of dimensions as @@ -7565,6 +7562,27 @@ $\left(\matrix{% @end example @end deffn +A few additional array functions are available in the module +@code{(ice-9 arrays)}. They can be used with: + +@example +(use-modules (ice-9 arrays)) +@end example + +@deffn {Scheme Procedure} array-copy src +Return a new array with the same elements, type and shape as +@var{src}. However, the array increments may not be the same as those of +@var{src}. In the current implementation, the returned array will be in +row-major order, but that might change in the future. Use +@code{array-copy!} on an array of known order if that is a concern. +@end deffn + +@deffn {Scheme Procedure} typed-array-copy type src +Return a new array with the same elements and shape as @var{src}, but +with the type given. This operation may fail if @var{type} is not +compatible with the values in @var{src}. +@end deffn + @node Shared Arrays @subsubsection Shared Arrays diff --git a/libguile/quicksort.i.c b/libguile/quicksort.i.c index cf1742e..5982672 100644 --- a/libguile/quicksort.i.c +++ b/libguile/quicksort.i.c @@ -27,7 +27,7 @@ reduces the probability of selecting a bad pivot value and eliminates certain extraneous comparisons. - 3. Only quicksorts NR_ELEMS / MAX_THRESH partitions, leaving insertion sort + 3. Only quicksorts (UBND-LBND+1) / MAX_THRESH partitions, leaving insertion sort to order the MAX_THRESH items within each partition. This is a big win, since insertion sort is faster for small, mostly sorted array segments. @@ -54,33 +54,29 @@ #defineSTACK_NOT_EMPTY (stack < top) static void -NAME (VEC_PARAM size_t nr_elems, INC_PARAM SCM less) +NAME (VEC_PARAM ssize_t lbnd, ssize_t ubnd, INC_PARAM SCM less) { /* Stack node declarations used to store unfulfilled partition obligations. */ typedef struct { -size_t lo; -size_t hi; +ssize_t lo; +ssize_t hi; } stack_node; static cons
[Guile-commits] 04/08: Fix sort, sort! for arrays with nonzero lower bound
lloda pushed a commit to branch wip-exception-truncate in repository guile. commit dbf4a2f9426450977cdc32b7e1a807320830eea5 Author: Daniel Llorens Date: Mon Feb 13 12:58:34 2017 +0100 Fix sort, sort! for arrays with nonzero lower bound * module/ice-9/arrays.scm (array-copy, typed-array-copy): New functions. Export. * module/Makefile.am: Install (ice-9 arrays). * doc/ref/api-data.texi: Add documentation for (ice-9 arrays). * libguile/quicksort.i.c: Use signed bounds throughout. * libguile/sort.c (scm_restricted_vector_sort_x): Fix error calls. Fix calls to quicksort. * test-suite/tests/sort.test: Actually test that the sorted results match the original data. Test cases for non-zero base index arrays for sort, sort!, and stable-sort!. --- doc/ref/api-data.texi | 38 + libguile/quicksort.i.c | 48 libguile/sort.c| 43 ++- module/Makefile.am | 1 + module/ice-9/arrays.scm| 53 +++--- test-suite/tests/sort.test | 133 - 6 files changed, 194 insertions(+), 122 deletions(-) diff --git a/doc/ref/api-data.texi b/doc/ref/api-data.texi index f5c8798..bb4b9f7 100644 --- a/doc/ref/api-data.texi +++ b/doc/ref/api-data.texi @@ -7495,10 +7495,6 @@ same type, and have corresponding elements which are either @code{equal?} (@pxref{Equality}) in that all arguments must be arrays. @end deffn -@c FIXME: array-map! accepts no source arrays at all, and in that -@c case makes calls "(proc)". Is that meant to be a documented -@c feature? -@c @c FIXME: array-for-each doesn't say what happens if the sources have @c different index ranges. The code currently iterates over the @c indices of the first and expects the others to cover those. That @@ -7506,14 +7502,15 @@ same type, and have corresponding elements which are either @c documented feature? @deffn {Scheme Procedure} array-map! dst proc src @dots{} -@deffnx {Scheme Procedure} array-map-in-order! dst proc src1 @dots{} srcN +@deffnx {Scheme Procedure} array-map-in-order! dst proc src @dots{} @deffnx {C Function} scm_array_map_x (dst, proc, srclist) -Set each element of the @var{dst} array to values obtained from calls -to @var{proc}. The value returned is unspecified. +Set each element of the @var{dst} array to values obtained from calls to +@var{proc}. The list of @var{src} arguments may be empty. The value +returned is unspecified. -Each call is @code{(@var{proc} @var{elem1} @dots{} @var{elemN})}, -where each @var{elem} is from the corresponding @var{src} array, at -the @var{dst} index. @code{array-map-in-order!} makes the calls in +Each call is @code{(@var{proc} @var{elem} @dots{})}, where each +@var{elem} is from the corresponding @var{src} array, at the +@var{dst} index. @code{array-map-in-order!} makes the calls in row-major order, @code{array-map!} makes them in an unspecified order. The @var{src} arrays must have the same number of dimensions as @@ -7565,6 +7562,27 @@ $\left(\matrix{% @end example @end deffn +A few additional array functions are available in the module +@code{(ice-9 arrays)}. They can be used with: + +@example +(use-modules (ice-9 arrays)) +@end example + +@deffn {Scheme Procedure} array-copy src +Return a new array with the same elements, type and shape as +@var{src}. However, the array increments may not be the same as those of +@var{src}. In the current implementation, the returned array will be in +row-major order, but that might change in the future. Use +@code{array-copy!} on an array of known order if that is a concern. +@end deffn + +@deffn {Scheme Procedure} typed-array-copy type src +Return a new array with the same elements and shape as @var{src}, but +with the type given. This operation may fail if @var{type} is not +compatible with the values in @var{src}. +@end deffn + @node Shared Arrays @subsubsection Shared Arrays diff --git a/libguile/quicksort.i.c b/libguile/quicksort.i.c index cf1742e..5982672 100644 --- a/libguile/quicksort.i.c +++ b/libguile/quicksort.i.c @@ -27,7 +27,7 @@ reduces the probability of selecting a bad pivot value and eliminates certain extraneous comparisons. - 3. Only quicksorts NR_ELEMS / MAX_THRESH partitions, leaving insertion sort + 3. Only quicksorts (UBND-LBND+1) / MAX_THRESH partitions, leaving insertion sort to order the MAX_THRESH items within each partition. This is a big win, since insertion sort is faster for small, mostly sorted array segments. @@ -54,33 +54,29 @@ #defineSTACK_NOT_EMPTY (stack < top) static void -NAME (VEC_PARAM size_t nr_elems, INC_PARAM SCM less) +NAME (VEC_PARAM ssize_t lbnd, ssize_t ubnd, INC_PARAM SCM less) { /* Stack node declarations used to store unfulfilled partition obligations. */ typedef struct { -size_t lo; -size_t hi; +ssize_t lo; +ssize_t hi; } stack_node; static cons