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