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.

1 files changed, 22 insertions, 0 deletions

diff --git a/tests/010/sort.tl b/tests/010/sort.tl
index 1fd48531..1fcc0c2d 100644
--- a/tests/010/sort.tl
+++ b/tests/010/sort.tl
@@ -21,3 +21,25 @@
     (sort slist) list
     (sort list (fun greater)) (reverse list)
     (sort slist (fun greater)) (reverse list)))
+
+(test (ssort ()) nil)
+
+(let* ((list (conses '(1 2 3 4 5 6 7 8)))
+       (sp (uniq [mapcar ssort (perm list (len list))])))
+  (mvtest (len sp) 1
+          (car sp) list))
+
+(test (ssort #()) #())
+
+(let* ((vec (conses #(1 2 3 4 5 6 7 8)))
+       (sp (uniq [mapcar ssort (perm vec (len vec))])))
+  (mvtest (len sp) 1
+          (car sp) vec))
+
+(let* ((list (range* 0 1000))
+       (slist (shuffle list)))
+  (mvtest
+    (ssort list) list
+    (ssort slist) list
+    (ssort list (fun greater)) (reverse list)
+    (ssort slist (fun greater)) (reverse list)))