]>
git.proxmox.com Git - mirror_ubuntu-jammy-kernel.git/blob - tools/lib/find_bit.c
1 /* bit search implementation
3 * Copied from lib/find_bit.c to tools/lib/find_bit.c
5 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
6 * Written by David Howells (dhowells@redhat.com)
8 * Copyright (C) 2008 IBM Corporation
9 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
10 * (Inspired by David Howell's find_next_bit implementation)
12 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
13 * size and improve performance, 2015.
15 * This program is free software; you can redistribute it and/or
16 * modify it under the terms of the GNU General Public License
17 * as published by the Free Software Foundation; either version
18 * 2 of the License, or (at your option) any later version.
21 #include <linux/bitops.h>
22 #include <linux/bitmap.h>
23 #include <linux/kernel.h>
25 #if !defined(find_next_bit)
28 * This is a common helper function for find_next_bit and
29 * find_next_zero_bit. The difference is the "invert" argument, which
30 * is XORed with each fetched word before searching it for one bits.
32 static unsigned long _find_next_bit(const unsigned long *addr
,
33 unsigned long nbits
, unsigned long start
, unsigned long invert
)
37 if (!nbits
|| start
>= nbits
)
40 tmp
= addr
[start
/ BITS_PER_LONG
] ^ invert
;
42 /* Handle 1st word. */
43 tmp
&= BITMAP_FIRST_WORD_MASK(start
);
44 start
= round_down(start
, BITS_PER_LONG
);
47 start
+= BITS_PER_LONG
;
51 tmp
= addr
[start
/ BITS_PER_LONG
] ^ invert
;
54 return min(start
+ __ffs(tmp
), nbits
);
60 * Find the next set bit in a memory region.
62 unsigned long find_next_bit(const unsigned long *addr
, unsigned long size
,
65 return _find_next_bit(addr
, size
, offset
, 0UL);
69 #ifndef find_first_bit
71 * Find the first set bit in a memory region.
73 unsigned long find_first_bit(const unsigned long *addr
, unsigned long size
)
77 for (idx
= 0; idx
* BITS_PER_LONG
< size
; idx
++) {
79 return min(idx
* BITS_PER_LONG
+ __ffs(addr
[idx
]), size
);