ABC: A System for Sequential Synthesis and Verification
 
Loading...
Searching...
No Matches
Macros
sort.h File Reference
#include "utilities.h"
#include "global.h"
Include dependency graph for sort.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Macros

#define GREATER_SWAP(TYPE, P, Q, LESS)
 
#define SORTER   (solver->sorter)
 
#define PARTITION(TYPE, L, R, A, LESS)
 
#define QUICK_SORT_LIMIT   10
 
#define QUICK_SORT(TYPE, N, A, LESS)
 
#define INSERTION_SORT(TYPE, N, A, LESS)
 
#define CHECK_SORTED(...)
 
#define SORT(TYPE, N, A, LESS)
 
#define SORT_STACK(TYPE, S, LESS)
 

Macro Definition Documentation

◆ CHECK_SORTED

#define CHECK_SORTED ( ...)
Value:
do { \
} while (0)

Definition at line 123 of file sort.h.

123#define CHECK_SORTED(...) \
124 do { \
125 } while (0)

◆ GREATER_SWAP

#define GREATER_SWAP ( TYPE,
P,
Q,
LESS )
Value:
do { \
if (LESS (Q, P)) \
SWAP (TYPE, P, Q); \
} while (0)
TYPE
@ TYPE
Definition inflate.h:34

Definition at line 9 of file sort.h.

9#define GREATER_SWAP(TYPE, P, Q, LESS) \
10 do { \
11 if (LESS (Q, P)) \
12 SWAP (TYPE, P, Q); \
13 } while (0)

◆ INSERTION_SORT

#define INSERTION_SORT ( TYPE,
N,
A,
LESS )
Value:
do { \
size_t L_INSERTION_SORT = 0; \
size_t R_INSERTION_SORT = N - 1; \
\
for (size_t I_INSERTION_SORT = R_INSERTION_SORT; \
I_INSERTION_SORT > L_INSERTION_SORT; I_INSERTION_SORT--) \
GREATER_SWAP (TYPE, A[I_INSERTION_SORT - 1], A[I_INSERTION_SORT], \
LESS); \
\
for (size_t I_INSERTION_SORT = L_INSERTION_SORT + 2; \
I_INSERTION_SORT <= R_INSERTION_SORT; I_INSERTION_SORT++) { \
TYPE PIVOT_INSERTION_SORT = A[I_INSERTION_SORT]; \
\
size_t J_INSERTION_SORT = I_INSERTION_SORT; \
\
while (LESS (PIVOT_INSERTION_SORT, A[J_INSERTION_SORT - 1])) { \
A[J_INSERTION_SORT] = A[J_INSERTION_SORT - 1]; \
J_INSERTION_SORT--; \
} \
\
A[J_INSERTION_SORT] = PIVOT_INSERTION_SORT; \
} \
} while (0)
GREATER_SWAP
#define GREATER_SWAP(TYPE, P, Q, LESS)
Definition sort.h:9

Definition at line 97 of file sort.h.

97#define INSERTION_SORT(TYPE, N, A, LESS) \
98 do { \
99 size_t L_INSERTION_SORT = 0; \
100 size_t R_INSERTION_SORT = N - 1; \
101\
102 for (size_t I_INSERTION_SORT = R_INSERTION_SORT; \
103 I_INSERTION_SORT > L_INSERTION_SORT; I_INSERTION_SORT--) \
104 GREATER_SWAP (TYPE, A[I_INSERTION_SORT - 1], A[I_INSERTION_SORT], \
105 LESS); \
106\
107 for (size_t I_INSERTION_SORT = L_INSERTION_SORT + 2; \
108 I_INSERTION_SORT <= R_INSERTION_SORT; I_INSERTION_SORT++) { \
109 TYPE PIVOT_INSERTION_SORT = A[I_INSERTION_SORT]; \
110\
111 size_t J_INSERTION_SORT = I_INSERTION_SORT; \
112\
113 while (LESS (PIVOT_INSERTION_SORT, A[J_INSERTION_SORT - 1])) { \
114 A[J_INSERTION_SORT] = A[J_INSERTION_SORT - 1]; \
115 J_INSERTION_SORT--; \
116 } \
117\
118 A[J_INSERTION_SORT] = PIVOT_INSERTION_SORT; \
119 } \
120 } while (0)

◆ PARTITION

#define PARTITION ( TYPE,
L,
R,
A,
LESS )
Value:
do { \
const size_t L_PARTITION = (L); \
I_QUICK_SORT = L_PARTITION - 1; \
\
size_t J_PARTITION = (R); \
\
TYPE PIVOT_PARTITION = A[J_PARTITION]; \
\
for (;;) { \
while (LESS (A[++I_QUICK_SORT], PIVOT_PARTITION)) \
; \
while (LESS (PIVOT_PARTITION, A[--J_PARTITION])) \
if (J_PARTITION == L_PARTITION) \
break; \
\
if (I_QUICK_SORT >= J_PARTITION) \
break; \
\
SWAP (TYPE, A[I_QUICK_SORT], A[J_PARTITION]); \
} \
\
SWAP (TYPE, A[I_QUICK_SORT], A[R]); \
} while (0)

Definition at line 17 of file sort.h.

17#define PARTITION(TYPE, L, R, A, LESS) \
18 do { \
19 const size_t L_PARTITION = (L); \
20 I_QUICK_SORT = L_PARTITION - 1; \
21\
22 size_t J_PARTITION = (R); \
23\
24 TYPE PIVOT_PARTITION = A[J_PARTITION]; \
25\
26 for (;;) { \
27 while (LESS (A[++I_QUICK_SORT], PIVOT_PARTITION)) \
28 ; \
29 while (LESS (PIVOT_PARTITION, A[--J_PARTITION])) \
30 if (J_PARTITION == L_PARTITION) \
31 break; \
32\
33 if (I_QUICK_SORT >= J_PARTITION) \
34 break; \
35\
36 SWAP (TYPE, A[I_QUICK_SORT], A[J_PARTITION]); \
37 } \
38\
39 SWAP (TYPE, A[I_QUICK_SORT], A[R]); \
40 } while (0)

◆ QUICK_SORT

#define QUICK_SORT ( TYPE,
N,
A,
LESS )

Definition at line 44 of file sort.h.

44#define QUICK_SORT(TYPE, N, A, LESS) \
45 do { \
46 KISSAT_assert (N); \
47 KISSAT_assert (EMPTY_STACK (SORTER)); \
48\
49 size_t L_QUICK_SORT = 0; \
50 size_t R_QUICK_SORT = N - 1; \
51\
52 if (R_QUICK_SORT - L_QUICK_SORT <= QUICK_SORT_LIMIT) \
53 break; \
54\
55 for (;;) { \
56 const size_t M = L_QUICK_SORT + (R_QUICK_SORT - L_QUICK_SORT) / 2; \
57\
58 SWAP (TYPE, A[M], A[R_QUICK_SORT - 1]); \
59\
60 GREATER_SWAP (TYPE, A[L_QUICK_SORT], A[R_QUICK_SORT - 1], LESS); \
61 GREATER_SWAP (TYPE, A[L_QUICK_SORT], A[R_QUICK_SORT], LESS); \
62 GREATER_SWAP (TYPE, A[R_QUICK_SORT - 1], A[R_QUICK_SORT], LESS); \
63\
64 size_t I_QUICK_SORT; \
65\
66 PARTITION (TYPE, L_QUICK_SORT + 1, R_QUICK_SORT - 1, A, LESS); \
67 KISSAT_assert (L_QUICK_SORT < I_QUICK_SORT); \
68 KISSAT_assert (I_QUICK_SORT <= R_QUICK_SORT); \
69\
70 size_t LL_QUICK_SORT; \
71 size_t RR_QUICK_SORT; \
72\
73 if (I_QUICK_SORT - L_QUICK_SORT < R_QUICK_SORT - I_QUICK_SORT) { \
74 LL_QUICK_SORT = I_QUICK_SORT + 1; \
75 RR_QUICK_SORT = R_QUICK_SORT; \
76 R_QUICK_SORT = I_QUICK_SORT - 1; \
77 } else { \
78 LL_QUICK_SORT = L_QUICK_SORT; \
79 RR_QUICK_SORT = I_QUICK_SORT - 1; \
80 L_QUICK_SORT = I_QUICK_SORT + 1; \
81 } \
82 if (R_QUICK_SORT - L_QUICK_SORT > QUICK_SORT_LIMIT) { \
83 KISSAT_assert (RR_QUICK_SORT - LL_QUICK_SORT > QUICK_SORT_LIMIT); \
84 PUSH_STACK (SORTER, LL_QUICK_SORT); \
85 PUSH_STACK (SORTER, RR_QUICK_SORT); \
86 } else if (RR_QUICK_SORT - LL_QUICK_SORT > QUICK_SORT_LIMIT) { \
87 L_QUICK_SORT = LL_QUICK_SORT; \
88 R_QUICK_SORT = RR_QUICK_SORT; \
89 } else if (!EMPTY_STACK (SORTER)) { \
90 R_QUICK_SORT = POP_STACK (SORTER); \
91 L_QUICK_SORT = POP_STACK (SORTER); \
92 } else \
93 break; \
94 } \
95 } while (0)

◆ QUICK_SORT_LIMIT

#define QUICK_SORT_LIMIT   10

Definition at line 42 of file sort.h.

◆ SORT

#define SORT ( TYPE,
N,
A,
LESS )
Value:
do { \
const size_t N_SORT = (N); \
if (!N_SORT) \
break; \
START (sort); \
TYPE *A_SORT = (A); \
QUICK_SORT (TYPE, N_SORT, A_SORT, LESS); \
INSERTION_SORT (TYPE, N_SORT, A_SORT, LESS); \
CHECK_SORTED (N_SORT, A_SORT, LESS); \
STOP (sort); \
} while (0)

Definition at line 135 of file sort.h.

135#define SORT(TYPE, N, A, LESS) \
136 do { \
137 const size_t N_SORT = (N); \
138 if (!N_SORT) \
139 break; \
140 START (sort); \
141 TYPE *A_SORT = (A); \
142 QUICK_SORT (TYPE, N_SORT, A_SORT, LESS); \
143 INSERTION_SORT (TYPE, N_SORT, A_SORT, LESS); \
144 CHECK_SORTED (N_SORT, A_SORT, LESS); \
145 STOP (sort); \
146 } while (0)

◆ SORT_STACK

#define SORT_STACK ( TYPE,
S,
LESS )
Value:
do { \
const size_t N_SORT_STACK = SIZE_STACK (S); \
if (N_SORT_STACK <= 1) \
break; \
TYPE *A_SORT_STACK = BEGIN_STACK (S); \
SORT (TYPE, N_SORT_STACK, A_SORT_STACK, LESS); \
} while (0)
BEGIN_STACK
#define BEGIN_STACK(S)
Definition stack.h:46
SIZE_STACK
#define SIZE_STACK(S)
Definition stack.h:19

Definition at line 148 of file sort.h.

148#define SORT_STACK(TYPE, S, LESS) \
149 do { \
150 const size_t N_SORT_STACK = SIZE_STACK (S); \
151 if (N_SORT_STACK <= 1) \
152 break; \
153 TYPE *A_SORT_STACK = BEGIN_STACK (S); \
154 SORT (TYPE, N_SORT_STACK, A_SORT_STACK, LESS); \
155 } while (0)

◆ SORTER

#define SORTER   (solver->sorter)

Definition at line 15 of file sort.h.