[linux-2.6-block.git] / tools / testing / selftests / kvm / include / sparsebit.h

/* SPDX-License-Identifier: GPL-2.0-only */
/*
 * tools/testing/selftests/kvm/include/sparsebit.h
 *
 * Copyright (C) 2018, Google LLC.
 *
 * Header file that describes API to the sparsebit library.
 * This library provides a memory efficient means of storing
 * the settings of bits indexed via a uint64_t.  Memory usage
 * is reasonable, significantly less than (2^64 / 8) bytes, as
 * long as bits that are mostly set or mostly cleared are close
 * to each other.  This library is efficient in memory usage
 * even in the case where most bits are set.
 */

#ifndef SELFTEST_KVM_SPARSEBIT_H
#define SELFTEST_KVM_SPARSEBIT_H

#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>

#ifdef __cplusplus
extern "C" {
#endif

struct sparsebit;
typedef uint64_t sparsebit_idx_t;
typedef uint64_t sparsebit_num_t;

struct sparsebit *sparsebit_alloc(void);
void sparsebit_free(struct sparsebit **sbitp);
void sparsebit_copy(struct sparsebit *dstp, const struct sparsebit *src);

bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx);
bool sparsebit_is_set_num(const struct sparsebit *sbit,
			  sparsebit_idx_t idx, sparsebit_num_t num);
bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx);
bool sparsebit_is_clear_num(const struct sparsebit *sbit,
			    sparsebit_idx_t idx, sparsebit_num_t num);
sparsebit_num_t sparsebit_num_set(const struct sparsebit *sbit);
bool sparsebit_any_set(const struct sparsebit *sbit);
bool sparsebit_any_clear(const struct sparsebit *sbit);
bool sparsebit_all_set(const struct sparsebit *sbit);
bool sparsebit_all_clear(const struct sparsebit *sbit);
sparsebit_idx_t sparsebit_first_set(const struct sparsebit *sbit);
sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *sbit);
sparsebit_idx_t sparsebit_next_set(const struct sparsebit *sbit, sparsebit_idx_t prev);
sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *sbit, sparsebit_idx_t prev);
sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *sbit,
				       sparsebit_idx_t start, sparsebit_num_t num);
sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit,
					 sparsebit_idx_t start, sparsebit_num_t num);

void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx);
void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start,
		       sparsebit_num_t num);
void sparsebit_set_all(struct sparsebit *sbitp);

void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx);
void sparsebit_clear_num(struct sparsebit *sbitp,
			 sparsebit_idx_t start, sparsebit_num_t num);
void sparsebit_clear_all(struct sparsebit *sbitp);

void sparsebit_dump(FILE *stream, const struct sparsebit *sbit,
		    unsigned int indent);
void sparsebit_validate_internal(const struct sparsebit *sbit);

/*
 * Iterate over an inclusive ranges within sparsebit @s. In each iteration,
 * @range_begin and @range_end will take the beginning and end of the set
 * range, which are of type sparsebit_idx_t.
 *
 * For example, if the range [3, 7] (inclusive) is set, within the
 * iteration,@range_begin will take the value 3 and @range_end will take
 * the value 7.
 *
 * Ensure that there is at least one bit set before using this macro with
 * sparsebit_any_set(), because sparsebit_first_set() will abort if none
 * are set.
 */
#define sparsebit_for_each_set_range(s, range_begin, range_end)         \
	for (range_begin = sparsebit_first_set(s),                      \
	     range_end = sparsebit_next_clear(s, range_begin) - 1;	\
	     range_begin && range_end;                                  \
	     range_begin = sparsebit_next_set(s, range_end),            \
	     range_end = sparsebit_next_clear(s, range_begin) - 1)

#ifdef __cplusplus
}
#endif

#endif /* SELFTEST_KVM_SPARSEBIT_H */
Commit	Line	Data
7a338472	1	/* SPDX-License-Identifier: GPL-2.0-only */
783e9e51 PB	2	/*
	3	* tools/testing/selftests/kvm/include/sparsebit.h
	4	*
	5	* Copyright (C) 2018, Google LLC.
	6	*
783e9e51 PB	7	* Header file that describes API to the sparsebit library.
	8	* This library provides a memory efficient means of storing
	9	* the settings of bits indexed via a uint64_t. Memory usage
	10	* is reasonable, significantly less than (2^64 / 8) bytes, as
	11	* long as bits that are mostly set or mostly cleared are close
	12	* to each other. This library is efficient in memory usage
	13	* even in the case where most bits are set.
	14	*/
	15
cc68765d AJ	16	#ifndef SELFTEST_KVM_SPARSEBIT_H
cc68765d AJ	17	#define SELFTEST_KVM_SPARSEBIT_H
783e9e51 PB	18
	19	#include <stdbool.h>
	20	#include <stdint.h>
	21	#include <stdio.h>
	22
	23	#ifdef __cplusplus
	24	extern "C" {
	25	#endif
	26
	27	struct sparsebit;
	28	typedef uint64_t sparsebit_idx_t;
	29	typedef uint64_t sparsebit_num_t;
	30
	31	struct sparsebit *sparsebit_alloc(void);
	32	void sparsebit_free(struct sparsebit **sbitp);
35f50c91	33	void sparsebit_copy(struct sparsebit dstp, const struct sparsebit src);
783e9e51	34
35f50c91 MR	35	bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx);
35f50c91 MR	36	bool sparsebit_is_set_num(const struct sparsebit *sbit,
783e9e51	37	sparsebit_idx_t idx, sparsebit_num_t num);
35f50c91 MR	38	bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx);
35f50c91 MR	39	bool sparsebit_is_clear_num(const struct sparsebit *sbit,
783e9e51	40	sparsebit_idx_t idx, sparsebit_num_t num);
35f50c91 MR	41	sparsebit_num_t sparsebit_num_set(const struct sparsebit *sbit);
	42	bool sparsebit_any_set(const struct sparsebit *sbit);
	43	bool sparsebit_any_clear(const struct sparsebit *sbit);
	44	bool sparsebit_all_set(const struct sparsebit *sbit);
	45	bool sparsebit_all_clear(const struct sparsebit *sbit);
	46	sparsebit_idx_t sparsebit_first_set(const struct sparsebit *sbit);
	47	sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *sbit);
	48	sparsebit_idx_t sparsebit_next_set(const struct sparsebit *sbit, sparsebit_idx_t prev);
	49	sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *sbit, sparsebit_idx_t prev);
	50	sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *sbit,
783e9e51	51	sparsebit_idx_t start, sparsebit_num_t num);
35f50c91	52	sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit,
783e9e51 PB	53	sparsebit_idx_t start, sparsebit_num_t num);
	54
	55	void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx);
	56	void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start,
	57	sparsebit_num_t num);
	58	void sparsebit_set_all(struct sparsebit *sbitp);
	59
	60	void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx);
	61	void sparsebit_clear_num(struct sparsebit *sbitp,
	62	sparsebit_idx_t start, sparsebit_num_t num);
	63	void sparsebit_clear_all(struct sparsebit *sbitp);
	64
35f50c91	65	void sparsebit_dump(FILE stream, const struct sparsebit sbit,
783e9e51	66	unsigned int indent);
35f50c91	67	void sparsebit_validate_internal(const struct sparsebit *sbit);
783e9e51	68
57e19f05 AT	69	/*
	70	* Iterate over an inclusive ranges within sparsebit @s. In each iteration,
	71	* @range_begin and @range_end will take the beginning and end of the set
	72	* range, which are of type sparsebit_idx_t.
	73	*
	74	* For example, if the range [3, 7] (inclusive) is set, within the
	75	* iteration,@range_begin will take the value 3 and @range_end will take
	76	* the value 7.
	77	*
	78	* Ensure that there is at least one bit set before using this macro with
	79	* sparsebit_any_set(), because sparsebit_first_set() will abort if none
	80	* are set.
	81	*/
	82	#define sparsebit_for_each_set_range(s, range_begin, range_end) \
	83	for (range_begin = sparsebit_first_set(s), \
	84	range_end = sparsebit_next_clear(s, range_begin) - 1; \
	85	range_begin && range_end; \
	86	range_begin = sparsebit_next_set(s, range_end), \
	87	range_end = sparsebit_next_clear(s, range_begin) - 1)
	88
783e9e51 PB	89	#ifdef __cplusplus
	90	}
	91	#endif
	92
cc68765d	93	#endif /* SELFTEST_KVM_SPARSEBIT_H */