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