LXR linux/tools/lib/find

   1/* bit search implementation
   2 *
   3 * Copied from lib/find_bit.c to tools/lib/find_bit.c
   4 *
   5 * Copyright (C) 2004 Red Hat, Inc. All Rights Reserved.
   6 * Written by David Howells (dhowells@redhat.com)
   7 *
   8 * Copyright (C) 2008 IBM Corporation
   9 * 'find_last_bit' is written by Rusty Russell <rusty@rustcorp.com.au>
  10 * (Inspired by David Howell's find_next_bit implementation)
  11 *
  12 * Rewritten by Yury Norov <yury.norov@gmail.com> to decrease
  13 * size and improve performance, 2015.
  14 *
  15 * This program is free software; you can redistribute it and/or
  16 * modify it under the terms of the GNU General Public License
  17 * as published by the Free Software Foundation; either version
  18 * 2 of the License, or (at your option) any later version.
  19 */
  20
  21#include <linux/bitops.h>
  22#include <linux/bitmap.h>
  23#include <linux/kernel.h>
  24
  25#if !defined(find_next_bit)
  26
  27/*
  28 * This is a common helper function for find_next_bit and
  29 * find_next_zero_bit.  The difference is the "invert" argument, which
  30 * is XORed with each fetched word before searching it for one bits.
  31 */
  32static unsigned long _find_next_bit(const unsigned long *addr,
  33                unsigned long nbits, unsigned long start, unsigned long invert)
  34{
  35        unsigned long tmp;
  36
  37        if (unlikely(start >= nbits))
  38                return nbits;
  39
  40        tmp = addr[start / BITS_PER_LONG] ^ invert;
  41
  42        /* Handle 1st word. */
  43        tmp &= BITMAP_FIRST_WORD_MASK(start);
  44        start = round_down(start, BITS_PER_LONG);
  45
  46        while (!tmp) {
  47                start += BITS_PER_LONG;
  48                if (start >= nbits)
  49                        return nbits;
  50
  51                tmp = addr[start / BITS_PER_LONG] ^ invert;
  52        }
  53
  54        return min(start + __ffs(tmp), nbits);
  55}
  56#endif
  57
  58#ifndef find_next_bit
  59/*
  60 * Find the next set bit in a memory region.
  61 */
  62unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  63                            unsigned long offset)
  64{
  65        return _find_next_bit(addr, size, offset, 0UL);
  66}
  67#endif
  68
  69#ifndef find_first_bit
  70/*
  71 * Find the first set bit in a memory region.
  72 */
  73unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
  74{
  75        unsigned long idx;
  76
  77        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  78                if (addr[idx])
  79                        return min(idx * BITS_PER_LONG + __ffs(addr[idx]), size);
  80        }
  81
  82        return size;
  83}
  84#endif
  85
  86#ifndef find_first_zero_bit
  87/*
  88 * Find the first cleared bit in a memory region.
  89 */
  90unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
  91{
  92        unsigned long idx;
  93
  94        for (idx = 0; idx * BITS_PER_LONG < size; idx++) {
  95                if (addr[idx] != ~0UL)
  96                        return min(idx * BITS_PER_LONG + ffz(addr[idx]), size);
  97        }
  98
  99        return size;
 100}
 101#endif
 102
 103#ifndef find_next_zero_bit
 104unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
 105                                 unsigned long offset)
 106{
 107        return _find_next_bit(addr, size, offset, ~0UL);
 108}
 109#endif
 110