Re: [PATCH] bitops: simplify generic bit finding functions

["Alexander van Heukelum" <heukelum@fastmail.fm>]

Hi,

Ingo just pointed me to this thread.

On Sun, 27 Apr 2008 13:19:51 -0700, "Harvey Harrison"
<harvey.harrison@gmail.com> said:
> No need for a sentinal if we explicitly catch the no bits/all bits set
> cases, make it clear they are special cases returning size/BITS_PER_LONG.
> 
> Signed-off-by: Harvey Harrison <harvey.harrison@gmail.com>
> ---
>  include/linux/bitops.h |   93
>  ++++++++++++++++++++----------------------------
>  1 files changed, 39 insertions(+), 54 deletions(-)
> 
> diff --git a/include/linux/bitops.h b/include/linux/bitops.h
> index 48bde60..d9eb58a 100644
> --- a/include/linux/bitops.h
> +++ b/include/linux/bitops.h
> @@ -127,18 +127,17 @@ extern unsigned long __find_first_bit(const
> unsigned long *addr,
>  static __always_inline unsigned long
>  find_first_bit(const unsigned long *addr, unsigned long size)
>  {
> -	/* Avoid a function call if the bitmap size is a constant */
> -	/* and not bigger than BITS_PER_LONG. */
> -
> -	/* insert a sentinel so that __ffs returns size if there */
> -	/* are no set bits in the bitmap */
> -	if (__builtin_constant_p(size) && (size < BITS_PER_LONG))
> -		return __ffs((*addr) | (1ul << size));
> -
> -	/* the result of __ffs(0) is undefined, so it needs to be */
> -	/* handled separately */
> -	if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
> -		return ((*addr) == 0) ? BITS_PER_LONG : __ffs(*addr);
> +	/*
> +	 * Avoid a function call if the bitmap size is a constant and not
> +	 * bigger than BITS_PER_LONG.  Ensure we return size if there are
> +	 * no set bits.
> +	 */
> +	if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
> +		if (*addr == 0)
> +			return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
> +		else
> +			return __ffs(*addr);
> +	}

Ehm... assume size=16 and *addr=0x80000000
    then __ffs(*addr) = 31. Not 16.

>  	/* size is not constant or too big */
>  	return __find_first_bit(addr, size);
> @@ -157,20 +156,17 @@ extern unsigned long __find_first_zero_bit(const
> unsigned long *addr,
>  static __always_inline unsigned long
>  find_first_zero_bit(const unsigned long *addr, unsigned long size)
>  {
> -	/* Avoid a function call if the bitmap size is a constant */
> -	/* and not bigger than BITS_PER_LONG. */
> -
> -	/* insert a sentinel so that __ffs returns size if there */
> -	/* are no set bits in the bitmap */
> -	if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
> -		return __ffs(~(*addr) | (1ul << size));
> +	/*
> +	 * Avoid a function call if the bitmap size is a constant and not
> +	 * bigger than BITS_PER_LONG.  Ensure we return size if all bits set.
> +	 */
> +	if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
> +		if ((~(*addr)) == 0)
> +			return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
> +		else
> +			return __ffs(~(*addr));
>  	}
>  
> -	/* the result of __ffs(0) is undefined, so it needs to be */
> -	/* handled separately */
> -	if (__builtin_constant_p(size) && (size == BITS_PER_LONG))
> -		return (~(*addr) == 0) ? BITS_PER_LONG : __ffs(~(*addr));
> -
>  	/* size is not constant or too big */
>  	return __find_first_zero_bit(addr, size);
>  }
> @@ -192,22 +188,17 @@ find_next_bit(const unsigned long *addr, unsigned
> long size,
>  {
>  	unsigned long value;
>  
> -	/* Avoid a function call if the bitmap size is a constant */
> -	/* and not bigger than BITS_PER_LONG. */
> -
> -	/* insert a sentinel so that __ffs returns size if there */
> -	/* are no set bits in the bitmap */
> -	if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
> +	/*
> +	 * Avoid a function call if the bitmap size is a constant and not
> +	 * bigger than BITS_PER_LONG.  Ensure we return size if there are
> +	 * no set bits.
> +	 */
> +	if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
>  		value = (*addr) & ((~0ul) << offset);
> -		value |= (1ul << size);
> -		return __ffs(value);
> -	}
> -
> -	/* the result of __ffs(0) is undefined, so it needs to be */
> -	/* handled separately */
> -	if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
> -		value = (*addr) & ((~0ul) << offset);
> -		return (value == 0) ? BITS_PER_LONG : __ffs(value);
> +		if (value == 0)
> +			return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
> +		else
> +			return __ffs(value);
>  	}
>  
>  	/* size is not constant or too big */
> @@ -229,22 +220,16 @@ find_next_zero_bit(const unsigned long *addr,
> unsigned long size,
>  {
>  	unsigned long value;
>  
> -	/* Avoid a function call if the bitmap size is a constant */
> -	/* and not bigger than BITS_PER_LONG. */
> -
> -	/* insert a sentinel so that __ffs returns size if there */
> -	/* are no set bits in the bitmap */
> -	if (__builtin_constant_p(size) && (size < BITS_PER_LONG)) {
> -		value = (~(*addr)) & ((~0ul) << offset);
> -		value |= (1ul << size);
> -		return __ffs(value);
> -	}
> -
> -	/* the result of __ffs(0) is undefined, so it needs to be */
> -	/* handled separately */
> -	if (__builtin_constant_p(size) && (size == BITS_PER_LONG)) {
> +	/*
> +	 * Avoid a function call if the bitmap size is a constant and not
> +	 * bigger than BITS_PER_LONG.  Ensure we return size if all bits set.
> +	 */
> +	if (__builtin_constant_p(size) && (size <= BITS_PER_LONG)) {
>  		value = (~(*addr)) & ((~0ul) << offset);
> -		return (value == 0) ? BITS_PER_LONG : __ffs(value);
> +		if (value == 0)
> +			return (size < BITS_PER_LONG) ? size : BITS_PER_LONG;
> +		else
> +			return __ffs(value);
>  	}
>  
>  	/* size is not constant or too big */
> -- 
> 1.5.5.1.270.g89765
-- 
  Alexander van Heukelum
  heukelum@fastmail.fm

-- 
http://www.fastmail.fm - mmm... Fastmail...