LXR linux/lib/find

   1/* bit search implementation
   2 *
   3 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   4 * Written by David Howells (dhowells@redhat.com)
   5 *
   6 * Copyright (C) 2008 IBM Corporation
   7 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
   8 * (Inspired by David Howell's find_next_bit implementation)
   9 *
  10 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
  11 * size and improve performance, 2015.
  12 *
  13 * This program is free software; you can redistribute it and/or
  14 * modify it under the terms of the GNU General Public License
  15 * as published by the Free Software Foundation; either version
  16 * 2 of the License, or (at your option) any later version.
  17 */
  18
  19#include <linux/bitops.h>
  20#include <linux/bitmap.h>
  21#include <linux/export.h>
  22#include <linux/kernel.h>
  23
  24#if !defined(find_next_bit) || !defined(find_next_zero_bit)
  25
  26/*
  27 * This is a common helper function for find_next_bit and
  28 * find_next_zero_bit.  The difference is the "invert" argument, which
  29 * is XORed with each fetched word before searching it for one bits.
  30 */
  31static unsigned long _find_next_bit(const unsigned long *addr,
  32                unsigned long nbits, unsigned long start, unsigned long invert)
  33{
  34        unsigned long tmp;
  35
  36        if (unlikely(start >= nbits))
  37                return nbits;
  38
  39        tmp = addr[start / BITS_PER_LONG] ^ invert;
  40
  41        /* Handle 1st word. */
  42        tmp &= BITMAP_FIRST_WORD_MASK(start);
  43        start = round_down(start, BITS_PER_LONG);
  44
  45        while (!tmp) {
  46                start += BITS_PER_LONG;
  47                if (start >= nbits)
  48                        return nbits;
  49
  50                tmp = addr[start / BITS_PER_LONG] ^ invert;
  51        }
  52
  53        return min(start + __ffs(tmp), nbits);
  54}
  55#endif
  56
  57#ifndef find_next_bit
  58/*
  59 * Find the next set bit in a memory region.
  60 */
  61unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  62                            unsigned long offset)
  63{
  64        return _find_next_bit(addr, size, offset, 0UL);
  65}
  66EXPORT_SYMBOL(find_next_bit);
  67#endif
  68
  69#ifndef find_next_zero_bit
  70unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  71                                 unsigned long offset)
  72{
  73        return _find_next_bit(addr, size, offset, ~0UL);
  74}
  75EXPORT_SYMBOL(find_next_zero_bit);
  76#endif
  77
  78#ifndef find_first_bit
  79/*
  80 * Find the first set bit in a memory region.
  81 */
  82unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  83{
  84        unsigned long idx;
  85
  86        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  87                if (addr[idx])
  88                        return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  89        }
  90
  91        return size;
  92}
  93EXPORT_SYMBOL(find_first_bit);
  94#endif
  95
  96#ifndef find_first_zero_bit
  97/*
  98 * Find the first cleared bit in a memory region.
  99 */
 100unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 101{
 102        unsigned long idx;
 103
 104        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 105                if (addr[idx] != ~0UL)
 106                        return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 107        }
 108
 109        return size;
 110}
 111EXPORT_SYMBOL(find_first_zero_bit);
 112#endif
 113
 114#ifndef find_last_bit
 115unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 116{
 117        if (size) {
 118                unsigned long val = BITMAP_LAST_WORD_MASK(size);
 119                unsigned long idx = (size-1) / BITS_PER_LONG;
 120
 121                do {
 122                        val &= addr[idx];
 123                        if (val)
 124                                return idx * BITS_PER_LONG + __fls(val);
 125
 126                        val = ~0ul;
 127                } while (idx--);
 128        }
 129        return size;
 130}
 131EXPORT_SYMBOL(find_last_bit);
 132#endif
 133
 134#ifdef __BIG_ENDIAN
 135
 136/* include/linux/byteorder does not support "unsigned long" type */
 137static inline unsigned long ext2_swab(const unsigned long y)
 138{
 139#if BITS_PER_LONG == 64
 140        return (unsigned long) __swab64((u64) y);
 141#elif BITS_PER_LONG == 32
 142        return (unsigned long) __swab32((u32) y);
 143#else
 144#error BITS_PER_LONG not defined
 145#endif
 146}
 147
 148#if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
 149static unsigned long _find_next_bit_le(const unsigned long *addr,
 150                unsigned long nbits, unsigned long start, unsigned long invert)
 151{
 152        unsigned long tmp;
 153
 154        if (unlikely(start >= nbits))
 155                return nbits;
 156
 157        tmp = addr[start / BITS_PER_LONG] ^ invert;
 158
 159        /* Handle 1st word. */
 160        tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
 161        start = round_down(start, BITS_PER_LONG);
 162
 163        while (!tmp) {
 164                start += BITS_PER_LONG;
 165                if (start >= nbits)
 166                        return nbits;
 167
 168                tmp = addr[start / BITS_PER_LONG] ^ invert;
 169        }
 170
 171        return min(start + __ffs(ext2_swab(tmp)), nbits);
 172}
 173#endif
 174
 175#ifndef find_next_zero_bit_le
 176unsigned long find_next_zero_bit_le(const void *addr, unsigned
 177                long size, unsigned long offset)
 178{
 179        return _find_next_bit_le(addr, size, offset, ~0UL);
 180}
 181EXPORT_SYMBOL(find_next_zero_bit_le);
 182#endif
 183
 184#ifndef find_next_bit_le
 185unsigned long find_next_bit_le(const void *addr, unsigned
 186                long size, unsigned long offset)
 187{
 188        return _find_next_bit_le(addr, size, offset, 0UL);
 189}
 190EXPORT_SYMBOL(find_next_bit_le);
 191#endif
 192
 193#endif /* __BIG_ENDIAN */
 194