summaryrefslogtreecommitdiff
path: root/libguile
diff options
context:
space:
mode:
authorMarius Vollmer <mvo@zagadka.de>2004-10-22 13:17:04 +0000
committerMarius Vollmer <mvo@zagadka.de>2004-10-22 13:17:04 +0000
commitee1ac75beba4ab938759e6cac23d1ede9aa134c7 (patch)
treed1d0a13bceef49d5ee25dd41f5100f47ef6c65a7 /libguile
parent6191ccecf1a1bfff270b1625c5043a43236c5fbd (diff)
downloadguile-ee1ac75beba4ab938759e6cac23d1ede9aa134c7.tar.gz
(quicksort, scm_merge, scm_merge_list_x,
scm_merge_list_step, scm_merge_vector_step): Inserted SCM_TICKs at strategic places so that the loops can be interrupted.
Diffstat (limited to 'libguile')
-rw-r--r--libguile/sort.c10
1 files changed, 9 insertions, 1 deletions
diff --git a/libguile/sort.c b/libguile/sort.c
index 5be336109..e7c388725 100644
--- a/libguile/sort.c
+++ b/libguile/sort.c
@@ -39,11 +39,11 @@
#include "libguile/feature.h"
#include "libguile/vectors.h"
#include "libguile/lang.h"
+#include "libguile/async.h"
#include "libguile/validate.h"
#include "libguile/sort.h"
-
/* The routine quicksort was extracted from the GNU C Library qsort.c
written by Douglas C. Schmidt (schmidt@ics.uci.edu)
and adapted to guile by adding an extra pointer less
@@ -129,6 +129,8 @@ quicksort (SCM *const base_ptr, size_t nr_elems, scm_t_trampoline_2 cmp, SCM les
size_t right;
SCM pivot;
+ SCM_TICK;
+
/* Select median value from among LO, MID, and HI. Rearrange
LO and HI so the three values are sorted. This lowers the
probability of picking a pathological pivot value and
@@ -246,6 +248,8 @@ quicksort (SCM *const base_ptr, size_t nr_elems, scm_t_trampoline_2 cmp, SCM les
run = 1;
while (++run <= end)
{
+ SCM_TICK;
+
tmp = run - 1;
while (scm_is_true ((*cmp) (less, base_ptr[run], base_ptr[tmp])))
{
@@ -425,6 +429,7 @@ SCM_DEFINE (scm_merge, "merge", 3, 0, 0,
last = build;
while ((alen > 0) && (blen > 0))
{
+ SCM_TICK;
if (scm_is_true ((*cmp) (less, SCM_CAR (blist), SCM_CAR (alist))))
{
SCM_SETCDR (last, scm_cons (SCM_CAR (blist), SCM_EOL));
@@ -477,6 +482,7 @@ scm_merge_list_x (SCM alist, SCM blist,
last = build;
while ((alen > 0) && (blen > 0))
{
+ SCM_TICK;
if (scm_is_true ((*cmp) (less, SCM_CAR (blist), SCM_CAR (alist))))
{
SCM_SETCDR (last, blist);
@@ -540,6 +546,7 @@ scm_merge_list_step (SCM * seq, scm_t_trampoline_2 cmp, SCM less, long n)
if (n > 2)
{
long mid = n / 2;
+ SCM_TICK;
a = scm_merge_list_step (seq, cmp, less, mid);
b = scm_merge_list_step (seq, cmp, less, n - mid);
return scm_merge_list_x (a, b, mid, n - mid, cmp, less);
@@ -704,6 +711,7 @@ scm_merge_vector_step (SCM vp,
if (high > low)
{
long mid = (low + high) / 2;
+ SCM_TICK;
scm_merge_vector_step (vp, temp, cmp, less, low, mid);
scm_merge_vector_step (vp, temp, cmp, less, mid+1, high);
scm_merge_vector_x (vp, temp, cmp, less, low, mid, high);