1 /* SPDX-License-Identifier: GPL-2.0 */ 1 /* SPDX-License-Identifier: GPL-2.0 */
2 #ifndef __LINUX_FIND_H_ 2 #ifndef __LINUX_FIND_H_
3 #define __LINUX_FIND_H_ 3 #define __LINUX_FIND_H_
4 4
5 #ifndef __LINUX_BITMAP_H 5 #ifndef __LINUX_BITMAP_H
6 #error only <linux/bitmap.h> can be included d 6 #error only <linux/bitmap.h> can be included directly
7 #endif 7 #endif
8 8
9 #include <linux/bitops.h> 9 #include <linux/bitops.h>
10 10
11 unsigned long _find_next_bit(const unsigned lo 11 unsigned long _find_next_bit(const unsigned long *addr1, unsigned long nbits,
12 unsigned long 12 unsigned long start);
13 unsigned long _find_next_and_bit(const unsigne 13 unsigned long _find_next_and_bit(const unsigned long *addr1, const unsigned long *addr2,
14 unsign 14 unsigned long nbits, unsigned long start);
15 unsigned long _find_next_andnot_bit(const unsi 15 unsigned long _find_next_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
16 unsign 16 unsigned long nbits, unsigned long start);
17 unsigned long _find_next_or_bit(const unsigned 17 unsigned long _find_next_or_bit(const unsigned long *addr1, const unsigned long *addr2,
18 unsign 18 unsigned long nbits, unsigned long start);
19 unsigned long _find_next_zero_bit(const unsign 19 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
20 unsig 20 unsigned long start);
21 extern unsigned long _find_first_bit(const uns 21 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
22 unsigned long __find_nth_bit(const unsigned lo 22 unsigned long __find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n);
23 unsigned long __find_nth_and_bit(const unsigne 23 unsigned long __find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
24 unsigned long 24 unsigned long size, unsigned long n);
25 unsigned long __find_nth_andnot_bit(const unsi 25 unsigned long __find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
26 unsign 26 unsigned long size, unsigned long n);
27 unsigned long __find_nth_and_andnot_bit(const 27 unsigned long __find_nth_and_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
28 const 28 const unsigned long *addr3, unsigned long size,
29 unsign 29 unsigned long n);
30 extern unsigned long _find_first_and_bit(const 30 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
31 const 31 const unsigned long *addr2, unsigned long size);
32 unsigned long _find_first_and_and_bit(const un 32 unsigned long _find_first_and_and_bit(const unsigned long *addr1, const unsigned long *addr2,
33 const un 33 const unsigned long *addr3, unsigned long size);
34 extern unsigned long _find_first_zero_bit(cons 34 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
35 extern unsigned long _find_last_bit(const unsi 35 extern unsigned long _find_last_bit(const unsigned long *addr, unsigned long size);
36 36
37 #ifdef __BIG_ENDIAN 37 #ifdef __BIG_ENDIAN
38 unsigned long _find_first_zero_bit_le(const un 38 unsigned long _find_first_zero_bit_le(const unsigned long *addr, unsigned long size);
39 unsigned long _find_next_zero_bit_le(const un 39 unsigned long _find_next_zero_bit_le(const unsigned long *addr, unsigned
40 long s 40 long size, unsigned long offset);
41 unsigned long _find_next_bit_le(const unsigned 41 unsigned long _find_next_bit_le(const unsigned long *addr, unsigned
42 long size, uns 42 long size, unsigned long offset);
43 #endif 43 #endif
44 44
45 #ifndef find_next_bit 45 #ifndef find_next_bit
46 /** 46 /**
47 * find_next_bit - find the next set bit in a 47 * find_next_bit - find the next set bit in a memory region
48 * @addr: The address to base the search on 48 * @addr: The address to base the search on
49 * @size: The bitmap size in bits 49 * @size: The bitmap size in bits
50 * @offset: The bitnumber to start searching a 50 * @offset: The bitnumber to start searching at
51 * 51 *
52 * Returns the bit number for the next set bit 52 * Returns the bit number for the next set bit
53 * If no bits are set, returns @size. 53 * If no bits are set, returns @size.
54 */ 54 */
55 static inline 55 static inline
56 unsigned long find_next_bit(const unsigned lon 56 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
57 unsigned long offs 57 unsigned long offset)
58 { 58 {
59 if (small_const_nbits(size)) { 59 if (small_const_nbits(size)) {
60 unsigned long val; 60 unsigned long val;
61 61
62 if (unlikely(offset >= size)) 62 if (unlikely(offset >= size))
63 return size; 63 return size;
64 64
65 val = *addr & GENMASK(size - 1 65 val = *addr & GENMASK(size - 1, offset);
66 return val ? __ffs(val) : size 66 return val ? __ffs(val) : size;
67 } 67 }
68 68
69 return _find_next_bit(addr, size, offs 69 return _find_next_bit(addr, size, offset);
70 } 70 }
71 #endif 71 #endif
72 72
73 #ifndef find_next_and_bit 73 #ifndef find_next_and_bit
74 /** 74 /**
75 * find_next_and_bit - find the next set bit i 75 * find_next_and_bit - find the next set bit in both memory regions
76 * @addr1: The first address to base the searc 76 * @addr1: The first address to base the search on
77 * @addr2: The second address to base the sear 77 * @addr2: The second address to base the search on
78 * @size: The bitmap size in bits 78 * @size: The bitmap size in bits
79 * @offset: The bitnumber to start searching a 79 * @offset: The bitnumber to start searching at
80 * 80 *
81 * Returns the bit number for the next set bit 81 * Returns the bit number for the next set bit
82 * If no bits are set, returns @size. 82 * If no bits are set, returns @size.
83 */ 83 */
84 static inline 84 static inline
85 unsigned long find_next_and_bit(const unsigned 85 unsigned long find_next_and_bit(const unsigned long *addr1,
86 const unsigned long *addr2, un 86 const unsigned long *addr2, unsigned long size,
87 unsigned long offset) 87 unsigned long offset)
88 { 88 {
89 if (small_const_nbits(size)) { 89 if (small_const_nbits(size)) {
90 unsigned long val; 90 unsigned long val;
91 91
92 if (unlikely(offset >= size)) 92 if (unlikely(offset >= size))
93 return size; 93 return size;
94 94
95 val = *addr1 & *addr2 & GENMAS 95 val = *addr1 & *addr2 & GENMASK(size - 1, offset);
96 return val ? __ffs(val) : size 96 return val ? __ffs(val) : size;
97 } 97 }
98 98
99 return _find_next_and_bit(addr1, addr2 99 return _find_next_and_bit(addr1, addr2, size, offset);
100 } 100 }
101 #endif 101 #endif
102 102
103 #ifndef find_next_andnot_bit 103 #ifndef find_next_andnot_bit
104 /** 104 /**
105 * find_next_andnot_bit - find the next set bi 105 * find_next_andnot_bit - find the next set bit in *addr1 excluding all the bits
106 * in *addr2 106 * in *addr2
107 * @addr1: The first address to base the searc 107 * @addr1: The first address to base the search on
108 * @addr2: The second address to base the sear 108 * @addr2: The second address to base the search on
109 * @size: The bitmap size in bits 109 * @size: The bitmap size in bits
110 * @offset: The bitnumber to start searching a 110 * @offset: The bitnumber to start searching at
111 * 111 *
112 * Returns the bit number for the next set bit 112 * Returns the bit number for the next set bit
113 * If no bits are set, returns @size. 113 * If no bits are set, returns @size.
114 */ 114 */
115 static inline 115 static inline
116 unsigned long find_next_andnot_bit(const unsig 116 unsigned long find_next_andnot_bit(const unsigned long *addr1,
117 const unsigned long *addr2, un 117 const unsigned long *addr2, unsigned long size,
118 unsigned long offset) 118 unsigned long offset)
119 { 119 {
120 if (small_const_nbits(size)) { 120 if (small_const_nbits(size)) {
121 unsigned long val; 121 unsigned long val;
122 122
123 if (unlikely(offset >= size)) 123 if (unlikely(offset >= size))
124 return size; 124 return size;
125 125
126 val = *addr1 & ~*addr2 & GENMA 126 val = *addr1 & ~*addr2 & GENMASK(size - 1, offset);
127 return val ? __ffs(val) : size 127 return val ? __ffs(val) : size;
128 } 128 }
129 129
130 return _find_next_andnot_bit(addr1, ad 130 return _find_next_andnot_bit(addr1, addr2, size, offset);
131 } 131 }
132 #endif 132 #endif
133 133
134 #ifndef find_next_or_bit 134 #ifndef find_next_or_bit
135 /** 135 /**
136 * find_next_or_bit - find the next set bit in 136 * find_next_or_bit - find the next set bit in either memory regions
137 * @addr1: The first address to base the searc 137 * @addr1: The first address to base the search on
138 * @addr2: The second address to base the sear 138 * @addr2: The second address to base the search on
139 * @size: The bitmap size in bits 139 * @size: The bitmap size in bits
140 * @offset: The bitnumber to start searching a 140 * @offset: The bitnumber to start searching at
141 * 141 *
142 * Returns the bit number for the next set bit 142 * Returns the bit number for the next set bit
143 * If no bits are set, returns @size. 143 * If no bits are set, returns @size.
144 */ 144 */
145 static inline 145 static inline
146 unsigned long find_next_or_bit(const unsigned 146 unsigned long find_next_or_bit(const unsigned long *addr1,
147 const unsigned long *addr2, un 147 const unsigned long *addr2, unsigned long size,
148 unsigned long offset) 148 unsigned long offset)
149 { 149 {
150 if (small_const_nbits(size)) { 150 if (small_const_nbits(size)) {
151 unsigned long val; 151 unsigned long val;
152 152
153 if (unlikely(offset >= size)) 153 if (unlikely(offset >= size))
154 return size; 154 return size;
155 155
156 val = (*addr1 | *addr2) & GENM 156 val = (*addr1 | *addr2) & GENMASK(size - 1, offset);
157 return val ? __ffs(val) : size 157 return val ? __ffs(val) : size;
158 } 158 }
159 159
160 return _find_next_or_bit(addr1, addr2, 160 return _find_next_or_bit(addr1, addr2, size, offset);
161 } 161 }
162 #endif 162 #endif
163 163
164 #ifndef find_next_zero_bit 164 #ifndef find_next_zero_bit
165 /** 165 /**
166 * find_next_zero_bit - find the next cleared 166 * find_next_zero_bit - find the next cleared bit in a memory region
167 * @addr: The address to base the search on 167 * @addr: The address to base the search on
168 * @size: The bitmap size in bits 168 * @size: The bitmap size in bits
169 * @offset: The bitnumber to start searching a 169 * @offset: The bitnumber to start searching at
170 * 170 *
171 * Returns the bit number of the next zero bit 171 * Returns the bit number of the next zero bit
172 * If no bits are zero, returns @size. 172 * If no bits are zero, returns @size.
173 */ 173 */
174 static inline 174 static inline
175 unsigned long find_next_zero_bit(const unsigne 175 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
176 unsigned long 176 unsigned long offset)
177 { 177 {
178 if (small_const_nbits(size)) { 178 if (small_const_nbits(size)) {
179 unsigned long val; 179 unsigned long val;
180 180
181 if (unlikely(offset >= size)) 181 if (unlikely(offset >= size))
182 return size; 182 return size;
183 183
184 val = *addr | ~GENMASK(size - 184 val = *addr | ~GENMASK(size - 1, offset);
185 return val == ~0UL ? size : ff 185 return val == ~0UL ? size : ffz(val);
186 } 186 }
187 187
188 return _find_next_zero_bit(addr, size, 188 return _find_next_zero_bit(addr, size, offset);
189 } 189 }
190 #endif 190 #endif
191 191
192 #ifndef find_first_bit 192 #ifndef find_first_bit
193 /** 193 /**
194 * find_first_bit - find the first set bit in 194 * find_first_bit - find the first set bit in a memory region
195 * @addr: The address to start the search at 195 * @addr: The address to start the search at
196 * @size: The maximum number of bits to search 196 * @size: The maximum number of bits to search
197 * 197 *
198 * Returns the bit number of the first set bit 198 * Returns the bit number of the first set bit.
199 * If no bits are set, returns @size. 199 * If no bits are set, returns @size.
200 */ 200 */
201 static inline 201 static inline
202 unsigned long find_first_bit(const unsigned lo 202 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
203 { 203 {
204 if (small_const_nbits(size)) { 204 if (small_const_nbits(size)) {
205 unsigned long val = *addr & GE 205 unsigned long val = *addr & GENMASK(size - 1, 0);
206 206
207 return val ? __ffs(val) : size 207 return val ? __ffs(val) : size;
208 } 208 }
209 209
210 return _find_first_bit(addr, size); 210 return _find_first_bit(addr, size);
211 } 211 }
212 #endif 212 #endif
213 213
214 /** 214 /**
215 * find_nth_bit - find N'th set bit in a memor 215 * find_nth_bit - find N'th set bit in a memory region
216 * @addr: The address to start the search at 216 * @addr: The address to start the search at
217 * @size: The maximum number of bits to search 217 * @size: The maximum number of bits to search
218 * @n: The number of set bit, which position i 218 * @n: The number of set bit, which position is needed, counting from 0
219 * 219 *
220 * The following is semantically equivalent: 220 * The following is semantically equivalent:
221 * idx = find_nth_bit(addr, size, 0); 221 * idx = find_nth_bit(addr, size, 0);
222 * idx = find_first_bit(addr, size); 222 * idx = find_first_bit(addr, size);
223 * 223 *
224 * Returns the bit number of the N'th set bit. 224 * Returns the bit number of the N'th set bit.
225 * If no such, returns >= @size. 225 * If no such, returns >= @size.
226 */ 226 */
227 static inline 227 static inline
228 unsigned long find_nth_bit(const unsigned long 228 unsigned long find_nth_bit(const unsigned long *addr, unsigned long size, unsigned long n)
229 { 229 {
230 if (n >= size) 230 if (n >= size)
231 return size; 231 return size;
232 232
233 if (small_const_nbits(size)) { 233 if (small_const_nbits(size)) {
234 unsigned long val = *addr & G 234 unsigned long val = *addr & GENMASK(size - 1, 0);
235 235
236 return val ? fns(val, n) : siz 236 return val ? fns(val, n) : size;
237 } 237 }
238 238
239 return __find_nth_bit(addr, size, n); 239 return __find_nth_bit(addr, size, n);
240 } 240 }
241 241
242 /** 242 /**
243 * find_nth_and_bit - find N'th set bit in 2 m 243 * find_nth_and_bit - find N'th set bit in 2 memory regions
244 * @addr1: The 1st address to start the search 244 * @addr1: The 1st address to start the search at
245 * @addr2: The 2nd address to start the search 245 * @addr2: The 2nd address to start the search at
246 * @size: The maximum number of bits to search 246 * @size: The maximum number of bits to search
247 * @n: The number of set bit, which position i 247 * @n: The number of set bit, which position is needed, counting from 0
248 * 248 *
249 * Returns the bit number of the N'th set bit. 249 * Returns the bit number of the N'th set bit.
250 * If no such, returns @size. 250 * If no such, returns @size.
251 */ 251 */
252 static inline 252 static inline
253 unsigned long find_nth_and_bit(const unsigned 253 unsigned long find_nth_and_bit(const unsigned long *addr1, const unsigned long *addr2,
254 unsigned long 254 unsigned long size, unsigned long n)
255 { 255 {
256 if (n >= size) 256 if (n >= size)
257 return size; 257 return size;
258 258
259 if (small_const_nbits(size)) { 259 if (small_const_nbits(size)) {
260 unsigned long val = *addr1 & 260 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
261 261
262 return val ? fns(val, n) : siz 262 return val ? fns(val, n) : size;
263 } 263 }
264 264
265 return __find_nth_and_bit(addr1, addr2 265 return __find_nth_and_bit(addr1, addr2, size, n);
266 } 266 }
267 267
268 /** 268 /**
269 * find_nth_andnot_bit - find N'th set bit in 269 * find_nth_andnot_bit - find N'th set bit in 2 memory regions,
270 * flipping bits in 2nd 270 * flipping bits in 2nd region
271 * @addr1: The 1st address to start the search 271 * @addr1: The 1st address to start the search at
272 * @addr2: The 2nd address to start the search 272 * @addr2: The 2nd address to start the search at
273 * @size: The maximum number of bits to search 273 * @size: The maximum number of bits to search
274 * @n: The number of set bit, which position i 274 * @n: The number of set bit, which position is needed, counting from 0
275 * 275 *
276 * Returns the bit number of the N'th set bit. 276 * Returns the bit number of the N'th set bit.
277 * If no such, returns @size. 277 * If no such, returns @size.
278 */ 278 */
279 static inline 279 static inline
280 unsigned long find_nth_andnot_bit(const unsign 280 unsigned long find_nth_andnot_bit(const unsigned long *addr1, const unsigned long *addr2,
281 unsigned long 281 unsigned long size, unsigned long n)
282 { 282 {
283 if (n >= size) 283 if (n >= size)
284 return size; 284 return size;
285 285
286 if (small_const_nbits(size)) { 286 if (small_const_nbits(size)) {
287 unsigned long val = *addr1 & 287 unsigned long val = *addr1 & (~*addr2) & GENMASK(size - 1, 0);
288 288
289 return val ? fns(val, n) : siz 289 return val ? fns(val, n) : size;
290 } 290 }
291 291
292 return __find_nth_andnot_bit(addr1, ad 292 return __find_nth_andnot_bit(addr1, addr2, size, n);
293 } 293 }
294 294
295 /** 295 /**
296 * find_nth_and_andnot_bit - find N'th set bit 296 * find_nth_and_andnot_bit - find N'th set bit in 2 memory regions,
297 * excluding those s 297 * excluding those set in 3rd region
298 * @addr1: The 1st address to start the search 298 * @addr1: The 1st address to start the search at
299 * @addr2: The 2nd address to start the search 299 * @addr2: The 2nd address to start the search at
300 * @addr3: The 3rd address to start the search 300 * @addr3: The 3rd address to start the search at
301 * @size: The maximum number of bits to search 301 * @size: The maximum number of bits to search
302 * @n: The number of set bit, which position i 302 * @n: The number of set bit, which position is needed, counting from 0
303 * 303 *
304 * Returns the bit number of the N'th set bit. 304 * Returns the bit number of the N'th set bit.
305 * If no such, returns @size. 305 * If no such, returns @size.
306 */ 306 */
307 static __always_inline 307 static __always_inline
308 unsigned long find_nth_and_andnot_bit(const un 308 unsigned long find_nth_and_andnot_bit(const unsigned long *addr1,
309 const 309 const unsigned long *addr2,
310 const 310 const unsigned long *addr3,
311 unsign 311 unsigned long size, unsigned long n)
312 { 312 {
313 if (n >= size) 313 if (n >= size)
314 return size; 314 return size;
315 315
316 if (small_const_nbits(size)) { 316 if (small_const_nbits(size)) {
317 unsigned long val = *addr1 & 317 unsigned long val = *addr1 & *addr2 & (~*addr3) & GENMASK(size - 1, 0);
318 318
319 return val ? fns(val, n) : siz 319 return val ? fns(val, n) : size;
320 } 320 }
321 321
322 return __find_nth_and_andnot_bit(addr1 322 return __find_nth_and_andnot_bit(addr1, addr2, addr3, size, n);
323 } 323 }
324 324
325 #ifndef find_first_and_bit 325 #ifndef find_first_and_bit
326 /** 326 /**
327 * find_first_and_bit - find the first set bit 327 * find_first_and_bit - find the first set bit in both memory regions
328 * @addr1: The first address to base the searc 328 * @addr1: The first address to base the search on
329 * @addr2: The second address to base the sear 329 * @addr2: The second address to base the search on
330 * @size: The bitmap size in bits 330 * @size: The bitmap size in bits
331 * 331 *
332 * Returns the bit number for the next set bit 332 * Returns the bit number for the next set bit
333 * If no bits are set, returns @size. 333 * If no bits are set, returns @size.
334 */ 334 */
335 static inline 335 static inline
336 unsigned long find_first_and_bit(const unsigne 336 unsigned long find_first_and_bit(const unsigned long *addr1,
337 const unsigne 337 const unsigned long *addr2,
338 unsigned long 338 unsigned long size)
339 { 339 {
340 if (small_const_nbits(size)) { 340 if (small_const_nbits(size)) {
341 unsigned long val = *addr1 & * 341 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
342 342
343 return val ? __ffs(val) : size 343 return val ? __ffs(val) : size;
344 } 344 }
345 345
346 return _find_first_and_bit(addr1, addr 346 return _find_first_and_bit(addr1, addr2, size);
347 } 347 }
348 #endif 348 #endif
349 349
350 /** 350 /**
351 * find_first_and_and_bit - find the first set 351 * find_first_and_and_bit - find the first set bit in 3 memory regions
352 * @addr1: The first address to base the searc 352 * @addr1: The first address to base the search on
353 * @addr2: The second address to base the sear 353 * @addr2: The second address to base the search on
354 * @addr3: The third address to base the searc 354 * @addr3: The third address to base the search on
355 * @size: The bitmap size in bits 355 * @size: The bitmap size in bits
356 * 356 *
357 * Returns the bit number for the first set bi 357 * Returns the bit number for the first set bit
358 * If no bits are set, returns @size. 358 * If no bits are set, returns @size.
359 */ 359 */
360 static inline 360 static inline
361 unsigned long find_first_and_and_bit(const uns 361 unsigned long find_first_and_and_bit(const unsigned long *addr1,
362 const uns 362 const unsigned long *addr2,
363 const uns 363 const unsigned long *addr3,
364 unsigned 364 unsigned long size)
365 { 365 {
366 if (small_const_nbits(size)) { 366 if (small_const_nbits(size)) {
367 unsigned long val = *addr1 & * 367 unsigned long val = *addr1 & *addr2 & *addr3 & GENMASK(size - 1, 0);
368 368
369 return val ? __ffs(val) : size 369 return val ? __ffs(val) : size;
370 } 370 }
371 371
372 return _find_first_and_and_bit(addr1, 372 return _find_first_and_and_bit(addr1, addr2, addr3, size);
373 } 373 }
374 374
375 #ifndef find_first_zero_bit 375 #ifndef find_first_zero_bit
376 /** 376 /**
377 * find_first_zero_bit - find the first cleare 377 * find_first_zero_bit - find the first cleared bit in a memory region
378 * @addr: The address to start the search at 378 * @addr: The address to start the search at
379 * @size: The maximum number of bits to search 379 * @size: The maximum number of bits to search
380 * 380 *
381 * Returns the bit number of the first cleared 381 * Returns the bit number of the first cleared bit.
382 * If no bits are zero, returns @size. 382 * If no bits are zero, returns @size.
383 */ 383 */
384 static inline 384 static inline
385 unsigned long find_first_zero_bit(const unsign 385 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
386 { 386 {
387 if (small_const_nbits(size)) { 387 if (small_const_nbits(size)) {
388 unsigned long val = *addr | ~G 388 unsigned long val = *addr | ~GENMASK(size - 1, 0);
389 389
390 return val == ~0UL ? size : ff 390 return val == ~0UL ? size : ffz(val);
391 } 391 }
392 392
393 return _find_first_zero_bit(addr, size 393 return _find_first_zero_bit(addr, size);
394 } 394 }
395 #endif 395 #endif
396 396
397 #ifndef find_last_bit 397 #ifndef find_last_bit
398 /** 398 /**
399 * find_last_bit - find the last set bit in a 399 * find_last_bit - find the last set bit in a memory region
400 * @addr: The address to start the search at 400 * @addr: The address to start the search at
401 * @size: The number of bits to search 401 * @size: The number of bits to search
402 * 402 *
403 * Returns the bit number of the last set bit, 403 * Returns the bit number of the last set bit, or size.
404 */ 404 */
405 static inline 405 static inline
406 unsigned long find_last_bit(const unsigned lon 406 unsigned long find_last_bit(const unsigned long *addr, unsigned long size)
407 { 407 {
408 if (small_const_nbits(size)) { 408 if (small_const_nbits(size)) {
409 unsigned long val = *addr & GE 409 unsigned long val = *addr & GENMASK(size - 1, 0);
410 410
411 return val ? __fls(val) : size 411 return val ? __fls(val) : size;
412 } 412 }
413 413
414 return _find_last_bit(addr, size); 414 return _find_last_bit(addr, size);
415 } 415 }
416 #endif 416 #endif
417 417
418 /** 418 /**
419 * find_next_and_bit_wrap - find the next set 419 * find_next_and_bit_wrap - find the next set bit in both memory regions
420 * @addr1: The first address to base the searc 420 * @addr1: The first address to base the search on
421 * @addr2: The second address to base the sear 421 * @addr2: The second address to base the search on
422 * @size: The bitmap size in bits 422 * @size: The bitmap size in bits
423 * @offset: The bitnumber to start searching a 423 * @offset: The bitnumber to start searching at
424 * 424 *
425 * Returns the bit number for the next set bit 425 * Returns the bit number for the next set bit, or first set bit up to @offset
426 * If no bits are set, returns @size. 426 * If no bits are set, returns @size.
427 */ 427 */
428 static inline 428 static inline
429 unsigned long find_next_and_bit_wrap(const uns 429 unsigned long find_next_and_bit_wrap(const unsigned long *addr1,
430 const 430 const unsigned long *addr2,
431 unsign 431 unsigned long size, unsigned long offset)
432 { 432 {
433 unsigned long bit = find_next_and_bit( 433 unsigned long bit = find_next_and_bit(addr1, addr2, size, offset);
434 434
435 if (bit < size || offset == 0) 435 if (bit < size || offset == 0)
436 return bit; 436 return bit;
437 437
438 bit = find_first_and_bit(addr1, addr2, 438 bit = find_first_and_bit(addr1, addr2, offset);
439 return bit < offset ? bit : size; 439 return bit < offset ? bit : size;
440 } 440 }
441 441
442 /** 442 /**
443 * find_next_bit_wrap - find the next set bit 443 * find_next_bit_wrap - find the next set bit in a memory region
444 * @addr: The address to base the search on 444 * @addr: The address to base the search on
445 * @size: The bitmap size in bits 445 * @size: The bitmap size in bits
446 * @offset: The bitnumber to start searching a 446 * @offset: The bitnumber to start searching at
447 * 447 *
448 * Returns the bit number for the next set bit 448 * Returns the bit number for the next set bit, or first set bit up to @offset
449 * If no bits are set, returns @size. 449 * If no bits are set, returns @size.
450 */ 450 */
451 static inline 451 static inline
452 unsigned long find_next_bit_wrap(const unsigne 452 unsigned long find_next_bit_wrap(const unsigned long *addr,
453 unsign 453 unsigned long size, unsigned long offset)
454 { 454 {
455 unsigned long bit = find_next_bit(addr 455 unsigned long bit = find_next_bit(addr, size, offset);
456 456
457 if (bit < size || offset == 0) 457 if (bit < size || offset == 0)
458 return bit; 458 return bit;
459 459
460 bit = find_first_bit(addr, offset); 460 bit = find_first_bit(addr, offset);
461 return bit < offset ? bit : size; 461 return bit < offset ? bit : size;
462 } 462 }
463 463
464 /* 464 /*
465 * Helper for for_each_set_bit_wrap(). Make su 465 * Helper for for_each_set_bit_wrap(). Make sure you're doing right thing
466 * before using it alone. 466 * before using it alone.
467 */ 467 */
468 static inline 468 static inline
469 unsigned long __for_each_wrap(const unsigned l 469 unsigned long __for_each_wrap(const unsigned long *bitmap, unsigned long size,
470 unsigned long 470 unsigned long start, unsigned long n)
471 { 471 {
472 unsigned long bit; 472 unsigned long bit;
473 473
474 /* If not wrapped around */ 474 /* If not wrapped around */
475 if (n > start) { 475 if (n > start) {
476 /* and have a bit, just return 476 /* and have a bit, just return it. */
477 bit = find_next_bit(bitmap, si 477 bit = find_next_bit(bitmap, size, n);
478 if (bit < size) 478 if (bit < size)
479 return bit; 479 return bit;
480 480
481 /* Otherwise, wrap around and 481 /* Otherwise, wrap around and ... */
482 n = 0; 482 n = 0;
483 } 483 }
484 484
485 /* Search the other part. */ 485 /* Search the other part. */
486 bit = find_next_bit(bitmap, start, n); 486 bit = find_next_bit(bitmap, start, n);
487 return bit < start ? bit : size; 487 return bit < start ? bit : size;
488 } 488 }
489 489
490 /** 490 /**
491 * find_next_clump8 - find next 8-bit clump wi 491 * find_next_clump8 - find next 8-bit clump with set bits in a memory region
492 * @clump: location to store copy of found clu 492 * @clump: location to store copy of found clump
493 * @addr: address to base the search on 493 * @addr: address to base the search on
494 * @size: bitmap size in number of bits 494 * @size: bitmap size in number of bits
495 * @offset: bit offset at which to start searc 495 * @offset: bit offset at which to start searching
496 * 496 *
497 * Returns the bit offset for the next set clu 497 * Returns the bit offset for the next set clump; the found clump value is
498 * copied to the location pointed by @clump. I 498 * copied to the location pointed by @clump. If no bits are set, returns @size.
499 */ 499 */
500 extern unsigned long find_next_clump8(unsigned 500 extern unsigned long find_next_clump8(unsigned long *clump,
501 const un 501 const unsigned long *addr,
502 unsigned 502 unsigned long size, unsigned long offset);
503 503
504 #define find_first_clump8(clump, bits, size) \ 504 #define find_first_clump8(clump, bits, size) \
505 find_next_clump8((clump), (bits), (siz 505 find_next_clump8((clump), (bits), (size), 0)
506 506
507 #if defined(__LITTLE_ENDIAN) 507 #if defined(__LITTLE_ENDIAN)
508 508
509 static inline unsigned long find_next_zero_bit 509 static inline unsigned long find_next_zero_bit_le(const void *addr,
510 unsigned long size, unsigned l 510 unsigned long size, unsigned long offset)
511 { 511 {
512 return find_next_zero_bit(addr, size, 512 return find_next_zero_bit(addr, size, offset);
513 } 513 }
514 514
515 static inline unsigned long find_next_bit_le(c 515 static inline unsigned long find_next_bit_le(const void *addr,
516 unsigned long size, unsigned l 516 unsigned long size, unsigned long offset)
517 { 517 {
518 return find_next_bit(addr, size, offse 518 return find_next_bit(addr, size, offset);
519 } 519 }
520 520
521 static inline unsigned long find_first_zero_bi 521 static inline unsigned long find_first_zero_bit_le(const void *addr,
522 unsigned long size) 522 unsigned long size)
523 { 523 {
524 return find_first_zero_bit(addr, size) 524 return find_first_zero_bit(addr, size);
525 } 525 }
526 526
527 #elif defined(__BIG_ENDIAN) 527 #elif defined(__BIG_ENDIAN)
528 528
529 #ifndef find_next_zero_bit_le 529 #ifndef find_next_zero_bit_le
530 static inline 530 static inline
531 unsigned long find_next_zero_bit_le(const void 531 unsigned long find_next_zero_bit_le(const void *addr, unsigned
532 long size, unsigned long offse 532 long size, unsigned long offset)
533 { 533 {
534 if (small_const_nbits(size)) { 534 if (small_const_nbits(size)) {
535 unsigned long val = *(const un 535 unsigned long val = *(const unsigned long *)addr;
536 536
537 if (unlikely(offset >= size)) 537 if (unlikely(offset >= size))
538 return size; 538 return size;
539 539
540 val = swab(val) | ~GENMASK(siz 540 val = swab(val) | ~GENMASK(size - 1, offset);
541 return val == ~0UL ? size : ff 541 return val == ~0UL ? size : ffz(val);
542 } 542 }
543 543
544 return _find_next_zero_bit_le(addr, si 544 return _find_next_zero_bit_le(addr, size, offset);
545 } 545 }
546 #endif 546 #endif
547 547
548 #ifndef find_first_zero_bit_le 548 #ifndef find_first_zero_bit_le
549 static inline 549 static inline
550 unsigned long find_first_zero_bit_le(const voi 550 unsigned long find_first_zero_bit_le(const void *addr, unsigned long size)
551 { 551 {
552 if (small_const_nbits(size)) { 552 if (small_const_nbits(size)) {
553 unsigned long val = swab(*(con 553 unsigned long val = swab(*(const unsigned long *)addr) | ~GENMASK(size - 1, 0);
554 554
555 return val == ~0UL ? size : ff 555 return val == ~0UL ? size : ffz(val);
556 } 556 }
557 557
558 return _find_first_zero_bit_le(addr, s 558 return _find_first_zero_bit_le(addr, size);
559 } 559 }
560 #endif 560 #endif
561 561
562 #ifndef find_next_bit_le 562 #ifndef find_next_bit_le
563 static inline 563 static inline
564 unsigned long find_next_bit_le(const void *add 564 unsigned long find_next_bit_le(const void *addr, unsigned
565 long size, unsigned long offse 565 long size, unsigned long offset)
566 { 566 {
567 if (small_const_nbits(size)) { 567 if (small_const_nbits(size)) {
568 unsigned long val = *(const un 568 unsigned long val = *(const unsigned long *)addr;
569 569
570 if (unlikely(offset >= size)) 570 if (unlikely(offset >= size))
571 return size; 571 return size;
572 572
573 val = swab(val) & GENMASK(size 573 val = swab(val) & GENMASK(size - 1, offset);
574 return val ? __ffs(val) : size 574 return val ? __ffs(val) : size;
575 } 575 }
576 576
577 return _find_next_bit_le(addr, size, o 577 return _find_next_bit_le(addr, size, offset);
578 } 578 }
579 #endif 579 #endif
580 580
581 #else 581 #else
582 #error "Please fix <asm/byteorder.h>" 582 #error "Please fix <asm/byteorder.h>"
583 #endif 583 #endif
584 584
585 #define for_each_set_bit(bit, addr, size) \ 585 #define for_each_set_bit(bit, addr, size) \
586 for ((bit) = 0; (bit) = find_next_bit( 586 for ((bit) = 0; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
587 587
588 #define for_each_and_bit(bit, addr1, addr2, si 588 #define for_each_and_bit(bit, addr1, addr2, size) \
589 for ((bit) = 0; 589 for ((bit) = 0; \
590 (bit) = find_next_and_bit((addr1) 590 (bit) = find_next_and_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
591 (bit)++) 591 (bit)++)
592 592
593 #define for_each_andnot_bit(bit, addr1, addr2, 593 #define for_each_andnot_bit(bit, addr1, addr2, size) \
594 for ((bit) = 0; 594 for ((bit) = 0; \
595 (bit) = find_next_andnot_bit((add 595 (bit) = find_next_andnot_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
596 (bit)++) 596 (bit)++)
597 597
598 #define for_each_or_bit(bit, addr1, addr2, siz 598 #define for_each_or_bit(bit, addr1, addr2, size) \
599 for ((bit) = 0; 599 for ((bit) = 0; \
600 (bit) = find_next_or_bit((addr1), 600 (bit) = find_next_or_bit((addr1), (addr2), (size), (bit)), (bit) < (size);\
601 (bit)++) 601 (bit)++)
602 602
603 /* same as for_each_set_bit() but use bit as v 603 /* same as for_each_set_bit() but use bit as value to start with */
604 #define for_each_set_bit_from(bit, addr, size) 604 #define for_each_set_bit_from(bit, addr, size) \
605 for (; (bit) = find_next_bit((addr), ( 605 for (; (bit) = find_next_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
606 606
607 #define for_each_clear_bit(bit, addr, size) \ 607 #define for_each_clear_bit(bit, addr, size) \
608 for ((bit) = 0; 608 for ((bit) = 0; \
609 (bit) = find_next_zero_bit((addr) 609 (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); \
610 (bit)++) 610 (bit)++)
611 611
612 /* same as for_each_clear_bit() but use bit as 612 /* same as for_each_clear_bit() but use bit as value to start with */
613 #define for_each_clear_bit_from(bit, addr, siz 613 #define for_each_clear_bit_from(bit, addr, size) \
614 for (; (bit) = find_next_zero_bit((add 614 for (; (bit) = find_next_zero_bit((addr), (size), (bit)), (bit) < (size); (bit)++)
615 615
616 /** 616 /**
617 * for_each_set_bitrange - iterate over all se 617 * for_each_set_bitrange - iterate over all set bit ranges [b; e)
618 * @b: bit offset of start of current bitrange 618 * @b: bit offset of start of current bitrange (first set bit)
619 * @e: bit offset of end of current bitrange ( 619 * @e: bit offset of end of current bitrange (first unset bit)
620 * @addr: bitmap address to base the search on 620 * @addr: bitmap address to base the search on
621 * @size: bitmap size in number of bits 621 * @size: bitmap size in number of bits
622 */ 622 */
623 #define for_each_set_bitrange(b, e, addr, size 623 #define for_each_set_bitrange(b, e, addr, size) \
624 for ((b) = 0; 624 for ((b) = 0; \
625 (b) = find_next_bit((addr), (size 625 (b) = find_next_bit((addr), (size), b), \
626 (e) = find_next_zero_bit((addr), 626 (e) = find_next_zero_bit((addr), (size), (b) + 1), \
627 (b) < (size); 627 (b) < (size); \
628 (b) = (e) + 1) 628 (b) = (e) + 1)
629 629
630 /** 630 /**
631 * for_each_set_bitrange_from - iterate over a 631 * for_each_set_bitrange_from - iterate over all set bit ranges [b; e)
632 * @b: bit offset of start of current bitrange 632 * @b: bit offset of start of current bitrange (first set bit); must be initialized
633 * @e: bit offset of end of current bitrange ( 633 * @e: bit offset of end of current bitrange (first unset bit)
634 * @addr: bitmap address to base the search on 634 * @addr: bitmap address to base the search on
635 * @size: bitmap size in number of bits 635 * @size: bitmap size in number of bits
636 */ 636 */
637 #define for_each_set_bitrange_from(b, e, addr, 637 #define for_each_set_bitrange_from(b, e, addr, size) \
638 for (; 638 for (; \
639 (b) = find_next_bit((addr), (size 639 (b) = find_next_bit((addr), (size), (b)), \
640 (e) = find_next_zero_bit((addr), 640 (e) = find_next_zero_bit((addr), (size), (b) + 1), \
641 (b) < (size); 641 (b) < (size); \
642 (b) = (e) + 1) 642 (b) = (e) + 1)
643 643
644 /** 644 /**
645 * for_each_clear_bitrange - iterate over all 645 * for_each_clear_bitrange - iterate over all unset bit ranges [b; e)
646 * @b: bit offset of start of current bitrange 646 * @b: bit offset of start of current bitrange (first unset bit)
647 * @e: bit offset of end of current bitrange ( 647 * @e: bit offset of end of current bitrange (first set bit)
648 * @addr: bitmap address to base the search on 648 * @addr: bitmap address to base the search on
649 * @size: bitmap size in number of bits 649 * @size: bitmap size in number of bits
650 */ 650 */
651 #define for_each_clear_bitrange(b, e, addr, si 651 #define for_each_clear_bitrange(b, e, addr, size) \
652 for ((b) = 0; 652 for ((b) = 0; \
653 (b) = find_next_zero_bit((addr), 653 (b) = find_next_zero_bit((addr), (size), (b)), \
654 (e) = find_next_bit((addr), (size 654 (e) = find_next_bit((addr), (size), (b) + 1), \
655 (b) < (size); 655 (b) < (size); \
656 (b) = (e) + 1) 656 (b) = (e) + 1)
657 657
658 /** 658 /**
659 * for_each_clear_bitrange_from - iterate over 659 * for_each_clear_bitrange_from - iterate over all unset bit ranges [b; e)
660 * @b: bit offset of start of current bitrange 660 * @b: bit offset of start of current bitrange (first set bit); must be initialized
661 * @e: bit offset of end of current bitrange ( 661 * @e: bit offset of end of current bitrange (first unset bit)
662 * @addr: bitmap address to base the search on 662 * @addr: bitmap address to base the search on
663 * @size: bitmap size in number of bits 663 * @size: bitmap size in number of bits
664 */ 664 */
665 #define for_each_clear_bitrange_from(b, e, add 665 #define for_each_clear_bitrange_from(b, e, addr, size) \
666 for (; 666 for (; \
667 (b) = find_next_zero_bit((addr), 667 (b) = find_next_zero_bit((addr), (size), (b)), \
668 (e) = find_next_bit((addr), (size 668 (e) = find_next_bit((addr), (size), (b) + 1), \
669 (b) < (size); 669 (b) < (size); \
670 (b) = (e) + 1) 670 (b) = (e) + 1)
671 671
672 /** 672 /**
673 * for_each_set_bit_wrap - iterate over all se 673 * for_each_set_bit_wrap - iterate over all set bits starting from @start, and
674 * wrapping around the end of bitmap. 674 * wrapping around the end of bitmap.
675 * @bit: offset for current iteration 675 * @bit: offset for current iteration
676 * @addr: bitmap address to base the search on 676 * @addr: bitmap address to base the search on
677 * @size: bitmap size in number of bits 677 * @size: bitmap size in number of bits
678 * @start: Starting bit for bitmap traversing, 678 * @start: Starting bit for bitmap traversing, wrapping around the bitmap end
679 */ 679 */
680 #define for_each_set_bit_wrap(bit, addr, size, 680 #define for_each_set_bit_wrap(bit, addr, size, start) \
681 for ((bit) = find_next_bit_wrap((addr) 681 for ((bit) = find_next_bit_wrap((addr), (size), (start)); \
682 (bit) < (size); 682 (bit) < (size); \
683 (bit) = __for_each_wrap((addr), ( 683 (bit) = __for_each_wrap((addr), (size), (start), (bit) + 1))
684 684
685 /** 685 /**
686 * for_each_set_clump8 - iterate over bitmap f 686 * for_each_set_clump8 - iterate over bitmap for each 8-bit clump with set bits
687 * @start: bit offset to start search and to s 687 * @start: bit offset to start search and to store the current iteration offset
688 * @clump: location to store copy of current 8 688 * @clump: location to store copy of current 8-bit clump
689 * @bits: bitmap address to base the search on 689 * @bits: bitmap address to base the search on
690 * @size: bitmap size in number of bits 690 * @size: bitmap size in number of bits
691 */ 691 */
692 #define for_each_set_clump8(start, clump, bits 692 #define for_each_set_clump8(start, clump, bits, size) \
693 for ((start) = find_first_clump8(&(clu 693 for ((start) = find_first_clump8(&(clump), (bits), (size)); \
694 (start) < (size); \ 694 (start) < (size); \
695 (start) = find_next_clump8(&(clum 695 (start) = find_next_clump8(&(clump), (bits), (size), (start) + 8))
696 696
697 #endif /*__LINUX_FIND_H_ */ 697 #endif /*__LINUX_FIND_H_ */
698 698
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.