| 1 |
|
| 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 u64. 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 u64 sparsebit_idx_t;
|
| 29 | typedef u64 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
|