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