OpenCoverage

randperm.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/randperm.c
Switch to Source codePreprocessed file
LineSourceCount
1-
2-
3-
4-
5-
6-
7-
8-
9static size_t __attribute__ ((__const__))-
10ceil_lg (size_t n)-
11{-
12 size_t b = 0;-
13 for (n--; n != 0
n != 0Description
TRUEevaluated 172 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 13 times by 1 test
Evaluated by:
  • shuf
; n /= 2)		13-172
14 b++;
executed 172 times by 1 test: b++;
Executed by:
  • shuf
172
15 return
executed 13 times by 1 test: return b;
Executed by:
  • shuf
 b;
executed 13 times by 1 test: return b;
Executed by:
  • shuf
13
16}-
17-
18-
19-
20-
21-
22size_t-
23randperm_bound (size_t h, size_t n)-
24{-
25-
26-
27 size_t lg_n = ceil_lg (n);-
28-
29-
30 size_t ar = lg_n * h;-
31-
32-
33 size_t bound = (ar + 8 - 1) / 8;-
34-
35 return
executed 13 times by 1 test: return bound;
Executed by:
  • shuf
 bound;
executed 13 times by 1 test: return bound;
Executed by:
  • shuf
13
36}-
37-
38-
39-
40static void-
41swap (size_t *v, size_t i, size_t j)-
42{-
43 size_t t = v[i];-
44 v[i] = v[j];-
45 v[j] = t;-
46}
executed 2104 times by 1 test: end of block
Executed by:
  • shuf
2104
47-
48-
49-
50-
51-
52-
53struct sparse_ent_-
54{-
55 size_t index;-
56 size_t val;-
57};-
58-
59static size_t-
60sparse_hash_ (void const *x, size_t table_size)-
61{-
62 struct sparse_ent_ const *ent = x;-
63 return
executed 8 times by 1 test: return ent->index % table_size;
Executed by:
  • shuf
 ent->index % table_size;
executed 8 times by 1 test: return ent->index % table_size;
Executed by:
  • shuf
8
64}-
65-
66static -
67 _Bool-
68-
69sparse_cmp_ (void const *x, void const *y)-
70{-
71 struct sparse_ent_ const *ent1 = x;-
72 struct sparse_ent_ const *ent2 = y;-
73 return
executed 2 times by 1 test: return ent1->index == ent2->index;
Executed by:
  • shuf
 ent1->index == ent2->index;
executed 2 times by 1 test: return ent1->index == ent2->index;
Executed by:
  • shuf
2
74}-
75-
76typedef Hash_table sparse_map;-
77-
78-
79-
80-
81-
82static sparse_map *-
83sparse_new (size_t size_hint)-
84{-
85 return
executed 1 time by 1 test: return hash_initialize (size_hint, ((void *)0) , sparse_hash_, sparse_cmp_, free);
Executed by:
  • shuf
 hash_initialize (size_hint,
executed 1 time by 1 test: return hash_initialize (size_hint, ((void *)0) , sparse_hash_, sparse_cmp_, free);
Executed by:
  • shuf
1
86 ((void *)0)
executed 1 time by 1 test: return hash_initialize (size_hint, ((void *)0) , sparse_hash_, sparse_cmp_, free);
Executed by:
  • shuf
1
87 , sparse_hash_, sparse_cmp_, free);
executed 1 time by 1 test: return hash_initialize (size_hint, ((void *)0) , sparse_hash_, sparse_cmp_, free);
Executed by:
  • shuf
1
88}-
89-
90-
91-
92-
93-
94static void-
95sparse_swap (sparse_map *sv, size_t* v, size_t i, size_t j)-
96{-
97 struct sparse_ent_ *v1 = hash_delete (sv, &(struct sparse_ent_) {i,0});-
98 struct sparse_ent_ *v2 = hash_delete (sv, &(struct sparse_ent_) {j,0});-
99-
100-
101 if (!v1
!v1Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • shuf
FALSEnever evaluated
)		0-2
102 {-
103 v1 = xmalloc (sizeof *v1);-
104 v1->index = v1->val = i;-
105 }
executed 2 times by 1 test: end of block
Executed by:
  • shuf
2
106 if (!v2
!v2Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • shuf
FALSEnever evaluated
)		0-2
107 {-
108 v2 = xmalloc (sizeof *v2);-
109 v2->index = v2->val = j;-
110 }
executed 2 times by 1 test: end of block
Executed by:
  • shuf
2
111-
112 size_t t = v1->val;-
113 v1->val = v2->val;-
114 v2->val = t;-
115 if (!hash_insert (sv, v1)
!hash_insert (sv, v1)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • shuf
)		0-2
116 xalloc_die ();
never executed: xalloc_die ();
0
117 if (!hash_insert (sv, v2)
!hash_insert (sv, v2)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • shuf
)		0-2
118 xalloc_die ();
never executed: xalloc_die ();
0
119-
120 v[i] = v1->val;-
121}
executed 2 times by 1 test: end of block
Executed by:
  • shuf
2
122-
123static void-
124sparse_free (sparse_map *sv)-
125{-
126 hash_free (sv);-
127}
executed 1 time by 1 test: end of block
Executed by:
  • shuf
1
128-
129-
130-
131-
132-
133-
134size_t *-
135randperm_new (struct randint_source *r, size_t h, size_t n)-
136{-
137 size_t *v;-
138-
139 switch (h)-
140 {-
141 case
executed 2 times by 1 test: case 0:
Executed by:
  • shuf
 0:
executed 2 times by 1 test: case 0:
Executed by:
  • shuf
2
142 v = -
143 ((void *)0)-
144 ;-
145 break;
executed 2 times by 1 test: break;
Executed by:
  • shuf
2
146-
147 case
executed 3 times by 1 test: case 1:
Executed by:
  • shuf
 1:
executed 3 times by 1 test: case 1:
Executed by:
  • shuf
3
148 v = xmalloc (sizeof *v);-
149 v[0] = randint_choose (r, n);-
150 break;
executed 3 times by 1 test: break;
Executed by:
  • shuf
3
151-
152 default
executed 9 times by 1 test: default:
Executed by:
  • shuf
:
executed 9 times by 1 test: default:
Executed by:
  • shuf
9
153 {-
154 -
155 _Bool -
156 sparse = (
(n >= (128 * 1024))Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
n >= (128 * 1024))
(n >= (128 * 1024))Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
 && (
(n / h >= 32)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEnever evaluated
n / h >= 32)
(n / h >= 32)Description
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEnever evaluated
;		0-8
157-
158 size_t i;-
159 sparse_map *sv;-
160-
161 if (sparse
sparseDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
)		1-8
162 {-
163 sv = sparse_new (h * 2);-
164 if (sv ==
sv == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 1 time by 1 test
Evaluated by:
  • shuf
0-1
165 ((void *)0)
sv == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 1 time by 1 test
Evaluated by:
  • shuf
0-1
166 )-
167 xalloc_die ();
never executed: xalloc_die ();
0
168 v = xnmalloc (h, sizeof *v);-
169 }
executed 1 time by 1 test: end of block
Executed by:
  • shuf
1
170 else-
171 {-
172 sv = -
173 ((void *)0)-
174 ;-
175 v = xnmalloc (n, sizeof *v);-
176 for (i = 0; i < n
i < nDescription
TRUEevaluated 2111 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
; i++)		8-2111
177 v[i] = i;
executed 2111 times by 1 test: v[i] = i;
Executed by:
  • shuf
2111
178 }
executed 8 times by 1 test: end of block
Executed by:
  • shuf
8
179-
180 for (i = 0; i < h
i < hDescription
TRUEevaluated 2106 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 9 times by 1 test
Evaluated by:
  • shuf
; i++)		9-2106
181 {-
182 size_t j = i + randint_choose (r, n - i);-
183 if (sparse
sparseDescription
TRUEevaluated 2 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 2104 times by 1 test
Evaluated by:
  • shuf
)		2-2104
184 sparse_swap (sv, v, i, j);
executed 2 times by 1 test: sparse_swap (sv, v, i, j);
Executed by:
  • shuf
2
185 else-
186 swap (v, i, j);
executed 2104 times by 1 test: swap (v, i, j);
Executed by:
  • shuf
2104
187 }-
188-
189 if (sparse
sparseDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
)		1-8
190 sparse_free (sv);
executed 1 time by 1 test: sparse_free (sv);
Executed by:
  • shuf
1
191 else-
192 v = xnrealloc (v, h, sizeof *v);
executed 8 times by 1 test: v = xnrealloc (v, h, sizeof *v);
Executed by:
  • shuf
8
193 }-
194 break;
executed 9 times by 1 test: break;
Executed by:
  • shuf
9
195 }-
196-
197 return
executed 14 times by 1 test: return v;
Executed by:
  • shuf
 v;
executed 14 times by 1 test: return v;
Executed by:
  • shuf
14
198}-
Switch to Source codePreprocessed file
Generated by Squish Coco 4.1.2