qsort(3) library function

C library function QSORT(3) is also polymorphic similar to FREAD(3). It has the following functionality.

 void qsort(void *base, size_t nmemb, size_t size,
            int(*compar)(const void *, const void *));

where

voild *base : the array to be sorted.
size_t nmemb : the number of array elements
size_t size : the size of each element data
int(*compar)(const void *, const void *) : a compare function that takes two data pointers.

As a statically typed polymoprhic language, ML should be able to represent this as the following polymorphic function.

qsort : 'a array * ('a ptr * 'a ptr -> int) -> unit

In SML#, this is easily done by using SML#'s mechnisms to use C functions with callbacks and polymorphic C functions.

 val libc = DynamicLink.dlopen "/lib/libc.so.6"
 val c_qsort = DynamicLink.dlsym (libc, "qsort")
 fun qsort (a, f) =
     _ffiapply c_qsort (a : 'a array,
                        Array.length a : int,
                        _sizeof('a),
                        f : ('a ptr, 'a ptr) -> int) : unit

SML# evaluates this code to produce the following binding.

val qsort = fn : ['a .'a Array.array * ('a ptr * 'a ptr  -> int)  -> unit]

To use this function, one need to write a comparison function that takes C pointers and return an integer. For this purpose, SML# provide the following overloaded operators.

!! : ['a::{int, real, word, byte, char}.'a ptr -> 'a]

Using this, sort can be used as follows.

 fun compareReal (p1, p2) =
     let
       val n1 = !!p1 : real
       val n2 = !!p2
     in
       if n1 > n2 then 1 else if n1 < n2 then ~1 else 0
     end
 val _ = qsort (aRealArray, compareReal)
Last modified:2007/04/03 13:02:19
Keyword(s):
References:[Program Examples]