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