4 * Userspace RCU library - RCU Judy Array population size test
6 * Copyright 2012 - Mathieu Desnoyers <mathieu.desnoyers@efficios.com>
8 * This library is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * This library is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with this library; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
24 * This program generates random populations, and shows the largest
25 * sub-class generated, as well as the distribution of sub-class size
26 * for the largest sub-class of each population.
36 static int sel_pool_len
= 50; /* default */
37 static int nr_distrib
= 2; /* default */
38 //#define SEL_POOL_LEN 100
39 //#define NR_POOLS 10000000ULL
41 static uint8_t pool
[256];
42 static uint8_t nr_one
[8];
43 static uint8_t nr_2d_11
[8][8];
44 static uint8_t nr_2d_10
[8][8];
45 static int global_max_minsubclass_len
= 0;
47 static unsigned int subclass_len_distrib
[256];
50 uint8_t random_char(void)
52 return (uint8_t) random();
61 for (i
= 0; i
< sel_pool_len
; i
++) {
62 printf("%d ", (int) pool
[i
]);
70 uint8_t src_pool
[256];
74 memset(pool
, 0, sizeof(pool
));
75 for (i
= 0; i
< 256; i
++)
76 src_pool
[i
] = (uint8_t) i
;
77 for (i
= 0; i
< sel_pool_len
; i
++) {
80 sel
= random_char() % nr_left
;
81 pool
[i
] = src_pool
[sel
];
82 src_pool
[sel
] = src_pool
[nr_left
- 1];
92 memset(nr_one
, 0, sizeof(nr_one
));
93 memset(nr_2d_11
, 0, sizeof(nr_2d_11
));
94 memset(nr_2d_10
, 0, sizeof(nr_2d_10
));
95 for (i
= 0; i
< sel_pool_len
; i
++) {
96 if (nr_distrib
== 2) {
99 for (j
= 0; j
< 8; j
++) {
100 if (pool
[i
] & (1U << j
))
105 if (nr_distrib
== 4) {
108 for (j
= 0; j
< 8; j
++) {
109 for (k
= 0; k
< j
; k
++) {
110 if ((pool
[i
] & (1U << j
)) && (pool
[i
] & (1U << k
))) {
113 if ((pool
[i
] & (1U << j
)) && !(pool
[i
] & (1U << k
))) {
123 void print_count(void)
127 printf("pool distribution:\n");
129 if (nr_distrib
== 2) {
131 printf("----------\n");
132 for (i
= 0; i
< 8; i
++) {
134 sel_pool_len
- nr_one
[i
], nr_one
[i
]);
138 if (nr_distrib
== 4) {
145 void stat_count(void)
147 int minsubclass_len
= INT_MAX
;
149 if (nr_distrib
== 2) {
152 for (i
= 0; i
< 8; i
++) {
155 diff
= (int) nr_one
[i
] * 2 - sel_pool_len
;
158 if ((diff
>> 1) < minsubclass_len
) {
159 minsubclass_len
= diff
>> 1;
164 if (nr_distrib
== 4) {
167 for (j
= 0; j
< 8; j
++) {
168 for (k
= 0; k
< j
; k
++) {
171 diff
[0] = (int) nr_2d_11
[j
][k
] * 4 - sel_pool_len
;
175 diff
[1] = (int) nr_2d_10
[j
][k
] * 4 - sel_pool_len
;
178 /* Get max linear array size */
179 if (diff
[1] > diff
[0])
181 if ((diff
[0] >> 2) < minsubclass_len
) {
182 minsubclass_len
= diff
[0] >> 2;
188 if (minsubclass_len
> global_max_minsubclass_len
) {
189 global_max_minsubclass_len
= minsubclass_len
;
191 subclass_len_distrib
[minsubclass_len
]++;
195 void print_distrib(void)
198 unsigned long long tot
= 0;
200 for (i
= 0; i
< 256; i
++) {
201 tot
+= subclass_len_distrib
[i
];
205 printf("Distribution:\n");
206 for (i
= 0; i
< 256; i
++) {
207 printf("(%u, %u, %llu%%) ",
208 i
, subclass_len_distrib
[i
],
209 100 * (unsigned long long) subclass_len_distrib
[i
] / tot
);
215 void print_stat(uint64_t i
)
217 printf("after %llu pools, global_max_minsubclass_len extra: %d\n",
218 (unsigned long long) i
, global_max_minsubclass_len
);
222 int main(int argc
, char **argv
)
229 sel_pool_len
= atoi(argv
[1]);
230 if (sel_pool_len
> 256 || sel_pool_len
< 1) {
231 printf("Wrong pool len\n");
235 printf("pool len: %d\n", sel_pool_len
);
238 nr_distrib
= atoi(argv
[2]);
239 if (nr_distrib
> 256 || nr_distrib
< 1) {
240 printf("Wrong number of distributions\n");
244 printf("pool distributions: %d\n", nr_distrib
);
246 if (nr_distrib
!= 2 && nr_distrib
!= 4) {
247 printf("Wrong number of distributions. Only 2 and 4 supported.\n");
251 //for (i = 0; i < NR_POOLS; i++) {
258 if (!(i
% 100000ULL))