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