randperm.c

Absolute File Name:

/home/opencoverage/opencoverage/guest-scripts/coreutils/src/gl/lib/randperm.c

Line

Source

Count

/* Generate random permutations.

This program is free software: you can redistribute it and/or modify

it under the terms of the GNU General Public License as published by

the Free Software Foundation, either version 3 of the License, or

(at your option) any later version.

This program is distributed in the hope that it will be useful,

but WITHOUT ANY WARRANTY; without even the implied warranty of

MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the

GNU General Public License for more details.

You should have received a copy of the GNU General Public License

along with this program. If not, see <https://www.gnu.org/licenses/>. */

/* Written by Paul Eggert. */

#include <config.h>

#include "hash.h"

#include "randperm.h"

#include <limits.h>

#include <stdlib.h>

#include "xalloc.h"

/* Return the ceiling of the log base 2 of N. If N is zero, return

an unspecified value. */

static size_t _GL_ATTRIBUTE_CONST

ceil_lg (size_t n)

{

size_t b = 0;

for (n--; n != 0; n /= 2)

n != 0	Description
TRUE	evaluated 172 times by 1 test Evaluated by: shuf
FALSE	evaluated 13 times by 1 test Evaluated by: shuf

13-172

b++;

executed 172 times by 1 test: b++;

Executed by:

shuf

172

return b;

executed 13 times by 1 test: return b;

Executed by:

shuf

}

/* Return an upper bound on the number of random bytes needed to

generate the first H elements of a random permutation of N

elements. H must not exceed N. */

size_t

randperm_bound (size_t h, size_t n)

{

/* Upper bound on number of bits needed to generate the first number

of the permutation. */

size_t lg_n = ceil_lg (n);

/* Upper bound on number of bits needed to generated the first H elements. */

size_t ar = lg_n * h;

/* Convert the bit count to a byte count. */

size_t bound = (ar + CHAR_BIT - 1) / CHAR_BIT;

return bound;

executed 13 times by 1 test: return bound;

Executed by:

shuf

}

/* Swap elements I and J in array V. */

static void

swap (size_t *v, size_t i, size_t j)

{

size_t t = v[i];

v[i] = v[j];

v[j] = t;

}

executed 2104 times by 1 test: end of block

Executed by:

shuf

2104

/* Structures and functions for a sparse_map abstract data type that's

used to effectively swap elements I and J in array V like swap(),

but in a more memory efficient manner (when the number of permutations

performed is significantly less than the size of the input). */

struct sparse_ent_

{

size_t index;

size_t val;

};

static size_t

sparse_hash_ (void const *x, size_t table_size)

{

struct sparse_ent_ const *ent = x;

return ent->index % table_size;

executed 8 times by 1 test: return ent->index % table_size;

Executed by:

shuf

}

static bool

sparse_cmp_ (void const *x, void const *y)

{

struct sparse_ent_ const *ent1 = x;

struct sparse_ent_ const *ent2 = y;

return ent1->index == ent2->index;

executed 2 times by 1 test: return ent1->index == ent2->index;

Executed by:

shuf

}

typedef Hash_table sparse_map;

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

104

static sparse_map *

105

sparse_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

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

114

static void

115

sparse_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)

!v1	Description
TRUE	evaluated 2 times by 1 test Evaluated by: shuf
FALSE	never 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

126

if (!v2)

!v2	Description
TRUE	evaluated 2 times by 1 test Evaluated by: shuf
FALSE	never 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

size_t t = v1->val;

v1->val = v2->val;

v2->val = t;

if (!hash_insert (sv, v1))

!hash_insert (sv, v1)	Description
TRUE	never evaluated
FALSE	evaluated 2 times by 1 test Evaluated by: shuf

0-2

136

xalloc_die ();

never executed: xalloc_die ();

137

if (!hash_insert (sv, v2))

!hash_insert (sv, v2)	Description
TRUE	never evaluated
FALSE	evaluated 2 times by 1 test Evaluated by: shuf

0-2

138

xalloc_die ();

never executed: xalloc_die ();

139

140

v[i] = v1->val;

141

}

executed 2 times by 1 test: end of block

Executed by:

shuf

142

143

static void

144

sparse_free (sparse_map *sv)

145

{

146

hash_free (sv);

147

}

executed 1 time by 1 test: end of block

Executed by:

shuf

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

154

size_t *

155

randperm_new (struct randint_source *r, size_t h, size_t n)

{

size_t *v;

switch (h)

{

case 0:

executed 2 times by 1 test: case 0:

Executed by:

shuf

162

v = NULL;

163

break;

executed 2 times by 1 test: break;

Executed by:

shuf

164

165

case 1:

executed 3 times by 1 test: case 1:

Executed by:

shuf

166

v = xmalloc (sizeof *v);

167

v[0] = randint_choose (r, n);

168

break;

executed 3 times by 1 test: break;

Executed by:

shuf

169

170

default:

executed 9 times by 1 test: default:

Executed by:

shuf

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

done

done

done

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
TRUE	evaluated 1 time by 1 test Evaluated by: shuf
FALSE	evaluated 8 times by 1 test Evaluated by: shuf

(n / h >= 32)	Description
TRUE	evaluated 1 time by 1 test Evaluated by: shuf
FALSE	never evaluated

0-8

size_t i;

sparse_map *sv;

if (sparse)

sparse	Description
TRUE	evaluated 1 time by 1 test Evaluated by: shuf
FALSE	evaluated 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
TRUE	never evaluated
FALSE	evaluated 1 time by 1 test Evaluated by: shuf

0-1

208

xalloc_die ();

never executed: xalloc_die ();

209

v = xnmalloc (h, sizeof *v);

210

}

executed 1 time by 1 test: end of block

Executed by:

shuf

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 < n	Description
TRUE	evaluated 2111 times by 1 test Evaluated by: shuf
FALSE	evaluated 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

218

219

for (i = 0; i < h; i++)

i < h	Description
TRUE	evaluated 2106 times by 1 test Evaluated by: shuf
FALSE	evaluated 9 times by 1 test Evaluated by: shuf

9-2106

220

{

221

size_t j = i + randint_choose (r, n - i);

222

if (sparse)

sparse	Description
TRUE	evaluated 2 times by 1 test Evaluated by: shuf
FALSE	evaluated 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

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)

sparse	Description
TRUE	evaluated 1 time by 1 test Evaluated by: shuf
FALSE	evaluated 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

230

else

231

v = xnrealloc (v, h, sizeof *v);

executed 8 times by 1 test: v = xnrealloc (v, h, sizeof *v);

Executed by:

shuf

232

}

233

break;

executed 9 times by 1 test: break;

Executed by:

shuf

234

}

235

236

return v;

executed 14 times by 1 test: return v;

Executed by:

shuf

237

}

Generated by Squish Coco 4.1.2