• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 /*
2  * tools/testing/selftests/kvm/include/sparsebit.h
3  *
4  * Copyright (C) 2018, Google LLC.
5  *
6  * This work is licensed under the terms of the GNU GPL, version 2.
7  *
8  *
9  * Header file that describes API to the sparsebit library.
10  * This library provides a memory efficient means of storing
11  * the settings of bits indexed via a uint64_t.  Memory usage
12  * is reasonable, significantly less than (2^64 / 8) bytes, as
13  * long as bits that are mostly set or mostly cleared are close
14  * to each other.  This library is efficient in memory usage
15  * even in the case where most bits are set.
16  */
17 
18 #ifndef SELFTEST_KVM_SPARSEBIT_H
19 #define SELFTEST_KVM_SPARSEBIT_H
20 
21 #include <stdbool.h>
22 #include <stdint.h>
23 #include <stdio.h>
24 
25 #ifdef __cplusplus
26 extern "C" {
27 #endif
28 
29 struct sparsebit;
30 typedef uint64_t sparsebit_idx_t;
31 typedef uint64_t sparsebit_num_t;
32 
33 struct sparsebit *sparsebit_alloc(void);
34 void sparsebit_free(struct sparsebit **sbitp);
35 void sparsebit_copy(struct sparsebit *dstp, struct sparsebit *src);
36 
37 bool sparsebit_is_set(struct sparsebit *sbit, sparsebit_idx_t idx);
38 bool sparsebit_is_set_num(struct sparsebit *sbit,
39 			  sparsebit_idx_t idx, sparsebit_num_t num);
40 bool sparsebit_is_clear(struct sparsebit *sbit, sparsebit_idx_t idx);
41 bool sparsebit_is_clear_num(struct sparsebit *sbit,
42 			    sparsebit_idx_t idx, sparsebit_num_t num);
43 sparsebit_num_t sparsebit_num_set(struct sparsebit *sbit);
44 bool sparsebit_any_set(struct sparsebit *sbit);
45 bool sparsebit_any_clear(struct sparsebit *sbit);
46 bool sparsebit_all_set(struct sparsebit *sbit);
47 bool sparsebit_all_clear(struct sparsebit *sbit);
48 sparsebit_idx_t sparsebit_first_set(struct sparsebit *sbit);
49 sparsebit_idx_t sparsebit_first_clear(struct sparsebit *sbit);
50 sparsebit_idx_t sparsebit_next_set(struct sparsebit *sbit, sparsebit_idx_t prev);
51 sparsebit_idx_t sparsebit_next_clear(struct sparsebit *sbit, sparsebit_idx_t prev);
52 sparsebit_idx_t sparsebit_next_set_num(struct sparsebit *sbit,
53 				       sparsebit_idx_t start, sparsebit_num_t num);
54 sparsebit_idx_t sparsebit_next_clear_num(struct sparsebit *sbit,
55 					 sparsebit_idx_t start, sparsebit_num_t num);
56 
57 void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx);
58 void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start,
59 		       sparsebit_num_t num);
60 void sparsebit_set_all(struct sparsebit *sbitp);
61 
62 void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx);
63 void sparsebit_clear_num(struct sparsebit *sbitp,
64 			 sparsebit_idx_t start, sparsebit_num_t num);
65 void sparsebit_clear_all(struct sparsebit *sbitp);
66 
67 void sparsebit_dump(FILE *stream, struct sparsebit *sbit,
68 		    unsigned int indent);
69 void sparsebit_validate_internal(struct sparsebit *sbit);
70 
71 #ifdef __cplusplus
72 }
73 #endif
74 
75 #endif /* SELFTEST_KVM_SPARSEBIT_H */
76