1 /* $NetBSD: bitmap.h,v 1.13 2021/12/19 12:21:30 riastradh Exp $ */ 2 3 /*- 4 * Copyright (c) 2018 The NetBSD Foundation, Inc. 5 * All rights reserved. 6 * 7 * This code is derived from software contributed to The NetBSD Foundation 8 * by Taylor R. Campbell. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 1. Redistributions of source code must retain the above copyright 14 * notice, this list of conditions and the following disclaimer. 15 * 2. Redistributions in binary form must reproduce the above copyright 16 * notice, this list of conditions and the following disclaimer in the 17 * documentation and/or other materials provided with the distribution. 18 * 19 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 * POSSIBILITY OF SUCH DAMAGE. 30 */ 31 32 #ifndef _LINUX_BITMAP_H_ 33 #define _LINUX_BITMAP_H_ 34 35 #include <sys/param.h> 36 #include <sys/types.h> 37 #include <sys/systm.h> 38 39 #include <linux/slab.h> 40 41 /* 42 * bitmap_zero(bitmap, nbits) 43 * 44 * Zero a bitmap that was allocated to have nbits bits. Yes, this 45 * zeros bits past nbits. 46 */ 47 static inline void 48 bitmap_zero(unsigned long *bitmap, size_t nbits) 49 { 50 const size_t bpl = NBBY * sizeof(*bitmap); 51 size_t n = howmany(nbits, bpl); 52 53 memset(bitmap, 0, n * sizeof(*bitmap)); 54 } 55 56 /* 57 * bitmap_empty(bitmap, nbits) 58 * 59 * Return true if all bits at 0, 1, 2, ..., nbits-2, nbits-1 are 60 * 0, or false if any of them is 1. 61 */ 62 static inline bool 63 bitmap_empty(const unsigned long *bitmap, size_t nbits) 64 { 65 const size_t bpl = NBBY * sizeof(*bitmap); 66 67 for (; nbits >= bpl; nbits -= bpl) { 68 if (*bitmap++) 69 return false; 70 } 71 72 if (nbits) { 73 if (*bitmap & ~(~0UL << nbits)) 74 return false; 75 } 76 77 return true; 78 } 79 80 /* 81 * bitmap_weight(bitmap, nbits) 82 * 83 * Compute the number of 1 bits at 0, 1, 2, ..., nbits-2, nbits-1. 84 */ 85 static inline int 86 bitmap_weight(const unsigned long *bitmap, size_t nbits) 87 { 88 const size_t bpl = NBBY * sizeof(*bitmap); 89 int weight = 0; 90 91 for (; nbits >= bpl; nbits -= bpl) 92 weight += popcountl(*bitmap++); 93 if (nbits) 94 weight += popcountl(*bitmap & ~(~0UL << nbits)); 95 96 return weight; 97 } 98 99 /* 100 * bitmap_set(bitmap, startbit, nbits) 101 * 102 * Set bits at startbit, startbit+1, ..., startbit+nbits-2, 103 * startbit+nbits-1 to 1. 104 */ 105 static inline void 106 bitmap_set(unsigned long *bitmap, size_t startbit, size_t nbits) 107 { 108 const size_t bpl = NBBY * sizeof(*bitmap); 109 unsigned long *p = bitmap + startbit/bpl; 110 unsigned initial = startbit%bpl; 111 112 /* Handle an initial odd word if any. */ 113 if (initial) { 114 /* Does the whole thing fit in a single word? */ 115 if (nbits <= bpl - initial) { 116 /* Yes: just set nbits starting at initial. */ 117 *p |= ~(~0ULL << nbits) << initial; 118 return; 119 } 120 /* Nope: set all bits above initial, and advance. */ 121 *p++ |= ~0ULL << initial; 122 nbits -= bpl - initial; 123 } 124 125 /* Set the middle part to all bits 1. */ 126 for (; nbits >= bpl; nbits -= bpl) 127 *p++ = ~0UL; 128 129 /* Handle a final odd word if any by setting its low nbits. */ 130 if (nbits) 131 *p |= ~(~0ULL << nbits); 132 } 133 134 /* 135 * bitmap_clear(bitmap, startbit, nbits) 136 * 137 * Clear bits at startbit, startbit+1, ..., startbit+nbits-2, 138 * startbit+nbits-1, replacing them by 0. 139 */ 140 static inline void 141 bitmap_clear(unsigned long *bitmap, size_t startbit, size_t nbits) 142 { 143 const size_t bpl = NBBY * sizeof(*bitmap); 144 unsigned long *p = bitmap + startbit/bpl; 145 unsigned initial = startbit%bpl; 146 147 /* Handle an initial odd word if any. */ 148 if (initial) { 149 /* Does the whole thing fit in a single word? */ 150 if (nbits <= bpl - initial) { 151 /* Yes: just clear nbits starting at initial. */ 152 *p &= ~(~(~0ULL << nbits) << initial); 153 return; 154 } 155 /* Nope: clear all bits above initial, and advance. */ 156 *p++ &= ~(~0ULL << initial); 157 nbits -= bpl - initial; 158 } 159 160 /* Zero the middle part. */ 161 for (; nbits >= bpl; nbits -= bpl) 162 *p++ = 0UL; 163 164 /* Handle a final odd word if any by clearing its low nbits. */ 165 if (nbits) 166 *p &= ~0ULL << nbits; 167 } 168 169 /* 170 * bitmap_copy(dst, src, nbits) 171 * 172 * Copy the bitmap from src to dst. dst and src may alias (but 173 * why would you bother?). 174 */ 175 static inline void 176 bitmap_copy(unsigned long *dst, const unsigned long *src, size_t nbits) 177 { 178 const size_t bpl = NBBY * sizeof(unsigned long); 179 size_t n = howmany(nbits, bpl); 180 181 while (n --> 0) 182 *dst++ = *src++; 183 } 184 185 /* 186 * bitmap_complement(dst, src, nbits) 187 * 188 * Set dst to the the bitwise NOT of src. dst and src may alias. 189 */ 190 static inline void 191 bitmap_complement(unsigned long *dst, const unsigned long *src, size_t nbits) 192 { 193 const size_t bpl = NBBY * sizeof(unsigned long); 194 size_t n = howmany(nbits, bpl); 195 196 while (n --> 0) 197 *dst++ = ~*src++; 198 } 199 200 /* 201 * bitmap_and(dst, src1, src2, nbits) 202 * 203 * Set dst to be the bitwise AND of src1 and src2, all bitmaps 204 * allocated to have nbits bits. Yes, this modifies bits past 205 * nbits. Any pair of {dst, src1, src2} may be aliases. 206 */ 207 static inline void 208 bitmap_and(unsigned long *dst, const unsigned long *src1, 209 const unsigned long *src2, size_t nbits) 210 { 211 const size_t bpl = NBBY * sizeof(unsigned long); 212 size_t n = howmany(nbits, bpl); 213 214 while (n --> 0) 215 *dst++ = *src1++ & *src2++; 216 } 217 218 /* 219 * bitmap_andnot(dst, src1, src2, nbits) 220 * 221 * Set dst to be the bitwise AND of src1 and ~src2, all bitmaps 222 * allocated to have nbits bits. Yes, this modifies bits past 223 * nbits. Any pair of {dst, src1, src2} may be aliases. 224 */ 225 static inline void 226 bitmap_andnot(unsigned long *dst, const unsigned long *src1, 227 const unsigned long *src2, size_t nbits) 228 { 229 const size_t bpl = NBBY * sizeof(unsigned long); 230 size_t n = howmany(nbits, bpl); 231 232 while (n --> 0) 233 *dst++ = *src1++ & ~*src2++; 234 } 235 236 /* 237 * bitmap_or(dst, src1, src2, nbits) 238 * 239 * Set dst to be the bitwise inclusive-OR of src1 and src2, all 240 * bitmaps allocated to have nbits bits. Yes, this modifies bits 241 * past nbits. Any pair of {dst, src1, src2} may be aliases. 242 */ 243 static inline void 244 bitmap_or(unsigned long *dst, const unsigned long *src1, 245 const unsigned long *src2, size_t nbits) 246 { 247 const size_t bpl = NBBY * sizeof(unsigned long); 248 size_t n = howmany(nbits, bpl); 249 250 while (n --> 0) 251 *dst++ = *src1++ | *src2++; 252 } 253 254 static inline unsigned long * 255 bitmap_zalloc(size_t nbits, gfp_t gfp) 256 { 257 const size_t bpl = NBBY * sizeof(unsigned long); 258 size_t n = howmany(nbits, bpl); 259 260 return kcalloc(n, sizeof(unsigned long), gfp); 261 } 262 263 static inline void 264 bitmap_free(unsigned long *bitmap) 265 { 266 267 kfree(bitmap); 268 } 269 270 #endif /* _LINUX_BITMAP_H_ */ 271
Indexes created Sat Sep 20 22:09:52 GMT 2025