diff options
author | Rusty Russell <rusty@rustcorp.com.au> | 2009-01-01 10:12:19 +1030 |
---|---|---|
committer | Rusty Russell <rusty@rustcorp.com.au> | 2009-01-01 10:12:19 +1030 |
commit | ab53d472e785e51fdfc08fc1d66252c1153e6c0f (patch) | |
tree | 19abab13d2e4e8fe00f960c0ac475e14bfb1a44e | |
parent | 0db5d3d2f58804edb394e8008c7d9744110338a2 (diff) | |
download | lwn-ab53d472e785e51fdfc08fc1d66252c1153e6c0f.tar.gz lwn-ab53d472e785e51fdfc08fc1d66252c1153e6c0f.zip |
bitmap: find_last_bit()
Impact: New API
As the name suggests. For the moment everyone uses the generic one.
Signed-off-by: Rusty Russell <rusty@rustcorp.com.au>
-rw-r--r-- | include/linux/bitops.h | 13 | ||||
-rw-r--r-- | lib/Kconfig | 4 | ||||
-rw-r--r-- | lib/Makefile | 1 | ||||
-rw-r--r-- | lib/find_last_bit.c | 45 |
4 files changed, 62 insertions, 1 deletions
diff --git a/include/linux/bitops.h b/include/linux/bitops.h index 024f2b027244..61829139795a 100644 --- a/include/linux/bitops.h +++ b/include/linux/bitops.h @@ -134,9 +134,20 @@ extern unsigned long find_first_bit(const unsigned long *addr, */ extern unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size); - #endif /* CONFIG_GENERIC_FIND_FIRST_BIT */ +#ifdef CONFIG_GENERIC_FIND_LAST_BIT +/** + * find_last_bit - find the last set bit in a memory region + * @addr: The address to start the search at + * @size: The maximum size to search + * + * Returns the bit number of the first set bit, or size. + */ +extern unsigned long find_last_bit(const unsigned long *addr, + unsigned long size); +#endif /* CONFIG_GENERIC_FIND_LAST_BIT */ + #ifdef CONFIG_GENERIC_FIND_NEXT_BIT /** diff --git a/lib/Kconfig b/lib/Kconfig index 2ba43c4a5b07..fc5f5ee50bc2 100644 --- a/lib/Kconfig +++ b/lib/Kconfig @@ -13,6 +13,10 @@ config GENERIC_FIND_FIRST_BIT config GENERIC_FIND_NEXT_BIT bool +config GENERIC_FIND_LAST_BIT + bool + default y + config CRC_CCITT tristate "CRC-CCITT functions" help diff --git a/lib/Makefile b/lib/Makefile index 80fe8a3ec12a..32b0e64ded27 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -37,6 +37,7 @@ lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o lib-$(CONFIG_GENERIC_FIND_FIRST_BIT) += find_next_bit.o lib-$(CONFIG_GENERIC_FIND_NEXT_BIT) += find_next_bit.o +lib-$(CONFIG_GENERIC_FIND_LAST_BIT) += find_last_bit.o obj-$(CONFIG_GENERIC_HWEIGHT) += hweight.o obj-$(CONFIG_LOCK_KERNEL) += kernel_lock.o obj-$(CONFIG_PLIST) += plist.o diff --git a/lib/find_last_bit.c b/lib/find_last_bit.c new file mode 100644 index 000000000000..5d202e36bdd8 --- /dev/null +++ b/lib/find_last_bit.c @@ -0,0 +1,45 @@ +/* find_last_bit.c: fallback find next bit implementation + * + * Copyright (C) 2008 IBM Corporation + * Written by Rusty Russell <rusty@rustcorp.com.au> + * (Inspired by David Howell's find_next_bit implementation) + * + * This program is free software; you can redistribute it and/or + * modify it under the terms of the GNU General Public License + * as published by the Free Software Foundation; either version + * 2 of the License, or (at your option) any later version. + */ + +#include <linux/bitops.h> +#include <linux/module.h> +#include <asm/types.h> +#include <asm/byteorder.h> + +unsigned long find_last_bit(const unsigned long *addr, unsigned long size) +{ + unsigned long words; + unsigned long tmp; + + /* Start at final word. */ + words = size / BITS_PER_LONG; + + /* Partial final word? */ + if (size & (BITS_PER_LONG-1)) { + tmp = (addr[words] & (~0UL >> (BITS_PER_LONG + - (size & (BITS_PER_LONG-1))))); + if (tmp) + goto found; + } + + while (words) { + tmp = addr[--words]; + if (tmp) { +found: + return words * BITS_PER_LONG + __fls(tmp); + } + } + + /* Not found */ + return size; +} +EXPORT_SYMBOL(find_last_bit); |