Paper Mario DX
Paper Mario (N64) modding
 
Loading...
Searching...
No Matches
Macros
qsort.h File Reference

Go to the source code of this file.

Macros

#define Q_SORT3(q_a1, q_a2, q_a3, Q_LESS, Q_SWAP)
 
#define Q_PARTITION(q_l, q_r, q_i, q_j, Q_UINT, Q_LESS, Q_SWAP)
 
#define Q_INSERTION_SORT(q_l, q_r, Q_UINT, Q_LESS, Q_SWAP)
 
#define Q_THRESH   16
 
#define Q_LOOP(Q_UINT, Q_N, Q_LESS, Q_SWAP)
 
#define Q_SUBFILES(q_l1, q_r1, q_l2, q_r2)
 
#define QSORT(Q_N, Q_LESS, Q_SWAP)
 

Macro Definition Documentation

◆ Q_SORT3

#define Q_SORT3 ( q_a1,
q_a2,
q_a3,
Q_LESS,
Q_SWAP )
Value:
do { \
if (Q_LESS(q_a2, q_a1)) { \
if (Q_LESS(q_a3, q_a2)) \
Q_SWAP(q_a1, q_a3); \
else { \
Q_SWAP(q_a1, q_a2); \
if (Q_LESS(q_a3, q_a2)) \
Q_SWAP(q_a2, q_a3); \
} \
} \
else if (Q_LESS(q_a3, q_a2)) { \
Q_SWAP(q_a2, q_a3); \
if (Q_LESS(q_a2, q_a1)) \
Q_SWAP(q_a1, q_a2); \
} \
} while (0)

Definition at line 41 of file qsort.h.

41#define Q_SORT3(q_a1, q_a2, q_a3, Q_LESS, Q_SWAP) \
42do { \
43 if (Q_LESS(q_a2, q_a1)) { \
44 if (Q_LESS(q_a3, q_a2)) \
45 Q_SWAP(q_a1, q_a3); \
46 else { \
47 Q_SWAP(q_a1, q_a2); \
48 if (Q_LESS(q_a3, q_a2)) \
49 Q_SWAP(q_a2, q_a3); \
50 } \
51 } \
52 else if (Q_LESS(q_a3, q_a2)) { \
53 Q_SWAP(q_a2, q_a3); \
54 if (Q_LESS(q_a2, q_a1)) \
55 Q_SWAP(q_a1, q_a2); \
56 } \
57} while (0)

◆ Q_PARTITION

#define Q_PARTITION ( q_l,
q_r,
q_i,
q_j,
Q_UINT,
Q_LESS,
Q_SWAP )
Value:
do { \
/* The middle element, not to be confused with the median. */ \
Q_UINT q_m = q_l + ((q_r - q_l) >> 1); \
/* Reorder the second, the middle, and the last items. \
* As [Edelkamp Weiss 2016] explain, using the second element \
* instead of the first one helps avoid bad behaviour for \
* decreasingly sorted arrays. This method is used in recent \
* versions of gcc's std::sort, see gcc bug 58437#c13, although \
* the details are somewhat different (cf. #c14). */ \
Q_SORT3(q_l + 1, q_m, q_r, Q_LESS, Q_SWAP); \
/* Place the median at the beginning. */ \
Q_SWAP(q_l, q_m); \
/* Partition [q_l+2, q_r-1] around the median which is in q_l. \
* q_i and q_j are initially off by one, they get decremented \
* in the do-while loops. */ \
q_i = q_l + 1; q_j = q_r; \
while (1) { \
do q_i++; while (Q_LESS(q_i, q_l)); \
do q_j--; while (Q_LESS(q_l, q_j)); \
if (q_i >= q_j) break; /* Sedgewick says "until j < i" */ \
Q_SWAP(q_i, q_j); \
} \
/* Compensate for the i==j case. */ \
q_i = q_j + 1; \
/* Put the median to its final place. */ \
Q_SWAP(q_l, q_j); \
/* The median is not part of the left subfile. */ \
q_j--; \
} while (0)

Definition at line 62 of file qsort.h.

62#define Q_PARTITION(q_l, q_r, q_i, q_j, Q_UINT, Q_LESS, Q_SWAP) \
63do { \
64 /* The middle element, not to be confused with the median. */ \
65 Q_UINT q_m = q_l + ((q_r - q_l) >> 1); \
66 /* Reorder the second, the middle, and the last items. \
67 * As [Edelkamp Weiss 2016] explain, using the second element \
68 * instead of the first one helps avoid bad behaviour for \
69 * decreasingly sorted arrays. This method is used in recent \
70 * versions of gcc's std::sort, see gcc bug 58437#c13, although \
71 * the details are somewhat different (cf. #c14). */ \
72 Q_SORT3(q_l + 1, q_m, q_r, Q_LESS, Q_SWAP); \
73 /* Place the median at the beginning. */ \
74 Q_SWAP(q_l, q_m); \
75 /* Partition [q_l+2, q_r-1] around the median which is in q_l. \
76 * q_i and q_j are initially off by one, they get decremented \
77 * in the do-while loops. */ \
78 q_i = q_l + 1; q_j = q_r; \
79 while (1) { \
80 do q_i++; while (Q_LESS(q_i, q_l)); \
81 do q_j--; while (Q_LESS(q_l, q_j)); \
82 if (q_i >= q_j) break; /* Sedgewick says "until j < i" */ \
83 Q_SWAP(q_i, q_j); \
84 } \

◆ Q_INSERTION_SORT

#define Q_INSERTION_SORT ( q_l,
q_r,
Q_UINT,
Q_LESS,
Q_SWAP )
Value:
do { \
Q_UINT q_i, q_j; \
/* For each item starting with the second... */ \
for (q_i = q_l + 1; q_i <= q_r; q_i++) \
/* move it down the array so that the first part is sorted. */ \
for (q_j = q_i; q_j > q_l && (Q_LESS(q_j, q_j - 1)); q_j--) \
Q_SWAP(q_j, q_j - 1); \
} while (0)

Definition at line 93 of file qsort.h.

93/* Insertion sort is applied to small subfiles - this is contrary to
94 * Sedgewick's suggestion to run a separate insertion sort pass after
95 * the partitioning is done. The reason I don't like a separate pass
96 * is that it triggers extra comparisons, because it can't see that the
97 * medians are already in their final positions and need not be rechecked.
98 * Since I do not assume that comparisons are cheap, I also do not try
99 * to eliminate the (q_j > q_l) boundary check. */
100#define Q_INSERTION_SORT(q_l, q_r, Q_UINT, Q_LESS, Q_SWAP) \
101do { \

◆ Q_THRESH

#define Q_THRESH   16

Definition at line 108 of file qsort.h.

◆ Q_LOOP

#define Q_LOOP ( Q_UINT,
Q_N,
Q_LESS,
Q_SWAP )

Definition at line 111 of file qsort.h.

111 * Q_THRESH, the algorithm performs recursive partitioning. When the size
112 * drops below Q_THRESH, the algorithm switches to insertion sort.
113 * The minimum valid value is probably 5 (with 5 items, the second and
114 * the middle items, the middle itself being rounded down, are distinct). */
115#define Q_THRESH 16
116
117/* The main loop. */
118#define Q_LOOP(Q_UINT, Q_N, Q_LESS, Q_SWAP) \
119do { \
120 Q_UINT q_l = 0; \
121 Q_UINT q_r = (Q_N) - 1; \
122 Q_UINT q_sp = 0; /* the number of frames pushed to the stack */ \
123 struct { Q_UINT q_l, q_r; } \
124 /* On 32-bit platforms, to sort a "char[3GB+]" array, \
125 * it may take full 32 stack frames. On 64-bit CPUs, \
126 * though, the address space is limited to 48 bits. \
127 * The usage is further reduced if Q_N has a 32-bit type. */ \
128 q_st[sizeof(Q_UINT) > 4 && sizeof(Q_N) > 4 ? 48 : 32]; \
129 while (1) { \
130 if (q_r - q_l + 1 >= Q_THRESH) { \
131 Q_UINT q_i, q_j; \
132 Q_PARTITION(q_l, q_r, q_i, q_j, Q_UINT, Q_LESS, Q_SWAP); \
133 /* Now have two subfiles: [q_l,q_j] and [q_i,q_r]. \
134 * Dealing with them depends on which one is bigger. */ \
135 if (q_j - q_l >= q_r - q_i) \
136 Q_SUBFILES(q_l, q_j, q_i, q_r); \
137 else \
138 Q_SUBFILES(q_i, q_r, q_l, q_j); \
Q_LOOP
#define Q_LOOP(Q_UINT, Q_N, Q_LESS, Q_SWAP)
Definition qsort.h:111
Q_THRESH
#define Q_THRESH
Definition qsort.h:108

◆ Q_SUBFILES

#define Q_SUBFILES ( q_l1,
q_r1,
q_l2,
q_r2 )
Value:
do { \
/* If the second subfile is only a single element, it needs \
* no further processing. The first subfile will be processed \
* on the next iteration (both subfiles cannot be only a single \
* element, due to Q_THRESH). */ \
if (q_l2 == q_r2) { \
q_l = q_l1; \
q_r = q_r1; \
} \
else { \
/* Otherwise, both subfiles need processing. \
* Push the larger subfile onto the stack. */ \
q_st[q_sp].q_l = q_l1; \
q_st[q_sp].q_r = q_r1; \
q_sp++; \
/* Process the smaller subfile on the next iteration. */ \
q_l = q_l2; \
q_r = q_r2; \
} \
} while (0)

Definition at line 142 of file qsort.h.

142 /* Pop subfiles from the stack, until it gets empty. */ \
143 if (q_sp == 0) break; \
144 q_sp--; \
145 q_l = q_st[q_sp].q_l; \
146 q_r = q_st[q_sp].q_r; \
147 } \
148 } \
149} while (0)
150
151/* The missing part: dealing with subfiles.
152 * Assumes that the first subfile is not smaller than the second. */
153#define Q_SUBFILES(q_l1, q_r1, q_l2, q_r2) \
154do { \
155 /* If the second subfile is only a single element, it needs \
156 * no further processing. The first subfile will be processed \
157 * on the next iteration (both subfiles cannot be only a single \
158 * element, due to Q_THRESH). */ \

◆ QSORT

#define QSORT ( Q_N,
Q_LESS,
Q_SWAP )
Value:
do { \
if ((Q_N) > 1) \
/* We could check sizeof(Q_N) and use "unsigned", but at least \
* on x86_64, this has the performance penalty of up to 5%. */ \
Q_LOOP(unsigned long, Q_N, Q_LESS, Q_SWAP); \
} while (0)

Definition at line 161 of file qsort.h.

161 q_r = q_r1; \
162 } \
163 else { \
164 /* Otherwise, both subfiles need processing. \
165 * Push the larger subfile onto the stack. */ \
166 q_st[q_sp].q_l = q_l1; \

Referenced by execute_render_tasks().