diff options
author | Han-Wen Nienhuys <hanwen@lilypond.org> | 2002-07-21 17:46:23 +0000 |
---|---|---|
committer | Han-Wen Nienhuys <hanwen@lilypond.org> | 2002-07-21 17:46:23 +0000 |
commit | 1d1559ce6dc6190cb46d00c479a12ec51af12011 (patch) | |
tree | 2ae422e19ac49817b5ce78d72edef3a11e928c3e /libguile/sort.c | |
parent | 8f28ea31bb2a95e88b9d9e6e4f29655ab077c939 (diff) | |
download | guile-1d1559ce6dc6190cb46d00c479a12ec51af12011.tar.gz |
* macros.c: include deprecation.h
* vectors.c (s_scm_vector_move_right_x): remove side effect in
macro arg.
(s_scm_vector_move_left_x): idem.
* net_db.c, posix.c, socket.c: variable naming: change ans to
result.
* sort.c (scm_merge_vector_x): accept vector as argument
iso. SCM*. This is needed for full GC correctness.
* gc.h: undo previous undocumented changes related to #ifdef
GENGC.
Diffstat (limited to 'libguile/sort.c')
-rw-r--r-- | libguile/sort.c | 88 |
1 files changed, 45 insertions, 43 deletions
diff --git a/libguile/sort.c b/libguile/sort.c index 8bca27c41..e8b332e42 100644 --- a/libguile/sort.c +++ b/libguile/sort.c @@ -437,7 +437,6 @@ SCM_DEFINE (scm_restricted_vector_sort_x, "restricted-vector-sort!", 4, 0, 0, len = SCM_INUM (endpos) - spos; quicksort (&vp[spos], len, size, scm_cmp_function (less), less); - SCM_GC_FLAG_OBJECT_WRITE(vec); return SCM_UNSPECIFIED; /* return vec; */ @@ -784,43 +783,55 @@ SCM_DEFINE (scm_sort, "sort", 2, 0, 0, #undef FUNC_NAME static void -scm_merge_vector_x (void *const vecbase, - void *const tempbase, +scm_merge_vector_x (SCM vec, + SCM * temp, cmp_fun_t cmp, SCM less, long low, long mid, long high) { - register SCM *vp = (SCM *) vecbase; - register SCM *temp = (SCM *) tempbase; long it; /* Index for temp vector */ long i1 = low; /* Index for lower vector segment */ long i2 = mid + 1; /* Index for upper vector segment */ /* Copy while both segments contain more characters */ for (it = low; (i1 <= mid) && (i2 <= high); ++it) - if ((*cmp) (less, &vp[i2], &vp[i1])) - temp[it] = vp[i2++]; - else - temp[it] = vp[i1++]; - - /* Copy while first segment contains more characters */ - while (i1 <= mid) - temp[it++] = vp[i1++]; + { + /* + Every call of LESS might invoke GC. For full correctness, we + should reset the generation of vecbase and tempbase between + every call of less. - /* Copy while second segment contains more characters */ - while (i2 <= high) - temp[it++] = vp[i2++]; + */ + register SCM *vp = SCM_WRITABLE_VELTS(vec); + + if ((*cmp) (less, &vp[i2], &vp[i1])) + temp[it] = vp[i2++]; + else + temp[it] = vp[i1++]; + } - /* Copy back from temp to vp */ - for (it = low; it <= high; ++it) - vp[it] = temp[it]; -} /* scm_merge_vector_x */ + { + register SCM *vp = SCM_WRITABLE_VELTS(vec); + + /* Copy while first segment contains more characters */ + while (i1 <= mid) + temp[it++] = vp[i1++]; + + /* Copy while second segment contains more characters */ + while (i2 <= high) + temp[it++] = vp[i2++]; + + /* Copy back from temp to vp */ + for (it = low; it <= high; ++it) + vp[it] = temp[it]; + } +} /* scm_merge_vector_x */ static void -scm_merge_vector_step (void *const vp, - void *const temp, +scm_merge_vector_step (SCM vp, + SCM * temp, cmp_fun_t cmp, SCM less, long low, @@ -860,18 +871,16 @@ SCM_DEFINE (scm_stable_sort_x, "stable-sort!", 2, 0, 0, } else if (SCM_VECTORP (items)) { - SCM *temp, *vp; + SCM *temp; len = SCM_VECTOR_LENGTH (items); - temp = malloc (len * sizeof(SCM)); - - vp = SCM_WRITABLE_VELTS (items); /* - This routine modifies VP - */ + the following array does not contain any new references to + SCM objects, so we can get away with allocing it on the heap. + */ + temp = malloc (len * sizeof(SCM)); - SCM_GC_FLAG_OBJECT_WRITE(items); - scm_merge_vector_step (vp, + scm_merge_vector_step (items, temp, scm_cmp_function (less), less, @@ -886,7 +895,6 @@ SCM_DEFINE (scm_stable_sort_x, "stable-sort!", 2, 0, 0, #undef FUNC_NAME /* stable_sort manages lists and vectors */ - SCM_DEFINE (scm_stable_sort, "stable-sort", 2, 0, 0, (SCM items, SCM less), "Sort the sequence @var{items}, which may be a list or a\n" @@ -894,13 +902,14 @@ SCM_DEFINE (scm_stable_sort, "stable-sort", 2, 0, 0, "This is a stable sort.") #define FUNC_NAME s_scm_stable_sort { - long len; /* list/vector length */ + if (SCM_NULL_OR_NIL_P (items)) return items; SCM_VALIDATE_NIM (2, less); if (SCM_CONSP (items)) { + long len; /* list/vector length */ SCM_VALIDATE_LIST_COPYLEN (1, items, len); items = scm_list_copy (items); return scm_merge_list_step (&items, scm_cmp_function (less), less, len); @@ -909,19 +918,12 @@ SCM_DEFINE (scm_stable_sort, "stable-sort", 2, 0, 0, /* support ordinary vectors even if arrays not available? */ else if (SCM_VECTORP (items)) { - SCM retvec; - SCM *temp, *vp; - len = SCM_VECTOR_LENGTH (items); - retvec = scm_make_uve (len, scm_array_prototype (items)); + long len = SCM_VECTOR_LENGTH (items); + SCM *temp = malloc (len * sizeof (SCM)); + SCM retvec = scm_make_uve (len, scm_array_prototype (items)); scm_array_copy_x (items, retvec); - temp = malloc (len * sizeof (SCM)); - - /* - don't worry about write barrier: retvec is new anyway. - */ - vp = SCM_WRITABLE_VELTS (retvec); - scm_merge_vector_step (vp, + scm_merge_vector_step (retvec, temp, scm_cmp_function (less), less, |