1 /* SPDX-License-Identifier: GPL-2.0-only */
2 /*
3 * tools/testing/selftests/kvm/include/sparsebit.h
4 *
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 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
16 #ifndef SELFTEST_KVM_SPARSEBIT_H
17 #define SELFTEST_KVM_SPARSEBIT_H
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);
33 void sparsebit_copy(struct sparsebit *dstp, const struct sparsebit *src);
34
35 bool sparsebit_is_set(const struct sparsebit *sbit, sparsebit_idx_t idx);
36 bool sparsebit_is_set_num(const struct sparsebit *sbit,
37 sparsebit_idx_t idx, sparsebit_num_t num);
38 bool sparsebit_is_clear(const struct sparsebit *sbit, sparsebit_idx_t idx);
39 bool sparsebit_is_clear_num(const struct sparsebit *sbit,
40 sparsebit_idx_t idx, sparsebit_num_t num);
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,
51 sparsebit_idx_t start, sparsebit_num_t num);
52 sparsebit_idx_t sparsebit_next_clear_num(const struct sparsebit *sbit,
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
65 void sparsebit_dump(FILE *stream, const struct sparsebit *sbit,
66 unsigned int indent);
67 void 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 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
89 #ifdef __cplusplus
90 }
91 #endif
92
93 #endif /* SELFTEST_KVM_SPARSEBIT_H */
94
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.