diff options
author | Kaz Kylheku <kaz@kylheku.com> | 2023-05-02 19:29:42 -0700 |
---|---|---|
committer | Kaz Kylheku <kaz@kylheku.com> | 2023-05-02 19:29:42 -0700 |
commit | 005b8909d995b699130ab97269cabab2bcf33a75 (patch) | |
tree | e3acda4fb0d5c361f3d2efb4dd245a8bcfa291c5 /lib.h | |
parent | f6cb6a21745822874789a33e150ef7ddbbf58979 (diff) | |
download | txr-005b8909d995b699130ab97269cabab2bcf33a75.tar.gz txr-005b8909d995b699130ab97269cabab2bcf33a75.tar.bz2 txr-005b8909d995b699130ab97269cabab2bcf33a75.zip |
sort: support stable sorting via ssort and snsort.
For array-like objecgts, these objects use an
array-based merge sort, using an auxiliary array
equal in size to the original array.
To provide the auxiliary array, a new kind of very simple
vector-like object is introduced into the gc module: protected
array. This looks like a raw dynamic C array of val type,
returned as a val *. Under the hood, there is a heap object
there, which makes the array traversable by the garbage
collector.
The whole point of this exercise is to make the new mergesort
function safe even if the caller-supplied functions misbehave
in such a way that the auxiliary array holds the only
references to heap objects.
* gc.c (struct prot_array): New struct,
(prot_array_cls): New static variable.
(gc_late_init): Register COBJ class, retaining in
prot_array_cls.
(prot_array_mark, prot_array_free): New static functions.
(prot_array_ops): New static structure.
(prot_array_alloc, prot_array_free): New functions.
* gc.h (prot_array_alloc, prot_array_free): Declared.
* lib.c (mergesort, ssort_vec): New static function.
(snsort, ssort): New functions.
* lib.h (snsort, ssort): Declared.
* tests/010/sort.tl: Cover ssort.
* txr.1: Documented.
* stdlib/doc-syms.tl: Updated.
Diffstat (limited to 'lib.h')
-rw-r--r-- | lib.h | 2 |
1 files changed, 2 insertions, 0 deletions
@@ -1319,6 +1319,8 @@ val interpose(val sep, val seq); val merge(val list1, val list2, val lessfun, val keyfun); val nsort(val seq, val lessfun, val keyfun); val sort(val seq, val lessfun, val keyfun); +val snsort(val seq, val lessfun, val keyfun); +val ssort(val seq, val lessfun, val keyfun); val nshuffle(val seq, val randstate); val shuffle(val seq, val randstate); val multi_sort(val lists, val funcs, val key_funcs); |