random_order.h File Reference

(69c572b)

Functions for generating random traversal orders. More...

#include <stddef.h>

Go to the source code of this file.

Data Structures
struct	random_order
	Context for a random traversal order. More...

Typedefs
typedef struct random_order	random_order_t
	Context for a random traversal order. More...

Functions
void	random_order_init (random_order_t *ctx, size_t min_len)
	Constructs a new, randomly-seeded traversal order, running from 0 to at least min_len. More...
size_t	random_order_len (const random_order_t *ctx)
	Returns the length of the sequence represented by ctx. More...
size_t	random_order_advance (random_order_t *ctx)
	Returns the next element in the sequence represented by ctx. More...

Detailed Description

Functions for generating random traversal orders.

Definition in file random_order.h.

---

Data Structure Documentation

random_order

struct random_order

Context for a random traversal order.

A "random traversal order" specifies a random order to walk through some buffer of length n, which is an important building block for constant-power code. Given n, the random order emits integers in the range 0..m, where m is an implementation-defined, per-random-order value greater than n. The order is guaranteed to visit each integer in 0..n at least once, but with some caveats:

• Values greater than n may be returned.
• The same value may be returned multiple times.

Users must be mindful of these constraints when using random_order_t. These caveats are intended to allow for implementation flexibility, such as intentionally adding decoys to the sequence.

Definition at line 35 of file random_order.h.

Data Fields
size_t	max
size_t	state

Typedef Documentation

random_order_t

typedef struct random_order random_order_t

Context for a random traversal order.

A "random traversal order" specifies a random order to walk through some buffer of length n, which is an important building block for constant-power code. Given n, the random order emits integers in the range 0..m, where m is an implementation-defined, per-random-order value greater than n. The order is guaranteed to visit each integer in 0..n at least once, but with some caveats:

• Values greater than n may be returned.
• The same value may be returned multiple times.

Users must be mindful of these constraints when using random_order_t. These caveats are intended to allow for implementation flexibility, such as intentionally adding decoys to the sequence.

Function Documentation

random_order_advance()

size_t random_order_advance

(

random_order_t *

ctx

)

Returns the next element in the sequence represented by ctx.

See random_order_len() for discovering how many times this function can be called.

Parameters

ctx	The context to advance.

Returns

The next value in the sequence.

Definition at line 19 of file random_order.c.

random_order_init()

void random_order_init	(	random_order_t *	ctx,
		size_t	min_len
	)

Constructs a new, randomly-seeded traversal order, running from 0 to at least min_len.

This function does not take a seed as input; instead, the seed is extracted, in some manner or another, from the hardware by this function.

Parameters

ctx	The context to initialize.
min_len	The minimum length this traversal order must visit.

Definition at line 12 of file random_order.c.

random_order_len()

size_t random_order_len

(

const random_order_t *

ctx

)

Returns the length of the sequence represented by ctx.

This value may be greater than min_len specified in random_order_init(), but the sequence is guaranteed to contain every integer in 0..min_len.

This value represents the number of times random_order_advance() may be called.

Parameters

ctx	The context to query.

Returns

The length of the sequence.

Definition at line 17 of file random_order.c.