tools/testing/selftests/kvm/include/sparsebit.h

   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 */