1 /*---------------------------------------------------------------------------*
2 Project: TwlSDK - include
3 File: qsort.h
4
5 Copyright 2003-2008 Nintendo. All rights reserved.
6
7 These coded instructions, statements, and computer programs contain
8 proprietary information of Nintendo of America Inc. and/or Nintendo
9 Company Ltd., and are protected by Federal copyright law. They may
10 not be disclosed to third parties or copied or duplicated in any form,
11 in whole or in part, without the prior written consent of Nintendo.
12
13 $Date:: $
14 $Rev:$
15 $Author:$
16 *---------------------------------------------------------------------------*/
17
18 #ifndef NITRO_MATH_QSORT_H_
19 #define NITRO_MATH_QSORT_H_
20
21 #ifdef __cplusplus
22 extern "C" {
23 #endif
24
25 #include <nitro/misc.h>
26 #include <nitro/types.h>
27 #include <nitro/math/math.h>
28
29 /* Function for comparing values. */
30 typedef s32 (*MATHCompareFunc) (void *elem1, void *elem2);
31
32 /* Maximum necessary stack size. */
33 /*---------------------------------------------------------------------------*
34 Name: MATH_QSortStackSize
35
36 Description: Calculates the necessary work buffer size for when executing MATH_QSort.
37
38 Arguments: num: Number of data items to sort
39
40 Returns: Necessary buffer size.
41 *---------------------------------------------------------------------------*/
MATH_QSortStackSize(u32 num)42 static inline u32 MATH_QSortStackSize(u32 num)
43 {
44 int tmp = MATH_ILog2(num);
45
46 if (tmp <= 0)
47 {
48 return sizeof(u32);
49 }
50 else
51 {
52 return (u32)((MATH_ILog2(num) + 1) * sizeof(u32) * 2);
53 }
54 }
55
56
57 /*---------------------------------------------------------------------------*
58 Name: MATH_QSort
59
60 Description: Performs a quicksort without using recursion.
61 The buffer area used for sorting must be passed, and the required buffer size can be obtained with MATH_QSORT_STACK_SIZE( num ).
62
63
64 Arguments: head: Pointer to the data to sort
65 num: Number of data items to sort
66 width: Data size of one portion of data to sort
67 comp: Pointer to comparison function
68 stackBuf: Buffer to use for sorting
69
70 Returns: None.
71 *---------------------------------------------------------------------------*/
72 void MATH_QSort(void *head, u32 num, u32 width, MATHCompareFunc comp, void *stackBuf);
73
74
75 #ifdef __cplusplus
76 } /* extern "C" */
77 #endif
78
79 /* NITRO_MATH_QSORT_H_ */
80 #endif
81