Home | History | Annotate | Download | only in sys
      1 /*
      2  * CDDL HEADER START
      3  *
      4  * The contents of this file are subject to the terms of the
      5  * Common Development and Distribution License (the "License").
      6  * You may not use this file except in compliance with the License.
      7  *
      8  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
      9  * or http://www.opensolaris.org/os/licensing.
     10  * See the License for the specific language governing permissions
     11  * and limitations under the License.
     12  *
     13  * When distributing Covered Code, include this CDDL HEADER in each
     14  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
     15  * If applicable, add the following below this CDDL HEADER, with the
     16  * fields enclosed by brackets "[]" replaced with your own identifying
     17  * information: Portions Copyright [yyyy] [name of copyright owner]
     18  *
     19  * CDDL HEADER END
     20  */
     21 
     22 /*
     23  * Copyright 2006 Sun Microsystems, Inc.  All rights reserved.
     24  * Use is subject to license terms.
     25  */
     26 
     27 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
     28 /*	  All Rights Reserved  	*/
     29 
     30 
     31 #ifndef _SYS_BITMAP_H
     32 #define	_SYS_BITMAP_H
     33 
     34 #pragma ident	"@(#)bitmap.h	1.29	06/09/11 SMI"
     35 
     36 #ifdef	__cplusplus
     37 extern "C" {
     38 #endif
     39 
     40 #include <sys/feature_tests.h>
     41 #if defined(__GNUC__) && defined(_ASM_INLINES) && \
     42 	(defined(__i386) || defined(__amd64))
     43 #include <asm/bitmap.h>
     44 #endif
     45 
     46 /*
     47  * Operations on bitmaps of arbitrary size
     48  * A bitmap is a vector of 1 or more ulong_t's.
     49  * The user of the package is responsible for range checks and keeping
     50  * track of sizes.
     51  */
     52 
     53 #ifdef _LP64
     54 #define	BT_ULSHIFT	6 /* log base 2 of BT_NBIPUL, to extract word index */
     55 #define	BT_ULSHIFT32	5 /* log base 2 of BT_NBIPUL, to extract word index */
     56 #else
     57 #define	BT_ULSHIFT	5 /* log base 2 of BT_NBIPUL, to extract word index */
     58 #endif
     59 
     60 #define	BT_NBIPUL	(1 << BT_ULSHIFT)	/* n bits per ulong_t */
     61 #define	BT_ULMASK	(BT_NBIPUL - 1)		/* to extract bit index */
     62 
     63 #ifdef _LP64
     64 #define	BT_NBIPUL32	(1 << BT_ULSHIFT32)	/* n bits per ulong_t */
     65 #define	BT_ULMASK32	(BT_NBIPUL32 - 1)	/* to extract bit index */
     66 #define	BT_ULMAXMASK	0xffffffffffffffff	/* used by bt_getlowbit */
     67 #else
     68 #define	BT_ULMAXMASK	0xffffffff
     69 #endif
     70 
     71 /*
     72  * bitmap is a ulong_t *, bitindex an index_t
     73  *
     74  * The macros BT_WIM and BT_BIW internal; there is no need
     75  * for users of this package to use them.
     76  */
     77 
     78 /*
     79  * word in map
     80  */
     81 #define	BT_WIM(bitmap, bitindex) \
     82 	((bitmap)[(bitindex) >> BT_ULSHIFT])
     83 /*
     84  * bit in word
     85  */
     86 #define	BT_BIW(bitindex) \
     87 	(1UL << ((bitindex) & BT_ULMASK))
     88 
     89 #ifdef _LP64
     90 #define	BT_WIM32(bitmap, bitindex) \
     91 	((bitmap)[(bitindex) >> BT_ULSHIFT32])
     92 
     93 #define	BT_BIW32(bitindex) \
     94 	(1UL << ((bitindex) & BT_ULMASK32))
     95 #endif
     96 
     97 /*
     98  * These are public macros
     99  *
    100  * BT_BITOUL == n bits to n ulong_t's
    101  */
    102 #define	BT_BITOUL(nbits) \
    103 	(((nbits) + BT_NBIPUL - 1l) / BT_NBIPUL)
    104 #define	BT_SIZEOFMAP(nbits) \
    105 	(BT_BITOUL(nbits) * sizeof (ulong_t))
    106 #define	BT_TEST(bitmap, bitindex) \
    107 	((BT_WIM((bitmap), (bitindex)) & BT_BIW(bitindex)) ? 1 : 0)
    108 #define	BT_SET(bitmap, bitindex) \
    109 	{ BT_WIM((bitmap), (bitindex)) |= BT_BIW(bitindex); }
    110 #define	BT_CLEAR(bitmap, bitindex) \
    111 	{ BT_WIM((bitmap), (bitindex)) &= ~BT_BIW(bitindex); }
    112 
    113 #ifdef _LP64
    114 #define	BT_BITOUL32(nbits) \
    115 	(((nbits) + BT_NBIPUL32 - 1l) / BT_NBIPUL32)
    116 #define	BT_SIZEOFMAP32(nbits) \
    117 	(BT_BITOUL32(nbits) * sizeof (uint_t))
    118 #define	BT_TEST32(bitmap, bitindex) \
    119 	((BT_WIM32((bitmap), (bitindex)) & BT_BIW32(bitindex)) ? 1 : 0)
    120 #define	BT_SET32(bitmap, bitindex) \
    121 	{ BT_WIM32((bitmap), (bitindex)) |= BT_BIW32(bitindex); }
    122 #define	BT_CLEAR32(bitmap, bitindex) \
    123 	{ BT_WIM32((bitmap), (bitindex)) &= ~BT_BIW32(bitindex); }
    124 #endif /* _LP64 */
    125 
    126 
    127 /*
    128  * BIT_ONLYONESET is a private macro not designed for bitmaps of
    129  * arbitrary size.  u must be an unsigned integer/long.  It returns
    130  * true if one and only one bit is set in u.
    131  */
    132 #define	BIT_ONLYONESET(u) \
    133 	((((u) == 0) ? 0 : ((u) & ((u) - 1)) == 0))
    134 
    135 #if defined(_KERNEL) && !defined(_ASM)
    136 #include <sys/atomic.h>
    137 
    138 /*
    139  * return next available bit index from map with specified number of bits
    140  */
    141 extern index_t	bt_availbit(ulong_t *bitmap, size_t nbits);
    142 /*
    143  * find the highest order bit that is on, and is within or below
    144  * the word specified by wx
    145  */
    146 extern int	bt_gethighbit(ulong_t *mapp, int wx);
    147 extern int	bt_range(ulong_t *bitmap, size_t *pos1, size_t *pos2,
    148 			size_t end_pos);
    149 /*
    150  * Find highest and lowest one bit set.
    151  *	Returns bit number + 1 of bit that is set, otherwise returns 0.
    152  * Low order bit is 0, high order bit is 31.
    153  */
    154 extern int	highbit(ulong_t);
    155 extern int	lowbit(ulong_t);
    156 extern int	bt_getlowbit(ulong_t *bitmap, size_t start, size_t stop);
    157 extern void	bt_copy(ulong_t *, ulong_t *, ulong_t);
    158 
    159 /*
    160  * find the parity
    161  */
    162 extern int	odd_parity(ulong_t);
    163 
    164 /*
    165  * Atomically set/clear bits
    166  * Atomic exclusive operations will set "result" to "-1"
    167  * if the bit is already set/cleared. "result" will be set
    168  * to 0 otherwise.
    169  */
    170 #define	BT_ATOMIC_SET(bitmap, bitindex) \
    171 	{ atomic_or_long(&(BT_WIM(bitmap, bitindex)), BT_BIW(bitindex)); }
    172 #define	BT_ATOMIC_CLEAR(bitmap, bitindex) \
    173 	{ atomic_and_long(&(BT_WIM(bitmap, bitindex)), ~BT_BIW(bitindex)); }
    174 
    175 #define	BT_ATOMIC_SET_EXCL(bitmap, bitindex, result) \
    176 	{ result = atomic_set_long_excl(&(BT_WIM(bitmap, bitindex)),	\
    177 	    (bitindex) % BT_NBIPUL); }
    178 #define	BT_ATOMIC_CLEAR_EXCL(bitmap, bitindex, result) \
    179 	{ result = atomic_clear_long_excl(&(BT_WIM(bitmap, bitindex)),	\
    180 	    (bitindex) % BT_NBIPUL); }
    181 
    182 /*
    183  * Extracts bits between index h (high, inclusive) and l (low, exclusive) from
    184  * u, which must be an unsigned integer.
    185  */
    186 #define	BITX(u, h, l)	(((u) >> (l)) & ((1LU << ((h) - (l) + 1LU)) - 1LU))
    187 
    188 #endif	/* _KERNEL && !_ASM */
    189 
    190 #ifdef	__cplusplus
    191 }
    192 #endif
    193 
    194 #endif	/* _SYS_BITMAP_H */
    195