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