diff options
author | Yury Norov <yury.norov@gmail.com> | 2022-09-15 05:07:30 +0300 |
---|---|---|
committer | Yury Norov <yury.norov@gmail.com> | 2022-09-21 22:21:44 +0300 |
commit | 6333cb31a711cc709b6a960d082e04546f4459ee (patch) | |
tree | c78875d9cba2167ab78e38de13343ef594fc1a2a /tools/lib | |
parent | e79864f3164c573afce09ec4b72b75ebe061c14d (diff) | |
download | linux-6333cb31a711cc709b6a960d082e04546f4459ee.tar.xz |
tools: sync find_bit() implementation
Sync find_first_bit() and find_next_bit() implementation with the
mother kernel.
Also, drop unused find_last_bit() and find_next_clump8().
Signed-off-by: Yury Norov <yury.norov@gmail.com>
Diffstat (limited to 'tools/lib')
-rw-r--r-- | tools/lib/find_bit.c | 149 |
1 files changed, 69 insertions, 80 deletions
diff --git a/tools/lib/find_bit.c b/tools/lib/find_bit.c index ba4b8d94e004..6a3dc167d30e 100644 --- a/tools/lib/find_bit.c +++ b/tools/lib/find_bit.c @@ -18,66 +18,54 @@ #include <linux/bitmap.h> #include <linux/kernel.h> -#if !defined(find_next_bit) || !defined(find_next_zero_bit) || \ - !defined(find_next_and_bit) - /* - * This is a common helper function for find_next_bit, find_next_zero_bit, and - * find_next_and_bit. The differences are: - * - The "invert" argument, which is XORed with each fetched word before - * searching it for one bits. - * - The optional "addr2", which is anded with "addr1" if present. + * Common helper for find_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) + * @MUNGE: The expression that post-processes a word containing found bit (may be empty) + * @size: The bitmap size in bits */ -unsigned long _find_next_bit(const unsigned long *addr1, - const unsigned long *addr2, unsigned long nbits, - unsigned long start, unsigned long invert, unsigned long le) -{ - unsigned long tmp, mask; - (void) le; - - if (unlikely(start >= nbits)) - return nbits; - - tmp = addr1[start / BITS_PER_LONG]; - if (addr2) - tmp &= addr2[start / BITS_PER_LONG]; - tmp ^= invert; - - /* Handle 1st word. */ - mask = BITMAP_FIRST_WORD_MASK(start); - - /* - * Due to the lack of swab() in tools, and the fact that it doesn't - * need little-endian support, just comment it out - */ -#if (0) - if (le) - mask = swab(mask); -#endif - - tmp &= mask; +#define FIND_FIRST_BIT(FETCH, MUNGE, size) \ +({ \ + unsigned long idx, val, sz = (size); \ + \ + for (idx = 0; idx * BITS_PER_LONG < sz; idx++) { \ + val = (FETCH); \ + if (val) { \ + sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(val)), sz); \ + break; \ + } \ + } \ + \ + sz; \ +}) - start = round_down(start, BITS_PER_LONG); - - while (!tmp) { - start += BITS_PER_LONG; - if (start >= nbits) - return nbits; - - tmp = addr1[start / BITS_PER_LONG]; - if (addr2) - tmp &= addr2[start / BITS_PER_LONG]; - tmp ^= invert; - } - -#if (0) - if (le) - tmp = swab(tmp); -#endif - - return min(start + __ffs(tmp), nbits); -} -#endif +/* + * Common helper for find_next_bit() function family + * @FETCH: The expression that fetches and pre-processes each word of bitmap(s) + * @MUNGE: The expression that post-processes a word containing found bit (may be empty) + * @size: The bitmap size in bits + * @start: The bitnumber to start searching at + */ +#define FIND_NEXT_BIT(FETCH, MUNGE, size, start) \ +({ \ + unsigned long mask, idx, tmp, sz = (size), __start = (start); \ + \ + if (unlikely(__start >= sz)) \ + goto out; \ + \ + mask = MUNGE(BITMAP_FIRST_WORD_MASK(__start)); \ + idx = __start / BITS_PER_LONG; \ + \ + for (tmp = (FETCH) & mask; !tmp; tmp = (FETCH)) { \ + if ((idx + 1) * BITS_PER_LONG >= sz) \ + goto out; \ + idx++; \ + } \ + \ + sz = min(idx * BITS_PER_LONG + __ffs(MUNGE(tmp)), sz); \ +out: \ + sz; \ +}) #ifndef find_first_bit /* @@ -85,14 +73,7 @@ unsigned long _find_next_bit(const unsigned long *addr1, */ unsigned long _find_first_bit(const unsigned long *addr, unsigned long size) { - unsigned long idx; - - for (idx = 0; idx * BITS_PER_LONG < size; idx++) { - if (addr[idx]) - return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size); - } - - return size; + return FIND_FIRST_BIT(addr[idx], /* nop */, size); } #endif @@ -104,15 +85,7 @@ unsigned long _find_first_and_bit(const unsigned long *addr1, const unsigned long *addr2, unsigned long size) { - unsigned long idx, val; - - for (idx = 0; idx * BITS_PER_LONG < size; idx++) { - val = addr1[idx] & addr2[idx]; - if (val) - return min(idx * BITS_PER_LONG + __ffs(val), size); - } - - return size; + return FIND_FIRST_BIT(addr1[idx] & addr2[idx], /* nop */, size); } #endif @@ -122,13 +95,29 @@ unsigned long _find_first_and_bit(const unsigned long *addr1, */ unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size) { - unsigned long idx; + return FIND_FIRST_BIT(~addr[idx], /* nop */, size); +} +#endif - for (idx = 0; idx * BITS_PER_LONG < size; idx++) { - if (addr[idx] != ~0UL) - return min(idx * BITS_PER_LONG + ffz(addr[idx]), size); - } +#ifndef find_next_bit +unsigned long _find_next_bit(const unsigned long *addr, unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(addr[idx], /* nop */, nbits, start); +} +#endif - return size; +#ifndef find_next_and_bit +unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2, + unsigned long nbits, unsigned long start) +{ + return FIND_NEXT_BIT(addr1[idx] & addr2[idx], /* nop */, nbits, start); +} +#endif + +#ifndef find_next_zero_bit +unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits, + unsigned long start) +{ + return FIND_NEXT_BIT(~addr[idx], /* nop */, nbits, start); } #endif |