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 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_zero_bit(const unsign 15 unsigned long _find_next_zero_bit(const unsigned long *addr, unsigned long nbits,
16 unsig 16 unsigned long start);
17 extern unsigned long _find_first_bit(const uns 17 extern unsigned long _find_first_bit(const unsigned long *addr, unsigned long size);
18 extern unsigned long _find_first_and_bit(const 18 extern unsigned long _find_first_and_bit(const unsigned long *addr1,
19 const 19 const unsigned long *addr2, unsigned long size);
20 extern unsigned long _find_first_zero_bit(cons 20 extern unsigned long _find_first_zero_bit(const unsigned long *addr, unsigned long size);
21 21
22 #ifndef find_next_bit 22 #ifndef find_next_bit
23 /** 23 /**
24 * find_next_bit - find the next set bit in a 24 * find_next_bit - find the next set bit in a memory region
25 * @addr: The address to base the search on 25 * @addr: The address to base the search on
26 * @size: The bitmap size in bits 26 * @size: The bitmap size in bits
27 * @offset: The bitnumber to start searching a 27 * @offset: The bitnumber to start searching at
28 * 28 *
29 * Returns the bit number for the next set bit 29 * Returns the bit number for the next set bit
30 * If no bits are set, returns @size. 30 * If no bits are set, returns @size.
31 */ 31 */
32 static inline 32 static inline
33 unsigned long find_next_bit(const unsigned lon 33 unsigned long find_next_bit(const unsigned long *addr, unsigned long size,
34 unsigned long offs 34 unsigned long offset)
35 { 35 {
36 if (small_const_nbits(size)) { 36 if (small_const_nbits(size)) {
37 unsigned long val; 37 unsigned long val;
38 38
39 if (unlikely(offset >= size)) 39 if (unlikely(offset >= size))
40 return size; 40 return size;
41 41
42 val = *addr & GENMASK(size - 1 42 val = *addr & GENMASK(size - 1, offset);
43 return val ? __ffs(val) : size 43 return val ? __ffs(val) : size;
44 } 44 }
45 45
46 return _find_next_bit(addr, size, offs 46 return _find_next_bit(addr, size, offset);
47 } 47 }
48 #endif 48 #endif
49 49
50 #ifndef find_next_and_bit 50 #ifndef find_next_and_bit
51 /** 51 /**
52 * find_next_and_bit - find the next set bit i 52 * find_next_and_bit - find the next set bit in both memory regions
53 * @addr1: The first address to base the searc 53 * @addr1: The first address to base the search on
54 * @addr2: The second address to base the sear 54 * @addr2: The second address to base the search on
55 * @size: The bitmap size in bits 55 * @size: The bitmap size in bits
56 * @offset: The bitnumber to start searching a 56 * @offset: The bitnumber to start searching at
57 * 57 *
58 * Returns the bit number for the next set bit 58 * Returns the bit number for the next set bit
59 * If no bits are set, returns @size. 59 * If no bits are set, returns @size.
60 */ 60 */
61 static inline 61 static inline
62 unsigned long find_next_and_bit(const unsigned 62 unsigned long find_next_and_bit(const unsigned long *addr1,
63 const unsigned long *addr2, un 63 const unsigned long *addr2, unsigned long size,
64 unsigned long offset) 64 unsigned long offset)
65 { 65 {
66 if (small_const_nbits(size)) { 66 if (small_const_nbits(size)) {
67 unsigned long val; 67 unsigned long val;
68 68
69 if (unlikely(offset >= size)) 69 if (unlikely(offset >= size))
70 return size; 70 return size;
71 71
72 val = *addr1 & *addr2 & GENMAS 72 val = *addr1 & *addr2 & GENMASK(size - 1, offset);
73 return val ? __ffs(val) : size 73 return val ? __ffs(val) : size;
74 } 74 }
75 75
76 return _find_next_and_bit(addr1, addr2 76 return _find_next_and_bit(addr1, addr2, size, offset);
77 } 77 }
78 #endif 78 #endif
79 79
80 #ifndef find_next_zero_bit 80 #ifndef find_next_zero_bit
81 /** 81 /**
82 * find_next_zero_bit - find the next cleared 82 * find_next_zero_bit - find the next cleared bit in a memory region
83 * @addr: The address to base the search on 83 * @addr: The address to base the search on
84 * @size: The bitmap size in bits 84 * @size: The bitmap size in bits
85 * @offset: The bitnumber to start searching a 85 * @offset: The bitnumber to start searching at
86 * 86 *
87 * Returns the bit number of the next zero bit 87 * Returns the bit number of the next zero bit
88 * If no bits are zero, returns @size. 88 * If no bits are zero, returns @size.
89 */ 89 */
90 static inline 90 static inline
91 unsigned long find_next_zero_bit(const unsigne 91 unsigned long find_next_zero_bit(const unsigned long *addr, unsigned long size,
92 unsigned long 92 unsigned long offset)
93 { 93 {
94 if (small_const_nbits(size)) { 94 if (small_const_nbits(size)) {
95 unsigned long val; 95 unsigned long val;
96 96
97 if (unlikely(offset >= size)) 97 if (unlikely(offset >= size))
98 return size; 98 return size;
99 99
100 val = *addr | ~GENMASK(size - 100 val = *addr | ~GENMASK(size - 1, offset);
101 return val == ~0UL ? size : ff 101 return val == ~0UL ? size : ffz(val);
102 } 102 }
103 103
104 return _find_next_zero_bit(addr, size, 104 return _find_next_zero_bit(addr, size, offset);
105 } 105 }
106 #endif 106 #endif
107 107
108 #ifndef find_first_bit 108 #ifndef find_first_bit
109 /** 109 /**
110 * find_first_bit - find the first set bit in 110 * find_first_bit - find the first set bit in a memory region
111 * @addr: The address to start the search at 111 * @addr: The address to start the search at
112 * @size: The maximum number of bits to search 112 * @size: The maximum number of bits to search
113 * 113 *
114 * Returns the bit number of the first set bit 114 * Returns the bit number of the first set bit.
115 * If no bits are set, returns @size. 115 * If no bits are set, returns @size.
116 */ 116 */
117 static inline 117 static inline
118 unsigned long find_first_bit(const unsigned lo 118 unsigned long find_first_bit(const unsigned long *addr, unsigned long size)
119 { 119 {
120 if (small_const_nbits(size)) { 120 if (small_const_nbits(size)) {
121 unsigned long val = *addr & GE 121 unsigned long val = *addr & GENMASK(size - 1, 0);
122 122
123 return val ? __ffs(val) : size 123 return val ? __ffs(val) : size;
124 } 124 }
125 125
126 return _find_first_bit(addr, size); 126 return _find_first_bit(addr, size);
127 } 127 }
128 #endif 128 #endif
129 129
130 #ifndef find_first_and_bit 130 #ifndef find_first_and_bit
131 /** 131 /**
132 * find_first_and_bit - find the first set bit 132 * find_first_and_bit - find the first set bit in both memory regions
133 * @addr1: The first address to base the searc 133 * @addr1: The first address to base the search on
134 * @addr2: The second address to base the sear 134 * @addr2: The second address to base the search on
135 * @size: The bitmap size in bits 135 * @size: The bitmap size in bits
136 * 136 *
137 * Returns the bit number for the next set bit 137 * Returns the bit number for the next set bit
138 * If no bits are set, returns @size. 138 * If no bits are set, returns @size.
139 */ 139 */
140 static inline 140 static inline
141 unsigned long find_first_and_bit(const unsigne 141 unsigned long find_first_and_bit(const unsigned long *addr1,
142 const unsigne 142 const unsigned long *addr2,
143 unsigned long 143 unsigned long size)
144 { 144 {
145 if (small_const_nbits(size)) { 145 if (small_const_nbits(size)) {
146 unsigned long val = *addr1 & * 146 unsigned long val = *addr1 & *addr2 & GENMASK(size - 1, 0);
147 147
148 return val ? __ffs(val) : size 148 return val ? __ffs(val) : size;
149 } 149 }
150 150
151 return _find_first_and_bit(addr1, addr 151 return _find_first_and_bit(addr1, addr2, size);
152 } 152 }
153 #endif 153 #endif
154 154
155 #ifndef find_first_zero_bit 155 #ifndef find_first_zero_bit
156 /** 156 /**
157 * find_first_zero_bit - find the first cleare 157 * find_first_zero_bit - find the first cleared bit in a memory region
158 * @addr: The address to start the search at 158 * @addr: The address to start the search at
159 * @size: The maximum number of bits to search 159 * @size: The maximum number of bits to search
160 * 160 *
161 * Returns the bit number of the first cleared 161 * Returns the bit number of the first cleared bit.
162 * If no bits are zero, returns @size. 162 * If no bits are zero, returns @size.
163 */ 163 */
164 static inline 164 static inline
165 unsigned long find_first_zero_bit(const unsign 165 unsigned long find_first_zero_bit(const unsigned long *addr, unsigned long size)
166 { 166 {
167 if (small_const_nbits(size)) { 167 if (small_const_nbits(size)) {
168 unsigned long val = *addr | ~G 168 unsigned long val = *addr | ~GENMASK(size - 1, 0);
169 169
170 return val == ~0UL ? size : ff 170 return val == ~0UL ? size : ffz(val);
171 } 171 }
172 172
173 return _find_first_zero_bit(addr, size 173 return _find_first_zero_bit(addr, size);
174 } 174 }
175 #endif 175 #endif
176 176
177 #endif /*__LINUX_FIND_H_ */ 177 #endif /*__LINUX_FIND_H_ */
178 178
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.