1 /* $OpenBSD: bitmap.h,v 1.8 2024/03/20 22:52:44 bluhm Exp $ */
2 /*
3 * Copyright (c) 2013, 2014, 2015 Mark Kettenis
4 *
5 * Permission to use, copy, modify, and distribute this software for any
6 * purpose with or without fee is hereby granted, provided that the above
7 * copyright notice and this permission notice appear in all copies.
8 *
9 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
10 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
11 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
12 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
13 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
14 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
15 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
16 */
17
18 #ifndef _LINUX_BITMAP_H
19 #define _LINUX_BITMAP_H
20
21 #include <linux/align.h>
22 #include <linux/bitops.h>
23 #include <linux/string.h>
24
25 #define bitmap_empty(p, n) (find_first_bit(p, n) == n)
26
27 static inline void
bitmap_set(void * p,int b,u_int n)28 bitmap_set(void *p, int b, u_int n)
29 {
30 u_int end = b + n;
31
32 for (; b < end; b++)
33 __set_bit(b, p);
34 }
35
36 static inline void
bitmap_clear(void * p,int b,u_int n)37 bitmap_clear(void *p, int b, u_int n)
38 {
39 u_int end = b + n;
40
41 for (; b < end; b++)
42 __clear_bit(b, p);
43 }
44
45 static inline void
bitmap_zero(void * p,u_int n)46 bitmap_zero(void *p, u_int n)
47 {
48 u_int *ptr = p;
49 u_int b;
50
51 for (b = 0; b < n; b += 32)
52 ptr[b >> 5] = 0;
53 }
54
55 static inline void
bitmap_fill(void * p,u_int n)56 bitmap_fill(void *p, u_int n)
57 {
58 u_int *ptr = p;
59 u_int b;
60
61 for (b = 0; b < n; b += 32)
62 ptr[b >> 5] = 0xffffffff;
63 }
64
65 static inline void
bitmap_or(void * d,void * s1,void * s2,u_int n)66 bitmap_or(void *d, void *s1, void *s2, u_int n)
67 {
68 u_int *dst = d;
69 u_int *src1 = s1;
70 u_int *src2 = s2;
71 u_int b;
72
73 for (b = 0; b < n; b += 32)
74 dst[b >> 5] = src1[b >> 5] | src2[b >> 5];
75 }
76
77 static inline void
bitmap_andnot(void * d,void * s1,void * s2,u_int n)78 bitmap_andnot(void *d, void *s1, void *s2, u_int n)
79 {
80 u_int *dst = d;
81 u_int *src1 = s1;
82 u_int *src2 = s2;
83 u_int b;
84
85 for (b = 0; b < n; b += 32)
86 dst[b >> 5] = src1[b >> 5] & ~src2[b >> 5];
87 }
88
89 static inline void
bitmap_complement(void * d,void * s,u_int n)90 bitmap_complement(void *d, void *s, u_int n)
91 {
92 u_int *dst = d;
93 u_int *src = s;
94 u_int b;
95
96 for (b = 0; b < n; b += 32)
97 dst[b >> 5] = ~src[b >> 5];
98 }
99
100 static inline bool
bitmap_intersects(const void * s1,const void * s2,u_int n)101 bitmap_intersects(const void *s1, const void *s2, u_int n)
102 {
103 const u_int *b1 = s1;
104 const u_int *b2 = s2;
105 u_int b;
106
107 for (b = 0; b < n; b += 32)
108 if (b1[b >> 5] & b2[b >> 5])
109 return true;
110 if ((n % 32) != 0)
111 if ((b1[n >> 5] & b2[b >> 5]) & (0xffffffff >> (32 - (n % 32))))
112 return true;
113
114 return false;
115 }
116
117 static inline void
bitmap_copy(void * d,const void * s,u_int n)118 bitmap_copy(void *d, const void *s, u_int n)
119 {
120 u_int *dst = d;
121 const u_int *src = s;
122 u_int b;
123
124 for (b = 0; b < n; b += 32)
125 dst[b >> 5] = src[b >> 5];
126 }
127
128 static inline void
bitmap_to_arr32(void * d,const unsigned long * src,u_int n)129 bitmap_to_arr32(void *d, const unsigned long *src, u_int n)
130 {
131 u_int *dst = d;
132 u_int b;
133
134 #ifdef __LP64__
135 for (b = 0; b < n; b += 32) {
136 dst[b >> 5] = src[b >> 6] & 0xffffffff;
137 b += 32;
138 if (b < n)
139 dst[b >> 5] = src[b >> 6] >> 32;
140 }
141 #else
142 bitmap_copy(d, src, n);
143 #endif
144 if ((n % 32) != 0)
145 dst[n >> 5] &= (0xffffffff >> (32 - (n % 32)));
146 }
147
148 static inline void
bitmap_from_arr32(unsigned long * dst,const void * s,u_int n)149 bitmap_from_arr32(unsigned long *dst, const void *s, u_int n)
150 {
151 const u_int *src = s;
152 u_int b;
153
154 #ifdef __LP64__
155 for (b = 0; b < n; b += 32) {
156 dst[b >> 6] = src[b >> 5];
157 b += 32;
158 if (b < n)
159 dst[b >> 6] |= ((unsigned long)src[b >> 5]) << 32;
160 }
161 if ((n % 64) != 0)
162 dst[n >> 6] &= (0xffffffffffffffffUL >> (64 - (n % 64)));
163 #else
164 bitmap_copy(dst, s, n);
165 if ((n % 32) != 0)
166 dst[n >> 5] &= (0xffffffff >> (32 - (n % 32)));
167 #endif
168 }
169
170 static inline int
bitmap_weight(const void * p,u_int n)171 bitmap_weight(const void *p, u_int n)
172 {
173 const u_int *ptr = p;
174 u_int b;
175 int sum = 0;
176
177 for (b = 0; b < n; b += 32)
178 sum += hweight32(ptr[b >> 5]);
179 return sum;
180 }
181
182 static inline int
bitmap_find_free_region(void * p,u_int n,int o)183 bitmap_find_free_region(void *p, u_int n, int o)
184 {
185 int b;
186
187 KASSERT(o == 0);
188 b = find_first_zero_bit(p, n);
189 if (b == n)
190 return -ENOMEM;
191 __set_bit(b, p);
192 return b;
193 }
194
195 static inline void
bitmap_release_region(void * p,u_int b,int o)196 bitmap_release_region(void *p, u_int b, int o)
197 {
198 KASSERT(o == 0);
199 __clear_bit(b, p);
200 }
201
202 void *bitmap_zalloc(u_int, gfp_t);
203 void bitmap_free(void *);
204
205 #endif
206