OpenCoverage

randperm.c

Absolute File Name:/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/randperm.c
Source codeSwitch to Preprocessed file
LineSourceCount
1/* Generate random permutations.-
2-
3 Copyright (C) 2006-2018 Free Software Foundation, Inc.-
4-
5 This program is free software: you can redistribute it and/or modify-
6 it under the terms of the GNU General Public License as published by-
7 the Free Software Foundation, either version 3 of the License, or-
8 (at your option) any later version.-
9-
10 This program is distributed in the hope that it will be useful,-
11 but WITHOUT ANY WARRANTY; without even the implied warranty of-
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the-
13 GNU General Public License for more details.-
14-
15 You should have received a copy of the GNU General Public License-
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */-
17-
18/* Written by Paul Eggert. */-
19-
20#include <config.h>-
21-
22#include "hash.h"-
23#include "randperm.h"-
24-
25#include <limits.h>-
26#include <stdlib.h>-
27-
28#include "xalloc.h"-
29-
30/* Return the ceiling of the log base 2 of N. If N is zero, return-
31 an unspecified value. */-
32-
33static size_t _GL_ATTRIBUTE_CONST-
34ceil_lg (size_t n)-
35{-
36 size_t b = 0;-
37 for (n--; n != 0; n /= 2)
n != 0Description
TRUEevaluated 172 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 13 times by 1 test
Evaluated by:
  • shuf
13-172
38 b++;
executed 172 times by 1 test: b++;
Executed by:
  • shuf
172
39 return b;
executed 13 times by 1 test: return b;
Executed by:
  • shuf
13
40}-
41-
42/* Return an upper bound on the number of random bytes needed to-
43 generate the first H elements of a random permutation of N-
44 elements. H must not exceed N. */-
45-
46size_t-
47randperm_bound (size_t h, size_t n)-
48{-
49 /* Upper bound on number of bits needed to generate the first number-
50 of the permutation. */-
51 size_t lg_n = ceil_lg (n);-
52-
53 /* Upper bound on number of bits needed to generated the first H elements. */-
54 size_t ar = lg_n * h;-
55-
56 /* Convert the bit count to a byte count. */-
57 size_t bound = (ar + CHAR_BIT - 1) / CHAR_BIT;-
58-
59 return bound;
executed 13 times by 1 test: return bound;
Executed by:
  • shuf
13
60}-
61-
62/* Swap elements I and J in array V. */-
63-
64static void-
65swap (size_t *v, size_t i, size_t j)-
66{-
67 size_t t = v[i];-
68 v[i] = v[j];-
69 v[j] = t;-
70}
executed 2104 times by 1 test: end of block
Executed by:
  • shuf
2104
71-
72/* Structures and functions for a sparse_map abstract data type that's-
73 used to effectively swap elements I and J in array V like swap(),-
74 but in a more memory efficient manner (when the number of permutations-
75 performed is significantly less than the size of the input). */-
76-
77struct sparse_ent_-
78{-
79 size_t index;-
80 size_t val;-
81};-
82-
83static size_t-
84sparse_hash_ (void const *x, size_t table_size)-
85{-
86 struct sparse_ent_ const *ent = x;-
87 return ent->index % table_size;
executed 8 times by 1 test: return ent->index % table_size;
Executed by:
  • shuf
8
88}-
89-
90static bool-
91sparse_cmp_ (void const *x, void const *y)-
92{-
93 struct sparse_ent_ const *ent1 = x;-
94 struct sparse_ent_ const *ent2 = y;-
95 return ent1->index == ent2->index;
executed 2 times by 1 test: return ent1->index == ent2->index;
Executed by:
  • shuf
2
96}-
97-
98typedef Hash_table sparse_map;-
99-
100/* Initialize the structure for the sparse map,-
101 when a best guess as to the number of entries-
102 specified with SIZE_HINT. */-
103-
104static sparse_map *-
105sparse_new (size_t size_hint)-
106{-
107 return hash_initialize (size_hint, NULL, 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
108}-
109-
110/* Swap the values for I and J. If a value is not already present-
111 then assume it's equal to the index. Update the value for-
112 index I in array V. */-
113-
114static void-
115sparse_swap (sparse_map *sv, size_t* v, size_t i, size_t j)-
116{-
117 struct sparse_ent_ *v1 = hash_delete (sv, &(struct sparse_ent_) {i,0});-
118 struct sparse_ent_ *v2 = hash_delete (sv, &(struct sparse_ent_) {j,0});-
119-
120 /* FIXME: reduce the frequency of these mallocs. */-
121 if (!v1)
!v1Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • shuf
FALSEnever evaluated
0-2
122 {-
123 v1 = xmalloc (sizeof *v1);-
124 v1->index = v1->val = i;-
125 }
executed 2 times by 1 test: end of block
Executed by:
  • shuf
2
126 if (!v2)
!v2Description
TRUEevaluated 2 times by 1 test
Evaluated by:
  • shuf
FALSEnever evaluated
0-2
127 {-
128 v2 = xmalloc (sizeof *v2);-
129 v2->index = v2->val = j;-
130 }
executed 2 times by 1 test: end of block
Executed by:
  • shuf
2
131-
132 size_t t = v1->val;-
133 v1->val = v2->val;-
134 v2->val = t;-
135 if (!hash_insert (sv, v1))
!hash_insert (sv, v1)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • shuf
0-2
136 xalloc_die ();
never executed: xalloc_die ();
0
137 if (!hash_insert (sv, v2))
!hash_insert (sv, v2)Description
TRUEnever evaluated
FALSEevaluated 2 times by 1 test
Evaluated by:
  • shuf
0-2
138 xalloc_die ();
never executed: xalloc_die ();
0
139-
140 v[i] = v1->val;-
141}
executed 2 times by 1 test: end of block
Executed by:
  • shuf
2
142-
143static void-
144sparse_free (sparse_map *sv)-
145{-
146 hash_free (sv);-
147}
executed 1 time by 1 test: end of block
Executed by:
  • shuf
1
148-
149-
150/* From R, allocate and return a malloc'd array of the first H elements-
151 of a random permutation of N elements. H must not exceed N.-
152 Return NULL if H is zero. */-
153-
154size_t *-
155randperm_new (struct randint_source *r, size_t h, size_t n)-
156{-
157 size_t *v;-
158-
159 switch (h)-
160 {-
161 case 0:
executed 2 times by 1 test: case 0:
Executed by:
  • shuf
2
162 v = NULL;-
163 break;
executed 2 times by 1 test: break;
Executed by:
  • shuf
2
164-
165 case 1:
executed 3 times by 1 test: case 1:
Executed by:
  • shuf
3
166 v = xmalloc (sizeof *v);-
167 v[0] = randint_choose (r, n);-
168 break;
executed 3 times by 1 test: break;
Executed by:
  • shuf
3
169-
170 default:
executed 9 times by 1 test: default:
Executed by:
  • shuf
9
171 {-
172 /* The algorithm is essentially the same in both-
173 the sparse and non sparse case. In the sparse case we use-
174 a hash to implement sparse storage for the set of n numbers-
175 we're shuffling. When to use the sparse method was-
176 determined with the help of this script:-
177-
178 #!/bin/sh-
179 for n in $(seq 2 32); do-
180 for h in $(seq 2 32); do-
181 test $h -gt $n && continue-
182 for s in o n; do-
183 test $s = o && shuf=shuf || shuf=./shuf-
184 num=$(env time -f "$s:${h},${n} = %e,%M" \-
185 $shuf -i0-$((2**$n-2)) -n$((2**$h-2)) | wc -l)-
186 test $num = $((2**$h-2)) || echo "$s:${h},${n} = failed" >&2-
187 done-
188 done-
189 done-
190-
191 This showed that if sparseness = n/h, then:-
192-
193 sparseness = 128 => .125 mem used, and about same speed-
194 sparseness = 64 => .25 mem used, but 1.5 times slower-
195 sparseness = 32 => .5 mem used, but 2 times slower-
196-
197 Also the memory usage was only significant when n > 128Ki-
198 */-
199 bool sparse = (n >= (128 * 1024)) && (n / h >= 32);
(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
0-8
200-
201 size_t i;-
202 sparse_map *sv;-
203-
204 if (sparse)
sparseDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
1-8
205 {-
206 sv = sparse_new (h * 2);-
207 if (sv == NULL)
sv == ((void *)0)Description
TRUEnever evaluated
FALSEevaluated 1 time by 1 test
Evaluated by:
  • shuf
0-1
208 xalloc_die ();
never executed: xalloc_die ();
0
209 v = xnmalloc (h, sizeof *v);-
210 }
executed 1 time by 1 test: end of block
Executed by:
  • shuf
1
211 else-
212 {-
213 sv = NULL; /* To placate GCC's -Wuninitialized. */-
214 v = xnmalloc (n, sizeof *v);-
215 for (i = 0; i < n; i++)
i < nDescription
TRUEevaluated 2111 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
8-2111
216 v[i] = i;
executed 2111 times by 1 test: v[i] = i;
Executed by:
  • shuf
2111
217 }
executed 8 times by 1 test: end of block
Executed by:
  • shuf
8
218-
219 for (i = 0; i < h; i++)
i < hDescription
TRUEevaluated 2106 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 9 times by 1 test
Evaluated by:
  • shuf
9-2106
220 {-
221 size_t j = i + randint_choose (r, n - i);-
222 if (sparse)
sparseDescription
TRUEevaluated 2 times by 1 test
Evaluated by:
  • shuf
FALSEevaluated 2104 times by 1 test
Evaluated by:
  • shuf
2-2104
223 sparse_swap (sv, v, i, j);
executed 2 times by 1 test: sparse_swap (sv, v, i, j);
Executed by:
  • shuf
2
224 else-
225 swap (v, i, j);
executed 2104 times by 1 test: swap (v, i, j);
Executed by:
  • shuf
2104
226 }-
227-
228 if (sparse)
sparseDescription
TRUEevaluated 1 time by 1 test
Evaluated by:
  • shuf
FALSEevaluated 8 times by 1 test
Evaluated by:
  • shuf
1-8
229 sparse_free (sv);
executed 1 time by 1 test: sparse_free (sv);
Executed by:
  • shuf
1
230 else-
231 v = xnrealloc (v, h, sizeof *v);
executed 8 times by 1 test: v = xnrealloc (v, h, sizeof *v);
Executed by:
  • shuf
8
232 }-
233 break;
executed 9 times by 1 test: break;
Executed by:
  • shuf
9
234 }-
235-
236 return v;
executed 14 times by 1 test: return v;
Executed by:
  • shuf
14
237}-
Source codeSwitch to Preprocessed file

Generated by Squish Coco 4.1.2