numpy 2.0.0
src/_sortmodule.c.src File Reference
#include "Python.h"
#include "numpy/noprefix.h"
#include "numpy/npy_math.h"
#include "numpy/halffloat.h"
#include "npy_config.h"

Defines

#define NOT_USED   NPY_UNUSED(unused)
#define PYA_QS_STACK   100
#define SMALL_QUICKSORT   15
#define SMALL_MERGESORT   20
#define SMALL_STRING   16
#define TYPE   @_SWAP(a,b) {@type@ tmp = (b); (b)=(a); (a) = tmp;}

Functions

static NPY_INLINE int TYPE _LT (@type @a,@type @b)
static NPY_INLINE int HALF_LT (npy_half a, npy_half b)
static NPY_INLINE int PyObject_LT (PyObject *pa, PyObject *pb)
static NPY_INLINE void STRING_COPY (char *s1, char *s2, size_t len)
static NPY_INLINE void STRING_SWAP (char *s1, char *s2, size_t len)
static NPY_INLINE int STRING_LT (char *s1, char *s2, size_t len)
static NPY_INLINE void UNICODE_COPY (npy_ucs4 *s1, npy_ucs4 *s2, size_t len)
static NPY_INLINE void UNICODE_SWAP (npy_ucs4 *s1, npy_ucs4 *s2, size_t len)
static NPY_INLINE int UNICODE_LT (npy_ucs4 *s1, npy_ucs4 *s2, size_t len)
static int TYPE _quicksort (@type @*start, npy_intp num, void *NOT_USED)
static int TYPE _aquicksort (@type @*v, npy_intp *tosort, npy_intp num, void *NOT_USED)
static int TYPE _heapsort (@type @*start, npy_intp n, void *NOT_USED)
static int TYPE _aheapsort (@type @*v, npy_intp *tosort, npy_intp n, void *NOT_USED)
static void TYPE _mergesort0 (@type @*pl,@type @*pr,@type @*pw)
static int TYPE _mergesort (@type @*start, npy_intp num, void *NOT_USED)
static void TYPE _amergesort0 (npy_intp *pl, npy_intp *pr,@type @*v, npy_intp *pw)
static int TYPE _amergesort (@type @*v, npy_intp *tosort, npy_intp num, void *NOT_USED)
static void TYPE _mergesort0 (@type @*pl,@type @*pr,@type @*pw,@type @*vp, size_t len)
static int TYPE _mergesort (@type @*start, npy_intp num, PyArrayObject *arr)
static int TYPE _quicksort (@type @*start, npy_intp num, PyArrayObject *arr)
static int TYPE _heapsort (@type @*start, npy_intp n, PyArrayObject *arr)
static int TYPE _aheapsort (@type @*v, npy_intp *tosort, npy_intp n, PyArrayObject *arr)
static int TYPE _aquicksort (@type @*v, npy_intp *tosort, npy_intp num, PyArrayObject *arr)
static void TYPE _amergesort0 (npy_intp *pl, npy_intp *pr,@type @*v, npy_intp *pw, int len)
static int TYPE _amergesort (@type @*v, npy_intp *tosort, npy_intp num, PyArrayObject *arr)
static void add_sortfuncs (void)
PyMODINIT_FUNC init_sort (void)

Variables

static struct PyMethodDef methods []

Define Documentation

#define NOT_USED   NPY_UNUSED(unused)
The purpose of this module is to add faster sort functions that are type-specific. This is done by altering the function table for the builtin descriptors.
These sorting functions are copied almost directly from numarray with a few modifications (complex comparisons compare the imaginary part if the real parts are equal, for example), and the names are changed.
The original sorting code is due to Charles R. Harris who wrote it for numarray.
Quick sort is usually the fastest, but the worst case scenario can be slower than the merge and heap sorts. The merge sort requires extra memory and so for large arrays may not be useful.
The merge sort is stable, meaning that equal components are unmoved from their entry versions, so it can be used to implement lexigraphic sorting on multiple keys.
The heap sort is included for completeness.
#define PYA_QS_STACK   100

Referenced by UNICODE_SWAP().

#define SMALL_MERGESORT   20
#define SMALL_QUICKSORT   15

Referenced by UNICODE_SWAP().

#define SMALL_STRING   16
#define TYPE   @_SWAP(a,b) {@type@ tmp = (b); (b)=(a); (a) = tmp;}

* SWAP MACROS **

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE,CLONGDOUBLE, INTP#
type = npy_bool, npy_byte, npy_ubyte, npy_short, npy_ushort, npy_int,
npy_uint, npy_long, npy_ulong, npy_longlong, npy_ulonglong, npy_half, npy_float, npy_double, npy_longdouble, npy_cfloat, npy_cdouble, npy_clongdouble, npy_intp#

</blockquote>

Referenced by _aheapsort(), _amergesort(), _heapsort(), _mergesort(), _quicksort(), and UNICODE_SWAP().


Function Documentation

static int TYPE _aheapsort ( @type @*  v,
npy_intp tosort,
npy_intp  n,
void *  NOT_USED 
) [static]

The arrays need to be offset by one for heapsort indexing

References _LT(), _mergesort0(), and TYPE.

static int TYPE _aheapsort ( @type @*  v,
npy_intp tosort,
npy_intp  n,
PyArrayObject arr 
) [static]

The array needs to be offset by one for heapsort indexing

static int TYPE _amergesort ( @type @*  v,
npy_intp tosort,
npy_intp  num,
void *  NOT_USED 
) [static]

References TYPE.

static int TYPE _amergesort ( @type @*  v,
npy_intp tosort,
npy_intp  num,
PyArrayObject arr 
) [static]
static void TYPE _amergesort0 ( npy_intp pl,
npy_intp pr,
@type @*  v,
npy_intp pw 
) [static]

merge sort
insertion sort

Referenced by _mergesort().

static void TYPE _amergesort0 ( npy_intp pl,
npy_intp pr,
@type @*  v,
npy_intp pw,
int  len 
) [static]

merge sort
insertion sort

References methods.

static int TYPE _aquicksort ( @type @*  v,
npy_intp tosort,
npy_intp  num,
PyArrayObject arr 
) [static]

quicksort partition
push largest partition on stack
insertion sort

static int TYPE _aquicksort ( @type @*  v,
npy_intp tosort,
npy_intp  num,
void *  NOT_USED 
) [static]

quicksort partition
push largest partition on stack
insertion sort

static int TYPE _heapsort ( @type @*  start,
npy_intp  n,
PyArrayObject arr 
) [static]
static int TYPE _heapsort ( @type @*  start,
npy_intp  n,
void *  NOT_USED 
) [static]

The array needs to be offset by one for heapsort indexing

References _LT(), and TYPE.

static NPY_INLINE int TYPE _LT ( @type @  a,
@type @  b 
) [static]
end repeat*

* COMPARISON FUNCTIONS **

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG#
type = Bool, byte, ubyte, short, ushort, int, uint, long, ulong,
longlong, ulonglong#

</blockquote>

end repeat*
begin repeat <blockquote> TYPE = FLOAT, DOUBLE, LONGDOUBLE# type = float, double, longdouble#</blockquote>
For inline functions SUN recommends not using a return in the then part of an if statement. It's a SUN compiler thing, so assign the return value to a variable instead.
begin repeat <blockquote> TYPE = CFLOAT, CDOUBLE, CLONGDOUBLE# type = cfloat, cdouble, clongdouble#</blockquote>

Referenced by _aheapsort(), _heapsort(), _quicksort(), and UNICODE_SWAP().

static int TYPE _mergesort ( @type @*  start,
npy_intp  num,
PyArrayObject arr 
) [static]

References TYPE.

static int TYPE _mergesort ( @type @*  start,
npy_intp  num,
void *  NOT_USED 
) [static]
static void TYPE _mergesort0 ( @type @*  pl,
@type @*  pr,
@type @*  pw,
@type @*  vp,
size_t  len 
) [static]
end repeat*

* STRING SORTS **

begin repeat <blockquote> TYPE = STRING, UNICODE# type = char, PyArray_UCS4#</blockquote>

merge sort
insertion sort

static void TYPE _mergesort0 ( @type @*  pl,
@type @*  pr,
@type @*  pw 
) [static]

merge sort
insertion sort

Referenced by _aheapsort().

static int TYPE _quicksort ( @type @*  start,
npy_intp  num,
void *  NOT_USED 
) [static]

* NUMERIC SORTS **

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE#
type = Bool, byte, ubyte, short, ushort, int, uint, long, ulong,
longlong, ulonglong, ushort, float, double, longdouble, cfloat, cdouble, clongdouble#

</blockquote>

quicksort partition
push largest partition on stack
insertion sort

static int TYPE _quicksort ( @type @*  start,
npy_intp  num,
PyArrayObject arr 
) [static]

quicksort partition
push largest partition on stack
insertion sort

References _LT(), and TYPE.

static void add_sortfuncs ( void  ) [static]
end repeat*

begin repeat <blockquote>

TYPE = BOOL, BYTE, UBYTE, SHORT, USHORT, INT, UINT, LONG, ULONG,
LONGLONG, ULONGLONG, HALF, FLOAT, DOUBLE, LONGDOUBLE, CFLOAT, CDOUBLE, CLONGDOUBLE, STRING, UNICODE#

</blockquote>

end repeat*

static NPY_INLINE int HALF_LT ( npy_half  a,
npy_half  b 
) [static]
end repeat*
PyMODINIT_FUNC init_sort ( void  )
Initialization function for the module
static NPY_INLINE int PyObject_LT ( PyObject *  pa,
PyObject *  pb 
) [static]
end repeat*
The PyObject functions are stubs for later use
static NPY_INLINE void STRING_COPY ( char *  s1,
char *  s2,
size_t  len 
) [static]
static NPY_INLINE int STRING_LT ( char *  s1,
char *  s2,
size_t  len 
) [static]
static NPY_INLINE void STRING_SWAP ( char *  s1,
char *  s2,
size_t  len 
) [static]
static NPY_INLINE void UNICODE_COPY ( npy_ucs4 *  s1,
npy_ucs4 *  s2,
size_t  len 
) [static]
static NPY_INLINE int UNICODE_LT ( npy_ucs4 *  s1,
npy_ucs4 *  s2,
size_t  len 
) [static]
static NPY_INLINE void UNICODE_SWAP ( npy_ucs4 *  s1,
npy_ucs4 *  s2,
size_t  len 
) [static]

Variable Documentation

struct PyMethodDef methods[] [static]
Initial value:
 {
    {NULL, NULL, 0, NULL}
}

Referenced by _amergesort0().