2 * Copyright (c) 2016-2018 Dmitry V. Levin <ldv@altlinux.org>
3 * Copyright (c) 2017-2019 The strace developers.
6 * SPDX-License-Identifier: LGPL-2.1-or-later
17 #include "number_set.h"
18 #include "static_assert.h"
21 typedef unsigned int number_slot_t;
22 #define BITS_PER_SLOT (sizeof(number_slot_t) * 8)
31 number_setbit(const unsigned int i, number_slot_t *const vec)
33 vec[i / BITS_PER_SLOT] |= (number_slot_t) 1 << (i % BITS_PER_SLOT);
37 number_isset(const unsigned int i, const number_slot_t *const vec)
39 return vec[i / BITS_PER_SLOT] & ((number_slot_t) 1 << (i % BITS_PER_SLOT));
43 reallocate_number_set(struct number_set *const set, const unsigned int new_nslots)
45 if (new_nslots <= set->nslots)
47 set->vec = xreallocarray(set->vec, new_nslots, sizeof(*set->vec));
48 memset(set->vec + set->nslots, 0,
49 sizeof(*set->vec) * (new_nslots - set->nslots));
50 set->nslots = new_nslots;
54 get_number_setbit(const struct number_set *const set)
56 static_assert(sizeof(number_slot_t) == sizeof(uint32_t),
57 "number_slot_t is not 32-bit long");
58 return popcount32(set->vec, set->nslots);
62 number_set_array_is_empty(const struct number_set *const set,
63 const unsigned int idx)
65 return !(set && (set[idx].nslots || set[idx].not));
69 is_number_in_set(const unsigned int number, const struct number_set *const set)
71 return set && ((number / BITS_PER_SLOT < set->nslots)
72 && number_isset(number, set->vec)) ^ set->not;
76 is_number_in_set_array(const unsigned int number, const struct number_set *const set,
77 const unsigned int idx)
79 return set && ((number / BITS_PER_SLOT < set[idx].nslots)
80 && number_isset(number, set[idx].vec)) ^ set[idx].not;
84 is_complete_set(const struct number_set *const set, const unsigned int max_numbers)
86 return set && ((set->not && !set->nslots) ||
87 (get_number_setbit(set) == max_numbers));
91 is_complete_set_array(const struct number_set *const set,
92 const unsigned int *const max_numbers,
93 const unsigned int nmemb)
95 for (unsigned int i = 0; i < nmemb; ++i) {
96 if (!is_complete_set(&set[i], max_numbers[i]))
103 add_number_to_set(const unsigned int number, struct number_set *const set)
105 reallocate_number_set(set, number / BITS_PER_SLOT + 1);
106 number_setbit(number, set->vec);
110 add_number_to_set_array(const unsigned int number, struct number_set *const set,
111 const unsigned int idx)
113 add_number_to_set(number, &set[idx]);
117 clear_number_set_array(struct number_set *const set, const unsigned int nmemb)
121 for (i = 0; i < nmemb; ++i) {
123 memset(set[i].vec, 0,
124 sizeof(*set[i].vec) * set[i].nslots);
130 invert_number_set_array(struct number_set *const set, const unsigned int nmemb)
134 for (i = 0; i < nmemb; ++i)
135 set[i].not = !set[i].not;
139 alloc_number_set_array(const unsigned int nmemb)
141 return xcalloc(nmemb, sizeof(struct number_set));
145 free_number_set_array(struct number_set *const set, unsigned int nmemb)
149 free(set[nmemb].vec);
150 set[nmemb].vec = NULL;