Home | History | Annotate | Line # | Download | only in linux
bitmap.h revision 1.6 
      1 /*	$NetBSD: bitmap.h,v 1.6 2018/08/27 14:50:52 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 /*
     40  * bitmap_zero(bitmap, nbits)
     41  *
     42  *	Zero a bitmap that was allocated to have nbits bits.  Yes, this
     43  *	zeros bits past nbits.
     44  */
     45 static inline void
     46 bitmap_zero(unsigned long *bitmap, size_t nbits)
     47 {
     48 	const size_t bpl = NBBY * sizeof(*bitmap);
     49 
     50 	memset(bitmap, 0, howmany(nbits, bpl) * sizeof(*bitmap));
     51 }
     52 
     53 /*
     54  * bitmap_empty(bitmap, nbits)
     55  *
     56  *	Return true if all bits at 0, 1, 2, ..., nbits-2, nbits-1 are
     57  *	0, or false if any of them is 1.
     58  */
     59 static inline bool
     60 bitmap_empty(const unsigned long *bitmap, size_t nbits)
     61 {
     62 	const size_t bpl = NBBY * sizeof(*bitmap);
     63 
     64 	for (; nbits >= bpl; nbits -= bpl) {
     65 		if (*bitmap++)
     66 			return false;
     67 	}
     68 
     69 	if (nbits) {
     70 		if (*bitmap & ~(~0UL << nbits))
     71 			return false;
     72 	}
     73 
     74 	return true;
     75 }
     76 
     77 /*
     78  * bitmap_weight(bitmap, nbits)
     79  *
     80  *	Compute the number of 1 bits at 0, 1, 2, ..., nbits-2, nbits-1.
     81  */
     82 static inline int
     83 bitmap_weight(const unsigned long *bitmap, size_t nbits)
     84 {
     85 	const size_t bpl = NBBY * sizeof(*bitmap);
     86 	int weight = 0;
     87 
     88 	for (; nbits >= bpl; nbits -= bpl)
     89 		weight += popcountl(*bitmap++);
     90 	if (nbits)
     91 		weight += popcountl(*bitmap & ~(~0UL << nbits));
     92 
     93 	return weight;
     94 }
     95 
     96 /*
     97  * bitmap_set(bitmap, startbit, nbits)
     98  *
     99  *	Set bits at startbit, startbit+1, ..., startbit+nbits-2,
    100  *	startbit+nbits-1 to 1.
    101  */
    102 static inline void
    103 bitmap_set(unsigned long *bitmap, size_t startbit, size_t nbits)
    104 {
    105 	const size_t bpl = NBBY * sizeof(*bitmap);
    106 	unsigned long *p = bitmap + startbit/bpl;
    107 	unsigned long mask;
    108 	unsigned sz;
    109 
    110 	for (sz = bpl - (startbit%bpl), mask = ~0UL << (startbit%bpl);
    111 	     nbits >= sz;
    112 	     nbits -= sz, sz = bpl, mask = ~0UL)
    113 		*p++ |= mask;
    114 
    115 	if (nbits)
    116 		*p |= mask & ~(~0UL << (nbits + bpl - sz));
    117 }
    118 
    119 /*
    120  * bitmap_clear(bitmap, startbit, nbits)
    121  *
    122  *	Clear bits at startbit, startbit+1, ..., startbit+nbits-2,
    123  *	startbit+nbits-1, replacing them by 0.
    124  */
    125 static inline void
    126 bitmap_clear(unsigned long *bitmap, size_t startbit, size_t nbits)
    127 {
    128 	const size_t bpl = NBBY * sizeof(*bitmap);
    129 	unsigned long *p = bitmap + startbit/bpl;
    130 	unsigned long mask;
    131 	unsigned sz;
    132 
    133 	for (sz = bpl - (startbit%bpl), mask = ~(~0UL << (startbit%bpl));
    134 	     nbits >= sz;
    135 	     nbits -= sz, sz = bpl, mask = 0UL)
    136 		*p++ &= mask;
    137 
    138 	if (nbits)
    139 		*p &= mask | (~0UL << (nbits + bpl - sz));
    140 }
    141 
    142 /*
    143  * bitmap_and(dst, src1, src2, nbits)
    144  *
    145  *	Set dst to be the bitwise AND of src1 and src2, all bitmaps
    146  *	allocated to have nbits bits.  Yes, this modifies bits past
    147  *	nbits.  Any pair of {dst, src1, src2} may be aliases.
    148  */
    149 static inline void
    150 bitmap_and(unsigned long *dst, const unsigned long *src1,
    151     const unsigned long *src2, size_t nbits)
    152 {
    153 	const size_t bpl = NBBY * sizeof(unsigned long);
    154 	size_t n = howmany(nbits, bpl);
    155 
    156 	while (n --> 0)
    157 		*dst++ = *src1++ & *src2++;
    158 }
    159 
    160 /*
    161  * bitmap_or(dst, src1, src2, nbits)
    162  *
    163  *	Set dst to be the bitwise inclusive-OR of src1 and src2, all
    164  *	bitmaps allocated to have nbits bits.  Yes, this modifies bits
    165  *	past nbits.  Any pair of {dst, src1, src2} may be aliases.
    166  */
    167 static inline void
    168 bitmap_or(unsigned long *dst, const unsigned long *src1,
    169     const unsigned long *src2, size_t nbits)
    170 {
    171 	const size_t bpl = NBBY * sizeof(unsigned long);
    172 	size_t n = howmany(nbits, bpl);
    173 
    174 	while (n --> 0)
    175 		*dst++ = *src1++ | *src2++;
    176 }
    177 
    178 #endif  /* _LINUX_BITMAP_H_ */
    179