Line data Source code
1 : /*
2 : * Copyright (C) 2013 Andrea Mazzoleni
3 : *
4 : * This program is free software: you can redistribute it and/or modify
5 : * it under the terms of the GNU General Public License as published by
6 : * the Free Software Foundation, either version 2 of the License, or
7 : * (at your option) any later version.
8 : *
9 : * This program is distributed in the hope that it will be useful,
10 : * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 : * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 : * GNU General Public License for more details.
13 : */
14 :
15 : #ifndef __RAID_COMBO_H
16 : #define __RAID_COMBO_H
17 :
18 : #include <assert.h>
19 :
20 : /**
21 : * Get the first permutation with repetition of r of n elements.
22 : *
23 : * Typical use is with permutation_next() in the form :
24 : *
25 : * int i[R];
26 : * permutation_first(R, N, i);
27 : * do {
28 : * code using i[0], i[1], ..., i[R-1]
29 : * } while (permutation_next(R, N, i));
30 : *
31 : * It's equivalent at the code :
32 : *
33 : * for(i[0]=0;i[0]<N;++i[0])
34 : * for(i[1]=0;i[1]<N;++i[1])
35 : * ...
36 : * for(i[R-2]=0;i[R-2]<N;++i[R-2])
37 : * for(i[R-1]=0;i[R-1]<N;++i[R-1])
38 : * code using i[0], i[1], ..., i[R-1]
39 : */
40 : static __always_inline void permutation_first(int r, int n, int *c)
41 : {
42 : int i;
43 :
44 : (void)n; /* unused, but kept for clarity */
45 18 : assert(0 < r && r <= n);
46 :
47 81 : for (i = 0; i < r; ++i)
48 63 : c[i] = 0;
49 : }
50 :
51 : /**
52 : * Get the next permutation with repetition of r of n elements.
53 : * Return ==0 when finished.
54 : */
55 : static __always_inline int permutation_next(int r, int n, int *c)
56 : {
57 167958 : int i = r - 1; /* present position */
58 :
59 : recurse:
60 : /* next element at position i */
61 201528 : ++c[i];
62 :
63 : /* if the position has reached the max */
64 201528 : if (c[i] >= n) {
65 :
66 : /* if we are at the first level, we have finished */
67 33588 : if (i == 0)
68 18 : return 0;
69 :
70 : /* increase the previous position */
71 33570 : --i;
72 : goto recurse;
73 : }
74 :
75 167940 : ++i;
76 :
77 : /* initialize all the next positions, if any */
78 201465 : while (i < r) {
79 33525 : c[i] = 0;
80 33525 : ++i;
81 : }
82 :
83 167940 : return 1;
84 : }
85 :
86 : /**
87 : * Get the first combination without repetition of r of n elements.
88 : *
89 : * Typical use is with combination_next() in the form :
90 : *
91 : * int i[R];
92 : * combination_first(R, N, i);
93 : * do {
94 : * code using i[0], i[1], ..., i[R-1]
95 : * } while (combination_next(R, N, i));
96 : *
97 : * It's equivalent at the code :
98 : *
99 : * for(i[0]=0;i[0]<N-(R-1);++i[0])
100 : * for(i[1]=i[0]+1;i[1]<N-(R-2);++i[1])
101 : * ...
102 : * for(i[R-2]=i[R-3]+1;i[R-2]<N-1;++i[R-2])
103 : * for(i[R-1]=i[R-2]+1;i[R-1]<N;++i[R-1])
104 : * code using i[0], i[1], ..., i[R-1]
105 : */
106 : static __always_inline void combination_first(int r, int n, int *c)
107 : {
108 : int i;
109 :
110 : (void)n; /* unused, but kept for clarity */
111 208022 : assert(0 < r && r <= n);
112 :
113 689674 : for (i = 0; i < r; ++i)
114 481652 : c[i] = i;
115 : }
116 :
117 : /**
118 : * Get the next combination without repetition of r of n elements.
119 : * Return ==0 when finished.
120 : */
121 : static __always_inline int combination_next(int r, int n, int *c)
122 : {
123 52408 : int i = r - 1; /* present position */
124 52408 : int h = n; /* high limit for this position */
125 :
126 : recurse:
127 : /* next element at position i */
128 85281 : ++c[i];
129 :
130 : /* if the position has reached the max */
131 85281 : if (c[i] >= h) {
132 :
133 : /* if we are at the first level, we have finished */
134 45103 : if (i == 0)
135 12230 : return 0;
136 :
137 : /* increase the previous position */
138 32873 : --i;
139 32873 : --h;
140 : goto recurse;
141 : }
142 :
143 40178 : ++i;
144 :
145 : /* initialize all the next positions, if any */
146 62723 : while (i < r) {
147 : /* each position start at the next value of the previous one */
148 22545 : c[i] = c[i - 1] + 1;
149 22545 : ++i;
150 : }
151 :
152 40178 : return 1;
153 : }
154 : #endif
155 :
|
