4 * Copyright (c) Intel Corporation.
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
11 * * Redistributions of source code must retain the above copyright
12 * notice, this list of conditions and the following disclaimer.
13 * * Redistributions in binary form must reproduce the above copyright
14 * notice, this list of conditions and the following disclaimer in
15 * the documentation and/or other materials provided with the
17 * * Neither the name of Intel Corporation nor the names of its
18 * contributors may be used to endorse or promote products derived
19 * from this software without specific prior written permission.
21 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
22 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
23 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
24 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
25 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
26 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
27 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
28 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
29 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
30 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
31 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34 #include "spdk/stdinc.h"
36 #include "spdk/bit_array.h"
39 #include "spdk/likely.h"
40 #include "spdk/util.h"
42 typedef uint64_t spdk_bit_array_word
;
43 #define SPDK_BIT_ARRAY_WORD_TZCNT(x) (__builtin_ctzll(x))
44 #define SPDK_BIT_ARRAY_WORD_POPCNT(x) (__builtin_popcountll(x))
45 #define SPDK_BIT_ARRAY_WORD_C(x) ((spdk_bit_array_word)(x))
46 #define SPDK_BIT_ARRAY_WORD_BYTES sizeof(spdk_bit_array_word)
47 #define SPDK_BIT_ARRAY_WORD_BITS (SPDK_BIT_ARRAY_WORD_BYTES * 8)
48 #define SPDK_BIT_ARRAY_WORD_INDEX_SHIFT spdk_u32log2(SPDK_BIT_ARRAY_WORD_BITS)
49 #define SPDK_BIT_ARRAY_WORD_INDEX_MASK ((1u << SPDK_BIT_ARRAY_WORD_INDEX_SHIFT) - 1)
51 struct spdk_bit_array
{
53 spdk_bit_array_word words
[];
56 struct spdk_bit_array
*
57 spdk_bit_array_create(uint32_t num_bits
)
59 struct spdk_bit_array
*ba
= NULL
;
61 spdk_bit_array_resize(&ba
, num_bits
);
67 spdk_bit_array_free(struct spdk_bit_array
**bap
)
69 struct spdk_bit_array
*ba
;
80 static inline uint32_t
81 bit_array_word_count(uint32_t num_bits
)
83 return (num_bits
+ SPDK_BIT_ARRAY_WORD_BITS
- 1) >> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT
;
86 static inline spdk_bit_array_word
87 bit_array_word_mask(uint32_t num_bits
)
89 assert(num_bits
< SPDK_BIT_ARRAY_WORD_BITS
);
90 return (SPDK_BIT_ARRAY_WORD_C(1) << num_bits
) - 1;
94 spdk_bit_array_resize(struct spdk_bit_array
**bap
, uint32_t num_bits
)
96 struct spdk_bit_array
*new_ba
;
97 uint32_t old_word_count
, new_word_count
;
101 * Max number of bits allowed is UINT32_MAX - 1, because we use UINT32_MAX to denote
102 * when a set or cleared bit cannot be found.
104 if (!bap
|| num_bits
== UINT32_MAX
) {
108 new_word_count
= bit_array_word_count(num_bits
);
109 new_size
= offsetof(struct spdk_bit_array
, words
) + new_word_count
* SPDK_BIT_ARRAY_WORD_BYTES
;
112 * Always keep one extra word with a 0 and a 1 past the actual required size so that the
113 * find_first functions can just keep going until they match.
115 new_size
+= SPDK_BIT_ARRAY_WORD_BYTES
;
117 new_ba
= (struct spdk_bit_array
*)spdk_realloc(*bap
, new_size
, 64);
123 * Set up special extra word (see above comment about find_first_clear).
125 * This is set to 0b10 so that find_first_clear will find a 0 at the very first
126 * bit past the end of the buffer, and find_first_set will find a 1 at the next bit
129 new_ba
->words
[new_word_count
] = 0x2;
133 new_ba
->bit_count
= 0;
135 old_word_count
= bit_array_word_count(new_ba
->bit_count
);
138 if (new_word_count
> old_word_count
) {
139 /* Zero out new entries */
140 memset(&new_ba
->words
[old_word_count
], 0,
141 (new_word_count
- old_word_count
) * SPDK_BIT_ARRAY_WORD_BYTES
);
142 } else if (new_word_count
== old_word_count
&& num_bits
< new_ba
->bit_count
) {
143 /* Make sure any existing partial last word is cleared beyond the new num_bits. */
144 uint32_t last_word_bits
;
145 spdk_bit_array_word mask
;
147 last_word_bits
= num_bits
& SPDK_BIT_ARRAY_WORD_INDEX_MASK
;
148 mask
= bit_array_word_mask(last_word_bits
);
149 new_ba
->words
[old_word_count
- 1] &= mask
;
152 new_ba
->bit_count
= num_bits
;
158 spdk_bit_array_capacity(const struct spdk_bit_array
*ba
)
160 return ba
->bit_count
;
164 bit_array_get_word(const struct spdk_bit_array
*ba
, uint32_t bit_index
,
165 uint32_t *word_index
, uint32_t *word_bit_index
)
167 if (spdk_unlikely(bit_index
>= ba
->bit_count
)) {
171 *word_index
= bit_index
>> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT
;
172 *word_bit_index
= bit_index
& SPDK_BIT_ARRAY_WORD_INDEX_MASK
;
178 spdk_bit_array_get(const struct spdk_bit_array
*ba
, uint32_t bit_index
)
180 uint32_t word_index
, word_bit_index
;
182 if (bit_array_get_word(ba
, bit_index
, &word_index
, &word_bit_index
)) {
186 return (ba
->words
[word_index
] >> word_bit_index
) & 1U;
190 spdk_bit_array_set(struct spdk_bit_array
*ba
, uint32_t bit_index
)
192 uint32_t word_index
, word_bit_index
;
194 if (bit_array_get_word(ba
, bit_index
, &word_index
, &word_bit_index
)) {
198 ba
->words
[word_index
] |= (SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index
);
203 spdk_bit_array_clear(struct spdk_bit_array
*ba
, uint32_t bit_index
)
205 uint32_t word_index
, word_bit_index
;
207 if (bit_array_get_word(ba
, bit_index
, &word_index
, &word_bit_index
)) {
209 * Clearing past the end of the bit array is a no-op, since bit past the end
215 ba
->words
[word_index
] &= ~(SPDK_BIT_ARRAY_WORD_C(1) << word_bit_index
);
218 static inline uint32_t
219 bit_array_find_first(const struct spdk_bit_array
*ba
, uint32_t start_bit_index
,
220 spdk_bit_array_word xor_mask
)
222 uint32_t word_index
, first_word_bit_index
;
223 spdk_bit_array_word word
, first_word_mask
;
224 const spdk_bit_array_word
*words
, *cur_word
;
226 if (spdk_unlikely(start_bit_index
>= ba
->bit_count
)) {
227 return ba
->bit_count
;
230 word_index
= start_bit_index
>> SPDK_BIT_ARRAY_WORD_INDEX_SHIFT
;
232 cur_word
= &words
[word_index
];
235 * Special case for first word: skip start_bit_index % SPDK_BIT_ARRAY_WORD_BITS bits
236 * within the first word.
238 first_word_bit_index
= start_bit_index
& SPDK_BIT_ARRAY_WORD_INDEX_MASK
;
239 first_word_mask
= bit_array_word_mask(first_word_bit_index
);
241 word
= (*cur_word
^ xor_mask
) & ~first_word_mask
;
244 * spdk_bit_array_resize() guarantees that an extra word with a 1 and a 0 will always be
245 * at the end of the words[] array, so just keep going until a word matches.
248 word
= *++cur_word
^ xor_mask
;
251 return ((uintptr_t)cur_word
- (uintptr_t)words
) * 8 + SPDK_BIT_ARRAY_WORD_TZCNT(word
);
256 spdk_bit_array_find_first_set(const struct spdk_bit_array
*ba
, uint32_t start_bit_index
)
260 bit_index
= bit_array_find_first(ba
, start_bit_index
, 0);
263 * If we ran off the end of the array and found the 1 bit in the extra word,
264 * return UINT32_MAX to indicate no actual 1 bits were found.
266 if (bit_index
>= ba
->bit_count
) {
267 bit_index
= UINT32_MAX
;
274 spdk_bit_array_find_first_clear(const struct spdk_bit_array
*ba
, uint32_t start_bit_index
)
278 bit_index
= bit_array_find_first(ba
, start_bit_index
, SPDK_BIT_ARRAY_WORD_C(-1));
281 * If we ran off the end of the array and found the 0 bit in the extra word,
282 * return UINT32_MAX to indicate no actual 0 bits were found.
284 if (bit_index
>= ba
->bit_count
) {
285 bit_index
= UINT32_MAX
;
292 spdk_bit_array_count_set(const struct spdk_bit_array
*ba
)
294 const spdk_bit_array_word
*cur_word
= ba
->words
;
295 uint32_t word_count
= bit_array_word_count(ba
->bit_count
);
296 uint32_t set_count
= 0;
298 while (word_count
--) {
300 * No special treatment is needed for the last (potentially partial) word, since
301 * spdk_bit_array_resize() makes sure the bits past bit_count are cleared.
303 set_count
+= SPDK_BIT_ARRAY_WORD_POPCNT(*cur_word
++);
310 spdk_bit_array_count_clear(const struct spdk_bit_array
*ba
)
312 return ba
->bit_count
- spdk_bit_array_count_set(ba
);
316 spdk_bit_array_store_mask(const struct spdk_bit_array
*ba
, void *mask
)
319 uint32_t num_bits
= spdk_bit_array_capacity(ba
);
321 size
= num_bits
/ CHAR_BIT
;
322 memcpy(mask
, ba
->words
, size
);
324 for (i
= 0; i
< num_bits
% CHAR_BIT
; i
++) {
325 if (spdk_bit_array_get(ba
, i
+ size
* CHAR_BIT
)) {
326 ((uint8_t *)mask
)[size
] |= (1U << i
);
328 ((uint8_t *)mask
)[size
] &= ~(1U << i
);
334 spdk_bit_array_load_mask(struct spdk_bit_array
*ba
, const void *mask
)
337 uint32_t num_bits
= spdk_bit_array_capacity(ba
);
339 size
= num_bits
/ CHAR_BIT
;
340 memcpy(ba
->words
, mask
, size
);
342 for (i
= 0; i
< num_bits
% CHAR_BIT
; i
++) {
343 if (((uint8_t *)mask
)[size
] & (1U << i
)) {
344 spdk_bit_array_set(ba
, i
+ size
* CHAR_BIT
);
346 spdk_bit_array_clear(ba
, i
+ size
* CHAR_BIT
);
352 spdk_bit_array_clear_mask(struct spdk_bit_array
*ba
)
355 uint32_t num_bits
= spdk_bit_array_capacity(ba
);
357 size
= num_bits
/ CHAR_BIT
;
358 memset(ba
->words
, 0, size
);
360 for (i
= 0; i
< num_bits
% CHAR_BIT
; i
++) {
361 spdk_bit_array_clear(ba
, i
+ size
* CHAR_BIT
);