tools/include/linux/find.h

   1 /* SPDX-License-Identifier: GPL-2.0 */
   2 #ifndef _TOOLS_LINUX_FIND_H_
   3 #define _TOOLS_LINUX_FIND_H_
   4
   5 #ifndef _TOOLS_LINUX_BITMAP_H
   6 #error tools: only <linux/bitmap.h> can be included directly
   7 #endif
   8
   9 #include <linux/bitops.h>
  10
  11 unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbits,
  12                                 unsigned long start);
  13 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
  14                                         unsigned long nbits, unsigned long start);
  15 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
  16                                          unsigned long start);
  17 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
  18 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
  19                                          const unsigned long *addr2, unsigned long size);
  20 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
  21
  22 #ifndef find_next_bit
  23 /**
  24  * find_next_bit - find the next set bit in a memory region
  25  * @addr: The address to base the search on
  26  * @size: The bitmap size in bits
  27  * @offset: The bitnumber to start searching at
  28  *
  29  * Returns the bit number for the next set bit
  30  * If no bits are set, returns @size.
  31  */
  32 static inline
  33 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
  34                             unsigned long offset)
  35 {
  36         if (small_const_nbits(size)) {
  37                 unsigned long val;
  38
  39                 if (unlikely(offset >= size))
  40                         return size;
  41
  42                 val = *addr & GENMASK(size - 1, offset);
  43                 return val ? __ffs(val) : size;
  44         }
  45
  46         return _find_next_bit(addr, size, offset);
  47 }
  48 #endif
  49
  50 #ifndef find_next_and_bit
  51 /**
  52  * find_next_and_bit - find the next set bit in both memory regions
  53  * @addr1: The first address to base the search on
  54  * @addr2: The second address to base the search on
  55  * @size: The bitmap size in bits
  56  * @offset: The bitnumber to start searching at
  57  *
  58  * Returns the bit number for the next set bit
  59  * If no bits are set, returns @size.
  60  */
  61 static inline
  62 unsigned long find_next_and_bit(const unsigned long *addr1,
  63                 const unsigned long *addr2, unsigned long size,
  64                 unsigned long offset)
  65 {
  66         if (small_const_nbits(size)) {
  67                 unsigned long val;
  68
  69                 if (unlikely(offset >= size))
  70                         return size;
  71
  72                 val = *addr1 & *addr2 & GENMASK(size - 1, offset);
  73                 return val ? __ffs(val) : size;
  74         }
  75
  76         return _find_next_and_bit(addr1, addr2, size, offset);
  77 }
  78 #endif
  79
  80 #ifndef find_next_zero_bit
  81 /**
  82  * find_next_zero_bit - find the next cleared bit in a memory region
  83  * @addr: The address to base the search on
  84  * @size: The bitmap size in bits
  85  * @offset: The bitnumber to start searching at
  86  *
  87  * Returns the bit number of the next zero bit
  88  * If no bits are zero, returns @size.
  89  */
  90 static inline
  91 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
  92                                  unsigned long offset)
  93 {
  94         if (small_const_nbits(size)) {
  95                 unsigned long val;
  96
  97                 if (unlikely(offset >= size))
  98                         return size;
  99
 100                 val = *addr | ~GENMASK(size - 1, offset);
 101                 return val == ~0UL ? size : ffz(val);
 102         }
 103
 104         return _find_next_zero_bit(addr, size, offset);
 105 }
 106 #endif
 107
 108 #ifndef find_first_bit
 109 /**
 110  * find_first_bit - find the first set bit in a memory region
 111  * @addr: The address to start the search at
 112  * @size: The maximum number of bits to search
 113  *
 114  * Returns the bit number of the first set bit.
 115  * If no bits are set, returns @size.
 116  */
 117 static inline
 118 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
 119 {
 120         if (small_const_nbits(size)) {
 121                 unsigned long val = *addr & GENMASK(size - 1, 0);
 122
 123                 return val ? __ffs(val) : size;
 124         }
 125
 126         return _find_first_bit(addr, size);
 127 }
 128 #endif
 129
 130 #ifndef find_first_and_bit
 131 /**
 132  * find_first_and_bit - find the first set bit in both memory regions
 133  * @addr1: The first address to base the search on
 134  * @addr2: The second address to base the search on
 135  * @size: The bitmap size in bits
 136  *
 137  * Returns the bit number for the next set bit
 138  * If no bits are set, returns @size.
 139  */
 140 static inline
 141 unsigned long find_first_and_bit(const unsigned long *addr1,
 142                                  const unsigned long *addr2,
 143                                  unsigned long size)
 144 {
 145         if (small_const_nbits(size)) {
 146                 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
 147
 148                 return val ? __ffs(val) : size;
 149         }
 150
 151         return _find_first_and_bit(addr1, addr2, size);
 152 }
 153 #endif
 154
 155 #ifndef find_first_zero_bit
 156 /**
 157  * find_first_zero_bit - find the first cleared bit in a memory region
 158  * @addr: The address to start the search at
 159  * @size: The maximum number of bits to search
 160  *
 161  * Returns the bit number of the first cleared bit.
 162  * If no bits are zero, returns @size.
 163  */
 164 static inline
 165 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
 166 {
 167         if (small_const_nbits(size)) {
 168                 unsigned long val = *addr | ~GENMASK(size - 1, 0);
 169
 170                 return val == ~0UL ? size : ffz(val);
 171         }
 172
 173         return _find_first_zero_bit(addr, size);
 174 }
 175 #endif
 176
 177 #endif /*__LINUX_FIND_H_ */