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