1*0Sstevel@tonic-gate /*
2*0Sstevel@tonic-gate * CDDL HEADER START
3*0Sstevel@tonic-gate *
4*0Sstevel@tonic-gate * The contents of this file are subject to the terms of the
5*0Sstevel@tonic-gate * Common Development and Distribution License, Version 1.0 only
6*0Sstevel@tonic-gate * (the "License"). You may not use this file except in compliance
7*0Sstevel@tonic-gate * with the License.
8*0Sstevel@tonic-gate *
9*0Sstevel@tonic-gate * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10*0Sstevel@tonic-gate * or http://www.opensolaris.org/os/licensing.
11*0Sstevel@tonic-gate * See the License for the specific language governing permissions
12*0Sstevel@tonic-gate * and limitations under the License.
13*0Sstevel@tonic-gate *
14*0Sstevel@tonic-gate * When distributing Covered Code, include this CDDL HEADER in each
15*0Sstevel@tonic-gate * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16*0Sstevel@tonic-gate * If applicable, add the following below this CDDL HEADER, with the
17*0Sstevel@tonic-gate * fields enclosed by brackets "[]" replaced with your own identifying
18*0Sstevel@tonic-gate * information: Portions Copyright [yyyy] [name of copyright owner]
19*0Sstevel@tonic-gate *
20*0Sstevel@tonic-gate * CDDL HEADER END
21*0Sstevel@tonic-gate */
22*0Sstevel@tonic-gate /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
23*0Sstevel@tonic-gate /* All Rights Reserved */
24*0Sstevel@tonic-gate
25*0Sstevel@tonic-gate
26*0Sstevel@tonic-gate /*
27*0Sstevel@tonic-gate * Copyright 2004 Sun Microsystems, Inc. All rights reserved.
28*0Sstevel@tonic-gate * Use is subject to license terms.
29*0Sstevel@tonic-gate */
30*0Sstevel@tonic-gate
31*0Sstevel@tonic-gate #pragma ident "%Z%%M% %I% %E% SMI"
32*0Sstevel@tonic-gate
33*0Sstevel@tonic-gate /*
34*0Sstevel@tonic-gate * Operations on bitmaps of arbitrary size
35*0Sstevel@tonic-gate * A bitmap is a vector of 1 or more ulongs.
36*0Sstevel@tonic-gate * The user of the package is responsible for range checks and keeping
37*0Sstevel@tonic-gate * track of sizes.
38*0Sstevel@tonic-gate */
39*0Sstevel@tonic-gate
40*0Sstevel@tonic-gate #include <sys/types.h>
41*0Sstevel@tonic-gate #include <sys/bitmap.h>
42*0Sstevel@tonic-gate #include <sys/debug.h> /* ASSERT */
43*0Sstevel@tonic-gate
44*0Sstevel@tonic-gate /*
45*0Sstevel@tonic-gate * Return index of first available bit in denoted bitmap, or -1 for
46*0Sstevel@tonic-gate * failure. Size is the cardinality of the bitmap; that is, the
47*0Sstevel@tonic-gate * number of bits.
48*0Sstevel@tonic-gate * No side-effects. In particular, does not update bitmap.
49*0Sstevel@tonic-gate * Caller is responsible for range checks.
50*0Sstevel@tonic-gate */
51*0Sstevel@tonic-gate index_t
bt_availbit(ulong_t * bitmap,size_t nbits)52*0Sstevel@tonic-gate bt_availbit(ulong_t *bitmap, size_t nbits)
53*0Sstevel@tonic-gate {
54*0Sstevel@tonic-gate index_t maxword; /* index of last in map */
55*0Sstevel@tonic-gate index_t wx; /* word index in map */
56*0Sstevel@tonic-gate
57*0Sstevel@tonic-gate /*
58*0Sstevel@tonic-gate * Look for a word with a bit off.
59*0Sstevel@tonic-gate * Subtract one from nbits because we're converting it to a
60*0Sstevel@tonic-gate * a range of indices.
61*0Sstevel@tonic-gate */
62*0Sstevel@tonic-gate nbits -= 1;
63*0Sstevel@tonic-gate maxword = nbits >> BT_ULSHIFT;
64*0Sstevel@tonic-gate for (wx = 0; wx <= maxword; wx++)
65*0Sstevel@tonic-gate if (bitmap[wx] != ~0)
66*0Sstevel@tonic-gate break;
67*0Sstevel@tonic-gate
68*0Sstevel@tonic-gate if (wx <= maxword) {
69*0Sstevel@tonic-gate /*
70*0Sstevel@tonic-gate * Found a word with a bit off. Now find the bit in the word.
71*0Sstevel@tonic-gate */
72*0Sstevel@tonic-gate index_t bx; /* bit index in word */
73*0Sstevel@tonic-gate index_t maxbit; /* last bit to look at */
74*0Sstevel@tonic-gate ulong_t word;
75*0Sstevel@tonic-gate ulong_t bit;
76*0Sstevel@tonic-gate
77*0Sstevel@tonic-gate maxbit = wx == maxword ? nbits & BT_ULMASK : BT_NBIPUL - 1;
78*0Sstevel@tonic-gate word = bitmap[wx];
79*0Sstevel@tonic-gate bit = 1;
80*0Sstevel@tonic-gate for (bx = 0; bx <= maxbit; bx++, bit <<= 1) {
81*0Sstevel@tonic-gate if (!(word & bit)) {
82*0Sstevel@tonic-gate return (wx << BT_ULSHIFT | bx);
83*0Sstevel@tonic-gate }
84*0Sstevel@tonic-gate }
85*0Sstevel@tonic-gate }
86*0Sstevel@tonic-gate return (-1);
87*0Sstevel@tonic-gate }
88*0Sstevel@tonic-gate
89*0Sstevel@tonic-gate
90*0Sstevel@tonic-gate /*
91*0Sstevel@tonic-gate * Find highest order bit that is on, and is within or below
92*0Sstevel@tonic-gate * the word specified by wx.
93*0Sstevel@tonic-gate */
94*0Sstevel@tonic-gate int
bt_gethighbit(ulong_t * mapp,int wx)95*0Sstevel@tonic-gate bt_gethighbit(ulong_t *mapp, int wx)
96*0Sstevel@tonic-gate {
97*0Sstevel@tonic-gate ulong_t word;
98*0Sstevel@tonic-gate
99*0Sstevel@tonic-gate while ((word = mapp[wx]) == 0) {
100*0Sstevel@tonic-gate wx--;
101*0Sstevel@tonic-gate if (wx < 0) {
102*0Sstevel@tonic-gate return (-1);
103*0Sstevel@tonic-gate }
104*0Sstevel@tonic-gate }
105*0Sstevel@tonic-gate return (wx << BT_ULSHIFT | (highbit(word) - 1));
106*0Sstevel@tonic-gate }
107*0Sstevel@tonic-gate
108*0Sstevel@tonic-gate
109*0Sstevel@tonic-gate /*
110*0Sstevel@tonic-gate * Search the bitmap for a consecutive pattern of 1's.
111*0Sstevel@tonic-gate * Search starts at position pos1.
112*0Sstevel@tonic-gate * Returns 1 on success and 0 on failure.
113*0Sstevel@tonic-gate * Side effects.
114*0Sstevel@tonic-gate * Returns indices to the first bit (pos1)
115*0Sstevel@tonic-gate * and one past the last bit (pos2) in the pattern.
116*0Sstevel@tonic-gate */
117*0Sstevel@tonic-gate int
bt_range(ulong_t * bitmap,size_t * pos1,size_t * pos2,size_t end_pos)118*0Sstevel@tonic-gate bt_range(ulong_t *bitmap, size_t *pos1, size_t *pos2, size_t end_pos)
119*0Sstevel@tonic-gate {
120*0Sstevel@tonic-gate size_t pos;
121*0Sstevel@tonic-gate
122*0Sstevel@tonic-gate for (pos = *pos1; pos < end_pos; pos++)
123*0Sstevel@tonic-gate if (BT_TEST(bitmap, pos))
124*0Sstevel@tonic-gate break;
125*0Sstevel@tonic-gate
126*0Sstevel@tonic-gate if (pos == end_pos)
127*0Sstevel@tonic-gate return (0);
128*0Sstevel@tonic-gate
129*0Sstevel@tonic-gate *pos1 = pos;
130*0Sstevel@tonic-gate
131*0Sstevel@tonic-gate for (; pos < end_pos; pos++)
132*0Sstevel@tonic-gate if (!BT_TEST(bitmap, pos))
133*0Sstevel@tonic-gate break;
134*0Sstevel@tonic-gate *pos2 = pos;
135*0Sstevel@tonic-gate
136*0Sstevel@tonic-gate return (1);
137*0Sstevel@tonic-gate }
138*0Sstevel@tonic-gate
139*0Sstevel@tonic-gate
140*0Sstevel@tonic-gate /*
141*0Sstevel@tonic-gate * return the parity of the supplied long
142*0Sstevel@tonic-gate *
143*0Sstevel@tonic-gate * this works by successively partitioning the argument in half, and
144*0Sstevel@tonic-gate * setting the parity of the result to the parity of the 2 halfs, until
145*0Sstevel@tonic-gate * only one bit is left
146*0Sstevel@tonic-gate */
147*0Sstevel@tonic-gate int
odd_parity(ulong_t i)148*0Sstevel@tonic-gate odd_parity(ulong_t i)
149*0Sstevel@tonic-gate {
150*0Sstevel@tonic-gate #ifdef _LP64
151*0Sstevel@tonic-gate i ^= i >> 32;
152*0Sstevel@tonic-gate #endif
153*0Sstevel@tonic-gate i ^= i >> 16;
154*0Sstevel@tonic-gate i ^= i >> 8;
155*0Sstevel@tonic-gate i ^= i >> 4;
156*0Sstevel@tonic-gate i ^= i >> 2;
157*0Sstevel@tonic-gate i ^= i >> 1;
158*0Sstevel@tonic-gate
159*0Sstevel@tonic-gate return (i & 0x01);
160*0Sstevel@tonic-gate }
161*0Sstevel@tonic-gate
162*0Sstevel@tonic-gate
163*0Sstevel@tonic-gate /*
164*0Sstevel@tonic-gate * get the lowest bit in the range of 'start' and 'stop', inclusive.
165*0Sstevel@tonic-gate * I.e., if caller calls bt_getlowbit(map, X, Y), any value between X and Y,
166*0Sstevel@tonic-gate * including X and Y can be returned.
167*0Sstevel@tonic-gate * Neither start nor stop is required to align with word boundaries.
168*0Sstevel@tonic-gate * If a bit is set in the range, the bit position is returned; otherwise,
169*0Sstevel@tonic-gate * a -1 is returned.
170*0Sstevel@tonic-gate */
171*0Sstevel@tonic-gate int
bt_getlowbit(ulong_t * map,size_t start,size_t stop)172*0Sstevel@tonic-gate bt_getlowbit(ulong_t *map, size_t start, size_t stop)
173*0Sstevel@tonic-gate {
174*0Sstevel@tonic-gate ulong_t word;
175*0Sstevel@tonic-gate int counter = start >> BT_ULSHIFT;
176*0Sstevel@tonic-gate int limit = stop >> BT_ULSHIFT;
177*0Sstevel@tonic-gate index_t partial_start = start & BT_ULMASK;
178*0Sstevel@tonic-gate index_t partial_stop = stop & BT_ULMASK;
179*0Sstevel@tonic-gate
180*0Sstevel@tonic-gate if (start > stop) {
181*0Sstevel@tonic-gate return (-1);
182*0Sstevel@tonic-gate }
183*0Sstevel@tonic-gate
184*0Sstevel@tonic-gate /*
185*0Sstevel@tonic-gate * The range between 'start' and 'stop' can be very large, and the
186*0Sstevel@tonic-gate * '1' bits in this range can be sparse.
187*0Sstevel@tonic-gate * For performance reason, the underlying implementation operates
188*0Sstevel@tonic-gate * on words, not on bits.
189*0Sstevel@tonic-gate */
190*0Sstevel@tonic-gate word = map[counter];
191*0Sstevel@tonic-gate
192*0Sstevel@tonic-gate if (partial_start) {
193*0Sstevel@tonic-gate /*
194*0Sstevel@tonic-gate * Since the start is not aligned on word boundary, we
195*0Sstevel@tonic-gate * need to patch the unwanted low order bits with 0's before
196*0Sstevel@tonic-gate * operating on the first bitmap word.
197*0Sstevel@tonic-gate */
198*0Sstevel@tonic-gate word = word & (BT_ULMAXMASK << partial_start);
199*0Sstevel@tonic-gate }
200*0Sstevel@tonic-gate
201*0Sstevel@tonic-gate /*
202*0Sstevel@tonic-gate * Locate a word from the map array with one of the bits set.
203*0Sstevel@tonic-gate */
204*0Sstevel@tonic-gate
205*0Sstevel@tonic-gate while ((word == 0) && (counter < limit)) {
206*0Sstevel@tonic-gate word = map[++counter];
207*0Sstevel@tonic-gate }
208*0Sstevel@tonic-gate
209*0Sstevel@tonic-gate /*
210*0Sstevel@tonic-gate * The end of range has similar problems if it is not aligned.
211*0Sstevel@tonic-gate * Taking care of the end which is not aligned.
212*0Sstevel@tonic-gate */
213*0Sstevel@tonic-gate
214*0Sstevel@tonic-gate if ((counter == limit) && (partial_stop != BT_ULMASK)) {
215*0Sstevel@tonic-gate /*
216*0Sstevel@tonic-gate * Take care the partial word by patch the high order
217*0Sstevel@tonic-gate * bits with 0's. Here we dealing with the case that
218*0Sstevel@tonic-gate * the last word of the bitmap is not aligned.
219*0Sstevel@tonic-gate */
220*0Sstevel@tonic-gate
221*0Sstevel@tonic-gate ASSERT(partial_stop < BT_ULMASK);
222*0Sstevel@tonic-gate word = word & (~(BT_ULMAXMASK << partial_stop + 1));
223*0Sstevel@tonic-gate }
224*0Sstevel@tonic-gate
225*0Sstevel@tonic-gate /*
226*0Sstevel@tonic-gate * Examine the word.
227*0Sstevel@tonic-gate */
228*0Sstevel@tonic-gate if (word == 0) {
229*0Sstevel@tonic-gate return (-1);
230*0Sstevel@tonic-gate } else {
231*0Sstevel@tonic-gate return ((counter << BT_ULSHIFT) | (lowbit(word) - 1));
232*0Sstevel@tonic-gate }
233*0Sstevel@tonic-gate }
234*0Sstevel@tonic-gate
235*0Sstevel@tonic-gate /*
236*0Sstevel@tonic-gate * Copy the bitmap.
237*0Sstevel@tonic-gate */
238*0Sstevel@tonic-gate void
bt_copy(ulong_t * from,ulong_t * to,ulong_t size)239*0Sstevel@tonic-gate bt_copy(ulong_t *from, ulong_t *to, ulong_t size)
240*0Sstevel@tonic-gate {
241*0Sstevel@tonic-gate ulong_t i;
242*0Sstevel@tonic-gate for (i = 0; i < size; i++)
243*0Sstevel@tonic-gate *to++ = *from++;
244*0Sstevel@tonic-gate }
245