LXR linux/lib/find_next

   1/* find_next_bit.c: fallback find next bit implementation
   2 *
   3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   4 * Written by David Howells (dhowells@redhat.com)
   5 *
   6 * This program is free software; you can redistribute it and/or
   7 * modify it under the terms of the GNU General Public License
   8 * as published by the Free Software Foundation; either version
   9 * 2 of the License, or (at your option) any later version.
  10 */
  11
  12#include <linux/bitops.h>
  13#include <linux/module.h>
  14#include <asm/types.h>
  15#include <asm/byteorder.h>
  16
  17#define BITOP_WORD(nr)          ((nr) / BITS_PER_LONG)
  18
  19/**
  20 * find_next_bit - find the next set bit in a memory region
  21 * @addr: The address to base the search on
  22 * @offset: The bitnumber to start searching at
  23 * @size: The maximum size to search
  24 */
  25unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  26                unsigned long offset)
  27{
  28        const unsigned long *p = addr + BITOP_WORD(offset);
  29        unsigned long result = offset & ~(BITS_PER_LONG-1);
  30        unsigned long tmp;
  31
  32        if (offset >= size)
  33                return size;
  34        size -= result;
  35        offset %= BITS_PER_LONG;
  36        if (offset) {
  37                tmp = *(p++);
  38                tmp &= (~0UL << offset);
  39                if (size < BITS_PER_LONG)
  40                        goto found_first;
  41                if (tmp)
  42                        goto found_middle;
  43                size -= BITS_PER_LONG;
  44                result += BITS_PER_LONG;
  45        }
  46        while (size & ~(BITS_PER_LONG-1)) {
  47                if ((tmp = *(p++)))
  48                        goto found_middle;
  49                result += BITS_PER_LONG;
  50                size -= BITS_PER_LONG;
  51        }
  52        if (!size)
  53                return result;
  54        tmp = *p;
  55
  56found_first:
  57        tmp &= (~0UL >> (BITS_PER_LONG - size));
  58        if (tmp == 0UL)         /* Are any bits set? */
  59                return result + size;   /* Nope. */
  60found_middle:
  61        return result + __ffs(tmp);
  62}
  63
  64EXPORT_SYMBOL(find_next_bit);
  65
  66/*
  67 * This implementation of find_{first,next}_zero_bit was stolen from
  68 * Linus' asm-alpha/bitops.h.
  69 */
  70unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  71                unsigned long offset)
  72{
  73        const unsigned long *p = addr + BITOP_WORD(offset);
  74        unsigned long result = offset & ~(BITS_PER_LONG-1);
  75        unsigned long tmp;
  76
  77        if (offset >= size)
  78                return size;
  79        size -= result;
  80        offset %= BITS_PER_LONG;
  81        if (offset) {
  82                tmp = *(p++);
  83                tmp |= ~0UL >> (BITS_PER_LONG - offset);
  84                if (size < BITS_PER_LONG)
  85                        goto found_first;
  86                if (~tmp)
  87                        goto found_middle;
  88                size -= BITS_PER_LONG;
  89                result += BITS_PER_LONG;
  90        }
  91        while (size & ~(BITS_PER_LONG-1)) {
  92                if (~(tmp = *(p++)))
  93                        goto found_middle;
  94                result += BITS_PER_LONG;
  95                size -= BITS_PER_LONG;
  96        }
  97        if (!size)
  98                return result;
  99        tmp = *p;
 100
 101found_first:
 102        tmp |= ~0UL << size;
 103        if (tmp == ~0UL)        /* Are any bits zero? */
 104                return result + size;   /* Nope. */
 105found_middle:
 106        return result + ffz(tmp);
 107}
 108
 109EXPORT_SYMBOL(find_next_zero_bit);
 110
 111#ifdef __BIG_ENDIAN
 112
 113/* include/linux/byteorder does not support "unsigned long" type */
 114static inline unsigned long ext2_swabp(const unsigned long * x)
 115{
 116#if BITS_PER_LONG == 64
 117        return (unsigned long) __swab64p((u64 *) x);
 118#elif BITS_PER_LONG == 32
 119        return (unsigned long) __swab32p((u32 *) x);
 120#else
 121#error BITS_PER_LONG not defined
 122#endif
 123}
 124
 125/* include/linux/byteorder doesn't support "unsigned long" type */
 126static inline unsigned long ext2_swab(const unsigned long y)
 127{
 128#if BITS_PER_LONG == 64
 129        return (unsigned long) __swab64((u64) y);
 130#elif BITS_PER_LONG == 32
 131        return (unsigned long) __swab32((u32) y);
 132#else
 133#error BITS_PER_LONG not defined
 134#endif
 135}
 136
 137unsigned long generic_find_next_zero_le_bit(const unsigned long *addr, unsigned
 138                long size, unsigned long offset)
 139{
 140        const unsigned long *p = addr + BITOP_WORD(offset);
 141        unsigned long result = offset & ~(BITS_PER_LONG - 1);
 142        unsigned long tmp;
 143
 144        if (offset >= size)
 145                return size;
 146        size -= result;
 147        offset &= (BITS_PER_LONG - 1UL);
 148        if (offset) {
 149                tmp = ext2_swabp(p++);
 150                tmp |= (~0UL >> (BITS_PER_LONG - offset));
 151                if (size < BITS_PER_LONG)
 152                        goto found_first;
 153                if (~tmp)
 154                        goto found_middle;
 155                size -= BITS_PER_LONG;
 156                result += BITS_PER_LONG;
 157        }
 158
 159        while (size & ~(BITS_PER_LONG - 1)) {
 160                if (~(tmp = *(p++)))
 161                        goto found_middle_swap;
 162                result += BITS_PER_LONG;
 163                size -= BITS_PER_LONG;
 164        }
 165        if (!size)
 166                return result;
 167        tmp = ext2_swabp(p);
 168found_first:
 169        tmp |= ~0UL << size;
 170        if (tmp == ~0UL)        /* Are any bits zero? */
 171                return result + size; /* Nope. Skip ffz */
 172found_middle:
 173        return result + ffz(tmp);
 174
 175found_middle_swap:
 176        return result + ffz(ext2_swab(tmp));
 177}
 178
 179EXPORT_SYMBOL(generic_find_next_zero_le_bit);
 180
 181#endif /* __BIG_ENDIAN */
 182