find.h (5909B)
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 11extern unsigned long _find_next_bit(const unsigned long *addr1, 12 const unsigned long *addr2, unsigned long nbits, 13 unsigned long start, unsigned long invert, unsigned long le); 14extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size); 15extern unsigned long _find_first_and_bit(const unsigned long *addr1, 16 const unsigned long *addr2, unsigned long size); 17extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size); 18extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size); 19 20#ifndef find_next_bit 21/** 22 * find_next_bit - find the next set bit in a memory region 23 * @addr: The address to base the search on 24 * @offset: The bitnumber to start searching at 25 * @size: The bitmap size in bits 26 * 27 * Returns the bit number for the next set bit 28 * If no bits are set, returns @size. 29 */ 30static inline 31unsigned long find_next_bit(const unsigned long *addr, unsigned long size, 32 unsigned long offset) 33{ 34 if (small_const_nbits(size)) { 35 unsigned long val; 36 37 if (unlikely(offset >= size)) 38 return size; 39 40 val = *addr & GENMASK(size - 1, offset); 41 return val ? __ffs(val) : size; 42 } 43 44 return _find_next_bit(addr, NULL, size, offset, 0UL, 0); 45} 46#endif 47 48#ifndef find_next_and_bit 49/** 50 * find_next_and_bit - find the next set bit in both memory regions 51 * @addr1: The first address to base the search on 52 * @addr2: The second address to base the search on 53 * @offset: The bitnumber to start searching at 54 * @size: The bitmap size in bits 55 * 56 * Returns the bit number for the next set bit 57 * If no bits are set, returns @size. 58 */ 59static inline 60unsigned long find_next_and_bit(const unsigned long *addr1, 61 const unsigned long *addr2, unsigned long size, 62 unsigned long offset) 63{ 64 if (small_const_nbits(size)) { 65 unsigned long val; 66 67 if (unlikely(offset >= size)) 68 return size; 69 70 val = *addr1 & *addr2 & GENMASK(size - 1, offset); 71 return val ? __ffs(val) : size; 72 } 73 74 return _find_next_bit(addr1, addr2, size, offset, 0UL, 0); 75} 76#endif 77 78#ifndef find_next_zero_bit 79/** 80 * find_next_zero_bit - find the next cleared bit in a memory region 81 * @addr: The address to base the search on 82 * @offset: The bitnumber to start searching at 83 * @size: The bitmap size in bits 84 * 85 * Returns the bit number of the next zero bit 86 * If no bits are zero, returns @size. 87 */ 88static inline 89unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size, 90 unsigned long offset) 91{ 92 if (small_const_nbits(size)) { 93 unsigned long val; 94 95 if (unlikely(offset >= size)) 96 return size; 97 98 val = *addr | ~GENMASK(size - 1, offset); 99 return val == ~0UL ? size : ffz(val); 100 } 101 102 return _find_next_bit(addr, NULL, size, offset, ~0UL, 0); 103} 104#endif 105 106#ifndef find_first_bit 107/** 108 * find_first_bit - find the first set bit in a memory region 109 * @addr: The address to start the search at 110 * @size: The maximum number of bits to search 111 * 112 * Returns the bit number of the first set bit. 113 * If no bits are set, returns @size. 114 */ 115static inline 116unsigned long find_first_bit(const unsigned long *addr, unsigned long size) 117{ 118 if (small_const_nbits(size)) { 119 unsigned long val = *addr & GENMASK(size - 1, 0); 120 121 return val ? __ffs(val) : size; 122 } 123 124 return _find_first_bit(addr, size); 125} 126#endif 127 128#ifndef find_first_and_bit 129/** 130 * find_first_and_bit - find the first set bit in both memory regions 131 * @addr1: The first address to base the search on 132 * @addr2: The second address to base the search on 133 * @size: The bitmap size in bits 134 * 135 * Returns the bit number for the next set bit 136 * If no bits are set, returns @size. 137 */ 138static inline 139unsigned long find_first_and_bit(const unsigned long *addr1, 140 const unsigned long *addr2, 141 unsigned long size) 142{ 143 if (small_const_nbits(size)) { 144 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0); 145 146 return val ? __ffs(val) : size; 147 } 148 149 return _find_first_and_bit(addr1, addr2, size); 150} 151#endif 152 153#ifndef find_first_zero_bit 154/** 155 * find_first_zero_bit - find the first cleared bit in a memory region 156 * @addr: The address to start the search at 157 * @size: The maximum number of bits to search 158 * 159 * Returns the bit number of the first cleared bit. 160 * If no bits are zero, returns @size. 161 */ 162static inline 163unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size) 164{ 165 if (small_const_nbits(size)) { 166 unsigned long val = *addr | ~GENMASK(size - 1, 0); 167 168 return val == ~0UL ? size : ffz(val); 169 } 170 171 return _find_first_zero_bit(addr, size); 172} 173#endif 174 175#ifndef find_last_bit 176/** 177 * find_last_bit - find the last set bit in a memory region 178 * @addr: The address to start the search at 179 * @size: The number of bits to search 180 * 181 * Returns the bit number of the last set bit, or size. 182 */ 183static inline 184unsigned long find_last_bit(const unsigned long *addr, unsigned long size) 185{ 186 if (small_const_nbits(size)) { 187 unsigned long val = *addr & GENMASK(size - 1, 0); 188 189 return val ? __fls(val) : size; 190 } 191 192 return _find_last_bit(addr, size); 193} 194#endif 195 196/** 197 * find_next_clump8 - find next 8-bit clump with set bits in a memory region 198 * @clump: location to store copy of found clump 199 * @addr: address to base the search on 200 * @size: bitmap size in number of bits 201 * @offset: bit offset at which to start searching 202 * 203 * Returns the bit offset for the next set clump; the found clump value is 204 * copied to the location pointed by @clump. If no bits are set, returns @size. 205 */ 206extern unsigned long find_next_clump8(unsigned long *clump, 207 const unsigned long *addr, 208 unsigned long size, unsigned long offset); 209 210#define find_first_clump8(clump, bits, size) \ 211 find_next_clump8((clump), (bits), (size), 0) 212 213 214#endif /*__LINUX_FIND_H_ */