kvm/include/sparsebit.h

0001 /* SPDX-License-Identifier: GPL-2.0-only */
0002 /*
0003  * tools/testing/selftests/kvm/include/sparsebit.h
0004  *
0005  * Copyright (C) 2018, Google LLC.
0006  *
0007  * Header file that describes API to the sparsebit library.
0008  * This library provides a memory efficient means of storing
0009  * the settings of bits indexed via a uint64_t.  Memory usage
0010  * is reasonable, significantly less than (2^64 / 8) bytes, as
0011  * long as bits that are mostly set or mostly cleared are close
0012  * to each other.  This library is efficient in memory usage
0013  * even in the case where most bits are set.
0014  */
0015
0016 #ifndef SELFTEST_KVM_SPARSEBIT_H
0017 #define SELFTEST_KVM_SPARSEBIT_H
0018
0019 #include <stdbool.h>
0020 #include <stdint.h>
0021 #include <stdio.h>
0022
0023 #ifdef __cplusplus
0024 extern "C" {
0025 #endif
0026
0027 struct sparsebit;
0028 typedef uint64_t sparsebit_idx_t;
0029 typedef uint64_t sparsebit_num_t;
0030
0031 struct sparsebit *sparsebit_alloc(void);
0032 void sparsebit_free(struct sparsebit **sbitp);
0033 void sparsebit_copy(struct sparsebit *dstp, struct sparsebit *src);
0034
0035 bool sparsebit_is_set(struct sparsebit *sbit, sparsebit_idx_t idx);
0036 bool sparsebit_is_set_num(struct sparsebit *sbit,
0037               sparsebit_idx_t idx, sparsebit_num_t num);
0038 bool sparsebit_is_clear(struct sparsebit *sbit, sparsebit_idx_t idx);
0039 bool sparsebit_is_clear_num(struct sparsebit *sbit,
0040                 sparsebit_idx_t idx, sparsebit_num_t num);
0041 sparsebit_num_t sparsebit_num_set(struct sparsebit *sbit);
0042 bool sparsebit_any_set(struct sparsebit *sbit);
0043 bool sparsebit_any_clear(struct sparsebit *sbit);
0044 bool sparsebit_all_set(struct sparsebit *sbit);
0045 bool sparsebit_all_clear(struct sparsebit *sbit);
0046 sparsebit_idx_t sparsebit_first_set(struct sparsebit *sbit);
0047 sparsebit_idx_t sparsebit_first_clear(struct sparsebit *sbit);
0048 sparsebit_idx_t sparsebit_next_set(struct sparsebit *sbit, sparsebit_idx_t prev);
0049 sparsebit_idx_t sparsebit_next_clear(struct sparsebit *sbit, sparsebit_idx_t prev);
0050 sparsebit_idx_t sparsebit_next_set_num(struct sparsebit *sbit,
0051                        sparsebit_idx_t start, sparsebit_num_t num);
0052 sparsebit_idx_t sparsebit_next_clear_num(struct sparsebit *sbit,
0053                      sparsebit_idx_t start, sparsebit_num_t num);
0054
0055 void sparsebit_set(struct sparsebit *sbitp, sparsebit_idx_t idx);
0056 void sparsebit_set_num(struct sparsebit *sbitp, sparsebit_idx_t start,
0057                sparsebit_num_t num);
0058 void sparsebit_set_all(struct sparsebit *sbitp);
0059
0060 void sparsebit_clear(struct sparsebit *sbitp, sparsebit_idx_t idx);
0061 void sparsebit_clear_num(struct sparsebit *sbitp,
0062              sparsebit_idx_t start, sparsebit_num_t num);
0063 void sparsebit_clear_all(struct sparsebit *sbitp);
0064
0065 void sparsebit_dump(FILE *stream, struct sparsebit *sbit,
0066             unsigned int indent);
0067 void sparsebit_validate_internal(struct sparsebit *sbit);
0068
0069 #ifdef __cplusplus
0070 }
0071 #endif
0072
0073 #endif /* SELFTEST_KVM_SPARSEBIT_H */