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                !defined(find_next_and_bit)
  26
  27/*
  28 * This is a common helper function for find_next_bit, find_next_zero_bit, and
  29 * find_next_and_bit. The differences are:
  30 *  - The "invert" argument, which is XORed with each fetched word before
  31 *    searching it for one bits.
  32 *  - The optional "addr2", which is anded with "addr1" if present.
  33 */
  34static inline unsigned long _find_next_bit(const unsigned long *addr1,
  35                const unsigned long *addr2, unsigned long nbits,
  36                unsigned long start, unsigned long invert)
  37{
  38        unsigned long tmp;
  39
  40        if (unlikely(start >= nbits))
  41                return nbits;
  42
  43        tmp = addr1[start / BITS_PER_LONG];
  44        if (addr2)
  45                tmp &= addr2[start / BITS_PER_LONG];
  46        tmp ^= invert;
  47
  48        /* Handle 1st word. */
  49        tmp &= BITMAP_FIRST_WORD_MASK(start);
  50        start = round_down(start, BITS_PER_LONG);
  51
  52        while (!tmp) {
  53                start += BITS_PER_LONG;
  54                if (start >= nbits)
  55                        return nbits;
  56
  57                tmp = addr1[start / BITS_PER_LONG];
  58                if (addr2)
  59                        tmp &= addr2[start / BITS_PER_LONG];
  60                tmp ^= invert;
  61        }
  62
  63        return min(start + __ffs(tmp), nbits);
  64}
  65#endif
  66
  67#ifndef find_next_bit
  68/*
  69 * Find the next set bit in a memory region.
  70 */
  71unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  72                            unsigned long offset)
  73{
  74        return _find_next_bit(addr, NULL, size, offset, 0UL);
  75}
  76EXPORT_SYMBOL(find_next_bit);
  77#endif
  78
  79#ifndef find_next_zero_bit
  80unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  81                                 unsigned long offset)
  82{
  83        return _find_next_bit(addr, NULL, size, offset, ~0UL);
  84}
  85EXPORT_SYMBOL(find_next_zero_bit);
  86#endif
  87
  88#if !defined(find_next_and_bit)
  89unsigned long find_next_and_bit(const unsigned long *addr1,
  90                const unsigned long *addr2, unsigned long size,
  91                unsigned long offset)
  92{
  93        return _find_next_bit(addr1, addr2, size, offset, 0UL);
  94}
  95EXPORT_SYMBOL(find_next_and_bit);
  96#endif
  97
  98#ifndef find_first_bit
  99/*
 100 * Find the first set bit in a memory region.
 101 */
 102unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 103{
 104        unsigned long idx;
 105
 106        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 107                if (addr[idx])
 108                        return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
 109        }
 110
 111        return size;
 112}
 113EXPORT_SYMBOL(find_first_bit);
 114#endif
 115
 116#ifndef find_first_zero_bit
 117/*
 118 * Find the first cleared bit in a memory region.
 119 */
 120unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 121{
 122        unsigned long idx;
 123
 124        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
 125                if (addr[idx] != ~0UL)
 126                        return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
 127        }
 128
 129        return size;
 130}
 131EXPORT_SYMBOL(find_first_zero_bit);
 132#endif
 133
 134#ifndef find_last_bit
 135unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
 136{
 137        if (size) {
 138                unsigned long val = BITMAP_LAST_WORD_MASK(size);
 139                unsigned long idx = (size-1) / BITS_PER_LONG;
 140
 141                do {
 142                        val &= addr[idx];
 143                        if (val)
 144                                return idx * BITS_PER_LONG + __fls(val);
 145
 146                        val = ~0ul;
 147                } while (idx--);
 148        }
 149        return size;
 150}
 151EXPORT_SYMBOL(find_last_bit);
 152#endif
 153
 154#ifdef __BIG_ENDIAN
 155
 156/* include/linux/byteorder does not support "unsigned long" type */
 157static inline unsigned long ext2_swab(const unsigned long y)
 158{
 159#if BITS_PER_LONG == 64
 160        return (unsigned long) __swab64((u64) y);
 161#elif BITS_PER_LONG == 32
 162        return (unsigned long) __swab32((u32) y);
 163#else
 164#error BITS_PER_LONG not defined
 165#endif
 166}
 167
 168#if !defined(find_next_bit_le) || !defined(find_next_zero_bit_le)
 169static inline unsigned long _find_next_bit_le(const unsigned long *addr1,
 170                const unsigned long *addr2, unsigned long nbits,
 171                unsigned long start, unsigned long invert)
 172{
 173        unsigned long tmp;
 174
 175        if (unlikely(start >= nbits))
 176                return nbits;
 177
 178        tmp = addr1[start / BITS_PER_LONG];
 179        if (addr2)
 180                tmp &= addr2[start / BITS_PER_LONG];
 181        tmp ^= invert;
 182
 183        /* Handle 1st word. */
 184        tmp &= ext2_swab(BITMAP_FIRST_WORD_MASK(start));
 185        start = round_down(start, BITS_PER_LONG);
 186
 187        while (!tmp) {
 188                start += BITS_PER_LONG;
 189                if (start >= nbits)
 190                        return nbits;
 191
 192                tmp = addr1[start / BITS_PER_LONG];
 193                if (addr2)
 194                        tmp &= addr2[start / BITS_PER_LONG];
 195                tmp ^= invert;
 196        }
 197
 198        return min(start + __ffs(ext2_swab(tmp)), nbits);
 199}
 200#endif
 201
 202#ifndef find_next_zero_bit_le
 203unsigned long find_next_zero_bit_le(const void *addr, unsigned
 204                long size, unsigned long offset)
 205{
 206        return _find_next_bit_le(addr, NULL, size, offset, ~0UL);
 207}
 208EXPORT_SYMBOL(find_next_zero_bit_le);
 209#endif
 210
 211#ifndef find_next_bit_le
 212unsigned long find_next_bit_le(const void *addr, unsigned
 213                long size, unsigned long offset)
 214{
 215        return _find_next_bit_le(addr, NULL, size, offset, 0UL);
 216}
 217EXPORT_SYMBOL(find_next_bit_le);
 218#endif
 219
 220#endif /* __BIG_ENDIAN */
 221