From 005b8909d995b699130ab97269cabab2bcf33a75 Mon Sep 17 00:00:00 2001 From: Kaz Kylheku Date: Tue, 2 May 2023 19:29:42 -0700 Subject: 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. --- gc.h | 3 +++ 1 file changed, 3 insertions(+) (limited to 'gc.h') diff --git a/gc.h b/gc.h index ea09cfad..58d057db 100644 --- a/gc.h +++ b/gc.h @@ -86,3 +86,6 @@ INLINE void gc_stack_check(void) if (&v < gc_stack_limit) gc_stack_overflow(); } + +val *gc_prot_array_alloc(cnum size, val self); +void gc_prot_array_free(val *); -- cgit v1.2.3