94 lines · c
1/* SPDX-License-Identifier: GPL-2.0-only */2/*3 * tools/testing/selftests/kvm/include/sparsebit.h4 *5 * Copyright (C) 2018, Google LLC.6 *7 * Header file that describes API to the sparsebit library.8 * This library provides a memory efficient means of storing9 * the settings of bits indexed via a uint64_t. Memory usage10 * is reasonable, significantly less than (2^64 / 8) bytes, as11 * long as bits that are mostly set or mostly cleared are close12 * to each other. This library is efficient in memory usage13 * even in the case where most bits are set.14 */15 16#ifndef SELFTEST_KVM_SPARSEBIT_H17#define SELFTEST_KVM_SPARSEBIT_H18 19#include <stdbool.h>20#include <stdint.h>21#include <stdio.h>22 23#ifdef __cplusplus24extern "C" {25#endif26 27struct sparsebit;28typedef uint64_t sparsebit_idx_t;29typedef uint64_t sparsebit_num_t;30 31struct sparsebit *sparsebit_alloc(void);32void sparsebit_free(struct sparsebit **sbitp);33void sparsebit_copy(struct sparsebit *dstp, const struct sparsebit *src);34 35bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx);36bool sparsebit_is_set_num(const struct sparsebit *sbit,37 sparsebit_idx_t idx, sparsebit_num_t num);38bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx);39bool sparsebit_is_clear_num(const struct sparsebit *sbit,40 sparsebit_idx_t idx, sparsebit_num_t num);41sparsebit_num_t sparsebit_num_set(const struct sparsebit *sbit);42bool sparsebit_any_set(const struct sparsebit *sbit);43bool sparsebit_any_clear(const struct sparsebit *sbit);44bool sparsebit_all_set(const struct sparsebit *sbit);45bool sparsebit_all_clear(const struct sparsebit *sbit);46sparsebit_idx_t sparsebit_first_set(const struct sparsebit *sbit);47sparsebit_idx_t sparsebit_first_clear(const struct sparsebit *sbit);48sparsebit_idx_t sparsebit_next_set(const struct sparsebit *sbit, sparsebit_idx_t prev);49sparsebit_idx_t sparsebit_next_clear(const struct sparsebit *sbit, sparsebit_idx_t prev);50sparsebit_idx_t sparsebit_next_set_num(const struct sparsebit *sbit,51 sparsebit_idx_t start, sparsebit_num_t num);52sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit,53 sparsebit_idx_t start, sparsebit_num_t num);54 55void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx);56void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start,57 sparsebit_num_t num);58void sparsebit_set_all(struct sparsebit *sbitp);59 60void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx);61void sparsebit_clear_num(struct sparsebit *sbitp,62 sparsebit_idx_t start, sparsebit_num_t num);63void sparsebit_clear_all(struct sparsebit *sbitp);64 65void sparsebit_dump(FILE *stream, const struct sparsebit *sbit,66 unsigned int indent);67void sparsebit_validate_internal(const struct sparsebit *sbit);68 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 set72 * range, which are of type sparsebit_idx_t.73 *74 * For example, if the range [3, 7] (inclusive) is set, within the75 * iteration,@range_begin will take the value 3 and @range_end will take76 * the value 7.77 *78 * Ensure that there is at least one bit set before using this macro with79 * sparsebit_any_set(), because sparsebit_first_set() will abort if none80 * 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 89#ifdef __cplusplus90}91#endif92 93#endif /* SELFTEST_KVM_SPARSEBIT_H */94