lkml.org 
[lkml]   [2006]   [Feb]   [1]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    Patch in this message
    /
    Date
    From
    Subject[patch 11/44] generic find_{next,first}{,_zero}_bit()
    This patch introduces the C-language equivalents of the functions below:

    unsigned logn find_next_bit(const unsigned long *addr, unsigned long size,
    unsigned long offset);
    unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
    unsigned long offset);
    unsigned long find_first_zero_bit(const unsigned long *addr,
    unsigned long size);
    unsigned long find_first_bit(const unsigned long *addr, unsigned long size);

    In include/asm-generic/bitops/find.h

    This code largely copied from:
    arch/powerpc/lib/bitops.c

    Signed-off-by: Akinobu Mita <mita@miraclelinux.com>
    include/asm-generic/bitops/find.h | 99 ++++++++++++++++++++++++++++++++++++++
    1 files changed, 99 insertions(+)

    Index: 2.6-git/include/asm-generic/bitops/find.h
    ===================================================================
    --- /dev/null
    +++ 2.6-git/include/asm-generic/bitops/find.h
    @@ -0,0 +1,99 @@
    +#ifndef _ASM_GENERIC_BITOPS_FIND_H_
    +#define _ASM_GENERIC_BITOPS_FIND_H_
    +
    +#include <asm/types.h>
    +
    +#define BITOP_WORD(nr) ((nr) / BITS_PER_LONG)
    +
    +/**
    + * find_next_bit - find the next set bit in a memory region
    + * @addr: The address to base the search on
    + * @offset: The bitnumber to start searching at
    + * @size: The maximum size to search
    + */
    +static inline unsigned long find_next_bit(const unsigned long *addr,
    + unsigned long size, unsigned long offset)
    +{
    + const unsigned long *p = addr + BITOP_WORD(offset);
    + unsigned long result = offset & ~(BITS_PER_LONG-1);
    + unsigned long tmp;
    +
    + if (offset >= size)
    + return size;
    + size -= result;
    + offset %= BITS_PER_LONG;
    + if (offset) {
    + tmp = *(p++);
    + tmp &= (~0UL << offset);
    + if (size < BITS_PER_LONG)
    + goto found_first;
    + if (tmp)
    + goto found_middle;
    + size -= BITS_PER_LONG;
    + result += BITS_PER_LONG;
    + }
    + while (size & ~(BITS_PER_LONG-1)) {
    + if ((tmp = *(p++)))
    + goto found_middle;
    + result += BITS_PER_LONG;
    + size -= BITS_PER_LONG;
    + }
    + if (!size)
    + return result;
    + tmp = *p;
    +
    +found_first:
    + tmp &= (~0UL >> (BITS_PER_LONG - size));
    + if (tmp == 0UL) /* Are any bits set? */
    + return result + size; /* Nope. */
    +found_middle:
    + return result + __ffs(tmp);
    +}
    +
    +/*
    + * This implementation of find_{first,next}_zero_bit was stolen from
    + * Linus' asm-alpha/bitops.h.
    + */
    +static inline unsigned long find_next_zero_bit(const unsigned long *addr,
    + unsigned long size, unsigned long offset)
    +{
    + const unsigned long *p = addr + BITOP_WORD(offset);
    + unsigned long result = offset & ~(BITS_PER_LONG-1);
    + unsigned long tmp;
    +
    + if (offset >= size)
    + return size;
    + size -= result;
    + offset %= BITS_PER_LONG;
    + if (offset) {
    + tmp = *(p++);
    + tmp |= ~0UL >> (BITS_PER_LONG - offset);
    + if (size < BITS_PER_LONG)
    + goto found_first;
    + if (~tmp)
    + goto found_middle;
    + size -= BITS_PER_LONG;
    + result += BITS_PER_LONG;
    + }
    + while (size & ~(BITS_PER_LONG-1)) {
    + if (~(tmp = *(p++)))
    + goto found_middle;
    + result += BITS_PER_LONG;
    + size -= BITS_PER_LONG;
    + }
    + if (!size)
    + return result;
    + tmp = *p;
    +
    +found_first:
    + tmp |= ~0UL << size;
    + if (tmp == ~0UL) /* Are any bits zero? */
    + return result + size; /* Nope. */
    +found_middle:
    + return result + ffz(tmp);
    +}
    +
    +#define find_first_zero_bit(addr, size) find_next_zero_bit((addr), (size), 0)
    +#define find_first_bit(addr, size) find_next_bit((addr), (size), 0)
    +
    +#endif /*_ASM_GENERIC_BITOPS_FIND_H_ */
    --
    -
    To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
    the body of a message to majordomo@vger.kernel.org
    More majordomo info at http://vger.kernel.org/majordomo-info.html
    Please read the FAQ at http://www.tux.org/lkml/

    \
     
     \ /
      Last update: 2006-02-01 10:27    [W:4.024 / U:0.092 seconds]
    ©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site