Line data Source code
1 : // SPDX-License-Identifier: GPL-2.0-or-later
2 : // Copyright (C) 2013 Andrea Mazzoleni
3 :
4 : #ifndef __RAID_COMBO_H
5 : #define __RAID_COMBO_H
6 :
7 : #include <assert.h>
8 :
9 : /**
10 : * Get the first permutation with repetition of r of n elements.
11 : *
12 : * Typical use is with permutation_next() in the form:
13 : *
14 : * int i[R];
15 : * permutation_first(R, N, i);
16 : * do {
17 : * code using i[0], i[1], ..., i[R-1]
18 : * } while (permutation_next(R, N, i));
19 : *
20 : * It's equivalent to the code:
21 : *
22 : * for(i[0]=0;i[0]<N;++i[0])
23 : * for(i[1]=0;i[1]<N;++i[1])
24 : * ...
25 : * for(i[R-2]=0;i[R-2]<N;++i[R-2])
26 : * for(i[R-1]=0;i[R-1]<N;++i[R-1])
27 : * code using i[0], i[1], ..., i[R-1]
28 : */
29 : static __always_inline void permutation_first(int r, int n, int *c)
30 : {
31 : int i;
32 :
33 : (void)n; /* unused, but kept for clarity */
34 18 : assert(0 < r && r <= n);
35 :
36 81 : for (i = 0; i < r; ++i)
37 63 : c[i] = 0;
38 18 : }
39 :
40 : /**
41 : * Get the next permutation with repetition of r of n elements.
42 : * Return ==0 when finished.
43 : */
44 : static __always_inline int permutation_next(int r, int n, int *c)
45 : {
46 167958 : int i = r - 1; /* present position */
47 :
48 201528 : recurse:
49 : /* next element at position i */
50 201528 : ++c[i];
51 :
52 : /* if the position has reached the max */
53 201528 : if (c[i] >= n) {
54 :
55 : /* if we are at the first level, we have finished */
56 33588 : if (i == 0)
57 18 : return 0;
58 :
59 : /* increase the previous position */
60 33570 : --i;
61 33570 : goto recurse;
62 : }
63 :
64 167940 : ++i;
65 :
66 : /* initialize all the next positions, if any */
67 201465 : while (i < r) {
68 33525 : c[i] = 0;
69 33525 : ++i;
70 : }
71 :
72 167940 : return 1;
73 : }
74 :
75 : /**
76 : * Get the first combination without repetition of r of n elements.
77 : *
78 : * Typical use is with combination_next() in the form:
79 : *
80 : * int i[R];
81 : * combination_first(R, N, i);
82 : * do {
83 : * code using i[0], i[1], ..., i[R-1]
84 : * } while (combination_next(R, N, i));
85 : *
86 : * It's equivalent to the code:
87 : *
88 : * for(i[0]=0;i[0]<N-(R-1);++i[0])
89 : * for(i[1]=i[0]+1;i[1]<N-(R-2);++i[1])
90 : * ...
91 : * for(i[R-2]=i[R-3]+1;i[R-2]<N-1;++i[R-2])
92 : * for(i[R-1]=i[R-2]+1;i[R-1]<N;++i[R-1])
93 : * code using i[0], i[1], ..., i[R-1]
94 : */
95 : static __always_inline void combination_first(int r, int n, int *c)
96 : {
97 : int i;
98 :
99 : (void)n; /* unused, but kept for clarity */
100 224995 : assert(0 < r && r <= n);
101 :
102 749329 : for (i = 0; i < r; ++i)
103 524334 : c[i] = i;
104 224995 : }
105 :
106 : /**
107 : * Get the next combination without repetition of r of n elements.
108 : * Return ==0 when finished.
109 : */
110 : static __always_inline int combination_next(int r, int n, int *c)
111 : {
112 53619 : int i = r - 1; /* present position */
113 53619 : int h = n; /* high limit for this position */
114 :
115 86492 : recurse:
116 : /* next element at position i */
117 86492 : ++c[i];
118 :
119 : /* if the position has reached the max */
120 86492 : if (c[i] >= h) {
121 :
122 : /* if we are at the first level, we have finished */
123 46131 : if (i == 0)
124 13258 : return 0;
125 :
126 : /* increase the previous position */
127 32873 : --i;
128 32873 : --h;
129 32873 : goto recurse;
130 : }
131 :
132 40361 : ++i;
133 :
134 : /* initialize all the next positions, if any */
135 62906 : while (i < r) {
136 : /* each position starts at the next value of the previous one */
137 22545 : c[i] = c[i - 1] + 1;
138 22545 : ++i;
139 : }
140 :
141 40361 : return 1;
142 : }
143 : #endif
144 :
|
